Structured Prediction Energy Networks

David Belanger; Andrew McCallum

Source-linked AI summary

Structured Prediction Energy Networks

David Belanger, Andrew McCallum

arXiv:1511.06350v3Nov 19, 2015cs.LGstat.ML

TL;DR

Structured prediction must handle exponentially many candidate outputs while representing dependencies among structured labels. SPENs learn an input- and output-dependent deep energy and predict by iterative gradient-based optimization. The framework supports expressive, high-order structure with competitive benchmark performance, while exposing trade-offs in optimization guarantees, speed, and overfitting.

Problem
Structured prediction requires representations that capture interactions between x and structured outputs while allowing efficient optimization over exponentially many candidates.
Method
SPENs parameterize a discriminative energy over candidate labels with deep networks and obtain predictions by approximately minimizing it through iterative gradient descent.
Results
SPENs achieve competitive accuracy across benchmark multi-label classification tasks and support structure learning and analysis of prediction trade-offs.
Takeaways & Limitations
SPENs extend deep representation learning to structured outputs, enabling learned high-order interactions with minimal prior structural assumptions.
Takeaways & Limitations
SPEN prediction uses local optimization without algorithmic guarantees, and more expressive energy networks are more vulnerable to overfitting.

Abstract

from arXiv · show

We introduce structured prediction energy networks (SPENs), a flexible framework for structured prediction. A deep architecture is used to define an energy function of candidate labels, and then predictions are produced by using back-propagation to iteratively optimize the energy with respect to the labels. This deep architecture captures dependencies between labels that would lead to intractable graphical models, and performs structure learning by automatically learning discriminative features of the structured output. One natural application of our technique is multi-label classification, which traditionally has required strict prior assumptions about the interactions between labels to ensure tractable learning and prediction. We are able to apply SPENs to multi-label problems with substantially larger label sets than previous applications of structured prediction, while modeling high-order interactions using minimal structural assumptions. Overall, deep learning provides remarkable tools for learning features of the inputs to a prediction problem, and this work extends these techniques to learning features of structured outputs. Our experiments provide impressive performance on a variety of benchmark multi-label classification tasks, demonstrate that our technique can be used to provide interpretable structure learning, and illuminate fundamental trade-offs between feed-forward and iterative structured prediction.

1. Introduction

Structured prediction must represent interactions between inputs and structured outputs while making prediction computationally feasible. SPENs address this by learning output structure with a deep energy function and iterative gradient-based prediction, supporting expressive interactions with linear scaling in label count.

Motivation: Structured outputs create computational and statistical challenges because candidate labels grow exponentially and models must capture interactions among outputs.The representation must support both discriminative interactions between x and y and efficient combinatorial optimization.
Motivation: Prior deep structured-prediction methods typically retain a predefined graphical-model structure, limiting learned interactions between output variables.The paper characterizes this as an excessively strict inductive bias that prevents structure learning over y.
Approach: SPENs define the energy’s dependence on candidate labels with a deep architecture and obtain predictions by approximately minimizing that energy through iterative gradient descent.This allows the architecture to encode dependencies that would be difficult to represent with a fixed graphical model.
Trade-offs: SPENs model high-arity interactions with generic gradient descent, trading broader energy-function expressivity for a lack of algorithmic guarantees from local optimization.The paper contrasts this flexibility with structure-specific optimization methods such as message passing.
Approach: For multi-label classification, SPEN prediction complexity and parameter count scale linearly in the number of labels L while imposing only mild assumptions on label interactions.The approach uses a deep architecture to learn interactions rather than assuming a fixed topology.
Empirical scope: Experiments report competitive or improved performance across benchmark multi-label tasks, while also examining learning alternatives, convergence, and speed–accuracy trade-offs.The benchmark comparisons include competitive baselines and a novel adaptation of the CRF as RNN approach.

2. Structured Prediction Energy Networks

SPENs relax discrete structured prediction into continuous optimization and parameterize the resulting energy with differentiable deep networks. Predictions are obtained by iterative optimization, while the learned energy can represent output dependencies without requiring probabilistic assumptions.

Formulation: Structured prediction can be posed as minimizing an input-dependent energy over candidate outputs, including binary CRFs.Fixed structures such as trees can make this optimization tractable, but SPENs instead consider more general energies.
Formulation: SPENs optimize a general energy over a convex relaxation of the discrete constraint set rather than requiring a tractable graphical-model structure.The relaxed variable is denoted ¯y, and optimization is performed over a continuous domain.
Optimization: Because the relaxed energy may be non-convex, gradient-based optimization obtains a local minimum using projected gradient descent or entropic mirror descent.The paper uses entropic mirror descent because it keeps iterates inside (0, 1)^L.
Output representation: The relaxed prediction ¯y is not guaranteed to be nearly binary, so downstream systems may round it or retain soft predictions depending on the application.Soft predictions may be useful for detection problems.
Modeling choice: Unlike mean-field inference, SPENs make no probabilistic assumptions and directly parameterize a discriminative energy function.The continuous variables are not treated as marginal probabilities under a probabilistic model.
Architecture: A SPEN uses deep networks to map x and ¯y to a scalar energy, with a feature network F(x) feeding an energy network E(F(x), ¯y).The feature representation can be precomputed during iterative prediction, avoiding back-propagation through F when differentiating with respect to ¯y.

