The Taub Faculty of Computer Science Events and Talks

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.