Bethe Learning of Conditional Random Fields via MAP Decoding
This work addresses the efficiency bottleneck in learning probabilistic models for structured prediction, offering a more scalable solution for applications like computer vision and assignment problems.
The paper tackles the intractable partition function problem in maximum likelihood estimation for structured outputs by introducing MLE-Struct, a single-loop algorithm using the Bethe approximation and Frank-Wolfe optimization, which outperforms existing methods in image segmentation, vision matching, and roommate assignment tasks.
Many machine learning tasks can be formulated in terms of predicting structured outputs. In frameworks such as the structured support vector machine (SVM-Struct) and the structured perceptron, discriminative functions are learned by iteratively applying efficient maximum a posteriori (MAP) decoding. However, maximum likelihood estimation (MLE) of probabilistic models over these same structured spaces requires computing partition functions, which is generally intractable. This paper presents a method for learning discrete exponential family models using the Bethe approximation to the MLE. Remarkably, this problem also reduces to iterative (MAP) decoding. This connection emerges by combining the Bethe approximation with a Frank-Wolfe (FW) algorithm on a convex dual objective which circumvents the intractable partition function. The result is a new single loop algorithm MLE-Struct, which is substantially more efficient than previous double-loop methods for approximate maximum likelihood estimation. Our algorithm outperforms existing methods in experiments involving image segmentation, matching problems from vision, and a new dataset of university roommate assignments.