3. Example SPEN Architecture

The example SPEN architecture combines local, input-dependent scoring with a global network that learns label dependencies from data. Its expressive power introduces an overfitting trade-off and differs from conventional CRF parameterizations in scalability and representational analysis.

Energy network: The SPEN energy network sums a local term scoring labels with a global term scoring label configurations.The local network uses L linear models, while the global network scores configurations independently of x.
Global structure: Learned affine measurements C1y capture salient label features and support sophisticated nonlinear modeling of label dependencies.Learning C1 from data imposes minimal a-priori assumptions on interaction structure, while parameter growth remains linear in L.
Design trade-offs: More expressive energy networks are more vulnerable to overfitting, especially in settings with limited training data.The experiments found that a data-independent global energy helped prevent overfitting in such tasks.
Design trade-offs: Unlike CRFs, SPEN representational capacity is harder to characterize because it depends on the chosen deep architecture.For CRFs, the relationship between graph structure and representable conditional distributions is well understood.

4. Learning SPENs

SPEN learning combines approximate continuous prediction with gradient-based parameter training. The procedure accounts for non-convexity, relaxation, and boundary behavior when performing loss-augmented inference.

Learning procedure: SPEN prediction is produced by continuous optimization over relaxed outputs, while learning updates the energy network parameters by gradient-based methods.The paper distinguishes output optimization from parameter learning through the network energy E_x(ȳ).
SSVM learning: SSVM training is a reasonable approximate procedure when prediction uses energy evaluation and minimization, despite optimization errors.The approximation ignores errors from non-convexity and relaxation from y to ȳ.
SSVM learning: The SSVM subgradient with respect to model parameters is obtained by back-propagating through the energy network.Parameter optimization uses mini-batch stochastic gradient descent.
Loss-augmented inference: Loss-augmented inference uses gradient descent on the relaxed output rather than combinatorial optimization over discrete labels.Discrete losses such as Hamming loss are replaced by differentiable surrogates, including squared or log loss.
Loss-augmented inference: Mirror descent maintains ȳ in (0, 1)^L, which is crucial when the chosen log loss diverges at the boundary.The same interior-domain strategy is used for approximate prediction over the relaxed output space.
Comparison: SPEN SSVM learning is less straightforward than graphical-model SSVM learning because its inner optimization is approximate and potentially non-convex.Graphical-model relaxations can instead use tractable LP inference procedures such as graph cuts or message passing.

5. Applications of SPENs

SPENs are especially suited to multi-label classification, where labels may be correlated but no interaction structure is known in advance. Their learned measurement matrix provides a data-driven way to represent these dependencies.

Multi-label classification: Multi-label classification predicts a binary label vector y ∈ {0, 1}^L from a feature vector x.The labels may be correlated even when practitioners are given no prior structure among them.
Multi-label classification: SPENs naturally address multi-label classification because learning C1 allows label interactions to be learned from data.This avoids requiring an interaction structure to be specified in advance.
Broader applicability: SPENs can also be applied to prediction problems expressible as MAP inference in an undirected graphical model.Unlike some graphical-model applications, SPENs do not require the practitioner to choose a graph structure or parameter tying scheme in advance.

6. Related Work

Related approaches model structured outputs with independent classifiers, low-dimensional label embeddings, graphical models, or feed-forward predictors. SPENs are positioned as a more flexible alternative that learns output interactions while avoiding fixed graphical-model structure.

Multi-label methods: Independent binary relevance models can perform poorly when labels are rare or highly correlated.Other multi-label methods use max-margin or ranking losses to address label structure directly.
Multi-label methods: Low-dimensional label embeddings reduce prediction cost to linear in L but have limited expressivity for strict constraints such as mutual exclusivity and implicature.A nonlinear MLP can retain low-dimensional structure while also capturing interactions between outputs.
Motivation: Structured prediction models either incur super-linear parameter and computational growth in L or require strict assumptions about label dependencies.These constraints motivate methods that learn interactions with fewer structural assumptions.
Motivation: Compressed-sensing and error-correcting-code approaches often assume sparse labels or prior interaction knowledge, whereas SPENs learn their measurement matrix from data without assuming sparsity.The cited SPEN parameterization is inspired by these approaches but relaxes those assumptions.
Deep structured prediction: Deep-feature CRFs and structured feed-forward predictors retain scalability and expressivity limits imposed by their underlying graphical models.They also require inference algorithms specific to the chosen model structure.
Deep structured prediction: Backpropagation-based prediction has appeared in several deep-learning applications, but this paper applies it concretely to structured objects.The related applications include adversarial examples, document embeddings, and image synthesis.

