CSE 592 Advanced Topics in Computer Science -- Graphical Models
Fall 2009
Schedule
Section Information
Date: Tue-Thu
Time: 3:50pm-5:10pm
Room: S218 (Social and Behavioral Sciences Bldg)
Instructor Information
Instructor: Luis Ortiz
Email: le [last name] at cs followed
by .sunysb and finally .edu
Office: 2313-c
Phone: (631) 632-1805
Office Hours: 1:00pm-4:400pm Weds, and by appointment (please e-mail me in advance)
Course Description
Graphical models have revolutionized how we model and study large complex systems. The impact of graphical models has truly been broad. One can now find uses or instances of graphical models in statistics, computer science, applied mathematics, artificial intelligence, machine learning, electrical engineering, finance, psychology, cognitive science, game theory, economics, and the list keeps growing. Graphical models are used to address many problems in computer vision, robotics, (autonomous) control, reasoning and decision-making under uncertainty, coding and information theory, speech recognition, natural language processing, computational linguistics, machine translation, banking, computational biology and computer music, for example. Specific applications that rely on graphical models technology are by now wide-ranging and include expert systems in medical diagnosis, bioinformatics and system biology, forensics and genetic analysis, image processing and analysis, voice assisted/activated systems, automatic speech-to-text annotation/transcription and language translation systems, music-accompaniment systems, information retrieval, computer system troubleshooting, communications, agriculture, risk analysis, loan/credit rating, fraud detection, environmental conservation, water management and transportation, to name a few.
At the core of the representation is a graph (or network) which facilitates the modeling and interpretation of complex interactions between many entities in the system. The nature of the interactions depend on the system under study; as examples, the interactions may involve constraining, probabilistic, strategic and/or preferential relationships. The generality of the framework results from an available toolkit of basic representations and algorithms from which one can draw to develop a specific application.
This course will cover the fundamental ideas behind graphical models in the context of various representations and the computational methods that support them.
Course Purpose and Objectives
- To provide an introduction to the general area of
graphical models (and their applications), as well as the typical problems addressed, the basic representations and algorithms often used, and the fundamental ideas behind them
- To expose students to state-of-the-art methods and applications in a variety of domains
- To prepare students for continuing research and development work in the area
Course Organization
The course format involves formal lectures, discussions and presentations, some led by the students themselves. Reading material from a variety of sources, including textbooks, tutorials, classical and recent research papers, and other possible web content, will be handed out, posted or assigned to supplement the lectures.
Course Project
Students complete a research project on a
relevant topic. The specific problem requires the instructor's
approval. Possible projects include, but are not limited to, an application of a particular model and technique to a specific problem, the development of a system based on graphical model ideas to solve a particular problem for a particular application domain, or novel experimental evaluations and comparisons of one or various computational techniques. Ideally, the project would incorporate a combination of theoretical and experimental work. Projects that involve exclusively theoretical work may be permitted only under very close consultation with the instructor and should involve a narrowly and clearly defined problem description and line-of-attack.
Students periodically submit progress reports to monitor
the project's development. Students give a presentation and submit a
written report on the results of the project by the end of the course.
Student Evaluations
Students performance will be evaluated based on their level of participation during the discussions, and the quality of their topic
oral presentation and written report, as well as their project's
proposal, progress reports, oral presentation and final written
report. There may also be sporadic written and/or code/implementation homework assignments (at the discretion of the instructor).
Tentative List of Topics
NOTE: The list of topics, as well as the emphasis on each topic,
will likely vary depending on the background and interests of the course
participants.
Basic Topics
- Constraint Graphical Models
- Framework: constraint satisfaction problems (CSPs)
- Model: constraint network
- Concepts: primal, hidden and dual representations; compact representation and handling special constraints (e.g., binary, context-sensitivity); chordal graphs and triangulation; treewidth; (optimal) elimination orders; computational complexity
- Problems: finding consistent/satisfying assignments
- Methods: backtracking search; constraint propagation; dynamic programming (DP); variable elimination (VE); join/clique trees (JT); cutset conditioning (CC); simulated annealing and stochastic (local) search
- Advanced topics: hypergraph representations; factor graphs; k-SAT; survey propagation (SP)
- Probabilistic Graphical Models
- Framework: probability theory; (Bayesian) statistics
- Models: Markov random fields; Markov networks; Bayesian networks
- Special Models: Ising models; Naive-Bayes; Gaussian networks; hybrid (mixed discrete-continuous) models; mixture models (e.g., mixture of Gaussians); QMR-DT
- Concepts: Gibbs distributions; conditional independence; Hammersley-Clifford Theorem; context-sensitive independence; reasoning under uncertainty; inference formulation of CSPs
- Problems: most-likely assignment and MAP estimation; posterior distributions and belief inference
- Methods:
clique/junction trees; max-/sum-product algorithm; (generalized) belief propagation (BP); mean-field approximation and variational methods; stochastic simulation, likelihood weighting and (adaptive) importance sampling; Markov chain Monte Carlo (MCMC), Metropolis-Hastings and the Gibbs sampler
- Learning from data: complete vs. missing data; learning model parameters; learning model structure; model selection; maximum-likelihood (ML) and Bayesian statistical estimation; expectation-maximization (EM); gradient descent and local search
- Advanced topics: linear programing (LP) relaxations; hierarchical models; Rao-Blackwellization; iterative proportional fitting (IPF); maximum-entropy (MAXENT) models and iterative scaling; L1-regularization and logistic regression
- Decision-theoretic Graphical Models
- Framework: utility theory; decision theory
- Models: influence diagrams (aka decision networks)
- Concepts: decision-making under uncertainty; preferences; maximum-expected-utility principle
- Problems: optimal action selection
- Advanced topics: factored (partially observable) Markov decision processes ((PO)MDPs); policy selection; decentralized (PO)MPDs; multi-agent coordination; (factored) value and policy iteration; basis-function approximations; sparse sampling
Advanced Topics
- Stochastic Graphical Models
- Framework: Stochastic processes
- Models: factored hidden Markov models (fHMMs); temporal/dynamic Bayesian networks (DBNs)
- Problems: Viterbi/most-likely sequence; belief updating; belief-state tracking/estimation; prediction/forecasting
- Methods: Viterbi and forward-backward algorithms; factored belief-state projections; particle filter (PF), aka survival-of-the-fittest
- Learning models from data: Baum-Welch algorithm
- Game-theoretic Graphical Models
- Framework: Noncooperative game theory
- Model: Graphical games
- Problems: computing Nash and correlated equilibria
- Concepts: CSP formulation; graphical potential games and connections to probabilistic inference; decomposable graphical models
- Methods: NashProp; heuristic local search (e.g., hill climbing); linear feasibility systems and LPs
- Advanced topics: mathematical (competitive) economics; stochastic games; multi-agent influence diagrams (MAIDs); graphical economies; market equilibrium; continuation methods; ADProp; Papadimtiriuou's ellipsoid-based algorithm; no-regret learning; regret matching
- Causal, Econometric and Behavioral Graphical Models
- Framework: Cognitive Science and Psychology; Econometrics; Social Network Theory
- Models: Causal networks; simultaneous equation models (SEMs); linear threshold models (LTMs); generalized threshold models (GTMs);
- Problems: causal reasoning and prediction; identifying the most ``influential'' individuals in a social network; learning from behavioral data
- Graphical Models for First-order Logic
- Models: probabilistic relational models (PRMs); relational Markov networks; logical HMMs; dynamic probabilistic relational models (DPRMs); logical Markov decision processes
Motivating applications in computer vision, speech recognition, artificial intelligence (e.g., reasoning and decision-making under uncertainty) and machine learning will be embedded within the presentation of the different topics
Prerequisites
Some prior knowledge of basic probability and statistics is desirable. Some knowledge of basic computational concepts will be assumed (e.g., basic techniques in algorithms, such as
dynamic programming, runtime analysis and familiarity with basic concepts in computational
complexity such as NP-completeness).
Tentative Schedule
Tue Sep 1
Course Administrivia, Introduction/Overview and Motivation
Thu Sep 3
Constraint Networks (cont)
- Basic Concepts
- Intro CSPs
Tue Sep 8
Constraint Networks (cont)
Thu Sep 10
Constraint Networks (cont)
Tue Sep 15
Constraint Networks (cont)
Thu Sep 17
MRFs/Markov Networks
Tue Sep 22
MRFs/Markov Networks (cont)
Thu Sep 24
MRFs/Markov Networks (cont)
Tue Sep 29
NO MEETING: Correction Day
BUT: Project Proposal Draft DUE!
Wed Sep 30
Proposal Meetings with me (during office hours)
Thu Oct 1
Proposal Presentations
Tue Oct 6
MRFs/Markov Networks (cont)
Thu Oct 8
Bayesian Networks
Tue Oct 13
Bayesian Networks (cont)
Thu Oct 15
Learning from data
Tue Oct 20
Learning from data (cont)
Thu Oct 22
Influence Diagrams
Tue Oct 27
Dynamic Bayesian Networks
Project Progress Report I DUE!
Wed Oct 28
Project Progress Report I Meeting with me (during office hours)
Thu Oct 29
Progress Presentations I
Tue Nov 3
Dynamic Bayesian Networks (cont)
Thu Nov 5
Graphical Games
Tue Nov 10
Graphical Games (cont)
Thu Nov 12
Causal Models, Structural Equation Models and Linear Threshold Models
Tue Nov 17
Probabilistic Relational Models
Project Progress Report II and Topic Reports (for Thu Nov 19 Presentations) DUE
Wed Nov 18
Project Progress Presentation II and Topic Presentation (for Thu Nov 19) Meetings with me (during office hours)
Thu Nov 19
Topic Presentations
Tue Nov 24
Project Progress Presentations II
Thu Nov 26
NO MEETING: Thanksgiving Break
Sun Oct 29
Topic Reports (for Tue Dec 1 Presentations) DUE
Mon Oct 30
Topic Presentations (for Tue Dec 1) Meetings with me (time to be determined)
Tue Dec 1
Topic Presentations (cont)
Topic Reports (for Thu Dec 3 Presentations) and Draft of Final Presentations DUE
Wed Dec 2
Final Project Presentations and Topic Presentation (for Thu Dec 3) Meetings with me (during office hours)
Thu Dec 3
Topic Presentations (cont)
Tue Dec 8
Final Project Presentations
Thu Dec 10
Final Project Presentations (cont)
Wed Dec 16
Final Project Report DUE