Seminar: November 2

Pedro Felzenszwalb, University of Chicago

Fast Inference with Min-Sum Matrix Product (or how I finished a homework assignment 15 years later)

Graphical models provide a general framework for modeling dependencies among random variables. The MAP inference problem in a graphical model has a wide range of applications. I will show how important cases can be solved efficiently using a fast algorithm for computing min-sum products of n by n matrices. I will also describe an algorithm for computing the min-sum product in O(n2 log n) expected time, assuming the entries in the matrices are independent samples from a uniform distribution. Finally, I will describe some variants that work well for inputs that arise in several real problems. This leads to significant speedups over previous inference methods in applications within computer vision and natural language processing.