marina@ai.toronto.edu (Marina Haloulos) (11/10/89)
FLASH ANNOUNCEMENT
(SF = Sandford Fleming Building, 10 King's College Road)
-------------------------------------------------------------
ARTIFICIAL INTELLIGENCE SEMINAR
SF1105, at 11:00 a.m., Tuesday 14 November 1989
Dr. Paul Vitanyi
The Netherlands
"Inductive Reasoning and Kolmogorov Complexity"
Reasoning to obtain the `truth' about reality, from external data, is an
important, controversial, and complicated issue in man's effort to
understand nature. (Yet, today, we try to make machines do this.) There
have been old useful principles, new exciting models, and intricate
theories scattered in vastly different areas including philosophy of
science, statistics, computer science, and psychology. We focus on
inductive reasoning in correspondence with ideas of Solomonoff. While his
proposals result in perfect procedures, they involve the noncomputable
notion of Kolmogorov complexity. In this paper we develop the thesis that
Solomonoff's method is fundamental in the sense that many other induction
principles can be viewed as particular ways to obtain computable
approximations to it. We demonstrate this explicitly in the cases of
Gold's paradigm for inductive inference, Valiant's learning (by adding
computational requirements), Rissanen's minimum description length (MDL)
principle, Fisher's maximum likelihood principle, and Jaynes' maximum
entropy principle. We present several new theorems and derivations to this
effect. We also delimit what can be learned and what cannot be learned in
terms of Kolmogorov complexity, and we describe an experiment in machine
learning of handwritten characters.