Learning Deep Structured Models

Introduction

Deep learning algorithms attempt to model high-level abstractions of the data using architectures composed of multiple non-linear transformations. A multiplicity of variants have been proposed (Hinton et al., 1984; LeCun et al., 1998; Hinton & Salakhutdinov, 2006; Bengio et al., 2007; Salakhutdinov & Hinton, 2012; Zeiler & Fergus, 2014) and shown to be extremely successful in a wide variety of applications including object detection, speech recognition as well as natural language processing (Lee et al., 2009; Socher et al., 2012; Jia, 2013; Krizhevsky et al., 2013; Eigen et al., 2014). Recently, state-of-the-art results have been achieved in many computer vision tasks, outperforming competitive methods by a large margin (Krizhevsky et al., 2013; Girshick et al., 2014).

Deep neural networks can, however, be even more powerful when combined with graphical models in order to capture the statistical dependencies between the variables of interest. For example, Deng et al. (2014) exploit mutual exclusion, overlapping and subsumption properties of class labels in order to better predict in large scale classification tasks. In pose estimation, more accurate predictions can be obtained when encoding the spatial relationships between joint locations (Tompson et al., 2014).

It is, however, an open problem how to develop scalable deep learning algorithms that can learn higher-order knowledge taking into account the output variable’s dependencies. Existing approaches often rely on a two-step process (Nowozin et al., 2011; Xu et al., 2014) where a non-linear classifier that employs deep features is trained first, and its output is used to generate potentials for the structured predictor. This piece-wise training is, however, suboptimal as the deep features are learned while ignoring the dependencies between the variables of interest, e.g., independently learned segmentation and detection features (Hariharan et al., 2014) might be focusing on predicting the same examples correctly. But when learned jointly they can improve their predictive power by exploiting complementary information to fix additional mistakes.

In this paper we extend deep learning algorithms to learn complex representations taking into account the dependencies between the output random variables. Towards this goal, we propose a learning algorithm that is able to learn structured models with arbitrary graphs jointly with deep features that form Markov random field (MRF) potentials. Our approach is efficient as it blends learning and inference resulting in a single loop algorithm which makes use of GPU acceleration. We demonstrate the effectiveness of our method in the tasks of predicting words from noisy images, and multi-class classification of Flickr photographs. We show that joint learning of deep features and MRF parameters results in big performance gains.

Learning Deep Structured Models

In this work, we consider the general setting where $F(x,y;w)$ is an arbitrary scalar-valued function of $w$ and $(x,y)$. In our experiments $F$ is a function composition of non-linear base mappings like convolutions, rectifications, pooling etc. We let the probability of an arbitrary configuration $\hat{y}$ be given by the annealed soft-max $p_{(x,y)}(\hat{y}|w,\epsilon)=\frac{1}{Z_{\epsilon}(x,w)}\exp(F(x,\hat{y};w))^{1/\epsilon}.$ Hereby $Z_{\epsilon}(x,w)$ refers to the partition function, normalizing the distribution $p_{(x,y)}$ to lie within the probability simplex $\Delta$ via $Z(x,w)=\sum_{\hat{y}\in{\cal Y}}\exp(F(x,\hat{y};w))^{1/\epsilon}$. The annealing/temperature parameter $\epsilon\geq 0$ is used to adjust the uniformity of the distribution. We consider general graphical models where the computation of $Z_{\epsilon}(x,w)$ is #P-hard.

During learning, given a training set ${\cal D}$ of input-output pairs $(x,y)\in{\cal D}$, we are interested in finding the parameters $w$ of the model. We do so by maximizing the data likelihood, i.e., minimizing the negative log-likelihood $-\ln\prod_{(x,y)\in{\cal D}}p_{(x,y)}(y|w,\epsilon)$ which yields

Note that this is equivalent to maximizing the cross-entropy between a target distribution $p_{(x,y),\operatorname{tg}}(\hat{y})=\delta(\hat{y}=y)$ placing all its mass on the groundtruth label, and the model distribution $p_{(x,y)}(\hat{y}|w,\epsilon)$. Hence Eq. (1) is equivalently obtained by $\max_{w}\sum_{(x,y),\hat{y}\in{\cal Y}}p_{(x,y),\operatorname{tg}}(\hat{y})\ln p_{(x,y)}(\hat{y}|w,\epsilon)$. It is easily possible to incorporate more general target distributions into Eq. (1). Note also that $\epsilon=0$ recovers the structured hinge loss objective.