7. Experiments

Experiments evaluate SPENs on benchmark multi-label classification, alternative SSVM prediction methods, synthetic structure learning, and iterative prediction trade-offs. Results show competitive accuracy and interpretable learned structure, alongside slower prediction and local-optimization limitations.

Multi-Label Classification Benchmarks: SPENs are compared with BR, MLP, LR, and DMF on three standard multi-label datasets using macro-averaged F1.DMF uses five mean-field iterations in a fully connected pairwise CRF, while the SPEN local energy matches the MLP.
Multi-Label Classification Benchmarks: SPENs are competitive with the evaluated baselines, but MLP outperforms SPEN on Delicious because calibrated soft predictions and thresholding matter there.The Delicious SPEN result requires extra entropy terms to produce softer test-time predictions.
Alternative SSVM Approaches: On the 14-label Yeast dataset, SPEN performs similarly to EXACT and LP despite using approximate non-convex inference, whereas LBP performs worse.The comparison uses Hamming error and the same prediction method during SSVM training and testing.
Structure Learning Using SPENs: Synthetic experiments show SPEN measurement matrices recover block structure, with HardTanh yielding more interpretable structure learning than ReLU.The task contains four size-4 mutually exclusive label blocks; ReLU distributes constraint detection across linear combinations, while HardTanh encourages individual measurements.
Structure Learning Using SPENs: SPEN consistently outperforms MLP with 1.5k synthetic examples, while their performance is comparable with 15k examples.The limited-data difference is attributed to SPEN's simpler parameterization and injected constraint structure; the larger MLP benefits from more data.
Convergence Behavior of SPEN Prediction: Early termination achieves a 3-fold speedup at nearly no accuracy decrease, but SPEN prediction remains much slower than feed-forward prediction.On 2,515 Bibtex test items, total classification time is 1.2 seconds for SPEN versus 0.0025 seconds for MLP.
Convergence Behavior of SPEN Prediction: SPEN prediction lacks algorithmic guarantees because it performs only local energy optimization, and search error occurs about 8% of the time on Bibtex.The reported search error counts cases where the optimized energy exceeds the energy evaluated at the ground truth.

8. Conclusion and Future Work

SPENs learn representations of structured outputs jointly with inputs, enabling gradient-based prediction through expressive energy functions. Future work targets convexity in the output variables and training methods that differentiate through prediction.

8. Conclusion and Future Work: SPENs perform representation learning jointly over x and y for structured prediction.Their energy functions support gradient-descent prediction and provide a framework for automatic structure learning.
8. Conclusion and Future Work: The framework is motivated by parsimony and opportunities to inject domain knowledge when training from limited data.
8. Conclusion and Future Work: Future work will study SPENs convex in y but not necessarily in the model parameters.
8. Conclusion and Future Work: Future work will also explore training methods that backpropagate through gradient-based prediction.

A.1. Analysis of Convergence Behavior

The convergence analysis examines how batch termination and convergence tolerance trade prediction accuracy for computational speed. Early stopping can substantially reduce required iterations while preserving aggregate accuracy, whereas looser tolerances explicitly permit accuracy loss.

A.1. Analysis of Convergence Behavior: A histogram of required iterations shows that examples in a batch can converge at different times, causing unnecessary computation while waiting for the slowest examples.
A.1. Analysis of Convergence Behavior: Terminating batch optimization after a target convergence percentage provides impressive speedup with little decrease in accuracy.The analysis varies the percentage of converged examples used as the stopping criterion.
A.1. Analysis of Convergence Behavior: Looser convergence tolerances sacrifice accuracy for speed.

A.3. Deep Mean Field Predictor

The deep mean field predictor expresses label interactions through learned measurements and iterative inference. Its implementation uses vectorized mean-field updates, minibatch GPU computation, optimization enhancements, and staged training.

A.3. Deep Mean Field Predictor: Inference runs in parallel over minibatches on GPUs, with momentum-based optimization applied because the energy is generally non-convex.
A.3. Deep Mean Field Predictor: At test time, entropy can be added to the energy and handled through temperature normalization in entropic mirror descent.
A.3. Deep Mean Field Predictor: Inference speed improves by computing gradients only with respect to the label inputs rather than network parameters.
A.3. Deep Mean Field Predictor: Training proceeds by fitting the local energy, freezing it while fitting the global energy, then jointly updating all parameters with a small learning rate.