Bethe Projections for Non-Local Inference

Luke Vilnis, David Belanger, Daniel Sheldon, Andrew McCallum

Abstract

This paper introduces a method to incorporate complex, global constraints into structured prediction models without sacrificing tractability. By augmenting standard inference with a learned "non-local energy function" and solving it via non-Euclidean projected gradient descent using the Bethe entropy, the authors achieve state-of-the-art results in OCR and massive speedups in collective graphical models.

Introduction

Traditional graphical models, such as Conditional Random Fields (CRFs), are highly effective at capturing local dependencies (e.g., the likelihood of a character sequence in a word). However, they struggle with "non-local" or global regularities, such as ensuring a predicted word exists in a dictionary or that a sentence contains a verb. Directly modeling these global properties typically requires increasing the model's clique size, leading to an exponential explosion in computational complexity—a challenge known as the treewidth problem. Existing workarounds like dual decomposition are often restricted to simple linear constraints. This work seeks to learn and enforce arbitrary, non-linear global properties while keeping inference fast and scalable.

Methods: Bethe-RDA

The authors propose augmenting the standard marginal inference objective with a non-linear, parametric function $L_\psi(\mu)$, termed a non-local energy function. The core technical contribution is Algorithm 1: Bethe-RDA (Regularized Dual Averaging).

Instead of using standard Euclidean projections, which are computationally difficult over the complex marginal polytope of a graphical model, the authors employ a non-Euclidean projection using the Bethe entropy as a distance-generating function. This reframes the difficult task of inference with global constraints as a sequence of "easy" local inferences.

Key technical highlights include:

  • Anytime Performance: Unlike many message-passing schemes, this procedure maintains primal feasibility at every iteration, allowing for early stopping with valid marginals.
  • Learning: A "doubly-stochastic" learning algorithm is provided to discriminatively learn both base model parameters and global energy parameters simultaneously.
  • Handling Non-Convexity: The method remains effective even when the global energy function is non-convex, such as when pulling predictions toward discrete dictionary words.
Test accuracy as a function of inference iterations, demonstrating the anytime property of the Bethe-RDA algorithm.

Experiments and Datasets

The method was evaluated on three distinct tasks:

  1. UMass Citation Dataset: Segmenting research paper citations into fields like author and title.
  2. Handwriting Recognition (OCR): Testing non-convex energies that encourage sequences to match real vocabulary words.
  3. Bird Migration (Collective Graphical Models): Inferring migration patterns from noisy, aggregate counts using synthetic data.

Results and Discussion

The Bethe-RDA approach demonstrated significant improvements in both accuracy and efficiency across all tasks. In the Citation Extraction task, the method achieved an F1 score of 95.47, outperforming specialized dual decomposition baselines.

For the OCR task, the learned non-convex energy function achieved 98.83% accuracy, significantly outperforming the base model and even surpassing "Structured Prediction Cascades" that utilize computationally expensive 6-gram features.

OCR accuracy comparison showing the performance of learned non-local energy functions against the base model.

In the bird migration experiments, the method provided a massive leap in efficiency. For the largest problem size ($s=50k$), the proposed method took only 14 seconds compared to 690 seconds for a standard Interior Point (IP) solver—a ~50x speedup with no loss in accuracy.

Conclusion

By using Bethe projections, the authors provide a scalable framework for incorporating global constraints into structured prediction. While formal convergence is guaranteed for convex energies, the practical success with non-convex functions in OCR suggests broad applicability. Future work may explore broader classes of penalty functions in domains where global regularities are currently ignored due to computational complexity.

Summary updated

Abstract

Many inference problems in structured prediction are naturally solved by augmenting a tractable dependency structure with complex, non-local auxiliary objectives. This includes the mean field family of variational inference algorithms, soft- or hard-constrained inference using Lagrangian relaxation or linear programming, collective graphical models, and forms of semi-supervised learning such as posterior regularization. We present a method to discriminatively learn broad families of inference objectives, capturing powerful non-local statistics of the latent variables, while maintaining tractable and provably fast inference using non-Euclidean projected gradient descent with a distance-generating function given by the Bethe entropy. We demonstrate the performance and flexibility of our method by (1) extracting structured citations from research papers by learning soft global constraints, (2) achieving state-of-the-art results on a widely-used handwriting recognition task using a novel learned non-convex inference procedure, and (3) providing a fast and highly scalable algorithm for the challenging problem of inference in a collective graphical model applied to bird migration.
BibTeX
@inproceedings{vilnis2015bethe,
  author = {Luke Vilnis and David Belanger and Daniel Sheldon and Andrew McCallum},
  title = {{Bethe Projections for Non-Local Inference}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=rg-NcVet8bc},
}

Loading related content...

Figure