Computing the M Most Probable Modes of a Graphical Model

Chao Chen, Vladimir Kolmogorov, Yan Zhu, Dimitris Metaxas, Christoph Lampert
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:161-169, 2013.

Abstract

We introduce the M-modes problem for graphical models: predicting the M label configurations 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 codebook 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 underlying 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 topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-chen13a, title = {Computing the M Most Probable Modes of a Graphical Model }, author = {Chen, Chao and Kolmogorov, Vladimir and Zhu, Yan and Metaxas, Dimitris and Lampert, Christoph}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {161--169}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/chen13a.pdf}, url = {https://proceedings.mlr.press/v31/chen13a.html}, abstract = {We introduce the M-modes problem for graphical models: predicting the M label configurations 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 codebook 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 underlying 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 topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data.} }
Endnote
%0 Conference Paper %T Computing the M Most Probable Modes of a Graphical Model %A Chao Chen %A Vladimir Kolmogorov %A Yan Zhu %A Dimitris Metaxas %A Christoph Lampert %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-chen13a %I PMLR %P 161--169 %U https://proceedings.mlr.press/v31/chen13a.html %V 31 %X We introduce the M-modes problem for graphical models: predicting the M label configurations 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 codebook 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 underlying 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 topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data.
RIS
TY - CPAPER TI - Computing the M Most Probable Modes of a Graphical Model AU - Chao Chen AU - Vladimir Kolmogorov AU - Yan Zhu AU - Dimitris Metaxas AU - Christoph Lampert BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-chen13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 161 EP - 169 L1 - http://proceedings.mlr.press/v31/chen13a.pdf UR - https://proceedings.mlr.press/v31/chen13a.html AB - We introduce the M-modes problem for graphical models: predicting the M label configurations 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 codebook 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 underlying 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 topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. ER -
APA
Chen, C., Kolmogorov, V., Zhu, Y., Metaxas, D. & Lampert, C.. (2013). Computing the M Most Probable Modes of a Graphical Model . Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:161-169 Available from https://proceedings.mlr.press/v31/chen13a.html.

Related Material