INFORMATION THEORY

Related Information:

  • Course number EECS 229A, Fall 2020

  • Instructor: Prof. Kannan Ramchandran, email: kannanr@eecs.berkeley.edu

  • Co-instructor: Avishek Ghosh, email: avishek_ghosh@berkeley.edu

  • Time and place: Tu/Th 12:30-2:00 pm, Haviland 12

  • Office Hours: Tu 2:00-3:00pm

  • Units: 3

Course Description

This is a graduate level introductory course in information theory, a branch of engineering and statistics that quantifies, measures and makes inferences about information. Information theory was created by Claude Shannon in 1948 as a mathematical theory of communication, but has since found a broad range of applications in machine learning & statistics, computer science, finance, physics, computational biology, etc. As such, it should be of broad interest to students across EECS and beyond. Especially in this age of data deluge, fundamental quantification of information is indispensable to making intelligent decisions.


The first part (roughly two-thirds) of the course will cover the main concepts of information theory, including entropy and mutual information, and how they emerge as the fundamental limits of information representation (a.k.a data compression or source coding) and information transmission (a.k.a. reliable communication or channel coding) respectively. Additionally, we will cover computationally efficient algorithms that approach these fundamental limits for both data compression (based on arithmetic coding) and information communication (based on the coding theory constructions of polar codes and sparse-graph codes). Further, the role of sparse-graph codes in speeding up modern big data applications featuring sparsity will be highlighted with connections to areas like compressed sensing, learning mixtures of sparse linear regressions, and group testing. Time permitting, we will also explore the framework of distributed compression of correlated sources, with applications to distributed sensor networks and compression of encrypted data.


The first part (roughly two-thirds) of the course will cover the main concepts of information theory, including entropy and mutual information, and how they emerge as the fundamental limits of information representation (a.k.a data compression or source coding) and information transmission (a.k.a. reliable communication or channel coding) respectively. Additionally, we will cover computationally efficient algorithms that approach these fundamental limits for both data compression (based on arithmetic coding) and information communication (based on the coding theory constructions of polar codes and sparse-graph codes). Further, the role of sparse-graph codes in speeding up modern big data applications featuring sparsity will be highlighted with connections to areas like compressed sensing, learning mixtures of sparse linear regressions, and group testing. Time permitting, we will also explore the framework of distributed compression of correlated sources, with applications to distributed sensor networks and compression of encrypted data.

Course Goal

  • This course will introduce you to the fundamental and beautiful subject of information theory and equip you with the tools needed to make formal sense of information and to apply it effectively to your own research.

  • A big part of the course will be a final project based on a broad range of topics related to information theory and its applications to statistics, machine learning, communications, compression, the minimum description length principle for model selection, autoencoders, GANs, online learning, deep neural networks, computational biology, etc. These projects can be of a literature survey nature, or in the form of making original research contributions to the field.

Prerequisite

This course requires a strong understanding of probability at the undergraduate level (EECS 126 or equivalent), and a good level of mathematical maturity.

Notes on enrollment

Undergraduate enrollment is presently being capped at 20 students to allow ample opportunity for graduate students to enroll. Enrollment codes for undergraduate students will be assigned on a first-come-first-serve basis to the interested students who meet the prerequisite (A- or better in upper division probability course such as EECS 126 or equivalent in the math or statistics department).

Further Information:

TA Office Hours: Wednesday 11:00-12:00pm