ECE-5583: Information Theory and Probabilistic Programming

There has been a strong resurgence of AI in recent years. An important core technology of AI is statistical learning, which aims to automatically “program” machines with data. While the idea can date back to the 50's of the last century, the plethora of data and inexpensive computational power allow the techniques to thrive and penetrate into every aspect of our daily lives — customer behavior prediction, financial market prediction, fully automatic surveillance, self-driving vehicles, autonomous robots, and beyond.

Information theory was first introduced and developed by the great communications engineer, Claude Shannon in the 50's of the last century. The theory was introduced in an attempt to explain the principle behind point-to-point communication and data storing. However, the technique has been incorporated into statistical learning and has inspire many of the underlying principles. In this graduate course, we would try to explore the exciting area of statistical learning from the perspectives of information theorists. It facilitates students to have a deeper understanding of the omnipresent field of statistical learning and to appreciate the wide-spread significance of information theory. Moreover, we will look into recent advance in probabilistic programming technology that facilitates users to tackle inference problems through computer programs.

The course will start by providing an overview of information theory and statistical learning. We will then aid students to establish a solid foundation on core information theory principles including information measures, AEP, source and channel coding theory. We will then introduce common and yet powerful statistical techniques such as Bayesian learning, decision forests, and belief propagation algorithms and discuss how these modern statistical learning techniques are connected to information theory. To summarize, we will skim through some probablistic programming tools. The main reference text is a book by Professor Mackay — Information Theory, Inference, and Learning Algorithms but we will also borrow heavily from materials available online. Other most important reference texts are

Other Reference Materials

Office Hours

There are no “regular” office hours. But you are welcome to come catch me anytime or contact me through emails.

Course Syllabus (Tentative)

  • Probability review

  • Maximum likelihood estimator, MAP, Bayesian estimator

  • Graphical models and message passing algorithms

  • Lossless source coding theory, Huffmann coding, and introduction to Arithmetic coding

  • Asymptotic equipartition property (AEP), typicality and joint typicality

  • Entropy, conditional entropy, mutual information, and their properties

  • Channel coding theory, capacity, and Fano’s inequality Continuous random variables, differential entropy, Gaussian source, and Gaussian channel

  • Error correcting codes, linear codes, and introduction to low-density parity check code

  • Methods of type, large deviation theory, maximum entropy principle

N.B. You will expect to expose to some Python and Matlab. You won't become an expert on these things after this class. But it is good to get your hands dirty and play with them early.

Projects

Final project report is due date Dec 14.

Late Policy

  • There will be 5% deduction per each late day for all submissions

  • The deduction will be saturated after 10 days. So you will get half of your marks even if you are super late

Grading

Quizzes (In class participation): 10% (extra credits).

Presentations: 20%.

Homework: 20%.

"Mid-term": 20%. take home but will only have half of a day to complete.

Final Project: 40%.

Final Grade:

  • A: \(\sim\) 90 and above

  • B: \(\sim\) between 80 and 90

  • C: \(\sim\) between 70 and 80

  • D: \(\sim\) between 60 and 70

  • F: Below 60

Calendar

Topics Materials
8/24 Overview of IT, probability overview, Monty Hall problem, discrete and continuous random variables, expectation (video), (video last year) probability review, slides2022a
8/31 Joint and conditional probabilities, independence and conditional independence (video)
9/07 ML, MAP, Bayesian inference (video)
9/14 Conjugate prior, Beta distribution, Python introduction (video)
9/21 Law of large number (LLN), proof of weak LLN, sampling discrete distributions, asymptotic equal partition, Kelly's criterion (video) slides2022b
9/28 Typical sequences, Source Coding Theorem, Jensen's inequality (video) Quantifying information
10/05 Conditional entropy, Huffman coding, KL-divergence, entropy of Gaussian source, Gaussian source maximizes entropy, constructive proof of source coding theorem (video) information measure
10/12 Mutual information, Thiel index, cross-entropy, data processing inequality (video) (slides from Berkeley CS188)
10/19 Chain rule of mutual information, Shannon's perfect secrecy, Decision tree, TF-IDF (video)
10/26 Fano's inequality, channel capacity, binary symmetric channel, Gaussian channel, packing lemma, covering lemma (video) Read Lecture 7
11/02 Mid-term
11/09 Presentations (video)
11/16 More Lea, proof of channel coding theorem, Lagrange multiplier and KKT conditions, parallel Gaussian channel (video)
11/23 Thanksgiving (video)
11/26 Graphical models, Bayesian networks, undirected graphs, factor graphs (video) slides2022c

Academic Integrity

Academic honesty is incredibly important within this course. Cheating is strictly prohibited at the University of Oklahoma, because it devalues the degree you are working hard to get. As a member of the OU community, it is your responsibility to protect your educational investment by knowing and following the rules. For specific definitions on what constitutes cheating, review the Student’s Guide to Academic Integrity.