Minimizing Eq. (1) w.r.t. $w$ requires computation of the gradient $\frac{\partial}{\partial w}\sum_{(x,y)\in{\cal D}}-\ln p_{(x,y)}(y|w,\epsilon)$, which is given by a transformed difference between the distributions of the model $p_{(x,y)}(\hat{y}|w,\epsilon)$ and the target $p_{(x,y),\operatorname{tg}}(\hat{y})$:

A gradient descent algorithm for minimizing Eq. (1) will iterate between the following steps: (i) For a given $w$ evaluate the function $F$, (ii) compute the model distribution $p_{(x,y)}(\hat{y}|w,\epsilon)$, (iii) propagate the difference between the model and target distribution using a backward pass (resembling the chain rule for composite functions) and (iv) update the parameters $w$. This is summarized in Fig. 1.

2 Approximate Learning

Note that for general graphical models the exact computation of $p_{(x,y)}(\hat{y}|w,\epsilon)$ is not possible. As a consequence it is intractable to compute the exact gradient of the cost-function given in Eq. (2) and one has to resort to approximate solutions.

Inspired by approximations used for log-linear models, we make use of the following identity (Wainwright & Jordan, 2008; Koller & Friedman, 2009):

For most applications, $F(x,y;w)$ decomposes into a sum of functions, each depending on a local subset of variables $y_{r}$, i.e., $F(x,y;w)=\sum_{r\in{\cal R}}f_{r}(x,y_{r};w).$ Hereby $r$ is a restriction of the variable tuple $y=(y_{1},\ldots,y_{N})$ to the subset $r\subseteq\{1,\ldots,N\}$, i.e., $y_{r}=(y_{i})_{i\in r}$. All subsets $r$ required to compute the model function $F$ are summarized in the set ${\cal R}$.

Plugging this decomposition into Eq. (3), we equivalently get the log-partition function $\epsilon\ln Z_{\epsilon}(x,w)$ via $\max_{p_{(x,y)}(\hat{y})\in\Delta}\sum_{r,\hat{y}_{r}}p_{(x,y),r}(\hat{y}_{r})f_{r}(x,\hat{y}_{r};w)+\epsilon H(p_{(x,y)}),$ where we use marginals $p_{(x,y),r}(\hat{y}_{r})=\sum_{y\setminus y_{r}}p_{(x,y)}(y)$.

Despite the assumed locality of the scoring function, the learning task remains computationally challenging since the entropy $H(p_{(x,y)})$ can only be computed exactly for a very small set of models, e.g., models for which the joint distribution $p_{(x,y)}(y)$ is equivalently described by low tree-width models. In addition, the marginalization constraints are exponential in size.

To deal with both issues a common solution in log-linear models is to approximate the true marginals $p_{(x,y),r}$ with local beliefs $b_{(x,y),r}$ that are not required to fulfill marginalization constraints globally, but only locally (Wainwright & Jordan, 2008). That means marginals $b_{(x,y),r}$ are not required to arise from a common joint distribution $p_{(x,y)}$. In addition, we approximate the entropy via the fractional entropy (Wiegerinck & Heskes, 2003), i.e., $H(p_{(x,y)})\approx\sum_{r}c_{r}H(b_{(x,y),r})$. Counting numbers $c_{r}$ are employed to weight the marginal entropies. Putting all this together, we obtain the following approximation for $\epsilon\ln Z_{\epsilon}(x,w)$:

Hereby beliefs are constrained to the local polytope

with $P(r)$ the set of parents of region $r$, i.e., $P(r)\subseteq\{p\in{\cal R}:r\subset p\}$, which subsumes those regions for which we want the marginalization constraint to hold. Conversely, we define the set of children as $C(r)=\{c\in{\cal R}:r\in P(c)\}$.

We can thus rewrite the learning problem by plugging the approximations derived in Eq. (4) into Eq. (1). This gives rise to the new approximated learning program

