Source-linked AI summary
Learning Deep Structured Models
Liang-Chieh Chen, Alexander G. Schwing, Alan L. Yuille, Raquel Urtasun
TL;DR
Predicting statistically related variables requires models that capture output dependencies while learning complex representations. The paper jointly learns deep features and MRF parameters with an efficient blended learning-and-inference algorithm. Across word recognition and Flickr image classification, joint learning outperforms alternative training strategies, though approximate inference remains necessary for general graphical models.
Problem
Scalable deep learning methods for dependent outputs remain an open problem because common two-step training learns deep features before structured prediction and ignores output dependencies.
Method
The paper jointly learns arbitrary-graph structured models and deep features that form MRF potentials by blending parameter updates with inference in a GPU-accelerated single loop.
Results
Joint training outperforms other strategies on word recognition and Flickr image classification; on Flickr, PreTrainJoint achieves 7.25% mean error versus 7.70% for PwTrain and 9.36% for Unary only.
Takeaways & Limitations
Jointly learning deep features and MRF parameters yields better performance than alternative training strategies across the evaluated tasks.
Takeaways & Limitations
For general graphical models, exact inference and exact gradients are intractable, requiring approximate solutions; iterative message passing can otherwise create a slow double loop.
Abstract
from arXiv · showhide
Many problems in real-world applications involve predicting several random variables which are statistically related. Markov random fields (MRFs) are a great mathematical tool to encode such relationships. The goal of this paper is to combine MRFs with deep learning algorithms to estimate complex representations while taking into account the dependencies between the output random variables. Towards this goal, we propose a training algorithm that is able to learn structured models jointly with deep features that form the MRF potentials. Our approach is efficient as it blends learning and inference and makes use of GPU acceleration. We demonstrate the effectiveness of our algorithm in the tasks of predicting words from noisy images, as well as multi-class classification of Flickr photographs. We show that joint learning of the deep features and the MRF parameters results in significant performance gains.
1 INTRODUCTION
Deep neural networks can gain predictive power from graphical models that capture dependencies among output variables. The paper addresses scalable joint learning of deep features and structured models, demonstrating gains on word recognition and Flickr image classification.
- Motivation: Graphical models enhance deep networks by encoding statistical dependencies among variables of interest.Examples include label relationships in large-scale classification and spatial relationships between joints in pose estimation.
- Problem: Existing approaches commonly train deep-feature classifiers first and then use their outputs to construct structured-prediction potentials.This two-step, piece-wise procedure learns features while ignoring dependencies between output variables.
- Motivation: Jointly learning related features can exploit complementary information and correct additional prediction mistakes.Independently learned segmentation and detection features may focus on the same examples, whereas joint learning can improve predictive power.
- Contribution: The paper proposes an efficient algorithm that jointly learns arbitrary-graph structured models and deep features forming MRF potentials.Learning and inference are blended into a single-loop procedure using GPU acceleration.
- Evaluation: The method is evaluated on predicting words from noisy images and multi-class classification of Flickr photographs.The paper reports significant performance gains from jointly learning deep features and MRF parameters.
2 LEARNING DEEP STRUCTURED MODELS
The paper formulates deep structured prediction as scoring discrete output configurations with a general nonlinear function and a temperature-controlled soft-max distribution. Learning maximizes data likelihood, but exact inference and gradients are generally intractable, motivating approximate procedures.
- Model formulation: The model predicts a discrete configuration y by maximizing a scalar score F(x, y; w) over the product space of valid variable assignments.Each output variable has a discrete domain, and inference selects the highest-scoring configuration.
- Model formulation: Deep networks and log-linear models are included as special cases of the general scoring-function framework.Deep implementations compose nonlinear mappings, while log-linear models use F(x, y; w) = w⊤φ(x, y).
- Probabilistic model: The annealed soft-max distribution assigns configuration probabilities from exponentiated scores normalized by a partition function.The temperature parameter ϵ controls distribution uniformity, while general graphical-model partition-function computation is #P-hard.
- Learning objective: Training maximizes data likelihood, equivalently matching a ground-truth target distribution with the model distribution through cross-entropy.Setting ϵ = 0 recovers the structured hinge-loss objective.
- Computational challenge: Exact gradients are generally unavailable because computing the model distribution requires intractable inference, so approximate solutions are necessary.For general graphical models, inference is NP-hard and exact probability computation cannot be performed.
- Optimization: The learning procedure repeats parameter updates until a stopping criterion is reached.The supplied algorithm excerpt specifies iterative termination without detailing the stopping rule.
4. Update parameters w
The paper replaces exact, generally intractable structured learning with an approximate procedure that uses local beliefs and dual optimization. Its efficient algorithm interleaves parameter updates with inference, enabling GPU-accelerated learning without running inference to convergence.
- Approximate learning: The scoring function decomposes into local functions over subsets of output variables, allowing structured potentials to be represented through local regions.F(x, y; w) is expressed as a sum of functions f_r(x, y_r; w), where each region r selects a subset of variables.
- Approximate learning: Exact entropy and marginalization computations remain challenging for general graphical models, especially beyond low-tree-width structures.The learning task is computationally difficult because exact entropy is available only for a small set of models and marginalization constraints can be exponential in size.
- Approximate learning: The approximation replaces true marginals with locally consistent beliefs and entropy with a fractional-entropy expression weighted by counting numbers.These beliefs need not arise from one globally consistent joint distribution, reducing the original inference problem to a tractable local approximation.
- Efficient approximate learning: Duality converts the approximate min-max objective into a single minimization, making it possible to update model weights and inference messages by block coordinate descent.The resulting procedure avoids waiting for inference to converge; under ϵc_r ≥ 0 for all regions, even a single message update can suffice.
- Efficient approximate learning: The efficient algorithm alternates a forward pass over local functions, closed-form message updates, and a backward pass for the parameter gradient.The implementation supports GPU-accelerated forward and backward passes, mini-batches, momentum, and regularization.
- Experimental evaluation: Table 1 reports word and character accuracy, with performance improving under joint training, richer structure, and deeper unary classifiers.The caption identifies H1 and H2 as the hidden-unit counts in the first and second layers, respectively.
3 EXPERIMENTAL EVALUATION
Experiments on Word50 and Flickr compare unary-only, piecewise, and joint training across structured deep models. Joint training, richer structure, deeper features, nonlinear pairwise functions, and GPU-accelerated blended learning improve performance or efficiency.
- Word recognition: PreTrainJoint outperforms the other training strategies in almost all Word50 configurations.PwTrain often performs worse because it cannot adapt the nonlinearities while learning pairwise weights.
- Word recognition: Second-order Markov models consistently improve performance over less structured models on Word50.The second-order model adds links between neighboring and every-other variables.
- Word recognition: Deeper, more structured models and larger hidden layers achieve better Word50 performance.The experiments vary one- and two-layer perceptrons, short- and long-range MRF connections, and the second-layer width H2.
- Efficiency: GPU training takes 0.064s per iteration for first-order and 0.104s for second-order Markov models while training 831,166 weights.Training one-layer and multilayer models takes approximately the same time.
- Word recognition: Nonlinear pairwise functions attain the best Word50 performance with 16 to 64 hidden units sufficient for bigram combinations.The largest nonlinear pairwise model has 974,846 weights and requires 0.068s per training iteration on average.
- Image classification: On Flickr, mean classification error is 9.36% for Unary only, 7.70% for PwTrain, and 7.25% for PreTrainJoint.The task predicts 38 binary tags for each image using an eight-layer deep network with a 76-dimensional top layer.
4 DISCUSSION & CONCLUSION
The paper places its approach among methods that jointly optimize neural and graphical-model components, using blended learning and inference for efficient training. Experiments show that deeper, more structured models perform better and joint learning outperforms alternative training strategies.
- The approach extends prior work that jointly optimizes neural networks and graphical models for tasks such as speech recognition, document processing, and structured prediction.
- Blending converts the min-max learning task into minimization and uses block-coordinate descent to interleave parameter updates with inference.The paper notes that any order of block updates is possible, while the optimal tradeoff remains open.
- Across word prediction from noisy images and multi-class image classification, deeper and more structured models achieved better performance, while joint learning of all weights outperformed other strategies.The paper identifies holistic semantic scene understanding and models with hidden variables as future application directions.