Wei_Dai comments on Solomonoff Induction, by Shane Legg - Less Wrong

13 Post author: cousin_it 21 February 2011 12:32AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (7)

Comments (7)

You are viewing a single comment's thread. Show more comments above.

Comment author: Wei_Dai 21 February 2011 09:18:59AM *  0 points [-]

I mentioned to you a few days ago (in chat) that Scholarpedia stated:

The universal a priori probability m has many remarkable properties. A theorem of L.A. Levin states that among the lower semi-computable semi-measures it is the largest such function in the following sense: If p is a lower semi-computable semi-measure, then there is a constant c such that cm(x) >= p(x) for all x.

When you say "The tricky part for me was proving the equivalence of two views of the Solomonoff prior" do you mean you tried to re-derive this result?

Comment author: AlephNeil 22 February 2011 01:12:48AM *  0 points [-]

For the discrete version, doesn't this boil down to converting a program that semi-computes a semi-measure into a program that "semi-samples from" a semi-measure?

Which is pretty straightforward:

We interpret the remainder of our (infinite) input as a real number y in [0,1]. Every time the measure that we're semi-computing adds an amount p of probability to one of its possible values v, we increment a variable x (which was initialised to 0) by p. If and when x finally exceeds y, we return the value v whose probability was just incremented.

(The continuous version, which is the one we actually need, looks harder, but I guess the same general idea should work. Perhaps we just repeat the algorithm above once for every bit of the output?)

Comment author: cousin_it 21 February 2011 12:36:41PM *  0 points [-]

Yes. I eventually succeeded, but not without a tiny bit of help from the texts.

Powered by Reddit Powered by Reddit