To iteratively update the parameters for the non-smooth approximated cost function given in Eq. (5) we require a sub-gradient w.r.t. $w$, which in turn requires to solve the maximization w.r.t. the beliefs $b$ exactly. This is a non-trivial task in itself as inference in general graphical models is NP-hard. Iterative message passing algorithms (Pearl, 1988; Yedidia et al., 2005; Wainwright et al., 2005; Weiss et al., 2007; Meltzer et al., 2009) are typically employed. Importantly, note that combining the procedure outlined in Fig. 1 with iterative message passing to approximate $p_{(x,y)}(\hat{y}|w,\epsilon)$ results in a double-loop algorithm which would be slow for many graphical models of interest.

3 Efficient Approximate Learning by Blending Learning and Inference

In this section we propose a more efficient algorithm that is based on the principle of blending learning (i.e., parameter updates) and inference. Thus we are interested in only performing a single message passing iteration before updating the parameters $w$. Note that simply reducing the number of iterations is generally not an option as the obtained beliefs $b_{(x,y),r}$ are by no means accurate. However, assuming all counting numbers $c_{r}$ to be positive, we can derive an algorithm that is able to interleave minimization w.r.t. $w$ and maximization of the beliefs $b$. Such a procedure is more efficient as we are able to update the parameters $w$ much more frequently.

To interleave both programs we convert maximization of the beliefs into a minimization by employing the dual program as detailed in the following claim. This is possible since the maximization problem is concave in $b_{(x,y)}$ if $\forall r$, $\epsilon c_{r}\geq 0$.

Assume $\epsilon c_{r}\geq 0$ $\forall r$ and let $\overline{F}(w)=\sum_{(x,y)\in{\cal D}}F(x,y;w)$ denote the sum of empirical function observations. Let $\lambda_{(x,y),r\rightarrow p}(\hat{y}_{r})$ be the Lagrange multipliers for each marginalization constraint $\sum_{\hat{y}_{p}\setminus\hat{y}_{r}}b_{(x,y),p}(\hat{y}_{p})=b_{(x,y),r}(\hat{y}_{r})$ within the polytope ${\cal C}_{(x,y)}$. Then the approximated general structured prediction task shown in Eq. (5) is equivalent to

where we employed the re-parameterization score $\hat{f}_{r}(x,\hat{y}_{r};w,\lambda)=f_{r}(x,\hat{y}_{r};w)+\!\!\sum\limits_{c\in C(r)}\!\!\lambda_{(x,y),c\rightarrow r}(\hat{y}_{c})-\!\!\sum\limits_{p\in P(r)}\!\!\lambda_{(x,y),r\rightarrow p}(\hat{y}_{r})$.

Proof: To obtain the dual of the maximization w.r.t. $b_{(x,y)}$ we utilize its Lagrangian $L_{(x,y)}\!\!=\!\!\sum_{r,\hat{y}_{r}}\!b_{(x,y),r}(\hat{y}_{r})\hat{f}_{r}(x,\hat{y}_{r};w,\lambda)+\!\sum_{r}\!\epsilon c_{r}H(b_{(x,y),r}).$ Maximization of the Lagrangian w.r.t. the primal variables $b$ is possible by employing the relationship stated in Eq. (3) locally $\forall r$. We then obtain the dual function being the first term in Eq. (6). For strict convexity, i.e., $\epsilon c_{r}>0$, we reconstruct the beliefs to be proportional to the exponentiated, loss-augmented re-parameterization score $b_{(x,y),r}\propto\exp\frac{\hat{f}_{r}(x,\hat{y}_{r};w,\lambda)}{\epsilon c_{r}}.$ For $\epsilon c_{r}=0$ the beliefs correspond to a uniform distribution over the set of maximizers of the loss-augmented re-parameterization score $\hat{f}_{r}(x,\hat{y}_{r};w,\lambda)$. $\blacksquare$

