Computing the M Most Probable Modes of a Graphical Model
Chao Chen, Vladimir Kolmogorov, Yan S. Zhu, Dimitris N. Metaxas, Christoph H. Lampert · 2013
We introduce the M-Modes problem for graphical models: predicting the M label con-figurations of highest probability that are at the same time local maxima of the probability landscape. M-Modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as code-book vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-Modes problem. The first algorithm solves the problem in polynomial time when the un-derlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-Modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topog-raphy of the probability distribution of con-figurations, for example with relation to the training set size and amount of noise in the data. 1