Comp 150SRL - Statistical Relational Learning
Department of Computer Science
Tufts University
Spring 2009

Course Web Page (this page): http://www.cs.tufts.edu/comp/150SRL/

Announcement(s):
  • Updated links and presentations in table below.

Syllabus:

This course will explore an emerging area of research in Artificial Intelligence (AI) - Statistical Relational Learning. A basic realization is that building large scale AI systems requires abilities to represent, reason and learn in domains with both complex relational structure and rich probabilistic structure. Techniques for achieving that build on work from probability theory and graphical models, as well as logic and databases, to develop new representations and sophisticated algorithms to work with them. We will be reading a recent collection of articles written as a introduction to the field, as well as more recent work from conferences.

Prerequisites:

comp160: Algorithms, and comp135 or comp150ML: Machine Learning, or comp131 Artificial Intelligence or similar experience.

Instructor:

Roni Khardon

Textbooks

Course Work and Marking

The course will be run partly as a lecture course and partly a a reading seminar. Students will present and/or lead the discussion on some of the articles/chapters read. The course grade will be based on homework assignments (20%), paper presentations and class discussion (30%), and a final project (50%). The final project can investigate some new (or old) application of SRL, investigate some new (or old) methods, etc. I encourage initiative to create individually-tailored projects, and I am happy to consider group projects.

Rough Course Outline

After a crash course in Bayes Networks and Logic/ILP we will review various SRL models, tasks, and techniques for solving them.

Topic Reading/Assignments Due Date
Bayes Nets and CRFs (Lectures L1-L7) [GT] Chapters 2, 4; [RN] Chapter 14; [RN 1st edition] Chapter 15
Slides: Introduction to Bayes Networks
Slides: Inference part I (slides from [RN])
Slides: Inference part II
Slides: Markov Random Fields
Slides: Learning
Paper: Loopy belief-propagation for approximate inference: An empirical study. K. Murphy, Y. Weiss, and M. I. Jordan. in UAI 1999.
 
Additional Sources Belief propagation: Pearl's algorithm for multiplexer nodes, Kevin Murphy, 1999.
Belief Propagation: Alan Fern's class notes
Inference for undirected graphs (plus more): Graphical models M. I. Jordan, Statistical Science, 19, 140-155, 2004.
Overview of many topics: Appendix of Kevin Murphy's Thesis
 
Review Questions Review Questions  
Assignment 1 Assignment 1
Input files (netwroks and queries)
February 3
(First Order) Logic, Logic Programming and ILP (Lectures L8-L11) [RN] Chapters 7, 8; [GT] Chapter 3  
Assignment 2 Assignment 2 March 10
Relational BNs L12: PRM: [GT] Chapter 5. Presentation Slides (local access)
L13: RMN: [GT] Chapter 6 Presentation Slides (local access)
L14: RBN: Complex Probabilistic Modeling with Recursive Relational Bayesian Networks Manfred Jaeger, Annals of Mathematics and Artificial Intelligence 32 (2001), pp. 179 - 220. Presentation Slides (local access)
L15: RDN: [GT] Chapter 8 Presentation Slides (local access)
 
Logic plus Probabilities L16: BLP: [GT] Chapter 9
L17: MLN: [GT] Chapter 12 Presentation Slides (local access)
L18: BLOG: [GT] Chapter 13
 
L19: Recap and Comparison of Models Using examples from: Comparative Study of Probabilistic Logic Languages and Systems  
Relational MDPs L20: API: [GT] Chapter 18. Presentation Slides MDPs , API , (local access)
L21: First Order Decision Diagrams for Relational MDPs C. Wang, S. Joshi and R. Khardon, Journal of AI Research , Vol 31, pp431-472, 2008
Stochastic Planning with First Order Decision Diagrams, S. Joshi and R. Khardon, Proceedings of the International Conference on Automated Planning and Scheduling, 2008
 
FO Probabilitic Inference L22: FOPI: [GT] Chapter 15. Presentation Slides (local access)
Lifted Probabilistic Inference with Counting Formulas B. Milch, L. Zettlemoyer, K. Kersting, M. Haimes, L. Pack Kaelbling. Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-2008)
Lifted First-Order Belief Propagation Pedro domingos and Parag Singla. Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (pp. 1094-1099), 2008.
Exploiting Shared Correlations in Probabilistic Databases Prithviraj Sen, Amol Deshpande, Lise Getoor International Conference on Very Large Data Bases - 2008.
 
Techniques and Applications for NLP L23: [GT] Chapter 19
L24: [GT] Chapter 20. Presentation Slides (local access)
 
Project Presentations (L25-L26) Project Presentations