Loss Bounds and Time Complexity for Speed Priors

Daniel Filan, Jan Leike, Marcus Hutter
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1394-1402, 2016.

Abstract

This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002), and show that our prior can predict sequences drawn from probability measures that are estimable in polynomial time. Our speed prior is computable in doubly-exponential time, but not in polynomial time. On a polynomial time computable sequence our speed prior is computable in exponential time. We show that Schmidhuber’s speed prior has better complexity under the same conditions; however, the question of its predictive properties remains open.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-filan16, title = {Loss Bounds and Time Complexity for Speed Priors}, author = {Filan, Daniel and Leike, Jan and Hutter, Marcus}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {1394--1402}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/filan16.pdf}, url = {https://proceedings.mlr.press/v51/filan16.html}, abstract = {This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002), and show that our prior can predict sequences drawn from probability measures that are estimable in polynomial time. Our speed prior is computable in doubly-exponential time, but not in polynomial time. On a polynomial time computable sequence our speed prior is computable in exponential time. We show that Schmidhuber’s speed prior has better complexity under the same conditions; however, the question of its predictive properties remains open.} }
Endnote
%0 Conference Paper %T Loss Bounds and Time Complexity for Speed Priors %A Daniel Filan %A Jan Leike %A Marcus Hutter %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-filan16 %I PMLR %P 1394--1402 %U https://proceedings.mlr.press/v51/filan16.html %V 51 %X This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002), and show that our prior can predict sequences drawn from probability measures that are estimable in polynomial time. Our speed prior is computable in doubly-exponential time, but not in polynomial time. On a polynomial time computable sequence our speed prior is computable in exponential time. We show that Schmidhuber’s speed prior has better complexity under the same conditions; however, the question of its predictive properties remains open.
RIS
TY - CPAPER TI - Loss Bounds and Time Complexity for Speed Priors AU - Daniel Filan AU - Jan Leike AU - Marcus Hutter BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-filan16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 1394 EP - 1402 L1 - http://proceedings.mlr.press/v51/filan16.pdf UR - https://proceedings.mlr.press/v51/filan16.html AB - This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002), and show that our prior can predict sequences drawn from probability measures that are estimable in polynomial time. Our speed prior is computable in doubly-exponential time, but not in polynomial time. On a polynomial time computable sequence our speed prior is computable in exponential time. We show that Schmidhuber’s speed prior has better complexity under the same conditions; however, the question of its predictive properties remains open. ER -
APA
Filan, D., Leike, J. & Hutter, M.. (2016). Loss Bounds and Time Complexity for Speed Priors. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:1394-1402 Available from https://proceedings.mlr.press/v51/filan16.html.

Related Material