Approximate Inference and Constrained Optimization

Tom Heskes, Kees Albers, Bert KappenUAI 2003

TL;DR

This paper tackles the challenge of efficiently finding approximate solutions to complex inference problems in graphical models. They introduce a novel class of "double-loop" algorithms that break down the difficult non-convex optimization problem into a sequence of simpler, convex sub-problems, leading to significant speedups over existing methods.

What Problem Does This Paper Address?

In machine learning, we often deal with graphical models like Markov Random Fields and Bayesian Networks. To make predictions or understand these models, we need to perform "inference," which typically involves complex calculations over all possible states of the variables. For large models, these calculations become computationally intractable.

Loopy Belief Propagation (LBP) and its generalizations are popular approximate inference algorithms. Their fixed points are related to minimizing a quantity called the "Kikuchi free energy." However, LBP doesn't always converge, and directly minimizing the Kikuchi free energy can be challenging because it's often a non-convex optimization problem. Existing methods like CCCP and UPS, which aim to solve this non-convex problem, tend to be slow. This paper addresses the need for faster and more reliable algorithms for minimizing the Kikuchi free energy.

Methods

The core contribution is a class of "double-loop" algorithms. The general idea is to replace the difficult, non-convex minimization of the Kikuchi free energy with a sequence of simpler, convex minimizations.

Here's how it works:

  • Outer Loop: This loop iteratively refines an approximation by minimizing a sequence of upper bounds on the Kikuchi free energy.
  • Inner Loop: In each outer loop iteration, the algorithm minimizes a convex upper bound. This convex minimization is performed using a message-passing algorithm (Algorithm 1), which is a variation of generalized belief propagation.
  • Bounding: The key to making the inner loop convex and efficient lies in constructing tight convex upper bounds. The paper explores several strategies for creating these bounds, focusing on how to handle the concave entropy terms in the Kikuchi free energy. They introduce different bounding functions (Fconv1, Fconv2, Fconv3) by carefully manipulating overcounting numbers and potentials. The tighter the bound, the faster the outer loop is expected to converge.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and experimental validation using synthetic or standard benchmark problems in graphical models (e.g., Boltzmann grids, fully connected networks, QMR networks).

Key Insights and Ideas

  • Decomposition of Complexity: The most significant insight is that a complex, non-convex optimization problem can be effectively tackled by iteratively solving a sequence of simpler, convex sub-problems. This is a general strategy that has parallels in other areas like the EM algorithm.
  • Tighter Bounds = Faster Convergence: The paper strongly advocates for and demonstrates that using tighter convex bounds in the inner loop leads to faster convergence in terms of outer-loop iterations. This intuition is crucial for the practical performance of the algorithm.
  • Handling Concavity: The challenge of non-convexity arises from concave entropy terms. The paper provides systematic ways to bound these concave terms, turning the overall objective into a convex one for the inner loop.
  • Flexibility in Bounds: The proposed framework allows for different choices of convex bounds, offering a trade-off between the tightness of the bound and the complexity of the inner-loop minimization.

Key Results

The simulations presented in Figure 1 and discussed in Section 5 demonstrate the effectiveness of the proposed double-loop algorithms.

  • Speedup: The "just convex" bound (which is the tightest among the tested bounds) consistently shows the fastest convergence in terms of outer-loop iterations, often by a factor of ten or more compared to other methods.
  • Inner-Loop Trade-offs: While tighter bounds lead to faster outer-loop convergence, they can sometimes require more inner-loop iterations to meet a fixed convergence criterion. However, this increase in inner-loop iterations is generally compensated by the significant reduction in outer-loop steps.
  • Practical Performance: The algorithms are shown to converge to accurate approximations of marginals, even in cases where standard loopy belief propagation might fail to converge.

Limitations and Future Work

  • Convergence Guarantees: While the double-loop algorithm guarantees convergence to a local minimum of the Kikuchi free energy, finding the global minimum remains a challenge for non-convex problems.
  • Condition for Convexity: The paper provides theorems (Theorem 3.1 and 4.2) that give conditions for the Kikuchi free energy or its bounds to be convex. Checking these conditions can involve linear programming, and it would be beneficial to develop more efficient or direct methods for this.
  • Looser Bounds for Efficiency: The paper hints at the possibility of using looser bounds that might be more computationally efficient per inner-loop iteration, even if they require more outer-loop steps. Further exploration of this trade-off could be valuable.
  • Generalizing Conditions: The authors suggest that it would be useful to find conditions, looser than those for Theorem 3.1, that can predict whether Algorithm 1 (the inner-loop solver) will converge, taking into account graph properties and potential sizes.

Summary updated

BibTeX
@inproceedings{heskes2003approximate,
  author = {Tom Heskes and Kees Albers and Bert Kappen},
  title = {{Approximate Inference and Constrained Optimization}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}
Figure