Re: Solving the induction problem

marcus.hutter@xxxxxxx wrote:
Since inductive reasoning in one way or another is a key ingredient
in most AI systems, and the induction problem is a long-standing
(supposedly open) philosophical problem, the following (survey-like)
paper may be interesting to some list members:

The title of the posting is intentionally provocative, since the
paper I would like to discuss is too. The paper considers a range of
philosophical and statistical problems around induction; more
precisely problems that the well-known approaches to induction have.
The paper then shows how a specific single known (but not too
well-known) theory S has none of these problems, hence concludes
that the induction problem is solved. The problems discussed
include:

Confirmation of (universal) hypotheses in general, and
the classical Black ravens paradox in particular
(Maher's approach does not solve the problem).

Reparametrization invariance: How to extend the symmetry principle
from finite hypothesis classes (all hypotheses are equally likely)
to infinite hypothesis classes (Jeffrey's prior does not always
work).

Old-evidence problem / Ad-hoc hypotheses:
How can old evidence confirm a theory developed thereafter?
How can we spot ad-hoc hypotheses, just tailored towards
the past data?

Updating problem:
A Bayesian needs to choose the hypothesis/model class before
seeing the data, which seldomly reflects scientific practice.

Many other issues are discussed:
Error bounds, magic numbers, Carnap's confirmation theory,
Laplace rule, and many more.

I would like to encourage the interested list members to read and
reflect on the paper, and then ideally start a well-informed
critical discussion (here or offline).

Marcus Hutter, On Universal Prediction and Bayesian Confirmation
Theoretical Computer Science (2007)
http://dx.doi.org/10.1016/j.tcs.2007.05.016
http://www.hutter1.net/ai/uspx.pdf

Short version (very dense, not recommended):
Marcus Hutter, On the Foundations of Universal Sequence Prediction
Proc. 3rd Annual Conference on Theory and Applications of Models of
Computation (TAMC 2006)
http://arxiv.org/abs/cs.LG/0605009


Thanks, once in awhile Solomonoff Induction is mentioned on c.a.p.
.