Hacker News Reader

Comment by Strilanc | Hacker News Reader

I wasn't expecting this article to be about Sleeping Beauty problems and Solomonoff induction. There are people trying to apply real machine learning algorithms to real physics problems (e.g. [1][2]). This article is not about that.

It should go without saying that Solomonoff induction is totally useless for practical applications, if interesting theoretically. Brute forcing the space of all programs is ridiculously mindbogglingly universe-crushingly expensive. (Actually, even if the process was magically tractable, there would still be limitations and dangers [3].)

1: http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.108...

2; http://arxiv.org/abs/1404.1333

3: http://lesswrong.com/lw/jg1/solomonoff_cartesianism/

View on HN

> It should go without saying that Solomonoff induction is totally useless for practical applications, if interesting theoretically.

Indeed, just like Turing machines and the lambda calculus. Still an important theoretical step though!

Could Solomonoff induction guess sequences of prime-numbers?

The output of a program could be infinite and thus it never halts. Without Chatlin's constant or the Busy Beaver values, brute forcing is not feasible in a countably computable universe. It is still interesting to talk about Oracles, ie. Somehow getting hold of Chatlin's constant and thereby easily solving the halting problem and being able to use the induction.

Solomonoff Induction starts by using Kolmogorov complexity to calculate its prior distribution, which already requires Chaitin's constant to be known.

So yeah.

Solomonoff induction goes from program to output to prediction weighted by program's length. It never goes from type of prediction to shortest equivalent program. It doesn't need to compute Kolmogorov complexities.

(Well, more specifically, approximations to it with time cutoffs don't have to compute Kolmogorov complexities. Raw Solomonoff induction already trivially runs into the halting problem.)

These are easily fixed by dove tailing through the programs and using an increasing-over-time cutoff. Not fixed in the "made practical" sense, but in the "made non-contradictory" sense.

You can't use cutoffs. Timeouts deliver no guarantees within the universe of complexity.

You can think of Solomonoff induction as a weighted set of experts. At each step, each expert makes a prediction, and the overall prediction is the one that gets the highest total weight. Then the true data comes in, and the weight of each expert is increased or decreased based on whether that expert was right or wrong. And here's the kicker, the experts are all possible prediction programs, initially weighted by 2^-(program length). So yeah, in the long run Solomonoff induction will be at least as good as you at predicting any particular sequence, including prime numbers etc., because your own prediction algorithm is somewhere in the Solomonoff mixture. That also explains why approximating Solomonoff induction takes a huge amount of computation time. It's mostly a theoretical idea.

More specifically, every incorrect expert is removed at each step, and the remaining experts have their probabilities uniformly rescaled to sum to 1.

That relies on noiseless, unbiased data, right? What if an expert gets ruled out by accident?

Being able to average over every possible computer program is so powerful that it doesn't really matter.

Reply on news.ycombinator.com