Information-Theoretic Learning (ITL)

Leiden University, Spring Semester 2019

General Information

Important: All students are requested to register for the course via blackboard (in addition to USIS).
Important: Bachelor students who want to investigate the possibility of letting (the EC of) this course count towards their master's diploma, are advised to contact the chairman of the Exam Committee (Ronald van Luijk, rvl@math.leidenuniv.nl) at their earliest convenience.
LecturerProf. Dr. Peter Grünwald, Leiden University, Mathematical Institute, and Centrum Wiskunde & Informatica (CWI), Amsterdam
Teaching assistantMuriel Perez Ortiz, Leiden University, Mathematical Institute, and Centrum Wiskunde & Informatica (CWI), Amsterdam
Contact: send email to: muriel.perez at cwi.nl.

The URL of this webpage is www.cwi.nl/~pdg/teaching/inflearn. Visit this page regularly for changes, updates, etc.

This course is on an interesting but complicated subject. It is given at the master's or advanced bachelor's level. Although the only background knowledge required is elementary probability theory, the course does require serious work by the student. The course load is 6 ECTS. Click here (studiegids) for a general course description.

Many thanks are due to Steven de Rooij (Leiden University) who prepared a significant proportion of the exercises.

Lectures and Exercise Sessions

Lectures take place each Tuesday from 13.30--15.15 in room 412 of the Snellius Building, Niels Bohrweg 1, Leiden. The lectures are immediately followed by a mini-exercise session held by Muriel Perez. The first lecture will take place February 5th, 2019. There will be no lectures on March 19, April 16 and April 23 (note: the offical program says that there is no lecture on March 12th and that there is a lecture on March 19th - this has been changed: there is a lecture on March 12th, but not on March 19th). The last official lecture is scheduled for May 21, and the final exam is provisionally scheduled for Tuesday May 28th, in room 412 in the Snellius Bulding, from 14.00-17.00

Homework Assignments

Weekly Homework: At every lecture on Tuesday except the first there is a homework assignment. The assignment will also be made available on this webpage. Homework is obligatory and must be turned in at or before the beginning of the next lecture, i.e. one week after the assignment was handed out. You can turn in your homework digitally via blackboard or (printed or handwritten) by handing it over to me or Muriel at the beginning of the lecture. After the lecture, there is (approximately) 30 minutes homework session, during which the homework will be explained and discussed by Muriel. Turning in written complete homework in time is required, see below.

Credit

6 ECTS points.

Examination form

In order to pass the course, one must obtain a sufficient grade (5.5 or higher) on both of the following two:
  1. An open-book written examination (to be held Tuesday May 28th).
  2. Homework. Each student must hand in solutions to homework assignments at the beginning of the lecture after the homework was handed out. Discussing the problems in the group is encouraged, but every participant must write down her or his answers on her or his own. The final homework grade will be determined as an average of the weekly grades.
The final grade will be determined as the average of the two grades, with the homework counting 40% and the final exam counting 60%.

Literature

We will mainly use various chapters of the following source: P. Grünwald. The Minimum Description Length Principle, MIT Press, 2007. Some additional hand-outs will be made available free of charge as we go. For the second week, this is Luckiness and Regret in Minimum Description Length Inference, by Steven de Rooij and Peter Grünwald, Handbook of the Philosophy of Science, Volume 7: Philosophy of Statistics, 2011. This paper gives an overview of the part of this course that will be concerned with the relation between statistics, machine learning and data compression, as embodied in MDL learning.

Course Schedule

Lecture contents are subject to change at any time for any reason. A more precise schedule, with links to all exercises, will be determined as we go.
  1. February 5: introduction
  2. February 12: data compression without probability
  3. February 19: Codes and Probabilities (the most important lecture!)
  4. February 26: Preparatory Statistics.
  5. March 5th:
  6. March 12th: Universal Coding Note: there is a lecture on March 12th (location: De Sitter zaal, Huygens building) even though the official schedule on the web says there isn't!
  7. March 19th: No Lecture! (even though the official schedule on the web says that there is!)
  8. March 26th:
  9. April 2: Simple Refined MDL, Prequential Plugin Codes
  10. April 9: General Refined MDL, Prediction with MDL, Issues with Universal Codes/MDL
  11. April 16: No Lecture!
  12. April 23: No Lecture!
  13. April 30: Excursion: Large Deviations and/or Gambling!
  14. May 7th: Excursion, Part II.
  15. May 14th: Maximum Entropy
  16. May 21st: MaxEnt and MDL ; Overview/Wrap Up
  17. May 28th 14.00-17.00: Exam in Room 412 This overrides the previously planned time/date place for exam!. Example examination.

    Peter Grünwald’s home page