In this course, we will study the wide variety of research on probabilistic graphical models and structured prediction. These areas of machine learning research cover algorithmic approaches to learning and prediction in settings with dependencies in data, variables, and outputs. We will examine the currently understood methods for efficiently managing the complexities that arise when we consider these dependencies in models, study algorithms for reasoning and predicting using these models, and explore how other algorithms can learn parameters and structure from data.
The class will be a shared learning experience, where the students will lead discussions as we work through some seminal texts and recent papers.
Class meets Tuesday and Thursday from 3:30 PM to 4:45 PM in McBryde 232.
The course homepage is http://people.cs.vt.edu/~bhuang/courses/pgmsp16/ or equivalently http://berthuang.com/courses/pgmsp16/.
Topics include directed models (Bayes nets), undirected models (Markov/conditional random fields), exact inference (junction tree), approximate inference (belief propagation, dual decomposition), parameter learning (MLE, MAP, EM, max-margin), and structure learning.
Having successfully completed this course, the student will be able to:
The listed prerequisite courses cover relevant material that includes introductory-level knowledge of machine learning and statistical learning (likelihood, maximum likelihood, bias and variance, underfitting, overfitting, regularization, cross-validation), probability and statistics, and algorithms.
Please speak with the instructor if you are concerned about your background. Note: If any student needs special accommodations because of any disabilities, please contact the instructor during the first week of classes.
After the first two weeks of the semester, the class will center around discussion. We will work through the reading materials together, and you will lead discussion and participate in panels during class sessions. In each class session, you will have one of three roles: panel leader, panelist, or audience.
The goal of each class is to understand the ideas presented in the assigned reading as much as is possible. We will work through examples, work together to clarify points of confusion, and discuss the wider implications of the topics from the reading. To make sure this experience works for everyone, class attendance is mandatory. I will take attendance and penalize unexused absences at my discretion.
In the first week of class, you will rank dates for when to serve as panel leaders or panelists, and I will work out a schedule that satisfies your preferences as much as possible. Keep in mind that since every student must do the reading, serving as a panelist or leader is not much more work on top of the reading.
For each assigned reading, you will submit a writeup in your own words that contains two major components: a summary and at least two questions.
The summary should be 1-2 paragraphs describing what main ideas were presented in the text. You should cover the takeaway points, not the fine details.
You will then write (at least) two questions. The first will be a clarification question. What idea in the text was unclear to you? What do you want to understand better? For example, you might write, "Why is Lemma 3, which is presented without proof, guaranteed to be true?" In theory, clarification questions should have answers that we can attempt to find together as a class.
The second question you will include is a discussion question. You might ask about research ideas, how the technique we studied can be applied, or why a mathematical concept is important. In theory, a discussion question may not have a true answer, but we can speculate and brainstorm about them during our discussion.
You should submit your summary and questions on Canvas as posts in the discussion thread for the class session. These threads are set so you cannot see other posts until you post your own summary and questions.
For the class project, you will conduct research with the goal of producing findings worthy of publication at a conference. The project should be done in groups of 1–3 students, and should feature a novel algorithmic contribution to some aspect of learning, inference, prediction, analysis, or application using probabilistic graphical models or structured predictors. You are strongly encouraged to incorporate this project with any other research you are working on, and you are welcome to include collaborators outside the class as long as you are doing a substantial proportion of the research yourself.
You will first write a 1-page proposal on your project before Spring Break. You are highly encouraged to begin brainstorming about topics as soon as possible. You will write a 6–10 page paper on your findings due at the end of the semester, reporting your contribution, background material, evaluation (experiments and/or analysis), and conclusions. Details on the proposal and paper details are available at ./project_deliverables.html.
Here is a list of brainstormed project ideas to help you design your own project. See additional project ideas from similar courses, such as from CMU, UPenn, and the projects from the previous PGM course at VT for more ideas.
Various related courses have valuable materials that can help supplement our official reading. Some of these are linked below.
The tenets of the Virginia Tech Graduate Honor Code will be strictly enforced in this course, and all assignments shall be subject to the stipulations of the Graduate Honor Code. For more information on the Graduate Honor Code, please refer to the GHS Constitution at http://ghs.graduateschool.vt.edu.
This course will have a zero-tolerance policy regarding plagiarism or other forms of cheating. Your homework assignments must be your own work, and any external source of code, ideas, or language must be cited to give credit to the original source. I will not hesitate to report incidents of academic dishonesty to the graduate school.
| Session | Date | Topic | Reading | Panelists (Leaders in bold) |
|---|---|---|---|---|
| 1 | Tue 1/19 | Overview of Graphical Models and Structured Prediction | KF 1, 2 Why ML Needs Statistics by Welling (link) |
None |
| 2 | Thu 1/21 | Bayesian Networks | KF 3-3.2 | None |
| 3 | Tue 1/26 | Bayesian Networks | KF 3.3-3.5 | None |
| 4 | Thu 1/28 | Undirected Graphical Models | KF 4-4.4 | None |
| 5 | Tue 2/2 | Undirected Graphical Models | KF 4.5-4.7 | Tianyi Li, Jason Louis Granstedt, William Ryan Doan |
| 6 | Thu 2/4 | Exact Inference: Variable Elimination | KF 9-9.4, 9.7 | Sirui Yao, Abhilash Chowdhary, Aishwarya Agrawal, Arjun Chandrasekaran |
| 7 | Tue 2/9 | Exact Inference: Clique Trees | KF 10 | Arijit Ray, Aishwarya Agrawal, Arjun Chandrasekaran |
| 8 | Thu 2/11 | Inference as Optimization | KF 11-11.3 | Bert Huang, Aishwarya Agrawal, Viresh Ranjan, Xuan Zhang |
| 9 | Tue 2/16 | Inference as Optimization | KF 11.4-11.6 | Bert Huang |
| 10 | Thu 2/18 | MAP Inference | KF 13-13.5 | Yi Tian |
| 11 | Tue 2/23 | Parameter Learning in Bayesian Networks | KF 17 | Abhilash Chowdhary |
| 12 | Thu 2/25 | Structure Learning in Bayesian Networks | KF 18 | Bijaya Adhikari |
| 13 | Tue 3/1 | Partially Observed Data | KF 19.1-19.2 | Jiali Lin |
| 14 | Thu 3/3 | Learning Undirected Models | KF 20 | Bert Huang |
| Spring Break | ||||
| 15 | Tue 3/15 | Graphical Models as Exponential Families | WJ 3 | Elaheh Raisi |
| 16 | Thu 3/17 | Sum-Product, Bethe-Kikuchi, Expectation-Propagation | WJ 4 | Aroma Mahendru |
| 17 | Tue 3/22 | Variational Methods in Parameter Estimation | WJ 6 | Viresh Ranjan |
| 18 | Thu 3/24 | Convex Relaxations and Upper Bounds | WJ 7 | Bert Huang |
| 19 | Tue 3/29 | Dual Decomposition for Inference | Introduction to Dual Decomposition for Inference by Sontag et al. (link) | Arjun Chandrasekaran |
| 20 | Thu 3/31 | Structured SVM | Cutting Plane Training of Structural SVMs by Joachims et al. (link) | Jinwoo Choi |
| 21 | Tue 4/5 | Max-Margin Markov Networks and Inner-Dual Learning | Max-Margin Markov Networks by Taskar et al. (link) Learning Structured Prediction Models: A Large Margin Approach by Taskar et al. (link) |
Shuangfei Fan |
| 22 | Thu 4/7 | Inner-dual Learning with Dual Decomposition | Learning Efficiently with Approximate Inference via Dual Losses by Meshi et al. (link) A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction by Hazan and Urtasun (link) |
Bert Huang |
| 23 | Tue 4/12 | Markov Logic Networks | Markov Logic Networks by Richardson and Domingos (link) | Chris Dusold |
| 24 | Thu 4/14 | Hinge-Loss MRFs and Probabilistic Soft Logic | Hinge-Loss Markov Random Fields and Probabilistic Soft Logic by Bach et al. (link). Read Sections 1, 2, 3, 5, 6-6.3. Optionally skim the rest. | Walid Chaabene |
| 25 | Tue 4/19 | Latent-Variable Structured SVM | Learning Structural SVMs with Latent Variables by Yu et al. (link) Marginal Structured SVM with Hidden Variables by Ping et al. (link) |
Bert Huang |
| 26 | Thu 4/21 | Latent-Variable Inner-Dual methods | Efficient Structured Prediction with Latent Variables for General Graphical Models by Schwing et al. (link) Paired-Dual Learning for Fast Training of Latent Variable Hinge-Loss MRFs by Bach et al. (link) |
Subhodip Biswas |
| 27 | Tue 4/26 | Learning Deep Structured Models | Learning Deep Structured Models by Chen et al. (link) | William Ryan Doan |
| 28 | Thu 4/28 | Causality | KF 21 | Jason Louis Granstedt |
| 29 | Tue 5/3 | Wrap Up | Bert Huang |
Disclaimer: This syllabus details the plans for the course, which are subject to change. I will make sure any changes are clearly announced and will always be intended for your benefit.
For visitors outside the course: You are welcome to use the course materials for educational purposes. Do not sell any of this content.