The Solomonoff universal prior is fixed relative to a specific choice of universal Turing machine (UTM). Now, I understand that a UTM can simulate any other UTM, so that they assign a complexity to any bitstring that differs by at most a constant.

Doesn't this invalidate the whole point of the universal prior? Haven't we introduced bias by choosing one UTM versus another? Some machines will be simpler to define relative to one UTM than another. And while two UTMs will only disagree on the complexity of a bitstring by at most a fixed amount, that amount depends on the UTM pair and can be arbitrarily great.

One advantage to the Solomonoff universal prior is that it is over a model class that truly includes all computable models, which is about as large a model domain as we can hope for. And with enough data the true model should be assigned high probability in the posterior (assuming it is computable).

However, isn't it also true that any prior probability distribution that assigns non-zero probability to every computable model will also be able to converge to the true model?

In fact: won't such a prior distribution implicitly define a UTM?

Have we accomplished anything here?


Your thinking is right, but half complete. Optimality properties of universal prior is over all problems one may attempt to solve. If you try to solve a diverse set of problems using Solomonoff prior your overall success defined using some loss function will be better than any other prior. For a specific problem one can always find a better prior. The best prior given to you by an oracle will be just concentrated over the population parameters, hence you wouldn't need any data.

Basically if you don't have any prior information, given a randomly selected statistical problem to solve, universal prior is the best place to start. You may think of this as the occurance frequency of problems in our universe are distributed according to this prior. When given a random problem from our universe we start our search with the most likely problems encountered in this universe. If we move to another universe however over there the problems may be distributed differently.

Not all priors have this property.

http://www.jmlr.org/papers/volume4/hutter03a/hutter03a.pdf (theorem 6)

But Solomonoff's is not the only one. There are others with similar properties.

http://www.vallinder.se/solomonoff.pdf (page 40) tries to address your concern regarding other priors that assign non-zero probabilities.

While Solomonoff takes into consideration program length, some other priors also take into consideration the time and resources to finalize the computation.


  • $\begingroup$ "Optimality properties of universal prior is over all problems one may attempt to solve." This statement appears to contradict the No Free Lunch theorem. $\endgroup$ – user20160 Oct 18 '17 at 20:40
  • $\begingroup$ "You may think of this as the occurance frequency of problems in our universe are distributed according to this prior." It's not clear to me what "universe" means here. Certainly, we don't know this to be true for our physical universe. And, if we declare "universe" to be a distribution over computable problems that matches the universal prior for a given UTM, then the definition is circular (and, as the OP mentions, this distribution depends on the UTM) $\endgroup$ – user20160 Oct 18 '17 at 20:40
  • 2
    $\begingroup$ @user20160 arxiv.org/pdf/1111.3846.pdf. No Free Lunch Theorem is unfortunately broken, like many other all school statistical dogma. $\endgroup$ – Cagdas Ozgenc Oct 18 '17 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.