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.