Solomonoff induction is an ideal answer to questions like “What probably comes next in the sequence 1, 1, 2, 3, 5, 8?” or “Given the last three years of visual data from this webcam, what will this robot probably see next?” or “Will the sun rise tomorrow?” Solomonoff induction requires infinite computing power, and is defined by taking every computable algorithm for giving a probability distribution over future data given past data, weighted by their algorithmic simplicity, and updating those weights by comparison to the actual data.
E.g., somewhere in the ideal Solomonoff distribution is an exact copy of you, right now, staring at a string of 1s and 0s and trying to predict what comes next—though this copy of you starts out with a very low weight in the mixture owing to its complexity. Since a copy of you is present in this mixture of computable predictors, we can prove a theorem about how well Solomonoff induction does compared to an exact copy of you; namely, Solomonoff induction commits only a bounded amount of error relative to you, or any other computable way of making predictions. Solomonoff induction is thus a kind of perfect or rational ideal for probabilistically predicting sequences, although it cannot be implemented in reality due to requiring infinite computing power. Still, considering Solomonoff induction can give us important insights into how non-ideal reasoning should operate in the real world.
- Solomonoff induction: Intro Dialogue (Math 2)
An introduction to Solomonoff induction for the unfamiliar reader who isn’t bad at math
- Methodology of unbounded analysis
What we do and don’t understand how to do, using unlimited computing power, is a critical distinction and important frontier.
- Inductive prior
Some states of pre-observation belief can learn quickly; others never learn anything. An “inductive prior” is of the former type.