It is important to note that by applying duality we managed to convert the $\min$-$\max$ task in Eq. (5) into a single minimization as shown in Eq. (6). Performing block coordinate descent updates to minimize Eq. (6), we are therefore able to interleave both, updating the weights (i.e., learning) and the messages (i.e., inference). This results in a more efficient algorithm, as inference does not have to be run until convergence. Even a single update of the messages suffices. We note that this is possible only if $\epsilon c_{r}\geq 0$ $\forall r$. Strictly speaking, we require concavity only within the set of feasible beliefs ${\cal C}_{(x,y)}$. However, for simplicity we neglect this extension in the following.

Fig. 2 summarizes our efficient deep structured prediction algorithm which iterates between the following steps. Given parameters $w$ we perform a standard forward pass to compute $f_{r}(x,\hat{y}_{r};w)$ for all regions. We then iterate through all regions $r$ and use block-coordinate descent to find the globally optimal value of Eq. (6) w.r.t. $\lambda_{(x,y),r\rightarrow p}(\hat{y}_{r})$ $\forall(x,y),\hat{y}_{r},p\in P(r)$. This can be done in closed form and therefore is computed very efficiently. We refer the reader to Schwing (2013) for a derivation in the log-linear setting. We then compute the gradient using a standard backward pass before we update the parameters by performing a step of size $\eta$ along the negative gradient.

4 Implementation Details

We implemented the general algorithm presented in Fig. 2 in C++ as a library for Linux, Windows and OS X platforms. It supports usage of the GPU for the forward and backward pass using both, standard linear algebra packages and manually tuned GPU-kernels. In addition to standard gradient descent, we allow specification of both mini-batches, moments and different regularizers like $2$-norm and $\infty$-norm. Between iterations the step-size can be reduced based on either the negative log-likelihood or validation set performance. Contrasting available deep learning packages, our function $F$ is specified using a general computation tree. Hence we support an arbitrarily nested function structure composed of data, parameters and function prototypes (convolution, affine function aka fully connected, dropout, local response normalization, pooling, rectified linear, sigmoid and softmax units). The aforementioned library is accompanied by a program performing learning, inference and gradient checks. To accommodate for large datasets it reads data from HDF5 storage while a second thread simultaneously performs the computation. Google protocol buffers are employed to effectively specify the function $F$ without the need to modify any source code. We will release this library upon publication. We believe that it will be useful for many researchers.

Experimental Evaluation

We demonstrate the performance of our model on two tasks: word recognition and image classification. We investigate four strategies to learn the model parameters. ‘Unary only’ denotes training only unary classifiers while ignoring the structure of the graphical model, i.e., pairwise weights are equal to . ‘JointTrain’ initializes all weights at random and trains them jointly. ‘PwTrain’ uses piecewise training by first training the unary potentials and then keeping them fixed when learning the pairwise potentials. ‘PreTrainJoint’ pre-trains the unaries but jointly optimizes pairwise weights as well as unary weights in a second step.

Our first task consists of word recognition from noisy images. Towards this goal, we created a challenging dataset by randomly selecting 50 words, each consisting of five characters. We then generated writing variations of each word as follows: we took the lower case characters from the Chars74K dataset (de Campos et al., 2009), and inserted them in random background image patches (similar to Larochelle et al. (2007)) by alpha matting, i.e., characters have transparency. To increase the difficulty, we perturbed each character image of size $28\times 28$ by scaling, rotation and translation. As shown in Fig. 3 the task is very challenging, some characters are fairly difficult to recognize even for humans. We denote the resulting dataset ‘Word50.’ The training, validation and test sets have $10,000$, $2,000$ and $2,000$ variations of words respectively.

We experimented with graphical models composed of unary and pairwise regions defined over five random variables, one per character. We encode unary potentials $f_{r}(x,y_{i};w_{u})$ using multi-layer perceptrons (MLPs) with rectified linear units (ReLU). Unless otherwise stated, we define all pairwise interactions via

where $r=\{i,j\}$, $w_{p}=\{W\}$, $W_{mn}$ is the element of matrix $W$, and $\delta$ refers to the indicator function.

