Reply to 'Mathematical Inconsistency in Solomonoff Induction?'

Date: 2020-09-04

I went through the maths in OP and it seems to check out. I think the core inconsistency is that SI implies $l(X ∪ Y) = l(X )$ . I’m going to redo the maths below (breaking it down step-by-step more). curi has $2l(X ) = l(X)$ which is the same inconsistency given his substitution. I’m not sure we can make that substitution but I also don’t think we need to.

Let X and Y be independent hypotheses for Solomonoff induction.

According to the prior, the non-normalized probability of X (and similarly for Y ) is:

P(X ) =--1-- 2l(X )

(1)

what is the probability of $X ∪ Y$ ?

P (X ∪Y ) = P (X )+ P (Y )− P(X ∩ Y ) --1-- --1- --1-- -1-- = 2l(X ) + 2l(Y) − 2l(X) ⋅2l(Y) --1-- --1- ----1----- = 2l(X ) + 2l(Y) − 2l(X) ⋅2l(Y ) --1-- --1- ----1---- = 2l(X ) + 2l(Y) − 2l(X)+l(Y)

(2)

However, by Equation (1) we have:

1 P(X ∪ Y) = -l(X∪Y-) 2

(3)

thus

1 1 1 1 2l(X∪Y-) = 2l(X-) + 2l(Y-) − 2l(X)+l(Y)

(4)

This must hold for any and all X and Y .

curi considers the case where X and Y are the same length, starting with Equation (4)

---1---= --1--+ --1- − ---1----- 2l(X∪Y ) 2l(X ) 2l(Y) 2l(X)+l(Y) = --1--+ --1--− ----1---- 2l(X ) 2l(X ) 2l(X)+l(X ) = --2--− --1-- 2l(X ) 22l(X) = ---1---− --1-- 2l(X )−1 22l(X)

(5)

but

---1--- --1-- 2l(X)− 1 ≫ 22l(X)

(6)

and

0 ≈ --1-- 22l(X)

(7)

---1---≃ ---1--- 2l(X∪Y ) 2l(X )−1 ∴ l(X ∪ Y ) ≃ l(X )− 1 □

(8)

curi has slightly different logic and argues $l(X ∪ Y) ≃ 2l(X )$ which I think is reasonable. His argument means we get $l(X ) ≃ 2l(X )$ . I don’t think those steps are necessary but they are worth mentioning as a difference. I think Equation (8) is enough.

I was curious about what happens when $l(X ) ⁄= l(Y )$ . Let’s assume the following:

l(X) < l(Y ) ∴ -1l(X)-≫ -l1(Y-) 2 2

(9)

so, from Equation (2)

P (X ∪Y ) =--1--+ --1- − ----1---- 2l(X ) 2l(Y) 2l(X)+l(Y) 0 // 0 lim P (X ∪Y ) =--1--+ --/1/ − ---/1/--- l(Y)→∞ 2l(X ) /2l(Y) /2/l(X)+l(Y) ∴ P (X ∪Y ) ≃--1-- 2l(X )

(10)

by Equation (3) and Equation (10)

1 1 2l(X-∪Y) ≃ 2l(X) ∴ l(X ∪Y ) ≃ l(X) ⇒ l(Y ) ≃ 0

(11)

but Equation (9) says $l(X) < l(Y )$ – this contradicts Equation (11). $■$

So there’s an inconsistency regardless of whether $l(X ) = l(Y )$ or not.

You can leave a comment anonymously. No sign up or login is required. Use a junk email if not your own; email is only for notifications—though, FYI, I will be able to see it.