Solving M-Modes Using Heuristic Search

Cong Chen, Changhe Yuan, Chao ChenIJCAI 2016 · OpenReview

TL;DR

This paper introduces a heuristic search approach (A* and Depth-First Branch and Bound) to solve the "M-Modes" problem in graphical models—finding the top $M$ local maxima in a probability landscape. By searching through subgraphs of variables rather than single variables and using a Maximum A Posteriori (MAP) based heuristic, the authors achieve speedups of up to several hundred times over previous dynamic programming methods.

What Problem Does This Paper Address?

In structured prediction (like image labeling or protein folding), we often want more than just the single "best" answer. The traditional "M-Best" approach finds the $M$ most probable configurations, but these are often nearly identical, offering little diversity.

M-Modes is a better alternative: it finds the top $M$ configurations that are "local maxima"—meaning they are more probable than any other configuration within a certain distance (radius $\delta$). However, finding these modes is computationally expensive. The previous state-of-the-art used a Dynamic Programming (DP) approach that pre-calculated every possible local mode for every subgraph. This was highly inefficient because the vast majority of those local modes never actually ended up being part of a global mode.

Methods

The authors propose moving from DP to Heuristic Search (specifically A* and DFBnB). Their approach relies on a "local-global property": a configuration is a global mode if and only if it is a local mode in every connected subgraph of size $\delta$.

Key technical innovations include:

  • Subgraph-based Search Operator: Unlike standard search algorithms that assign one variable at a time, this algorithm searches by "piecing together" consistent local modes of subgraphs.
  • On-the-fly Verification: Instead of pre-calculating all local modes, the algorithm generates and verifies them only when needed during the search process.
  • Admissible Heuristic: To guide the search, they use a MAP-based heuristic. They perform a single "backward" message-passing pass (similar to the max-product algorithm) to create a look-up table that provides an upper bound on the potential of any partial solution.
  • Two Flavors: They implement both A (which expands fewer nodes but uses more memory) and Depth-First Branch and Bound (DFBnB)* (which is more memory-efficient).

Datasets

The researchers evaluated their algorithms on three types of data:

  1. Synthetic Tree Models: Randomly generated trees where they could strictly control dimensions, degrees, and the $\delta$ parameter.
  2. Real-World Datasets: Six datasets from the UCI repository and medical studies, including:
  3. Mushroom, Soybean, and Congress (classification/categorical data).
  4. M.P. and M.S.J. (molecular biology sequences).
  5. ADHD-200 (fMRI brain function data reduced to 264 dimensions).
  6. Loopy Models: Synthetic $k \times k$ grid models to test scalability on non-tree structures.

Key Insights and Ideas

  • The Power of Laziness: The biggest "aha" moment is that by not pre-calculating local modes, the search avoids a massive amount of wasted work. Most local configurations are "dead ends" that can be pruned early.
  • Subgraphs as Units: By treating subgraphs of size $\delta$ as the basic unit of search rather than individual variables, the algorithm directly respects the definition of a mode at every step.
  • Memory vs. Speed Tradeoff: While A* is theoretically optimal in the number of nodes expanded, DFBnB proved much more practical for large models (like the 264-variable ADHD dataset) because its memory footprint is significantly smaller.

Key Results

  • Massive Speedups: On real-world datasets, the heuristic search algorithms were several times to several hundred times faster than the previous DP method. For example, on the ADHD dataset, DFBnB took ~0.2 seconds while DP took over 6.6 seconds.
  • Scalability: The search algorithms successfully handled loopy graphical models with up to 700 variables, a scale that was previously prohibitive for M-Mode calculations.
  • Parameter Sensitivity: The algorithms are robust to the dimension and degree of the graph, whereas the DP method slowed down significantly as these increased.

Limitations and Future Work

  • Conditional Independence: The authors note that their current search strategy doesn't fully exploit the conditional independence structures inherent in graphical models.
  • Search Space Formulation: While efficient, the current ordering of subgraphs is a preprocessing step; the authors suggest that a more concise or "principled" formulation of the search space could lead to even better performance.
  • Loopy Models: While they tested on grids, the comparison with DP was limited to trees because the baseline DP algorithm was only designed for tree-structured models. Future work could involve more rigorous testing on complex, real-world loopy graphs.

Summary updated

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.
BibTeX
@inproceedings{chen2016solving,
  author = {Cong Chen and Changhe Yuan and Chao Chen},
  title = {{Solving M-Modes Using Heuristic Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=SybxrHMubH},
}
Figure