CS Colloquium on Aug. 19 at 11am

Title: Sequence Prediction based on Monotone Complexity

Speaker: Marcus Hutter, IDSIA, Lugano, Switzerland
         http://www.idsia.ch/~marcus/

Date: August 19 (Tuesday)
Time: 11am 
Place: MCS 135

Abstract:

In this talk we discuss sequence prediction based on the monotone
Kolmogorov complexity Km=-log m, i.e. based on universal
deterministic/one-part MDL. m is extremely close to Solomonoff's
prior M, the latter being an excellent predictor in deterministic
as well as probabilistic environments, where performance is measured
in terms of convergence of posteriors or losses. Despite
this closeness to M, it is difficult to assess the prediction
quality of m, since little is known about the closeness of their
posteriors, which are the important quantities for prediction. We
show that for deterministic computable environments, the
"posterior" and losses of m converge, but rapid convergence could
only be shown on-sequence; the off-sequence behavior is unclear.
In probabilistic environments, neither the posterior nor the
losses converge, in general.

Literature:
M. Hutter, Sequence Prediction based on Monotone Complexity
Proceedings of the 16th Conference on Computational Learning
Theory (COLT-2003)

http://www.idsia.ch/~marcus/ai/unimdl.htm

Short CV:
Marcus Hutter received his masters in computer sciences in 1992 at
TU-Munich, Germany. After his PhD in theoretical particle physics
he developed algorithms in a medical software company for 5 years.
For three years he has been working as a researcher at the AI
institute IDSIA in Lugano, Switzerland. His current interests are
centered around reinforcement learning, algorithmic information
theory and statistics, universal induction schemes, adaptive control
theory, and related areas.