Greg Shakhnarovich (TTI-Chicago)
Tuesday, 31.1.2012, 11:30
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.