CSE 592 Advanced Topics in Computer Science -- Graphical Models

Fall 2009



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

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

Advanced Topics

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


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)

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