Algorithmic Information Theory Reading Group

The Algorithmic Information Theory Reading Group will go through the standard textbook by Li&Vitanyi (2008; see below for details) on the subject, and possibly some other related works. The core sessions concentrate on the most important parts, the optional sessions deal with the rest. For a brief overview describing the major subfields, applications, history, and a map of the field, see the short introductory AIT Scholarpedia article. For more information, see below.

General Information

Welcome to the Algorithmic Information Theory Reading Group at RSISE@ANU

  • Who: Everyone is welcome.
  • When: Every Wednesday, 10:00-11:00 (just before the RL reading group)
    (If you want to attend, but the time does not suit you, please let me know)
  • Where: RSISE building, Common RHS Room, A206, Australian National University.
  • Assumed Background: calculus and computability (see below)
  • Operation mode: Reading should be done in advance. About 2 chapters per month. No email reminders. See schedule below.

Algorithmic Information Theory

Algorithmic Information Theory (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.

Regular Participants

  • Hendra Gunadi <ua.ude.una|0651794u#ua.ude.una|0651794u>
  • Marcus Hutter <ua.ude.una|rettuh.sucram#ua.ude.una|rettuh.sucram>
  • Jay Larson <ua.ude.una|nosral.yaj#ua.ude.una|nosral.yaj>
  • Avraham Ruderman <moc.liamg|maredur.iva#moc.liamg|maredur.iva>
  • Wen Shao <ua.ude.una|oahs.new#ua.ude.una|oahs.new>
  • Peter Sunehag <ua.ude.una|gahenus.retep#ua.ude.una|gahenus.retep>
  • Alwen Tiu <ua.ude.una|uit.newla#ua.ude.una|uit.newla>
  • Daniel Visentin <moc.liamg|nitnesivjd#moc.liamg|nitnesivjd>
  • Tor Lattimore <ua.ude.una.scec|eromittal.rot#ua.ude.una.scec|eromittal.rot>
  • Mayank Daswani <ua.ude.una|inawsad.knayam#ua.ude.una|inawsad.knayam>
  • and other ANU/NICTA students and researchers.

Reading List

The tentative schedule for the reading group is given below and will be regularly updated. Unless more material is dropped, we'll likely need more than 3 weeks per chapter.

Every 3rd reading group date is for answering questions regarding selected (or other) exercises. Exercises are mainly selected by relevance to the contents of the book. Some are selected because they provide some general insight. Some selected exercises are very hard and in any case they are too many to solve them all, but it is instructive to understand the results and why they are plausible (or not).

  • 22&29 Feb'11 and 7.Mar '12 core: [LV08] Chapter 6 by Mayank
    Selected Sections.
  • 23.Nov'11 optional: [LV08] Chapter 5:
    Exercises: 5.2.2, 5.2.11, 5.2.12? 5.3.5? 5.4.2? 5.4.3.
  • 2&9&16.Nov'11 core: [LV08] Chapter 5 by Avi Ruderman
    All Sections but 5.5 and 5.6.
  • 26.Oct'11 optional: [LV08] Chapter 4:
    Exercises 4.2.2, 4.3.2, 4.3.6, 4.3.8?? 4.4.1, 4.5.1, 4.5.2? 4.5.4? 4.5.13.
  • 17&24&31.Aug'11 core: [LV08] Chapter 4 by Tor Lattimore
    All Sections but 4.7.
  • 10. Aug'11 optional: [LV08] Chapter 3:
    Exercises: 3.1.5, 3.6.7? 3.6.12? 3.6.16?? 3.6.21.
    Some useful information is available here. Again please read critically.
  • 3.Aug'11 core: [LV08] Chapter 4 by Tor Lattimore
    All Sections but 4.7.
  • 20.27Jul'11 core: [LV08] Chapter 3 by Wen Shao
    Only Sections 3.0, 3.1, 3.6.
  • 6&13.Jul'11 optional: [LV08] Chapter 2:
    Exercises 2.1.1, 2.1.3, 2.1.5? 2.2.4? 2.4.1 or 2.4.4, 2.6.2, 2.7.7, 2.8.4!
    Draft solutions are available here. Please read critically.
  • 8&15&22&29.Jun'11 core: [LV08] Chapter 2 by Daniel Visentin:
    All Sections but 2.5 and 2.9.
  • 1.Jun'11 optional: [LV08] Chapter 1:
    Exercises 1.3.3, 1.5.4, 1.6.6, 1.6.7, 1.7.3, 1.7.4, 1.7.9? 1.7.10? 1.7.11! 1.10.1? 1.10.2, 1.10.6! 1.11.1? 1.11.2, 1.11.4.
    (In 1.3.3 use 1.5.4. Why is 1.7.11 surprising and hard)
    Draft solutions are available here. Please read critically.
  • 18&25.May'11 core: [LV08] Chapter 1 by Wen Shao:
    All sections are important to know/read.
  • 11.May'11 optional: Organizational:
    How to organize the reading group and what (not) to read.
  • 4.May'11 core: Overview of AIT. Pilot talk by Marcus Hutter.
    RSISE Seminar Room A105.

Resources

Contact

Wen Shao <ua.ude.una|oahs.new#ua.ude.una|oahs.new> or
Peter Sunehag <ua.ude.una|gahenus.retep#ua.ude.una|gahenus.retep> or
Marcus Hutter <ua.ude.una|rettuh.sucram#ua.ude.una|rettuh.sucram>

page revision: 19, last edited: 05 Mar 2012 10:15
Edit Tags History Files Print Site tools + Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License