Solomonoff Induction

Ray Solomonoff defined an inference system that will learn to correctly predict any computable sequence with only the absolute minimum amount of data. This system, in a certain sense, is the perfect universal prediction algorithm. To summarize it very informally, Solomonoff induction works by:

• Starting with all possible hypotheses (sequences) as represented by computer programs (that generate those sequences), weighted by their simplicity (2^-n, where n is the program length);
• Discarding those hypotheses that are inconsistent with the data.

Weighting hypotheses by simplicity, the system automatically incorporates a form of Occam's razor, which is why it has been playfully referred to as Solomonoff's lightsaber.

See also

• Kolmogorov complexity
• AIXI
• Occam's razor

References

• Algorithmic probability on Scholarpedia