Information-Theoretic Modeling

582650
5
Algorithms and machine learning
Advanced studies
The course introduces information-theoretic methods and their applications in modeling. The topics include Shannon"s noiseless source coding theorem, data compression, and Rissanen"s Minimum Description Length (MDL) principle.

Exam

18.10.2012 09.00 CK112
Year Semester Date Period Language In charge
2012 autumn 05.09-12.10. 1-1 English

Lectures

Time Room Lecturer Date
Wed 10-12 C222 Jyrki Kivinen 05.09.2012-12.10.2012
Fri 10-12 C222 Jyrki Kivinen 05.09.2012-12.10.2012

Exercise groups

Group: 1
Time Room Instructor Date Observe
Tue 10-12 C220 Hannes Wettig 10.09.2012—12.10.2012

General

The course has ended.  Thanks to everyone who participated.

You still have a little time to fill in the course feedback form, if you haven't done that yet.  The lecturer's reply to the feedback, and some other comments on the course, will appear in this space soon.

The content of the course was mainly the same as in the Autumn 2009 version lectured by Teemu Roos.

Prerequisites

The course has no formal prerequisites. Familiarity with basic concepts and manipulations from probability theory and calculus is however essential for successfully participating in the course.

Contents

  • basic concepts of information theory: entropy, mutual information etc.
  • lossy coding, noisy channel coding theorem
  • lossless source coding, theory: Shannon's theorem, Kraft's inequality
  • important lossless codes: Shannon-Fano, Huffman, arithmetic
  • universal codes and minimum description length (MDL)
  • Kolmogorov complexity

Completing the course

The course consisted of weekly exercise sessions (beginning from week 2) and a course exam.  Sufficient participation in the exercises was compulsory.

This course is a prerequisite for 582651 Project in Information-Theoretic Modeling in the next period. The project is not a part of this course, but doing also the project is highly recommended.

Literature and material

There is no textbook.  The homework and exam will be based on the lectures.  The lecture material will appear on this page.

Lecture notes

  • Lecture 1 (5 September): course administration, introductory examples. We covered these slides except for the last example (noisy channel coding), which was covered on 7 September
  • Lecture 2 (7 September): mathematical preliminaries. We covered parts 1 (calculus) and 2 (probabilities), leaving part 3 (inequalities) until 12 September.
  • Lecture 3 (12 September): we covered entropy, mutual information and basic inequalities. AEP was left for Friday.
  • Lecture 4 (14 September): noisy channels, capacities and rates, channel coding theorem. Hamming codes were left for next week.
  • Lectures 5 and 6 (19 and 21 September): prefix codes, Kraft inequality. Shannon coding, Huffman coding.
  • Lecture 7 (26 September): arithmetic coding
  • Lecture 8 (28 September): universal source coding, two-part codes, other universal codes
  • Lecture 9 (3 October): MDL principle
  • Lecture 10 (5 October): more MDL principle: examples and some technicalities
  • Lecture 11 (10 October): Kolmogorov complexity (we did not cover gambling)
  • Last lecture (12 October): we had a guest lecture by Teemu Roos and a quick summary of the course.

Exercises

Exercise sessions will be held on Tuesdays at 10:15–12:00 in classroom C220.

Recommended extra reading

  • Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley 2006 (2nd edition).