|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Loss Bounds and Time Complexity for Speed Priors | | Daniel Filan
; Marcus Hutter
; Jan Leike
; | | Date: |
12 Apr 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 better upper complexity bounds for Schmidhuber’s
speed prior under the same conditions, and that it predicts deterministic
sequences that are computable in polynomial time; however, we also show that it
is not computable in polynomial time, and the question of its predictive
properties for stochastic sequences remains open. | | Source: | arXiv, 1604.3343 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER