That seems to be equivalent to saying that Omega’s probability estimates will approach fifty-fifty fast enough. So if I understand correctly, it’s a provable property of Solomonoff induction that faced with a “maximally hostile” bit-string, its probability estimates will converge to fifty-fifty fast enough that it can’t blunder worse than a random guesser by more than a constant term in the log(P) game? If true, I find that quite fascinating.
Let’s regard Omega’s prior as being given by M(x) as shown here. Now let’s divide our monotone UTM’s programs into the following classes.
Ones that just say “Print the following: … ”
Every other program.
You can imagine Omega as a Bayesian reasoner trying to decide between the two hypotheses “the data was generated by a program in class 1” and “the data was generated by a program in class 2″. Omega’s prior will give each of these two hypotheses a non-zero probability.
To “cut to the chase”, what happens is that the “extra damage” to the score caused by “class 2” falls off quickly enough, relative to the current posterior probability of “class 2″, that the extra loss of score has to be finite.
Yes, it’s a provable property of Solomonoff induction. It was a surprise to me too when I worked it out some days ago (using Shane Legg’s paper linked from the post), but users AlephNeil and paulfchristiano didn’t seem surprised, and Eliezer always considered it obvious I guess.
But then it seems to me that Game 3 is unfair, in that it artificially amplifies infinitesimal errors. Faced with a hostile input, a Solomonoff predictor will correctly converge to saying “I don’t know,” i.e. producing p(0) ~ p(1) ~ 1⁄2. However, a game that forces it to nevertheless make binary predictions in this situation will force an answer based on the infinitesimal differences between the calculated probabilities and 1⁄2, and moreover, the correct answers are contrived so that these infinitesimal differences always point in the wrong direction.
If you instead let the Solomonoff predictor just honestly say “I don’t know,” as in the first two games, the problem disappears.
If you instead let the Solomonoff predictor just honestly say “I don’t know,” as in the first two games, the problem disappears.
True, though sometimes in real life, you can’t just say “I don’t know”, you have to choose an action. Game 3 is unfair, but real life can be unfair too.
The drop in Omega’s score on each step will approach |log(1/2)| fast enough that the two sums won’t differ by more than a constant.
That seems to be equivalent to saying that Omega’s probability estimates will approach fifty-fifty fast enough. So if I understand correctly, it’s a provable property of Solomonoff induction that faced with a “maximally hostile” bit-string, its probability estimates will converge to fifty-fifty fast enough that it can’t blunder worse than a random guesser by more than a constant term in the log(P) game? If true, I find that quite fascinating.
Let’s regard Omega’s prior as being given by M(x) as shown here. Now let’s divide our monotone UTM’s programs into the following classes.
Ones that just say “Print the following: … ”
Every other program.
You can imagine Omega as a Bayesian reasoner trying to decide between the two hypotheses “the data was generated by a program in class 1” and “the data was generated by a program in class 2″. Omega’s prior will give each of these two hypotheses a non-zero probability.
To “cut to the chase”, what happens is that the “extra damage” to the score caused by “class 2” falls off quickly enough, relative to the current posterior probability of “class 2″, that the extra loss of score has to be finite.
I see! That’s a very good intuitive explanation, thanks for writing it down.
Yes, it’s a provable property of Solomonoff induction. It was a surprise to me too when I worked it out some days ago (using Shane Legg’s paper linked from the post), but users AlephNeil and paulfchristiano didn’t seem surprised, and Eliezer always considered it obvious I guess.
But then it seems to me that Game 3 is unfair, in that it artificially amplifies infinitesimal errors. Faced with a hostile input, a Solomonoff predictor will correctly converge to saying “I don’t know,” i.e. producing p(0) ~ p(1) ~ 1⁄2. However, a game that forces it to nevertheless make binary predictions in this situation will force an answer based on the infinitesimal differences between the calculated probabilities and 1⁄2, and moreover, the correct answers are contrived so that these infinitesimal differences always point in the wrong direction.
If you instead let the Solomonoff predictor just honestly say “I don’t know,” as in the first two games, the problem disappears.
True, though sometimes in real life, you can’t just say “I don’t know”, you have to choose an action. Game 3 is unfair, but real life can be unfair too.