5 ms·

Solomonoff Induction isn't really an "algorithm" in the way we normally think of algorithms, as it isn't computable. There are computable approximations, but at

by deong 10y ago

Solomonoff Induction isn't really an "algorithm" in the way we normally think of algorithms, as it isn't computable. There are computable approximations, but at that point, you lose the claim of theoretically optimal.

Xcelerate 10y ago
> There are computable approximations, but at that point, you lose the claim of theoretically optimal. True, but I'm surprised more work isn't being done on "searching the space of programs that produce the data". There's very little research on this topic other than a few papers on minimum description length (MDL). I feel that this is probably the eventual route to AGI. We know what the "optimal" predictor is in theory; now work out the best time/memory approximation to it for practical purposes.
- Cybiote 10y ago
  There's lots of work that's being done related to program synthesis and inductive logic programming. You can even view the more sophisticated recurrent Neural nets, with more complex memory structures, as differentiable programs. Then you're searching the space of programs guided by gradients. SGD effectively acts as an additional prior (assumption) by the kind of solutions it tends towards. The reason (the general) you don't hear much about them if you don't go looking is that the state of the art hasn't budged much for the past couple decades. It's the same graph algorithms, searching and sorting toy problems. The search space over programs is difficult to traverse and it remains to be seen what the added compute power + gradients gets us. On a more practical level, the learning 2 search paradigm can be viewed as also searching for a particular program under certain strict constraints that make search tractable. Probabilistic programming where the priors and likelihoods are themselves complex programs instead of simple distributions from the exponential family are effectively also searching for programs.
Houshalter 10y ago
This is pedantic and I'm not even certain correct. Full SI will run forever without returning an answer, sure. But as it runs it will get closer and closer to the true answer. Eventually it will approach an answer within whatever degree of precision you want. And it will be more accurate than any alternative algorithm, so it's still optimal.

by deong 10y ago

Xcelerate 10y ago

> There are computable approximations, but at that point, you lose the claim of theoretically optimal. True, but I'm surprised more work isn't being done on "searching the space of programs that produce the data". There's very little research on this topic other than a few papers on minimum description length (MDL). I feel that this is probably the eventual route to AGI. We know what the "optimal" predictor is in theory; now work out the best time/memory approximation to it for practical purposes.

Cybiote 10y ago
There's lots of work that's being done related to program synthesis and inductive logic programming. You can even view the more sophisticated recurrent Neural nets, with more complex memory structures, as differentiable programs. Then you're searching the space of programs guided by gradients. SGD effectively acts as an additional prior (assumption) by the kind of solutions it tends towards. The reason (the general) you don't hear much about them if you don't go looking is that the state of the art hasn't budged much for the past couple decades. It's the same graph algorithms, searching and sorting toy problems. The search space over programs is difficult to traverse and it remains to be seen what the added compute power + gradients gets us. On a more practical level, the learning 2 search paradigm can be viewed as also searching for a particular program under certain strict constraints that make search tractable. Probabilistic programming where the priors and likelihoods are themselves complex programs instead of simple distributions from the exponential family are effectively also searching for programs.

Houshalter 10y ago

This is pedantic and I'm not even certain correct. Full SI will run forever without returning an answer, sure. But as it runs it will get closer and closer to the true answer. Eventually it will approach an answer within whatever degree of precision you want. And it will be more accurate than any alternative algorithm, so it's still optimal.