Religious Observance

It is the policy of the University to excuse the absences of students that result from religious observances and to reschedule examinations and additional required classwork that may fall on religious holidays, without penalty.

Reasonable Accommodation Policy

The Accessibility and Disability Resource Center is committed to supporting students with disabilities to ensure that they are able to enjoy equal access to all components of their education.  This includes your academics, housing, and community events.  If you are experiencing a disability, a mental/medical health condition that has a significant impact on one or more life functions, you can receive accommodations to provide equal access.  Possible disabilities include, but are not limited to, learning disabilities, AD(H)D, mental health, and chronic health.  Additionally, we support students with temporary medical conditions (broken wrist, shoulder surgery, etc.) and pregnancy.  To discuss potential accommodations, please contact the ADRC at 730 College Avenue, (ph.) 405.325.3852, or adrc@ou.edu. 

Title IX Resources and Reporting Requirement

Anyone who has been impacted by gender-based violence, including dating violence, domestic violence, stalking, harassment, and sexual assault, deserves access to resources so that they are supported personally and academically. The University of Oklahoma is committed to offering resources to those impacted, including: speaking with someone confidentially about your options, medical attention, counseling, reporting, academic support, and safety plans. If you would like to speak with someone confidentially, please contact OU Advocates (available 247 at 405-615-0013) or another confidential resource (see “Can I make an anonymous report?”). You may also choose to report gender-based violence and discrimination through other means, including by contacting the Institutional Equity Office (ieo@ou.edu, 405-325-3546) or police (911). Because the University of Oklahoma is committed to the safety of you and other students, I, as well as other faculty, Graduate Assistants, and Teaching Assistants, are mandatory reporters. This means that we are obligated to report gender-based violence that has been disclosed to us to the Institutional Equity Office. This includes disclosures that occur in: class discussion, writing assignments, discussion boards, emails and during StudentOffice Hours. For more information, please visit the Institutional Equity Office.

Adjustments for Pregnancy/Childbirth Related Issues

Should you need modifications or adjustments to your course requirements because of documented pregnancy-related or childbirth-related issues, please contact me as soon as possible to discuss. Generally, modifications will be made where medically necessary and similar in scope to accommodations based on temporary disability. Please see www.ou.edu/content/eoo/faqs/pregnancy-faqs.html for commonly asked questions.

Final Exam Preparation Period

Pre-finals week will be defined as the seven calendar days before the first day of finals. Faculty may cover new course material throughout this week. For specific provisions of the policy please refer to OU’s Final Exam Preparation Period policy.

Emergency Protocol

During an emergency, there are official university procedures that will maximize your safety. Severe Weather: If you receive an OU Alert to seek refuge or hear a tornado siren that signals severe weather 1. LOOK for severe weather refuge location maps located inside most OU buildings near the entrances 2. SEEK refuge inside a building. Do not leave one building to seek shelter in another building that you deem safer. If outside, get into the nearest building. 3. GO to the building’s severe weather refuge location. If you do not know where that is, go to the lowest level possible and seek refuge in an innermost room. Avoid outside doors and windows. 4. GET IN, GET DOWN, COVER UP. 5. WAIT for official notice to resume normal activities. Link to Severe Weather Refuge Areas, Severe Weather Preparedness - Video

Armed Subject/Campus Intruder

If you receive an OU Alert to shelter-in-place due to an active shooter or armed intruder situation or you hear what you perceive to be gunshots: 1. Avoid: If you believe you can get out of the area WITHOUT encountering the armed individual, move quickly towards the nearest building exit, move away from the building, and call 911. 2. Deny: If you cannot flee, move to an area that can be locked or barricaded, turn off lights, silence devices, spread out, and formulate a plan of attack if the shooter enters the room. 3. Defend: As a last resort fight to defend yourself. For more information, visit OU’s Emergency Preparedness site. Shots Fired on Campus Procedure – Video

Fire Alarm/General Emergency

If you receive an OU Alert that there is danger inside or near the building, or the fire alarm inside the building activates: 1. LEAVE the building. Do not use the elevators. 2. KNOW at least two building exits 3. ASSIST those that may need help 4. PROCEED to the emergency assembly area 5 ONCE safely outside, NOTIFY first responders of anyone that may still be inside building due to mobility issues. 6. WAIT for official notice before attempting to re-enter the building. OU Fire Safety on Campus

Mental Health Support Services

If you are experiencing any mental health issues that are impacting your academic performance, counseling is available at the University Counseling Center (UCC). The Center is located on the second floor of the Goddard Health Center, at 620 Elm Rm. 201, Norman, OK 73019. To schedule an appointment call (405) 325-2911. For more information, please visit University Counseling Center.