A Dilemma for Solomonoff Prediction
This is an incremental theoretical analysis for researchers in algorithmic information theory and machine learning foundations.
The paper identifies a tension between two known responses to problems with Solomonoff prediction—its dependence on a Universal Turing machine and non-computability—by arguing that computable approximations do not always converge, undermining the convergence claim.
The framework of Solomonoff prediction assigns prior probability to hypotheses inversely proportional to their Kolmogorov complexity. There are two well-known problems. First, the Solomonoff prior is relative to a choice of Universal Turing machine. Second, the Solomonoff prior is not computable. However, there are responses to both problems. Different Solomonoff priors converge with more and more data. Further, there are computable approximations to the Solomonoff prior. I argue that there is a tension between these two responses. This is because computable approximations to Solomonoff prediction do not always converge.