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.
Introduction
Undirected graphical models, such as Conditional Random Fields (CRFs), are powerful tools for modeling local dependencies in structured data. However, they struggle to incorporate global constraints—for instance, ensuring a citation contains exactly one "year" field. Traditionally, adding such long-range dependencies requires increasing the clique size of the graph, which often leads to NP-hard inference.
This paper introduces a fast, general method for performing inference in graphical models with complex, global dependencies. By augmenting the standard marginal inference objective with arbitrary penalty functions and optimizing it via non-Euclidean projected gradient descent (using Bethe entropy), the authors achieve state-of-the-art results on structured prediction tasks without sacrificing computational tractability.
Methodology
Instead of modifying the graph structure to handle global rules, the authors modify the optimization objective of the inference process itself through several key innovations:
- Non-Local Energies: Marginal inference is posed as an optimization problem over the marginal polytope, augmented with a parametric "non-local energy function" $L_\psi(\mu)$. This function penalizes or rewards specific global configurations based on the marginal probabilities.
- Bethe-RDA: To optimize this complex objective, the authors utilize a proximal gradient method called Regularized Dual Averaging (RDA).
- The Bethe Projection: A critical challenge in proximal gradient descent is the projection step, which usually requires calculating Euclidean distances. The authors use the Bethe entropy as a distance-generating function (Bregman divergence). Because Bethe entropy is strongly convex for trees, this transforms the difficult projection step into a standard marginal inference call (like belief propagation) on the base model with updated parameters.
- Learning: The parameters of the base CRF and the new global energy function are jointly learned using a doubly-stochastic variational EM algorithm.
Experimental Evaluation
Citation Extraction
On the UMass Citation dataset, the method achieved a 95.47 F1 score, outperforming specialized soft dual-decomposition baselines. A key advantage of the Bethe-RDA algorithm is its "anytime" property; it maintains primal feasibility across iterations, allowing for early stopping.
As shown above, most accuracy gains are realized in just 5 to 10 inference iterations, highlighting the efficiency of the projection-based approach.
Handwriting Recognition (OCR)
The authors designed a non-convex energy function to "nudge" character predictions toward known dictionary words. This approach achieved a state-of-the-art 98.83% character-level accuracy, outperforming computationally intensive 6-gram models.
Collective Graphical Models
In bird migration modeling, the generic Bethe-RDA algorithm provided massive computational speedups. On a problem with 50,000 edges, the method converged in 14 seconds, compared to 690 seconds for a standard interior-point solver, with no loss in accuracy.
Conclusion
By treating inference as a projection problem over the marginal polytope using Bethe entropy, this framework allows for the inclusion of complex, even non-convex, global constraints. While theoretical guarantees for non-convex energies remain an area for future rigorous proof, the empirical results demonstrate that the algorithm effectively navigates these landscapes to provide high-accuracy, scalable inference for structured prediction.
Summary updated