Tag Archives: prediction

Measuring Simplicity: Kolmogorov Complexity

Posted on by

Why does the sequence 0000000000 seem simpler than the sequence 1010001110? The first sequence has an obvious pattern: it has ten repeated zeros. Thus, we can compactly describe it as “the sequence of ten zeros.” By contrast the second sequence has no such pattern, and its most compact description is probably “the sequence 1010001110.”

This intuitive understanding of simplicity is formalized by Kolmogorov complexity. The Kolmogorov complexity of a sequence is the length of the shortest program that outputs the sequence. Simple sequences tend to have patterns, so they can be generated by short programs. Conversely, if a short program describes a sequence this is itself a pattern. Thus, simple sequences will tend to have low Kolmogorov complexity, complex sequences will tend to have high Kolmogorov complexity.

Continue reading →

Solomonoff-lite Evaluator

Posted on by

Solomonoff induction is a general, but uncomputable, solution to the problem of prediction: given the past, what probability should you assign each possible future?

In my previous post, I described a sequence predictor that works by modeling the sequence as generated by a random program in a simple language. I’ve hacked together an implementation of this predictor in python.

Solomonoff lite evaluator

Continue reading →

Solomonoff Induction

Posted on by

The problem of prediction is: given a series of past observations, what future observations do you expect? When we are rigorous about expectations we assign probabilities to the different possibilities. For example, given the weather today we assign 50% probability to a rainy day tomorrow, 30% probability to a cloudy day, and 20% probability to a sunny one.

How can we determine the probability of a future given the past? Solomonoff induction is a solution to this problem. Solomonoff induction has a strong performance guarantee: any other method assigns at most a constant factor larger probability to the actual future. This constant is equal to the complexity of that predictor.

Solmononoff induction itself is uncomputable, but there are computable analogs. It serves as a simple method of specifying a device which accurately predicts a series of observations. Were such a device to exist we would think it highly intelligent as it correctly predicted any patternful sequence we entered with little error.

Below the fold I describe some of the machinary behind Solomonoff induction. I describe a computable approximation which can be exactly and efficiently solved. Although this computable predictor is not particularly intelligent, it shares the same structure as Solomonoff induction.
Continue reading →