Home › Wiki › computer_science › theoretical › solomonoffs_theory_of_inductive_inference Solomonoff's theory of inductive inference Basic idea
A formal Bayesian theory of prediction: weight every computable hypothesis by 2 − K ( h ) 2^{-K(h)} 2 − K ( h )
Universal prior: M ( x ) = ∑ p : U ( p ) = x ∗ 2 − ∣ p ∣ M(x) = \sum_{p : U(p) = x*} 2^{-|p|} M ( x ) = ∑ p : U ( p ) = x ∗ 2 − ∣ p ∣
Conditional predictor: M ( x n + 1 ∣ x 1.. n ) = M ( x 1.. n + 1 ) / M ( x 1.. n ) M(x_{n+1} \mid x_{1..n}) = M(x_{1..n+1}) / M(x_{1..n}) M ( x n + 1 ∣ x 1.. n ) = M ( x 1.. n + 1 ) / M ( x 1.. n )
Convergence: total expected squared error ∑ n E [ ( M ( x n ∣ x < n ) − μ ( x n ∣ x < n ) ) 2 ] ≤ 1 2 ln 2 ⋅ K ( μ ) \sum_n \mathbb{E}[(M(x_n|x_{<n}) - \mu(x_n|x_{<n}))^2] \le \tfrac{1}{2}\ln 2 \cdot K(\mu) ∑ n E [( M ( x n ∣ x < n ) − μ ( x n ∣ x < n ) ) 2 ] ≤ 2 1 ln 2 ⋅ K ( μ )
Uncomputable but lower-semicomputable.
Resources
https://en.wikipedia.org/wiki/Solomonoff%27s_theory_of_inductive_inference