Applied Information Theory

CMPSCI 691GG • Fall 2010 • Tuesday and Thursday, 9:30-10:45 • Location CS Building, Room 140 (as of Sept. 28)

Instructor

Erik Learned-Miller
elm@cs.umass.edu
545-2993

Teaching Assistant: None

Prerequisites

Stats 515 or equivalent. Basic college-level probability. Basic programming ability in C++, Matlab, or Java.

Reading Materials

• Required text: Elements of Information Theory, Second Edition, by Thomas Cover and Joy Thomas.

• NOTE THAT THIS IS THE SECOND EDITION, NOT THE FIRST EDITION!!! If you have a copy of the first edition of this book, you might be able to use it, as the second edition is not too different. However, you should at least have access to the second edition to check for differences, page number references, problem set numbers, and other differences. I will not answer questions about the differences between the books, as I do not have time to figure this out. You should have at least one friend with a copy of the second edition if you want to use the first edition, so that you can find appropriate page number references and so on.

Resources

David Mackay's Information Theory book (electronic edition is free and on the web)

Minimum entropy joint alignment

Mutual Information Alignment

Problem Sets

Problem sets are due at any time on the day indicated on the course web page. If you turn them in after class, please slide them under the door of my office, or put them in my faculty mailbox. The latest you can turn in a problem set is midnight on the day due. The fact that you cannot get into the building after hours does not count as an excuse. If you're worried about that, turn it in earlier. I may take off 50% for problem sets turned in late.

If you want written feedback on your homework (such as how many points per problem you got), please hand it in on paper, rather than as an email.

Description

This course will introduce the basic concepts of Information Theory: entropy, relative entropy, mutual information, channel capacity, and rate distortion. Applications, rather than proofs, will be emphasized. In addition, the statistical problem of computing information theoretic quantities from data will be emphasized. Non-parametric and semi-parametric statistical models will also be covered.

Schedule
Date Lecture topic New assignments Assignments due Reading
Sept. 7 Introduction and Overview. Entropy as non-parametric likelihood. Mutual information as measure of dependence. Dreams as decoding. Duality of compressibility and likelihood. Plus much much more! Chap. 2, C+T
Sept. 9 Entropy, Relative entropy, Mutual Information Assignment 1 Posted Chap. 2, C+T
Sept. 14 Entropy, Relative entropy, Mutual Information continued Chap. 2, C+T
Sept. 16 Entropy, Relative entropy, Mutual Information continued Chap. 2, C+T
Sept. 21 Convexity, Jensen's Inequality, Basic Information Theory Inequalities Assignment 1 DUE Chap. 2
Sept. 23 APPLICATION 1: Information gain, conditional mutual information, and feature selection in face recognition. Chap. 2
Sept. 28 Fano's Inequality and the Asymptotic Equipartition Property Assignment 1 Solutions Chap. 3
Sept. 30 Source Coding and Compression Chap. 5
Oct. 5 Source coding 2 Assignment 2 Posted Write a 1-page description of paper. Include your specific opinions about the validity of the theory presented. I want you to argue for it or against it. Chap. 5
Oct. 7 "Shannon codes" and achievability of near entropy source coding. Huffman coding. Chap. 5
Oct. 12 Source Coding of Finite Sequences Chap. 5
Oct. 14 Differential Entropy and Density Estimation with Parzen Windows (beg. of Chap 8)
Oct. 19 Intro to Independent Components Analysis Assignment 2 DUE
Oct. 21 Ind. Comp. Analysis continued assignment 3. The assignment describes some audio files you are supposed to download. Here are the versions for matlab: mix1.mat,mix2.mat,mix3.mat. Here are the version for other languages. mix1ascii,mix2ascii,mix3ascii. Please read this paper on ICA
Oct. 26 Minimum Entropy Joint Alignment Algorithms
Oct. 28 Finish minimum entropy joint alignment. Start mutual information alignment. Optional reading: Joint alignment paper.
Nov. 2 Finish mutual info alignment. Structure finding in graphical models.
Nov. 4 Structure finding in graphical models and semi-parametric models. Assignment 3 due
Nov. 9 Channel coding. Assignment 4: The following 8 PROBLEMS from Cover and Thomas: 7.1, 7.2, 7.3, 7.8, 7.13, 7.15, 7.20, 7.30. This problem set is harder than the last set of problems from the book. Start as soon as you can!!! Come see me if you have trouble. Chapter 7, Cover and Thomas
Nov. 10 Channel coding. NOTE: THe EXAM ON Nov. 30th will cover all material up to and including this lecture. Chapter 7, Cover and Thomas
Nov. 16 Linear codes for channel coding. This is the first part of final assignment
Nov. 18 Exam review.
Nov. 23 IF WE HAVE TIME: Arithmetic coding (for compression). This will cover the second part of the final assignment Assignment 5 cancelled Assignment 4 due Solutions to homework 4.
Nov. 25 THANKSGIVING THANKSGIVING THANKSGIVING THANKSGIVING
Nov. 30 In CLASS EXAM. Exam will cover material up to and including Nov. 10 lecture.
Dec. 2 Channel coding theorem.. HOMEWORK 5 is CANCELLED
Dec. 7 Converse to channel coding theorem..
Dec. 9 ATTENDANCE MANDATORY. Finish channel coding theorems