Ray Solomonoff’s universal distribution

Everyone knows about Kolmogorov complexity. Kolmogorov addressed randomness and came up with the Kolmogorov complexity Cof a string  (defined as the length of the shortest program that can reproduce the string) as a measure of its randomness. Solomonoff, two years before Kolmogorov, looked at the problem from a much deeper perspective in my opinion. He asked, in drastic paraphrase: How should you weight  different programs that could generate a given string? And the two are related because it turns out that the function that Solomonoff picked is C. [So why isn’t it called Solomonoff complexity, though Kolmogorov referenced Solomonoff in his paper? Because Kolmogorov was already famous.]

What I would like to understand is the following: How do you go about generating programs that could reproduce the string? Induction is a hoary field, but most of the work is done assuming that you have to decide between different programs, and very little, in proportion, addresses the question of how to go about generating such programs. That is actually a problem because the search space is, to put it mildly, large. Is there a fundamental process that is the optimal manner to induce programs given data? This must itself be a probabilistic process. In other words, the program output match to the desired string must be allowed to be imperfect, so the search space summation is not just over programs that reproduce a given string S

\sum_{{\rm programs\ reproducing\ } S} \exp(-{\rm length}({\rm program}))

but rather weighted in some way to balance fitting S and reducing program length. Why does everything involve a balance between energy and entropy? Because there is nothing more fundamental in all of science.

So I think there should be a way to write something like

\sum_{S',{\rm programs\ producing\ } S'} \exp(-{\rm length}({\rm program})) \exp(- {\rm mismatch}(S,S'))

and then the question is: What is the universal form of the mismatch function? An interesting point here is that this process might work even with noisy S since if the correct string is 0101010101 but you read S= 0111010101, then you’ll find a very short program that can reproduce the string S' = 0101010101, and since the mismatch is only one bit this process would autocorrect your initial misread string.

We want symbols and rules for manipulation such that the resulting stream contains the known sequence of symbols. In other words, an inverse Godel problem: Given a stream of symbols, find a set of rules so that this stream is a proof.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s