Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Pixel Club: Diverse M-best Solutions in MRFs
event speaker icon
Greg Shakhnarovich (TTI-Chicago)
event date icon
Tuesday, 31.01.2012, 11:30
event location icon
Room 337-8 Taub Bld.
Much effort has been directed at algorithms for obtaining the highest probability (MAP) configuration in a probabilistic (random field) model. In many situations, one could benefit from additional solutions with high probability. Current methods for computing additional most probable configurations produce solutions that tend to be very similar to the MAP solution and each other. This is often an undesirable property. I will describe an algorithm for the M-Best Mode problem, which involves finding a diverse set of highly probable solutions under a discrete probabilistic model. Given a dissimilarity function measuring difference between two solutions, our algorithm maximizes a linear combination of the probability and dissimilarity to previous solutions. This is a generalization of the M-Best MAP problem and we show that for certain families of dissimilarity functions we can guarantee that these solutions can be found as easily as the MAP solution.

Joint work with Payman Yadollahpour and Dhruv Batra.