Information Processing and Learning

10-704, Spring 2015

Akshay Krishnamurthy, Aarti Singh

Teaching Assistant: Kirthevasan Kandasamy
Class Assistant: Sandra Winkler



You will be required to scribe up to two lectures this semester. Please sign up for scribing here. The template for scribing is available here.

Date Lecture Topics Suggested Readings Assignments
Jan 13
Notes

  • Intro
  • Information Content, Entropy, Relative Entropy
  • Connection to Maximum Likelihood Estimation
  • Cover-Thomas: 2.1-2.4
  • MacKay: 2.4, 4.1
Jan 15
Notes

  • Connection between channel coding and inference
  • Properties of Information theoretic quantities
  • Gibb's, Data Processing, and Fano's inequalities
  • Submodularity
Jan 20
Notes
  • Submodularity of Entropy and Mutual Information
  • Application: Sensor Placement
  • Differential Entropy
  • Application: Clustering
Jan 22
Notes
  • Estimators for entropy in discrete and continuous settings
  • Plugin estimator, histogram matching, and Von Mises Estimator
Jan 27
Notes
  • Review of estimators for entropy.
  • Application: Structure learning in tree graphical models
Jan 29
Notes
  • Application: Structure learning in general graphical models
  • Application: Maximum entropy density estimation
  • I-geometry, I-projection
Feb 3
Notes
  • I-projection
  • MaxEnt duality
  • Generalized MaxEnt
Feb 5
Notes
  • Generalized MaxEnt Examples
  • Entropy Rate of a Stochastic Process
  • Burg's Max Entropy Rate Theorem
  • Source coding basics
  • Cover-Thomas: 4.1, 4.2, 12.5, 12.6, 5.1
HW 1 due.
Feb 10
Notes
  • Source coding basics
  • Source Coding Theorem
  • Kraft and McMillan Theorems
  • Cover-Thomas: 3, 5.1-5.5
Feb 12
Notes
  • Source coding recap
  • Non-singular codes
  • Huffman Codes
  • Empirical Risk Minimization and Prefix Codes
Project Proposal Due.
Feb 17
Notes
  • Complexity Penalized ERM via Prefix codes
  • Example: Histogram Classifiers
  • Example: Decision Tree Classifiers
Feb 19
Notes
  • Example: Wavelet De-noising
  • Example: Markov-chains
  • Minimum Description Length Principle
Feb 24
Notes
  • Sequential/Universal Prediction and Universal Coding
  • Minimax Regret and Redundancy
  • Exponential Weights update
  • Redundancy Capacity Theorem
Feb 26
Notes
  • Sequential Prediction with Other losses
  • Loss-based redundancy upper bounds
  • Exponential Weights and Expert Learning
HW 2 due.
Mar 3
  • Midterm review
  • QnA 3 released (Practice).
  • Mar 5
    Quiz 1
  • Quiz 1, Solutions
  • Mar 10 Spring Break
    Mar 12
    Mar 17
    Notes
    • Universal Coding
    • Context-Tree-Weighting
    • Arithmetic Coding
    Mar 19
    Notes
    • Sufficient Statistics
    • Information Bottleneck Principle
    • Rate distortion function
    Mar 24
    Notes
    • Rate Distortion Theorem
    • Channel Capacity
    • Channel Coding Theorem
    • Cover-Thomas: Ch 7
  • QnA 4 released.
  • Mar 26
    Notes
      Capacity of:
    • Independent Gaussian channels
    • Correlated Gaussian channels
    • Multi-antenna channels (known, random)
    Project Midterm report due (Mar 27).
    Mar 31
    Notes
    • Application to Privacy
    • Converse of Channel coding theorem
    • Minimax Theory and Testing
  • HW 3 released.(Mar 29)
  • QnA 5 released.
  • Apr 2
    Notes
    • Minimax Theory and Estimation
    • Le Cam's and Fano's Methods
    • Lower bounds on normal means problems
    Apr 7
    Notes
    • Lower bounds for nonparametric regression
    • Lower bounds for adaptive compressive sensing
    • Assouad's Method
  • QnA 6 released.

  • Apr 9
    Notes
    • Data Processing Inequalities and Minimax Lower Bounds
    • Strong Data Processing under Differential Privacy
    • Strong Data Processing under Compression
    Apr 14
    Notes
    • Cramer-Rao lower bound
    • Fisher Information
    • Jeffrey and Reference Priors
    HW 3 due.
    Apr 16
    No Class -- Spring Carnival
  • HW 4 released.(Mar 29)
  • Apr 21
    Notes
    • Large deviation theory - Sanov's theorem
    • Error exponents in Hypothesis testing
    • Cover-Thomas: Ch 11
    Apr 23
    Notes
    • Channel Coding Schemes
    • LDPC Codes and Message Passing
    • Belief Propagation and Inference in Graphical Models
    HW 4 due.
    Apr 28 Quiz 2
    Apr 30 Project Presentations