Xref: utzoo ont.events:1367 uw.talks:63 uw.cs.grad:57
Path: utzoo!attcan!utgpu!watmath!watdragon!ylkingsbury
From: ylkingsbury@watdragon.waterloo.edu (Yvonne Kingsbury)
Newsgroups: ont.events,uw.talks,uw.cs.grad
Subject: ICR Colloquium
Keywords: Inductive Reasoning, Kolmogorov Complexity
Message-ID: <17808@watdragon.waterloo.edu>
Date: 3 Nov 89 17:24:33 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 43

ICR Colloquium

Inductive Reasoning and Kolmogorov Complexity

Dr. Paul M.B. Vitanyi

Centrum voor Wiskunde en Informatica
The Netherlands
&
Universiteit van Amsterdam
Faculteit Wiskunde en Informatica

Date: Wednesday, November 8, 1989
3:30 p.m.
Davis Centre, Room 1302

Abstract

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 the ideas of Solomonoff.
While his proposal results in perfect procedures, they involve
the noncomputable notion of Kolmogorov complexity.  We develop
the thesis that Solomonoff's method is fundamental in the
sense that many other inductive principles can be viewed in 
particular ways to obtain comutable approximations of the 
method.  We demonstrate this explicitly in the cases of
Gold's paradigm for inductive inference, Valiant's learning
(by adding computational requirements), Rissanen's 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 Kolmogorov complexity and its applications,
now in progress.

machine 
exerep