I don’t recall if I’ve mentioned this before, but Solomonoff induction in the mixture form makes no mention of the truth of its models. It just says that any computable probability distribution is in the mixture somewhere, so you can do as well as any computable form of cognitive uncertainty up to a constant.
Eliezer, if what you say is true, then it shouldn’t be possible for anyone, using just a Turing machine, to beat Solomonoff Induction at a pure prediction game (by more than a constant), even if the input sequence is uncomputable. But here is a counterexample. Suppose the input sequence consists of the unary encodings of Busy Beaver numbers BB(1), BB(2), BB(3), …, that is, BB(1) number of 1s followed by a zero, then BB(2) number of 1s followed by a 0, and so on. Let’s ask the predictor, after seeing n input symbols, what is the probability that it will eventually see a 0 again, and call this p(n). With Solomonoff Induction, p(n) will approach arbitrarily close to 0 as you increase n. A human mathematician on the other hand will recognize that the input sequence may not be computable and won’t let p(n) fall below some non-zero bound.
I don’t quite see this. With Solomonoff induction, as with a computable human mathematician, the probability of the next symbol being 0 will approach 0. I don’t see why a Solomonoff inductor using mixtures (that is, evaluating computable probability distributions rather than computable sequences) will ever assign a probability arbitrarily close to 0 of seeing another 0, ever.
Ask the human mathematician, over and over, what their probability of the next symbol being 0 is. They’re computable, so this distribution is in the mixture. What other distribution is it necessarily dominated by, in the Solomonoff mixture?
Or are we allowing the human mathematician to have an inconsistent probability distribution where he says “You’ll see another 0 eventually, I’m sure of it, but I’m also pretty sure that no matter how large a number of 1s I pick, it won’t be high enough.” If so, to be fair, we should factor out the symbol for “see another 0 eventually” and just ask the Solomonoff inductor about that separately via some input encoding, the same way we ask the human about it separately.
I don’t quite see this. With Solomonoff induction, as with a computable human mathematician, the probability of the next symbol being 0 will approach 0. I don’t see why a Solomonoff inductor using mixtures (that is, evaluating computable probability distributions rather than computable sequences) will ever assign a probability arbitrarily close to 0 of seeing another 0, ever.
Ask the human mathematician, over and over, what their probability of the next symbol being 0 is. They’re computable, so this distribution is in the mixture. What other distribution is it necessarily dominated by, in the Solomonoff mixture?
Or are we allowing the human mathematician to have an inconsistent probability distribution where he says “You’ll see another 0 eventually, I’m sure of it, but I’m also pretty sure that no matter how large a number of 1s I pick, it won’t be high enough.” If so, to be fair, we should factor out the symbol for “see another 0 eventually” and just ask the Solomonoff inductor about that separately via some input encoding, the same way we ask the human about it separately.