Solving M-Modes in Loopy Graphs Using Tree Decompositions

Cong Chen, Changhe Yuan, Ze Ye, Chao Chen
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:145-156, 2018.

Abstract

M-Modes is the problem of finding the top M labelings of a graphical model that are locally optimal. The state-of-the-art M-Modes algorithm is a heuristic search method that finds global modes by incrementally concatenating MAP solutions in local neighborhoods. The search method also relies on the guidance of a heuristic function to explore the most promising parts of the search space. However, due to the difficulty of coordinating mode search, heuristic function calculation and local MAP computation in general loopy graphs, the method was only implemented and tested on special graphical models such as trees or submodular grid graphs. This paper provides a more general implementation of the search method based on tree decompositions that is applicable to general loopy graphs. A tree decomposition allows a sequence of local subgraphs to be mapped to a set of sub-trees sweeping through the tree decomposition, thus enabling a smooth and efficient transition back and forth between mode search, heuristic functio

Cite this Paper

BibTeX
@InProceedings{pmlr-v72-chen18a, title = {Solving M-Modes in Loopy Graphs Using Tree Decompositions}, author = {Chen, Cong and Yuan, Changhe and Ye, Ze and Chen, Chao}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {145--156}, year = {2018}, editor = {Kratochvíl, Václav and Studený, Milan}, volume = {72}, series = {Proceedings of Machine Learning Research}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/chen18a/chen18a.pdf}, url = {https://proceedings.mlr.press/v72/chen18a.html}, abstract = {M-Modes is the problem of finding the top M labelings of a graphical model that are locally optimal. The state-of-the-art M-Modes algorithm is a heuristic search method that finds global modes by incrementally concatenating MAP solutions in local neighborhoods. The search method also relies on the guidance of a heuristic function to explore the most promising parts of the search space. However, due to the difficulty of coordinating mode search, heuristic function calculation and local MAP computation in general loopy graphs, the method was only implemented and tested on special graphical models such as trees or submodular grid graphs. This paper provides a more general implementation of the search method based on tree decompositions that is applicable to general loopy graphs. A tree decomposition allows a sequence of local subgraphs to be mapped to a set of sub-trees sweeping through the tree decomposition, thus enabling a smooth and efficient transition back and forth between mode search, heuristic functio} }
Endnote
%0 Conference Paper %T Solving M-Modes in Loopy Graphs Using Tree Decompositions %A Cong Chen %A Changhe Yuan %A Ze Ye %A Chao Chen %B Proceedings of the Ninth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2018 %E Václav Kratochvíl %E Milan Studený %F pmlr-v72-chen18a %I PMLR %P 145--156 %U https://proceedings.mlr.press/v72/chen18a.html %V 72 %X M-Modes is the problem of finding the top M labelings of a graphical model that are locally optimal. The state-of-the-art M-Modes algorithm is a heuristic search method that finds global modes by incrementally concatenating MAP solutions in local neighborhoods. The search method also relies on the guidance of a heuristic function to explore the most promising parts of the search space. However, due to the difficulty of coordinating mode search, heuristic function calculation and local MAP computation in general loopy graphs, the method was only implemented and tested on special graphical models such as trees or submodular grid graphs. This paper provides a more general implementation of the search method based on tree decompositions that is applicable to general loopy graphs. A tree decomposition allows a sequence of local subgraphs to be mapped to a set of sub-trees sweeping through the tree decomposition, thus enabling a smooth and efficient transition back and forth between mode search, heuristic functio
APA
Chen, C., Yuan, C., Ye, Z. & Chen, C.. (2018). Solving M-Modes in Loopy Graphs Using Tree Decompositions. Proceedings of the Ninth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 72:145-156 Available from https://proceedings.mlr.press/v72/chen18a.html.

Related Material