10-803: Markov Logic Networks

Machine Learning Department, Carnegie Mellon University


Semester: Fall 2008
Class meets: Thursdays 3:00-4:20 in Wean Hall 5409
Instructor: Pedro Domingos
Office Hours: Thursdays 2:00-3:00
Office: Wean Hall 5317
Course Secretary: Sharon Cavlovich
Mailing List: 10803-students at cs dot cmu dot edu

Course Summary

Modern AI/machine learning applications are characterized by high degrees of complexity and uncertainty. Complexity is well handled by first-order logic, and uncertainty by probabilistic graphical models. What has been sorely missing is a seamless combination of the two. Markov logic networks (MLNs) provide this by attaching weights to logical formulas and treating them as templates for features of Markov random fields. This course covers MLN representation, inference, learning and applications. Inference techniques covered include satisfiability testing, auxiliary-variable MCMC, and lifted belief propagation. Learning includes voted perceptrons, second-order techniques, pseudo-likelihood, inductive logic programming, predicate invention, and transfer learning. Applications include information extraction and integration, natural language processing, robot mapping, social networks, computational biology, and others. The algorithms covered are available in the open-source Alchemy package (alchemy.cs.washington.edu). In the class project, students will apply Alchemy to problems they're interested in, or develop new inference or learning algorithms for MLNs using the Alchemy infrastructure. The class is intended for graduate students (MS or PhD). Previous knowledge of AI/ML (particularly logic and probability) is helpful, but not necessary; the class is designed to be self-contained.

Schedule

Date Topics & Slides Readings Project
Sept. 11 Introduction Chapter 1 -
Sept. 18 Markov networks Section 2.2 -
Sept. 25 First-order logic and inductive logic programming Section 2.1 -
Oct. 2 Markov logic and other SRL approaches Sections 2.3 and 2.4 -
Oct. 9 Markov logic (contd.) Sections 2.3 and 2.4 Proposals due
Oct. 16 Applications of Markov logic Chapter 6, Alchemy tutorial -
Oct. 23 Weight learning Section 4.1 -
Oct. 30 Applications of Markov logic (contd.) Chapter 6, Alchemy tutorial -
Nov. 6 Inference Chapter 3 Progress reports due
Nov. 13 Inference (contd.) Chapter 3 -
Nov. 20 Structure learning Sections 4.2, 4.3 and 4.4 -
Nov. 27 Thanksgiving (no lecture) - -
Dec. 4 Project presentations - Final reports due

Textbook

Pedro Domingos and Daniel Lowd, Markov Logic: An Interface Layer for AI, Morgan & Claypool, 2008.
(This book has not been published yet; it will be distributed to the class.)

Software

The MLN algorithms covered in class are implemented in the Alchemy package.

Project

Class evaluation will be by means of a project. Projects can be done individually or in groups of two (or more, with permission of the instructor). Possible projects include applying MLNs in a domain of interest to you and developing new MLN algorithms.