Can we speed up (approximated) Solomonoff Induction with Dynamic Programming?

[Aruhan Borzigin]

Hi, all. This is my first post here.

Solomonoff Induction related approach to AI often involves program search.( Levin search, AIXI, Goedel machine ... )

In program search, what we interested in mostly is what the programs output, instead of states of program. This lead to a possible speed up: the execution trace of different programs might have shared substructures to exploit.

An example is Discrete Fourier Transform. Given a N dimensional vector, each element in the output of DFT would require O(N) operations alone, while computing all outputs of DFT would require only O(N log(N)) operations.

Solomonoff Induction, in it's raw form, requires an enumeration of outputs of all possible programs over certain UTM. Since it's of form "need outputs of multiple programs simultaneously", I wonder if there's a clever technique to exploit the shared substructures. Possibly using Dynamic Programming.

I'm aware SI is non-computable on TM, however a such technique would still be useful for speeding up SI approximations.

[Laurent]

Hi Aruhan,

Well, the short story is that if you can find a general way to do that, you'll be famous :)

Since Solomonoff induction is slightly impractical, it may be a better idea to do that for Levin search instead. Maybe you can even share computation resources more nicely if you consider programs that require approximately the same amount of computation?

--
Before posting, please read this: https://groups.google.com/forum/#!topic/magic-list/_nC7PGmCAE4
---
You received this message because you are subscribed to the Google Groups "MAGIC" group.
To unsubscribe from this group and stop receiving emails from it, send an email to magic-list+...@googlegroups.com.
To post to this group, send email to magic...@googlegroups.com.
Visit this group at https://groups.google.com/group/magic-list.

[Eray Ozkural]

Well, the sad story is that a straightforward approach doesn't work at all and you'll get slowdown instead (what unpublished benchmarks show), so sorry but no low hanging fruit there.

Cheers,

Eray

[Laurent]

Hi Eray,

It would be quite informative actually if you shared your negative experience to know what not to try! :)

[Eray Ozkural]

As a rule of thumb in a rigorous implementation of levin search generation takes like 20-40% of the time. So even if you saved all the time from testing proggies you can't improve the asymptotic behavior at all :'( I did try it.

But we will publish if we find a not so obvious way to get a substantial speedup.

So unfortunately even exp storage here doesn't improve much. Combined with Legg's result this means AGI is impossible (just kidding). Solomonoff was optimistic about such simple optimizations but in practice, not so fast. :)

Best,

Eray