Content: Information theory studies the transmission, processing, extraction, and utilization of information. This course covers the basic theory of information theory and selected applications to data management, machine learning and information retrieval. Topics include entropy, mutual information, cross entropy, data processing theorem, information inequalities, cox' theorem, maximum entropy solutions, and applications such as data normalization, decision trees, maximum likelihood, logistic regression, cross-entropy, VC dimensions. Students will gain hands-on experience through a project. The latter will be flexible, allowing students to explore information theory in aspects related to their PhD research.
Prerequisites: The course is fast-paced but self-contained. Standard undergraduate CS knowledge of probability theory (e.g., random variables, basic probability distributions, expectation, etc.), algorithms and complexity theory (e.g., from textbooks such as [Ericson'19], [Dasgupta, Papadimitriou, Vazirani'06], [Cormen, Leiserson, Rivest, Stein'09], [Kleinberg, Tardos'05], or [Lehman, Leighton, and Meyer'15]) will be helpful
PhD program: The course counts as "non-seminar" Theory course for the PhD breath requirement.
Time/location
Instructors: Wolfgang Gatterbauer, Javed Aslam
Contact: Please use Piazza (via direct access from within Canvas) for all questions related to lectures, coursework, and the project. Notice you can post questions anonymously to all other students, or anonymously even to the instructors. Alternatively, please use our anonymous feedback form to send anonymous comments that only the instructors can see.
50%: Course project: The main component of this course will be a research project in the latter part of this class. This project can be a new application of one of the techniques presented or theoretically-oriented. The topic will be flexible, allowing students to explore scalable data management and analysis aspects related to their individual PhD research. This will involve an initial project proposal, an intermediate report, a project presentation and a final report. The final report should resemble a workshop paper, and will be evaluated on the basis of soundness, significance, novelty, and clarity. Deliverables and dates are posted on the project page.
35%: Flipped class scribes: Students take turns in "illustrating" 7 lectures (to be consistent with standard notation we refer to it as "scribes"). Graduate theory classes often ask students to scribe the lecture content. However, we change the rule of the game. Rather than scribing (= repeating and summarizing) the content of the class, we ask you to "illustrate" some interesting aspect in the covered topics with imaginative and ideally tricky illustrating examples. Those illustrations are great if they in turn can help other students practice and solidify their understanding of the topics discussed. Please start either from our PPTX template or use your own template (as long as you include slide numbers), and submit it as PDF to Canvas, naming it "cs7840-fa24-[YOUR NAME]-scribe[NUMBER]-[SOME DESCRIPTIVE TITLE].PDF".
Justification: Georg Cantor is quoted as saying: "To ask the right question is harder than to answer it." In that spirit, our class scribes are closer to research than assignments: What particular aspect in a class is worthy to be "illustrated"? That's already part of the question. Scribes are done in PowerPoint and are due 1 week after class at midnight (Mon for Mon classes, Wed for Wed classes). They can be done individually or in teams of two (if you work in teams of two, you are expected to illustrate 14 classes instead of 7 classes). For some more pedagogic motivation see videos by Tim Brown on asking questions and reframing problems being key to creativity, Dan Meyer on formulating problem being more important than just solving them, Derek Muller on increasing learning by including possible misconceptions into stories, a blog post on example-based reasoning, and an older text of mine of the educational value of temporarily misleading the spectator before giving the correct answer.
Procedure:
15%: Class participation: Classes will be interactive and require concentration and participation of the students. We are a big fan of the Socratic Method (video clip from the 1973 movie "The Paper Chase"). Participate when we discuss the merits or shortcomings of algorithms, or when we have small group break-out sessions with exercises. Ask questions, during class or on Piazza. Questions that make us ponder or create new illustrating examples are all great examples of class participation. Also, *never* hesitate to point out to us any errors you spot in the slides, even if minor. You can post anonymously to the other students on Piazza (and even anonymously to the instructors, though then we would not be able to associate you with your greatly appreciated participation). Also, don't hesitate to point out to us any interesting links to interesting related material. It can only count towards class participation. Finally notice that while the class provides extensive readings for those interested, these pointers are almost exclusively optional (unless otherwise stated in class).
Recommended textbook: Thomas Cover. Elements of Information Theory, 2nd ed, 2006. Additional material (like papers and selected chapters) are made available on the calendar page.
Earlier versions of this course were taught by Javed Aslam in Fall 2015 and Fall 2011. The pedagogy of this class is inspired by 7240: Principles of scalable data management taught by Wolfgang Gatterbauer.