For all experiments, we share all unary weights across the nodes of the graphical model as well as all pairwise weights for all edges. Note that due to the use of ReLU units, the negative log-likelihood is non-smooth, non-linear and non-convex w.r.t. $w$. Because of the non-smoothness of $F$, we utilize momentum based sub-gradient descent methods to estimate the weights. In particular, we use a mini-batch size of $100$, a step size of $0.01$ and a momentum of $0.95$. If the unary potential is pre-trained, the initial step size is reduced to $0.001$. All the unary classifiers are trained with $100,000$ iterations over mini-batches. For all experiments, the validation set is only used to decrease the step size, i.e., if the accuracy on the validation set decreases, we reduce the step size by $0.5$. We use $\epsilon=1$, set $c_{r}=1$ for all regions $r$, and perform 10 message passing iterations to compute the marginal beliefs $b_{(x,y),r}$ at step 2 in Fig. 2 when dealing with loopy models.

We experiment with two graphical models, Markov models of first (i.e., there are links only between $y_{i}$ and $y_{i+1}$) and second order (i.e., there are links between $y_{i}$ and $y_{i+1}$, $y_{i+2}$) as well as two types of unary potentials with varying degree of structure. We report two metrics, the average character and word accuracy, which correspond to Hamming loss and zero-one loss respectively. Table 1 depicts the results for the different models, learning strategies and number of hidden units. We observe the following trends.

Joint training helps: Joint training with pre-trained unary classifiers (PreTrainJoint) outperforms all the other approaches in almost all cases. The piecewise training method (PwTrain), unable to adapt the non-linearities while learning pairwise weights, often leads to performance worse than joint training.

Structure helps: Adding structure to the model is key to capture complex dependencies. As shown in Table 1, more structured models (i.e., second order Markov model) consistently improves performance.

We tested our models using one layer and two-layer perceptrons with both short-range and long-range connections in the MRF. For the two-layer MLP, the number of hidden units in the first layer is fixed to $H_{1}=512$, and we varied the number of hidden units $H_{2}$ in the second layer. As shown in Table 1 we observe that the deeper and the more structured the model, the better the performance we achieve. As expected, performance also grows with the number of hidden units.

Efficiency: Using GPUs, it takes on average 0.064s per iteration for the 1st order Markov model and 0.104s for the 2nd order Markov model. The time employed for training the one layer vs. the multi-layer models is approximately the same. Note that our approach is very efficient, as this is the time per iteration to train 831,166 weights.

Learned parameters: As shown in the left column of Fig. 4, the learned unary weights resemble character strokes. The middle two panels show the learned pairwise weights for distance-1 edges (i.e., edges with only neighboring connections) and distance-2 edges (i.e., edges connecting every other variable). For example, it shows that ‘q’ is likely to be followed by ‘u,’ and ‘e’ is likely to be distance-2 away from ‘q’ in this dataset. On the right-most panel, we also show the negative log-likelihood as a function of the number of joint training iterations. PreTrainJoint can achieve the lowest cost value, while PwTrain has the highest value.

Non-linear pairwise functions: To further demonstrate the generality of our approach, we replaced the linear pairwise function in Eq. (7) by a one-layer MLP, while keeping the other settings identical. For this experiment we utilize a 1st order Markov model. As shown in Fig. 5, our model attains best performance when using a non-linear pairwise function. We found 16 to 64 hidden units for the non-linear pairwise function to be sufficient for modeling the bi-gram combinations in this dataset. In this case the largest model has 974,846 weights and training takes on average 0.068s per iteration.

2 Image Classification: Flickr

We next evaluate the importance of blending learning and inference. Towards this goal, we make use of the Flickr dataset, which consists of $10,000$ training and $10,000$ test images from Flickr. The task is to predict which of 38 possible tags should be assigned to each image. Fig. 6 shows some examples. The graphical model has 38 binary random variables, each denoting the presence/absence of a particular tag. We define the non-linear unaries $f_{r}(x,y_{i};w_{u})$ using the 8-layer deep-net architecture from Krizhevsky et al. (2013) followed by a $76$-dimensional top layer. Hence the function is composed out of two subsequent stacks of convolution, rectified linear (ReLU), pooling and local response normalization units. Those are followed by three convolution–ReLU function pairs. Afterwards pooling is applied before two fully-connected–ReLU–dropout combinations are employed to yield the input into a fully connected layer which finally computes the unary potentials. We employ pairwise potentials similar to Eq. (7) which now fully model the correlations between any pair of output variables. This amounts to a total of $57,182,408$ parameters arising from the convolutional units, fully connected units and corresponding biases as well as the pairwise weights.

