Algorithmic Information Theory

Marcus Hutter (ANU)

CECS SEMINAR SERIES Pilot Talk for Reading Group

DATE: 2011-05-04
TIME: 10:00:00 - 11:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
I will give a brief introduction to the field of algorithmic information theory (AIT), its underlying philosophy, the most important concepts, and some of its applications. In the following months there will be a reading group every Wednesday 10:00-11:00 in the RSISE Common RHS Room A206 on AIT. Everyone is welcome. There will be no further announcements. See http://grla.wikidot.com/ait for details and updates.

AIT arises by mixing information theory and computation theory to obtain an objective and absolute notion of information in an individual object, and in so doing gives rise to an objective and robust notion of randomness of individual objects. This is in contrast to classical information theory that is based on random variables and communication, and has no bearing on information and randomness of individual objects.

AIT has a wide range of applications, despite the fact that its core quantity, Kolmogorov complexity, is incomputable. Most importantly, AIT allows to quantify Occam's razor, the core scientific paradigm that "among two models that describe the data equally well, the simpler one should be preferred". This lead to universal theories of induction and action, in the field of machine learning and artificial intelligence, and practical versions like Minimum Encoding Length (MDL/MML) principles. The universal similarity metric probably spawned the greatest practical success of AIT. Approximated by standard compressors like Lempel-Ziv (zip) or bzip2 or PPMZ, it leads to the normalized compression distance, which has been used to fully automatically reconstruct language and phylogenetic trees, and many other clustering problems. AIT is has been applied in disciplines as remote as Cognitive Sciences, Biology, Physics, and Economics.

Recommended reading: Algorithmic Information Theory. Scholarpedia, 2:3 (2007) 2519 http://www.scholarpedia.org/article/Algorithmic_information_theory an extended encyclopedic entry

BIO:
http://people.cecs.anu.edu.au/user/470