Subsequence Induction (draft)

by Scott Garrabrant2 min read12th Oct 2015No comments

3

Personal Blog

This post is a draft, I have not written up the relevant proof yet, and when I do, I will probably change the notation around. The basic idea is that we do resource bounded Solomonoff induction, but we allow Turing machines to only make predictions on a subset of the bits. If a Turing machine does not make a prediction for a given bit, we treat it as though it assigned whatever probability this algorithm assigned for that bit.

Here, we define another ALU algorithm proposal. This one, we can prove has very nice properties. However, it only works in a very limited domain.

Consider an environment , which on input runs in time, and we want to predict it in time. The following algorithm only works when . This is a very restrictive condition. However, we are working on some ways that might be able to use this algorithm as a subroutine, and generalize it to a larger domain. (So far,, all of our attempts to extend it have failed, but we are still working on it.)

Consider an enumeration of all Turing machines. For this problem, we will use finite deterministic Turing machines. Assume that the first Turing machine outputs immediately for all inputs.

For each , we define a weight function on Turing machines with as follows.

where is the output of on input if on input outputs a rational probability in time at most . If does not output in time or does not output a probability, then is defined to equal , which is defined by:

is the the weighted average of over all such that on input outputs a rational probability in time at most , where gets weight .

Note that is recursively defined, since is computed using for values of less than . Let be a function such that can be computed in time .

has the following very valuable property. For any Turing machine , let be the set of all natural numbers on which outputs a probability in time on input . Then, there exists a nonzero constant such that for all , the product of the probabilities that assigns to the correct answer on the first bits of is at least times the product of the probabilities that assigns to the correct answer on the same bits.

This condition implies that passes the generalized Benford test for rational coins, but it is actually much stronger. not only dominates any Turing machine which runs in time , but also dominates any such Turing machine on any quickly computable subsequence.

Personal Blog

3

2 comments, sorted by Highlighting new comments since Today at 8:39 AM
New Comment

In online learning this is called the sleeping experts setting (we say an expert is "asleep" when it declines to make a prediction).

The algorithm in this post is the standard algorithm in the sleeping experts setting, though I don't actually know a good reference. I think it is described in the notes for this course.

Edit: I think that course actually calls the sleeping experts "specialists," if you are trying to ctrl+F for it.

This is a big deal! I like my analogy that is a prediction market where different can place bets on subsequences of (relative to the market price) and be rewarded based on their success, and the dominance property plays the role of the efficient market hypothesis...

Corrections, I think:

gets weight proportional to

Let be a function such that can be computed in time (not ).