What Cannot be Learned with Bethe Approximations

Uri Heinemann, Amir Globerson

Abstract

We address the problem of learning the parameters in graphical models when inference is intractable. A common strategy in this case is to replace the partition function with its Bethe approximation. We show that there exists a regime of empirical marginals where such Bethe learning will fail. By failure we mean that the empirical marginals cannot be recovered from the approximated maximum likelihood parameters (i.e., moment matching is not achieved). We provide several conditions on empirical marginals that yield outer and inner bounds on the set of Bethe learnable marginals. An interesting implication of our results is that there exists a large class of marginals that cannot be obtained as stable fixed points of belief propagation. Taken together our results provide a novel approach to analyzing learning with Bethe approximations and highlight when it can be expected to work or fail.

Introduction

In probabilistic graphical models, researchers often face two major hurdles: inference (calculating probabilities) and learning (estimating parameters from data). For complex models, exact inference is computationally impossible because calculating the partition function is #P-hard. To overcome this, the Bethe approximation is frequently used for both learning and inference.

In an ideal scenario, maximum likelihood learning results in "moment matching"—the learned model’s marginals should exactly match the empirical marginals of the training data. This paper investigates whether the Bethe approximation preserves this property. The authors discover that because the Bethe free energy is non-convex, there is a "regime of failure" where empirical data cannot be recovered, leading to models that fail to represent the data they were trained on.

Methods

The study defines the set of Bethe Learnable marginals ($B_L$). A distribution is "learnable" only if there exists a parameter set $\theta$ where the data's marginals are the unique global maximizer of the negative Bethe free energy.

Visualization of empirical marginals versus Bethe maximizers, highlighting the failure of moment matching.

The analytical approach includes:

  • Canonical Parameters: Proving that if a distribution is learnable, its optimal parameters must be the "canonical" ones derived from the data's marginals.
  • Hessian Analysis: For binary models, analyzing the Hessian of the Bethe entropy. If this Hessian is not negative-semi-definite, the point cannot be a maximum, rendering those marginals "unlearnable."
  • Stability Analysis: Linking learnability to the stability of Belief Propagation (BP) fixed points, showing that unlearnable marginals cannot be obtained as stable outcomes of the BP algorithm.

Key Results and Insights

The authors mapped the "Learnable" vs. "Unlearnable" space for 3x3 toroidal grid graphs using homogenous binary marginals.

Regions of learnability for a 3x3 toroidal grid graph, showing unlearnable (red), learnable (blue), and uncertain (black) regions.

Key findings include:

  • The Non-Convexity Trap: Unlike convex "Tree-Reweighted" (TRW) methods, the Bethe approximation is non-convex. This means the "optimum" might be a mixture of multiple global maxima, none of which match the training data.
  • Ferromagnetic Failure: For certain graphs, standard ferromagnetic distributions are fundamentally unlearnable via Bethe approximations.
  • BP's Hidden Limits: There is a large class of mathematically valid marginals that BP simply cannot reach as a stable solution, regardless of the parameters provided.

Limitations and Future Work

The primary limitation is that the provided bounds are not yet perfectly tight, leaving a "black region" where learnability remains uncertain. Additionally, the focus on pairwise binary models suggests that extending these proofs to multi-state variables or higher-order potentials is a necessary next step. Future work should also investigate whether these "unlearnable" marginals still perform adequately in practical tasks.

Summary updated

Abstract

We address the problem of learning the parameters in graphical models when inference is intractable. A common strategy in this case is to replace the partition function with its Bethe approximation. We show that there exists a regime of empirical marginals where such Bethe learning will fail. By failure we mean that the empirical marginals cannot be recovered from the approximated maximum likelihood parameters (i.e., moment matching is not achieved). We provide several conditions on empirical marginals that yield outer and inner bounds on the set of Bethe learnable marginals. An interesting implication of our results is that there exists a large class of marginals that cannot be obtained as stable fixed points of belief propagation. Taken together our results provide a novel approach to analyzing learning with Bethe approximations and highlight when it can be expected to work or fail.
BibTeX
@inproceedings{heinemann2011what,
  author = {Uri Heinemann and Amir Globerson},
  title = {{What Cannot be Learned with Bethe Approximations}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=Q9kBe4xOVz},
}
Figure