Anytime marginal maximum a posteriori inference

Denis Deratani Mauá, Cassio P. de CamposICML 2012

TL;DR

This paper introduces a novel "anytime" algorithm for marginal MAP inference in graphical models with bounded treewidth. The algorithm offers a trade-off between computation time and solution quality, providing increasingly accurate solutions as more resources are allocated. Experiments show it's competitive with existing state-of-the-art methods, especially on problems with moderate treewidth but large search spaces.

What Problem Does This Paper Address?

The Maximum a Posteriori (MAP) assignment problem is a fundamental task in probabilistic graphical models, aiming to find the most likely configuration of variables. A more challenging variant, the marginal MAP problem, involves finding the most likely assignment for a subset of variables while marginalizing (summing out) others. This problem is computationally hard, even for models with bounded treewidth. Existing exact methods can be prohibitively slow, and approximate methods often lack guarantees on solution quality. This paper tackles the need for an algorithm that can provide anytime solutions – meaning it can be interrupted at any point to yield a feasible, albeit potentially suboptimal, solution, with the quality improving as computation time increases.

Methods

The core of the paper is a new anytime algorithm called ANYTIME-INFERENCE, built upon a technique called FACTOR-SET-ELIMINATION. This method operates on clique trees, a standard data structure for efficient inference in graphical models.

Here's a breakdown of the key ideas:

  • FACTOR-SET-ELIMINATION: Instead of propagating single factors (as in standard algorithms like FACTOR-ELIMINATION), this algorithm propagates sets of factors. This allows it to explore multiple potential assignments simultaneously.
  • Pruning: To manage the complexity of propagating sets, the algorithm employs sophisticated pruning techniques. This includes:
  • Convex Combination Removal: Discarding factors that are convex combinations of others, as they are guaranteed to be outperformed by their constituents.
  • Pareto Dominance Removal: Eliminating factors that are "weakly dominated" by others (i.e., never better and sometimes worse).
  • Clustering and Representative Selection: Grouping remaining factors and selecting a representative for each cluster. This is crucial for controlling the size of the propagated sets.
  • Anytime Nature: The algorithm is made "anytime" by iteratively increasing the size of these factor sets (controlled by parameters $k_i$) at nodes of the clique tree. This iterative refinement allows the algorithm to continuously improve its lower and upper bounds on the optimal MAP assignment. The algorithm is guaranteed to converge to the optimal solution given enough time.

Datasets

The paper evaluates its algorithm on three groups of graphical models:

  1. Benchmark Bayesian Networks: Standard networks used in real-world applications, often involving inference on root nodes given evidence on leaf nodes.
  2. Multiple Knapsack Problems: Structured models with a chain of latent variables and root decision nodes, designed to test performance on large search spaces with low treewidth.
  3. Grid-Structured Graphical Models: Models with varying dimensions (rows, columns, planes) and variable types (binary, quaternary). These are used to assess the impact of treewidth and search space size.

No new datasets were introduced; existing benchmarks were used.

Key Insights and Ideas

  • Propagating Sets for Anytime MAP: The fundamental insight is that by propagating sets of factors instead of single ones, one can naturally explore multiple assignment possibilities and build anytime capabilities. This is a departure from traditional exact or approximate inference methods.
  • Sophisticated Pruning is Key: The efficiency of the set propagation hinges on clever pruning strategies. Identifying and removing non-extreme and dominated factors, and then strategically selecting representatives from clusters, are critical for managing computational complexity.
  • Trade-off Between Treewidth and Search Space: The experiments highlight that the algorithm performs particularly well on problems with moderate treewidth but a very large number of possible assignments. This is where exact methods struggle due to combinatorial explosion, and anytime methods can shine by providing good approximations.
  • Error Bounds and Convergence: The theoretical analysis provides bounds on the error produced by the algorithm for a given computational budget, demonstrating that this error can be made arbitrarily small. This theoretical backing is crucial for understanding the algorithm's guarantees.

Key Results

  • Competitive Performance: The proposed anytime algorithm (AFSE) is shown to be competitive with a state-of-the-art systematic search algorithm (SI) from Park & Darwiche (2003).
  • Speed Advantage on Certain Problems: AFSE significantly outperforms SI on problems with moderate treewidth but large search spaces (e.g., grid models with two planes). In some cases, SI exhausted available memory or time without finding a solution, while AFSE provided a feasible solution.
  • Degradation with High Treewidth: As treewidth increases, the bounds returned by AFSE become looser, indicating a limitation.
  • Time-Accuracy Trade-off Demonstrated: Figure 3 visually demonstrates how AFSE's lower and upper bounds converge to the optimal solution over time, showcasing its anytime nature. SI, while starting with a better lower bound, often gets stuck.

Limitations and Future Work

  • Performance Degradation with High Treewidth: The paper acknowledges that as treewidth increases, the algorithm's bounds become less tight. The authors suggest that decomposing propagated factors into smaller domains, as explored by Meek & Wexler (2011), could mitigate this.
  • Parameter Sensitivity: The impact of numerical parameters on complexity remains an open question.
  • Fully Polynomial-Time Approximation Scheme (FPTAS) Potential: The authors suggest that, similar to de Campos (2011), their anytime algorithm could potentially be shown to be a fully polynomial-time approximation scheme if both treewidth and the number of variable states are bounded. This would provide stronger theoretical guarantees for certain classes of problems.

Summary updated

Abstract

This paper presents a new anytime algorithm for the marginal MAP problem in graphical models of bounded treewidth. We show asymptotic convergence and theoretical error bounds for any fixed step. Experiments show that it compares well to a state-of-the-art systematic search algorithm.
BibTeX
@inproceedings{maua2012anytime,
  author = {Denis Deratani Mauá and Cassio P. de Campos},
  title = {{Anytime marginal maximum a posteriori inference}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
}
Figure