Solving M-Modes Using Heuristic Search

Cong Chen, Changhe Yuan, Chao Chen

Abstract

M-Modes for graphical models is the problem of finding top M label configurations of highest probability in their local neighborhoods. The state-of-the-art method for solving M-Modes is a dynamic programming algorithm which computes global modes by first computing local modes of each subgraph and then search through all their consistent combinations. A drawback of the algorithm is that most of its time is wasted on computing local modes that are never used in global modes. This paper introduces new algorithms that directly search the space of consistent local modes in finding the global modes, which is enabled by a novel search operator designed to search a subgraph of variables at each time. As a result, the search algorithms only need to generate and verify a small number of local modes and can hence lead to significant improvement in efficiency and scalability.

PDF

Bibtex

@INPROCEEDINGS{Chen16solving,
author = {Cong Chen and Changhe Yuan and Chao Chen},
title = {Solving M-Modes Using Heuristic Search},
booktitle = {Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI-16)},
address = {New York, NY},
year = {2016}
}