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
- [Hut07] Short introductory AIT Scholarpedia article
- AIT resources webpage
- [LV08] Li&Vitanyi (2008) book (ANU library QA267.7.L5 2008, Hutter office, Amazon, free delivery)
Older editions are fine too. - [Cal02] Calude's (2002) book on Algorithmic Randomness
- [LV92] Longer introductory AIT article: Li&Vitanyi (1992) Inductive Reasoning and Kolmogorov Complexity,
Journal of Computer and System Sciences, Vol.44 (1992) pages 343-384 - AIT Mailing List
- Recommended ANU course: Information Theory COMP2610
- Advantageous background:
Course on Theory of Computation, e.g. COMP3630 or
[HMU06] Hopcroft&Motwani&Ullman (2006) Introduction to Automata Theory, Language, and Computation.
Course in Calculus, e.g. MATH1115 and MATH1116 or similar or e.g. book
[GL06] Ghorpade & Limaye (2006) A Course in Calculus and Real Analysis.
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>