Abstract
Often when modeling structured domains, it is desirable to leverage information that is not naturally expressed as simply a label. Examples include knowledge about the evaluation measure that will be used at test time, and partial (weak) label information. When the additional information has structure that factorizes according to small subsets of variables (i.e., is low order, or decomposable), several approaches can be used to incorporate it into a learning procedure. Our focus in this work is the more challenging case, where the additional information does not factorize according to low order graphical model structure; we call this the high order case. We propose to formalize various forms of this additional information as high order loss functions, which may have complex interactions over large subsets of variables. We then address the computational challenges inherent in learning according to such loss functions, particularly focusing on the loss-augmented inference problem that arises in large margin learning; we show that learning with high order loss functions is often practical, giving strong empirical results, with one popular and several novel high-order loss functions, in several settings.
Introduction
In traditional machine learning, models are typically trained to minimize a loss function that decomposes over individual data points. However, in structured output tasks—such as image segmentation where every pixel must be labeled—the true measure of success is often a global metric. For instance, the PASCAL VOC challenge utilizes the "Intersection over Union" (IoU) score. This metric is fundamentally high-order and non-decomposable; the score for a single pixel cannot be determined without knowing the labels of all other pixels.
Historically, researchers have relied on low-order surrogates like pixel-wise error because they are computationally tractable. This paper addresses the gap by introducing a framework to perform efficient "loss-augmented inference" even when the loss function is globally coupled and complex.
Methodology: High-Order Loss as a Factor
The authors operate within the Structural SVM framework, which requires solving a loss-augmented MAP inference problem during training: finding a labeling that maximizes the sum of the model's current score and the loss. The core innovation is treating these complex high-order losses as specialized factors within a message-passing framework.
By leveraging advances in higher-order potentials, the authors derive efficient updates for three specific types of information:
- PASCAL Loss: The IoU metric is shown to be quasi-concave, allowing for optimization via fast local search or bisection methods.
- Bounding Box % Fullness: This loss uses cardinality potentials to encourage the model to label a specific percentage of pixels as foreground within a given bounding box, rather than assuming the entire box is ground truth.
- Local Border Convexity (LBC): This loss incorporates geometric intuition by penalizing labels that are not "locally convex" along rays extending from an object's center.
These specialized algorithms reduce the complexity of handling millions of variables to near-linear time ($O(N \log N)$ or $O(N)$), making high-order learning practical for high-resolution images.
Experimental Results
The approach was evaluated on synthetic deformable shape data and the PASCAL VOC Segmentation Challenge (focusing on Aeroplanes, Cars, Cows, and Dogs).
Key Insights: "Train How You Test"
A primary finding is that optimizing for a surrogate (like pixel accuracy) often results in overly conservative models. A model trained on pixel loss might under-segment an object to minimize false positives. In contrast, a model trained directly on the PASCAL loss learns to be bolder, as the IoU metric rewards covering the entire object even at the risk of small boundary errors.
On the "Cow" dataset, the model trained with PASCAL loss achieved a 58.4% PASCAL score, significantly outperforming the 54.1% achieved by the standard pixel-loss model. Furthermore, the scalability of the approach was demonstrated by processing PASCAL loss factors over 10 million variables in approximately 35 seconds per iteration.
Conclusion and Future Work
While the proposed method demonstrates that high-order losses are computationally feasible and empirically superior, some limitations remain. When high-order losses are combined with standard pairwise model terms (e.g., smoothness constraints), inference is no longer guaranteed to be exact and relies on approximate message passing. Additionally, each new high-order loss currently requires a custom derivation for efficient updates. Future research may extend these principles to video data to enforce temporal consistency across frames.
Summary updated