We use a momentum based sub-gradient method for training with a mini-batch size of $300$, a step size of $0.0001$, a momentum of $0.95$ and set $\epsilon=1$ and $c_{r}=1$ $\forall r$. We initialized the deep-net parameters using a model pre-trained on ImageNet (Deng et al., 2009). Our error metric is the classification error (i.e., Hamming loss).

Joint training helps: The mean error for unary only potentials (‘Unary only’), piecewise training (‘PwTrain’) and joint pretraining (‘PreTrainJoint’) is 9.36%, 7.70% and 7.25% respectively. Similar to the Word50 dataset we observe that joint training is beneficial. We provide examples for perfect (two left-most images), roughly accurate and failing predictions (right image) in Fig. 6.

Learned pairwise weights: In Fig. 7(a) we illustrate the learned correlations for a subset of the 38 classes. We observe that the class ‘people’ correlates highly with ‘female,’ ‘male,’ and ‘portrait.’ The ‘indoor’ tag does not co-occur with ‘sky,’ ‘structures,’ ‘plant life’ and ‘tree.’ ‘Sea’ appears typically with ‘water,’ ‘clouds,’ ‘lake’ and ‘sky.’

Efficiency of Blending: To illustrate that blending is indeed beneficial we compare the negative log-likelihood and the training error as a function of run-time in Fig. 7(b). The standard approach is limited to 20 iterations of message passing to avoid time-consuming, repeated computation of a stopping criterion involving both the approximated log-partition function and its dual. As show in Fig. 7(b) blending learning and inference speeds up parameter estimation significantly. For larger graphical models, we expect the differences to be even more significant.

Discussion & Conclusion

Joint training of neural networks and graphical models: Neural Networks have been incorporated as unary potentials in graphical models. One of the earliest works by Bridle (1990) jointly optimizes a system consisting of multilayer perceptrons and hidden Markov models for speech recognition. For document processing systems, Bottou et al. (1997) propose Graph Transformer Networks to jointly optimize sub-tasks, such as word segmentation and character recognition. Several works (Collobert et al., 2011; Peng et al., 2009; Ma et al., 2012; Do & Artieres, 2010; Prabhavalkar & Fosler-Lussier, 2010; Morris & Fosler-Lussier, 2008) have extended the linear unary potential in MRFs to incorporate non-linearities. However, they assume that exact inference can be performed either via a forward-backward pass within the graphical model or dynamic programming. In contrast, in this paper we present learning algorithms for general graphical models, where inference is hard. Moreover, all the previous works (except Do & Artieres (2010)) do not consider max-margin loss during training which is incorporated into our framework by choosing $\epsilon=0$. More recently, Li & Zemel (2014) use a hinge loss to learn the unary term defined as a neural net, but keep the pairwise potentials fixed (i.e., no joint training). Domke (2013) considers non-linear structured prediction and decomposes the learning problem into a subset of logistic regressors, which require the parameter updates to be run till convergence before updating the messages. Tompson et al. (2014) also jointly train convolutional neural networks and a graphical model for pose estimation. However, the MRF inference procedure is approximated by their Spatial-Model which ignores the partition function.

Blending learning and inference: In this paper we defined learning to be a $\min$-$\max$ task. The blending strategy, which was previously employed for learning log-linear models by (Meshi et al., 2010; Hazan & Urtasun, 2010), amounts to converting the maximization task into a minimization problem using its dual. Subsequently we make use of block-coordinate descent strategies to obtain a more efficient algorithm. Importantly any order of block-updates is possible. It remains an open problem to find the optimal tradeoff.

We have proposed an efficient algorithm to learn deep models enriched to capture the dependencies between the output variables. Our experiments on word prediction from noisy images and multi-class image classification showed that the deeper and the more structured the model, the better the performance we achieve. Furthermore, joint learning of all weights outperforms all other strategies. In the future we plan to learn deeper models in applications such as holistic semantic scene understanding. We will also extend our approach to deal with hidden variables.

We thank NVIDIA Corporation for the donation of GPUs used in this research. This work was partially funded by ONR-N00014-14-1-0232.

References