www.lesswrong.com/posts/dw8w3PNy9JanSJc8s/occam-alternatives
1 correction found
(speed prior) The likelihood of a hypothesis that explains the data is proportional to 2^(-L-N) for L, the length of the shortest code that produces a description of at least that hypothesis, and N, the number of calculations to get from the code to the description.
This is not Schmidhuber's published definition of the speed prior. The speed prior is defined via a resource-bounded semimeasure based on the fastest way of computing data, not by the simple formula 2^(-(L+N)).
Full reasoning
Schmidhuber's speed prior is a specific formal object, and the published definition does not say that a hypothesis gets weight proportional to 2^(-(L+N)) where N is the raw number of computation steps.
In Schmidhuber's own technical report, the speed prior is defined as a semimeasure
S(x) := \sum_{i=1}^{\infty} 2^{-i} S_i(x)
with S_i(x) built from programs that produce x in phase i of the FAST algorithm. In the same source, the motivating postulate is that the cumulative prior probability of data that cannot be computed within time t should be inversely proportional to t.
Schmidhuber's COLT 2002 paper/abstract describes the same idea in prose: the speed prior is "derived from the fastest way of computing data," and under it "the cumulative a priori probability of all data whose computation through an optimal algorithm requires more than O(n) resources is 1/n." His overview page likewise describes it as being based on "the fastest way of describing objects, not the shortest."
So the post's formula changes the definition in a substantive way: it replaces the actual phase/resource-based semimeasure with a much simpler 2^(-(L+N)) expression using the raw step count N. That is not the published speed prior.
3 sources
- Algorithmic Theories of Everything (Technical Report IDSIA-20-00, Version 2.0)
Definition 6.3 (Speed Prior S) Define the speed prior S on B* as S(x) := sum_{i=1}^∞ 2^{-i} S_i(x) ... Postulate 6.1: The cumulative prior probability measure of all x incomputable within time t by the most efficient way of computing everything should be inversely proportional to t.
- The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions
Here we suggest a more plausible measure derived from the fastest way of computing data ... Then we replace M by the novel Speed Prior S, under which the cumulative a priori probability of all data whose computation through an optimal algorithm requires more than O(n) resources is 1/n.
- Speed Prior
SPEED PRIOR ... based on the fastest way of describing objects, not the shortest.