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.
Liang-Chieh Chen Alexander G. Schwing Alan L. Yuille Raquel Urtasun
Accepted as a workshop contribution at ICLR 2015
LEARNING DEEPSTRUCTURED MODELS
Liang-Chieh Chen
Department of Computer Science, UCLA, lcchen@cs.ucla.edu
Alexander G. Schwing
Department of Computer Science, University of Toronto, aschwing@cs.toronto.edu
Alan L. Yuille
Department of Statistics, UCLA, yuille@stat.ucla.edu
Raquel Urtasun
Department of Computer Science, University of Toronto, urtasun@cs.toronto.edu
ABSTRACT
Many problems in real-world applications involve predicting several random vari-
ables which are statistically related. Markov random ﬁelds (MRFs) are a great
mathematical tool to encode such relationships. The goal of this paper is to com-
bine 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
efﬁcient 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 classiﬁcation of Flickr photographs. We
show that joint learning of the deep features and the MRF parameters results in
signiﬁcant performance gains.
1 I NTRODUCTION
Deep learning algorithms attempt to model high-level abstractions of the data using architec-
tures composed of multiple non-linear transformations. A multiplicity of variants have been pro-
posed (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 lan-
guage 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 or-
der to better predict in large scale classiﬁcation 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 classiﬁer
that employs deep features is trained ﬁrst, and its output is used to generate potentials for the struc-
tured predictor. This piece-wise training is, however, suboptimal as the deep features are learned
The ﬁrst two authors contributed equally to this work.
1arXiv:1407.2538v3  [cs.LG]  27 Apr 2015
Accepted as a workshop contribution at ICLR 2015
while ignoring the dependencies between the variables of interest, e.g., independently learned seg-
mentation 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 ﬁx additional mistakes.
In this paper we extend deep learning algorithms to learn complex representations taking into ac-
count 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 ﬁeld (MRF) potentials. Our approach is efﬁcient 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 classiﬁcation of Flickr photographs. We show that joint learning of deep features
and MRF parameters results in big performance gains.
2 L EARNING DEEPSTRUCTURED MODELS
In this section we investigate how to learn ‘deep features’ that take into account the dependen-
cies between the output variables. Let y2Y be the set of random variables y= (y1;:::;yN)
that we are interested in predicting. In this work we assume the space of valid conﬁgurations to
be a product space, i.e.,Y=QN
i=1Yi, and the domain of each individual variable yito be dis-
crete, i.e.,Yi=f1;:::;jYijg. Given input data x2X and parameters w2RAof the function
F(x;y;w) :XY RA!R, inference amounts to ﬁnding the highest scoring conﬁguration
y= arg max yF(x;y;w):Note that ifFis a deep network and there are no connections between
the output variables to be predicted, inference corresponds to a forward pass to evaluate the function,
followed by independently ﬁnding the largest response for each variable. This can be interpreted as
inference in a graphical model with only unary potentials. However, for arbitrary graphical models
it is NP-hard to ﬁnd the maximizing conﬁguration ysince the inference program generally requires
a search over a space of sizeQN
i=1jYij. Note also that log-linear models are a special case of this
program, with F(x;y;w) =w>(x;y)and(x;y)denoting a feature vector computed using the
input-output pair (x;y).
In this work, we consider the general setting where F(x;y;w)is an arbitrary scalar-valued func-
tion ofwand(x;y). In our experiments Fis a function composition of non-linear base mappings
like convolutions, rectiﬁcations, pooling etc. We let the probability of an arbitrary conﬁguration ^y
be given by the annealed soft-max p(x;y)(^yjw;) =1
Z(x;w)exp(F(x;^y;w))1=:HerebyZ(x;w)
refers to the partition function, normalizing the distribution p(x;y)to lie within the probability sim-
plexviaZ(x;w) =P
^y2Yexp(F(x;^y;w))1=. The annealing/temperature parameter 0is
used to adjust the uniformity of the distribution. We consider general graphical models where the
computation of Z(x;w)is #P-hard.
2.1 L EARNING VIA GRADIENT DESCENT
During learning, given a training set Dof input-output pairs (x;y)2D, we are interested in ﬁnding
the parameters wof the model. We do so by maximizing the data likelihood, i.e., minimizing the
negative log-likelihood lnQ
(x;y)2Dp(x;y)(yjw;)which yields
min
wX
(x;y)2D(lnZ(x;w)F(x;y;w)): (1)
Note that this is equivalent to maximizing the cross-entropy between a target distri-
butionp(x;y);tg(^y) =(^y=y)placing all its mass on the groundtruth label,
and the model distribution p(x;y)(^yjw;). Hence Eq. (1) is equivalently obtained by
maxwP
(x;y);^y2Yp(x;y);tg(^y) lnp(x;y)(^yjw;). It is easily possible to incorporate more general tar-
get distributions into Eq. (1). Note also that = 0recovers the structured hinge loss objective.
Minimizing Eq. (1) w.r.t. wrequires computation of the gradient@
@wP
(x;y)2Dlnp(x;y)(yjw;),
which is given by a transformed difference between the distributions of the model p(x;y)(^yjw;)and
2
Accepted as a workshop contribution at ICLR 2015
Repeat until stopping criteria
1. Forward pass to compute F(x;^y;w)
2. Compute p(x;y)(^yjw;)
3. Backward pass via chain rule to obtain gradient
4. Update parameters w
Figure 1: Gradient descent algorithm for learning deep structured models.
the targetp(x;y);tg(^y):
X
(x;y)2DX
^y2Y@
@wF(x;^y;w)
p(x;y)(^yjw;)p(x;y);tg(^y)
: (2)
A gradient descent algorithm for minimizing Eq. (1) will iterate between the following steps: (i) For
a givenwevaluate the function F, (ii) compute the model distribution p(x;y)(^yjw;), (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.2 A PPROXIMATE LEARNING
Note that for general graphical models the exact computation of p(x;y)(^yjw;)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 (Wain-
wright & Jordan, 2008; Koller & Friedman, 2009):
lnZ(x;w) = max
p(x;y)(^y)2E[F(x;^y;w)] +H(p(x;y)); (3)
where Edenotes an expectation over p(x;y)(^y)andHrefers to the entropy.
For most applications, F(x;y;w)decomposes into a sum of functions, each depending on a local
subset of variables yr,i.e.,F(x;y;w) =P
r2Rfr(x;yr;w):Herebyris a restriction of the variable
tupley= (y1;:::;yN)to the subset rf1;:::;Ng,i.e.,yr= (yi)i2r. All subsets rrequired to
compute the model function Fare summarized in the set R.
Plugging this decomposition into Eq. (3), we equivalently get the log-partition function
lnZ(x;w)viamaxp(x;y)(^y)2P
r;^yrp(x;y);r(^yr)fr(x;^yr;w) +H(p(x;y));where we use
marginalsp(x;y);r(^yr) =P
ynyrp(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);rwith local beliefs b(x;y);rthat are not required to fulﬁll marginalization constraints globally,
but only locally (Wainwright & Jordan, 2008). That means marginals b(x;y);rare 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))P
rcrH(b(x;y);r). Counting numbers cr
are employed to weight the marginal entropies. Putting all this together, we obtain the following
approximation for lnZ(x;w):
max
b(x;y)2C(x;y)X
r;^yrb(x;y);r(^yr)fr(x;^yr;w) +X
rcrH(b(x;y);r): (4)
Hereby beliefs are constrained to the local polytope
C(x;y)=(8r b (x;y);r2
8r;^yr;p2P(r)P
^ypn^yrb(x;y);p(^yp) =b(x;y);r(^yr);
3
Accepted as a workshop contribution at ICLR 2015
Let~cr;p=cp=(cr+P
p02P(r)cp0). Repeat until stopping criteria
1. Forward pass to compute fr(x;^yr;w)8(x;y);r;yr
2. Get beliefs b(x;y);r/exp^fr(x;^yr;w;)
crby iterating over r:8(x;y);p2P(r);^yr
(x;y);p!r(^yr) =cplnX
^ypn^yrexpfp(x;^yp;w)P
p02P(p)(x;y);p!p0(^yp) +P
r02C(p)nr(x;y);r0!p(^yr0)
cp
(x;y);r!p(^yr)/~cr;p0
@fr(x;^yr;w) +X
c2C(r)(x;y);c!r(^yc) +X
p2P(r)(x;y);p!r(^yr)1
A(x;y);p!r(^yr)
3. Backward pass via chain-rule for gradient g=P
(x;y);r;^yrb(x;y);r(^yr)rwfr(x;^yr;w)rwF(w)
4. Update parameters wusing stepsize viaw wg
Figure 2: Efﬁcient learning algorithm that blends learning and inference.
withP(r)the set of parents of region r,i.e.,P(r)fp2R :rpg, which subsumes those
regions for which we want the marginalization constraint to hold. Conversely, we deﬁne the set of
children asC(r) =fc2R:r2P(c)g.
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
min
wX
(x;y)2D0
@max
b(x;y)2C(x;y)8
<
:X
r;^yrb(x;y);r(^yr)fr(x;^yr;w) +X
rcrH(b(x;y);r)9
=
;F(x;y;w)1
A:(5)
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
bexactly. 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)(^yjw;)results
in a double-loop algorithm which would be slow for many graphical models of interest.
2.3 E FFICIENT APPROXIMATE LEARNING BY BLENDING LEARNING AND INFERENCE
In this section we propose a more efﬁcient 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);rare by no means accurate.
However, assuming all counting numbers crto be positive, we can derive an algorithm that is able
to interleave minimization w.r.t. wand maximization of the beliefs b. Such a procedure is more
efﬁcient as we are able to update the parameters wmuch more frequently.
To interleave both programs we convert maximization of the beliefs into a minimization by employ-
ing the dual program as detailed in the following claim. This is possible since the maximization
problem is concave in b(x;y)if8r,cr0.
Claim 1 Assumecr08rand letF(w) =P
(x;y)2DF(x;y;w)denote the sum of empirical
function observations. Let (x;y);r!p(^yr)be the Lagrange multipliers for each marginalization
constraintP
^ypn^yrb(x;y);p(^yp) =b(x;y);r(^yr)within the polytope C(x;y). Then the approximated
general structured prediction task shown in Eq. (5)is equivalent to
min
w;X
(x;y);rcrlnX
^yrexp^fr(x;^yr;w;)
crF(w); (6)
4
Accepted as a workshop contribution at ICLR 2015
banal julep resty
drein yojan mothy
Figure 3: Samples from the Word50 dataset. High degree of rotation, scaling and translation.
where we employed the re-parameterization score ^fr(x;^yr;w;) =fr(x;^yr;w) +P
c2C(r)(x;y);c!r(^yc)P
p2P(r)(x;y);r!p(^yr).
Proof: To obtain the dual of the maximization w.r.t. b(x;y)we utilize its Lagrangian L(x;y)=P
r;^yrb(x;y);r(^yr)^fr(x;^yr;w;)+P
rcrH(b(x;y);r):Maximization of the Lagrangian w.r.t. the pri-
mal variables bis possible by employing the relationship stated in Eq. (3) locally 8r. We then obtain
the dual function being the ﬁrst term in Eq. (6). For strict convexity, i.e.,cr>0, we recon-
struct the beliefs to be proportional to the exponentiated, loss-augmented re-parameterization score
b(x;y);r/exp^fr(x;^yr;w;)
cr:Forcr= 0the beliefs correspond to a uniform distribution over the set
of maximizers of the loss-augmented re-parameterization score ^fr(x;^yr;w;). 
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 efﬁcient algorithm, as inference does not have
to be run until convergence. Even a single update of the messages sufﬁces. We note that this is
possible only if cr08r. Strictly speaking, we require concavity only within the set of feasible
beliefsC(x;y). However, for simplicity we neglect this extension in the following.
Fig. 2 summarizes our efﬁcient deep structured prediction algorithm which iterates between the
following steps. Given parameters wwe perform a standard forward pass to compute fr(x;^yr;w)
for all regions. We then iterate through all regions rand use block-coordinate descent to ﬁnd the
globally optimal value of Eq. (6) w.r.t. (x;y);r!p(^yr)8(x;y);^yr;p2P(r). This can be done in
closed form and therefore is computed very efﬁciently. 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 along the negative gradient.
2.4 I MPLEMENTATION 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 gradi-
ent descent, we allow speciﬁcation of both mini-batches, moments and different regularizers like
2-norm and1-norm. Between iterations the step-size can be reduced based on either the nega-
tive log-likelihood or validation set performance. Contrasting available deep learning packages, our
functionFis speciﬁed using a general computation tree. Hence we support an arbitrarily nested
function structure composed of data, parameters and function prototypes (convolution, afﬁne func-
tion aka fully connected, dropout, local response normalization, pooling, rectiﬁed 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 em-
ployed to effectively specify the function Fwithout the need to modify any source code. We will
release this library upon publication. We believe that it will be useful for many researchers.
5
Accepted as a workshop contribution at ICLR 2015
Graph MLP Method H1= 128H1= 256H1= 512H1= 768H1= 1024
1st order Markov One LayerUnary only 8.60 / 61.32 10.80 / 64.41 12.50 / 65.69 12.95 / 66.66 13.40 / 67.02
JointTrain 16.80 / 65.28 25.20 / 70.75 31.80 / 74.90 33.05 / 76.42 34.30 / 77.02
PwTrain 12.70 / 64.35 18.00 / 68.27 22.80 / 71.29 23.25 / 72.62 26.30 / 73.96
PreTrainJoint 20.65 /67.42 25.70 /71.65 31.70 / 75.56 34.50 /77.14 35.85 /78.05
2nd order Markov One LayerJointTrain 25.50 / 67.13 34.60 / 73.19 45.55 / 79.60 51.55 /82.37 54.05 /83.57
PwTrain 10.05 / 58.90 14.10 / 63.44 18.10 / 67.31 20.40 / 70.14 22.20 / 71.25
PreTrainJoint 28.15 /69.07 36.85 /75.21 45.75 /80.09 50.10 / 82.30 52.25 / 83.39
H1= 512H2= 32H2= 64H2= 128H2= 256H2= 512
1st order Markov Two LayerUnary only 15.25 / 69.04 18.15 / 70.66 19.00 / 71.43 19.20 / 72.06 20.40 / 72.51
JointTrain 35.95 / 76.92 43.80 / 81.64 44.75 / 82.22 46.00 / 82.96 47.70 / 83.64
PwTrain 34.85 / 79.11 38.95 / 80.93 42.75 / 82.38 45.10 / 83.67 45.75 / 83.88
PreTrainJoint 42.25 /81.10 44.85 /82.96 46.85 /83.50 47.95 /84.21 47.05 / 84.08
2nd order Markov Two LayerJointTrain 54.65 / 83.98 61.80 / 87.30 66.15 / 89.09 64.85 / 88.93 68.00 / 89.96
PwTrain 39.95 / 81.14 48.25 / 84.45 52.65 / 86.24 57.10 / 87.61 62.90 / 89.49
PreTrainJoint 62.60 /88.03 65.80 /89.32 68.75 /90.47 68.60 /90.42 69.35 /90.75
Table 1: Word / Character accuracy. Performance improves as (1) joint-training is employed, (2) the
model is more structured, and (3) deeper unary classiﬁers are utilized. The number of hidden units
for the ﬁrst and second layer are denoted as H1andH2respectively.
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
00.511.522.533.544.55
x 1043004005006007008009001000Neg. Log−Likelihood
Iteration  
JointTrain
PwTrain
PreTrainJoint
Unary weights distance-1 edges distance-2 edges Neg. Log-Likelihood
Figure 4: (left) Subset of the learned unary weights. Pairwise weights (middle two panels), the
darker, the larger the weight. (right) Negative log-likelihood for different learning approaches.
3 E XPERIMENTAL EVALUATION
We demonstrate the performance of our model on two tasks: word recognition and image classiﬁ-
cation. We investigate four strategies to learn the model parameters. ‘ Unary only ’ denotes training
only unary classiﬁers while ignoring the structure of the graphical model, i.e., pairwise weights are
equal to 0. ‘JointTrain ’ initializes all weights at random and trains them jointly. ‘ PwTrain ’ uses
piecewise training by ﬁrst training the unary potentials and then keeping them ﬁxed when learn-
ing the pairwise potentials. ‘ PreTrainJoint ’ pre-trains the unaries but jointly optimizes pairwise
weights as well as unary weights in a second step.
3.1 W ORD RECOGNITION : W ORD50
Our ﬁrst task consists of word recognition from noisy images. Towards this goal, we created a
challenging dataset by randomly selecting 50 words, each consisting of ﬁve 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 difﬁculty, we perturbed each character image of size 2828by scaling, rotation and translation.
As shown in Fig. 3 the task is very challenging, some characters are fairly difﬁcult to recognize even
for humans. We denote the resulting dataset ‘ Word50 .’ The training, validation and test sets have
10;000,2;000and2;000variations of words respectively.
We experimented with graphical models composed of unary and pairwise regions deﬁned over ﬁve
random variables, one per character. We encode unary potentials fr(x;yi;wu)using multi-layer per-
ceptrons (MLPs) with rectiﬁed linear units (ReLU). Unless otherwise stated, we deﬁne all pairwise
6
Accepted as a workshop contribution at ICLR 2015
H1=128 H1=256 H1=512 H1=768 H1=1024161820222426283032343638
  
Linear
PairH16
PairH32
PairH64
H2=32 H2=64 H2=128 H2=256 H2=512343638404244464850
  
Linear
PairH16
PairH32
PairH64
One-Layer MLP Chain Two-Layer MLP Chain
Figure 5: Learning non-linear pairwise functions: Word recognition as a function of the number
of hidden units for the unary potential. Colors represent different number of hidden units for the
pairwise potentials. The y-axis shows the word accuracy of using Linear function, or 16 (PairH16),
32 (PairH32), and 64 (PairH64) hidden units for the pairwise function.
female/indoor/portrait sky/plant life/tree water/animals/sea animals/dog/indoor indoor/ﬂower/plant life
female/indoor/portrait sky/plant life/tree water/animals/sky animals/dog ;
Figure 6: Flickr test set images and some assigned tags as well as our predictions (bottom row).
interactions via
fr(x;yi;yj;wp) =X
mnWmn(yi=m;yj=n); (7)
wherer=fi;jg,wp=fWg,Wmnis the element of matrix W, andrefers 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:01and a momentum of 0:95. If the unary potential is pre-
trained, the initial step size is reduced to 0:001. All the unary classiﬁers 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= 1, setcr= 1 for all regions r, and perform 10 message passing iterations to compute the
marginal beliefs b(x;y);rat step 2 in Fig. 2 when dealing with loopy models.
We experiment with two graphical models, Markov models of ﬁrst ( i.e., there are links only between
yiandyi+1) and second order ( i.e., there are links between yiandyi+1,yi+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 classiﬁers (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 perfor-
mance.
7
Accepted as a workshop contribution at ICLR 2015
0.00 0.68 0.04 0.06 0.02 0.24 0.03 −0.00 −0.01 0.01 0.04 −0.00 −0.05 −0.01 0.07 −0.01 −0.00 −0.12 0.04 0.01 0.01 0.02 0.04 0.02
0.68 0.00 0.06 0.06 −0.00 0.36 0.03 −0.08 −0.05 −0.03 0.02 −0.06 −0.12 −0.05 0.74 −0.04 −0.03 −0.21 0.01 −0.03 −0.03 −0.03 0.05 −0.03
0.04 0.06 0.00 0.05 −0.06 0.07 −0.12 −0.07 −0.35 −0.03 −0.46 −0.02 −0.34 0.11 0.02 −0.15 −0.14 −0.01 −0.07 −0.21 0.03 −0.08 0.06 −0.03
0.06 0.06 0.05 0.00 0.10 0.11 0.07 0.09 0.03 0.10 0.01 0.10 0.02 0.09 0.06 0.08 0.07 0.07 0.08 0.06 0.09 0.09 0.08 0.10
0.02 −0.00 −0.06 0.10 0.00 0.04 0.08 0.05 0.16 0.17 −0.02 0.09 −0.02 0.06 0.03 0.14 0.36 0.06 0.05 0.01 0.08 0.14 0.06 0.10
0.24 0.36 0.07 0.11 0.04 0.00 0.01 0.03 −0.02 0.05 −0.02 0.04 −0.01 0.03 0.12 0.02 0.01 −0.07 0.05 0.05 0.03 0.04 0.07 0.05
0.03 0.03 −0.12 0.07 0.08 0.01 0.00 0.02 0.14 0.07 0.14 0.04 0.05 0.03 0.06 0.08 0.07 −0.03 0.36 0.10 0.04 0.05 0.04 0.07
−0.00 −0.08 −0.07 0.09 0.05 0.03 0.02 0.00 0.02 0.07 −0.03 0.07 0.34 0.04 −0.04 0.04 0.04 0.02 0.05 0.06 0.06 0.06 0.02 0.07
−0.01 −0.05 −0.35 0.03 0.16 −0.02 0.14 0.02 0.00 0.12 0.22 0.04 0.24 −0.02 −0.00 0.44 0.12 −0.04 0.10 0.30 0.01 0.23 0.05 0.11
0.01 −0.03 −0.03 0.10 0.17 0.05 0.07 0.07 0.12 0.00 −0.00 0.09 0.09 0.07 0.01 0.12 0.26 0.06 0.06 0.10 0.07 0.12 0.07 0.18
0.04 0.02 −0.46 0.01 −0.02 −0.02 0.14 −0.03 0.22 −0.00 0.00 0.01 0.04 −0.05 0.06 0.08 −0.04 −0.06 0.14 0.09 −0.00 0.06 0.03 0.02
−0.00 −0.06 −0.02 0.10 0.09 0.04 0.04 0.07 0.04 0.09 0.01 0.00 0.04 0.07 −0.01 0.06 0.09 0.26 0.06 0.05 0.07 0.09 0.05 0.09
−0.05 −0.12 −0.34 0.02 −0.02 −0.01 0.05 0.34 0.24 0.09 0.04 0.04 0.00 −0.03 −0.07 0.09 0.01 0.01 0.08 0.68 0.02 0.05 −0.07 0.10
−0.01 −0.05 0.11 0.09 0.06 0.03 0.03 0.04 −0.02 0.07 −0.05 0.07 −0.03 0.00 −0.01 0.03 0.03 0.03 0.05 0.01 0.06 0.06 0.04 0.07
0.07 0.74 0.02 0.06 0.03 0.12 0.06 −0.04 −0.00 0.01 0.06 −0.01 −0.07 −0.01 0.00 0.00 −0.01 −0.10 0.04 −0.02 0.01 0.00 0.06 0.01
−0.01 −0.04 −0.15 0.08 0.14 0.02 0.08 0.04 0.44 0.12 0.08 0.06 0.09 0.03 0.00 0.00 0.09 −0.00 0.07 0.11 0.05 0.22 −0.01 0.10
−0.00 −0.03 −0.14 0.07 0.36 0.01 0.07 0.04 0.12 0.26 −0.04 0.09 0.01 0.03 −0.01 0.09 0.00 0.05 0.02 0.03 0.05 0.10 0.03 0.27
−0.12 −0.21 −0.01 0.07 0.06 −0.07 −0.03 0.02 −0.04 0.06 −0.06 0.26 0.01 0.03 −0.10 −0.00 0.05 0.00 0.02 0.00 0.22 0.03 −0.01 0.05
0.04 0.01 −0.07 0.08 0.05 0.05 0.36 0.05 0.10 0.06 0.14 0.06 0.08 0.05 0.04 0.07 0.02 0.02 0.00 0.11 0.06 0.08 0.07 0.06
0.01 −0.03 −0.21 0.06 0.01 0.05 0.10 0.06 0.30 0.10 0.09 0.05 0.68 0.01 −0.02 0.11 0.03 0.00 0.11 0.00 0.04 0.09 −0.00 0.12
0.01 −0.03 0.03 0.09 0.08 0.03 0.04 0.06 0.01 0.07 −0.00 0.07 0.02 0.06 0.01 0.05 0.05 0.22 0.06 0.04 0.00 0.06 0.05 0.07
0.02 −0.03 −0.08 0.09 0.14 0.04 0.05 0.06 0.23 0.12 0.06 0.09 0.05 0.06 0.00 0.22 0.10 0.03 0.08 0.09 0.06 0.00 0.06 0.10
0.04 0.05 0.06 0.08 0.06 0.07 0.04 0.02 0.05 0.07 0.03 0.05 −0.07 0.04 0.06 −0.01 0.03 −0.01 0.07 −0.00 0.05 0.06 0.00 0.07
0.02 −0.03 −0.03 0.10 0.10 0.05 0.07 0.07 0.11 0.18 0.02 0.09 0.10 0.07 0.01 0.10 0.27 0.05 0.06 0.12 0.07 0.10 0.07 0.00female
people
indoor
baby
sea
portrait
transport
flower
sky
lake
structures
bird
plant life
food
male
clouds
water
animals
car
tree
dog
sunset
night
river
femalepeopleindoorbabyseaportraittransportflowerskylakestructuresbirdplant lifefoodmalecloudswateranimalscartreedogsunsetnightriver
0 5000 100000246810x 105
Time [s]Neg. Log−Likelihood
  
w/o blend
w blend
0 5000 100000200040006000800010000
Time [s]Training error
  
w/o blend
w blend
(a) (b)
Figure 7: (a) Correlation matrix ( i.e., pairwise potentials) learned on the Flickr dataset. (b) Blending
learning and inference speeds-up training signiﬁcantly.
Deep helps: 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 ﬁrst layer is ﬁxed to H1= 512 , and we varied the number of hidden units H2in 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.
Efﬁciency: 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 efﬁcient, 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 sufﬁcient 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.
3.2 I MAGE 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;000training and 10;000test 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 deﬁne the non-linear unaries fr(x;yi;wu)using the 8-layer deep-net archi-
tecture from Krizhevsky et al. (2013) followed by a 76-dimensional top layer. Hence the function
is composed out of two subsequent stacks of convolution, rectiﬁed linear (ReLU), pooling and local
response normalization units. Those are followed by three convolution–ReLU function pairs. After-
wards pooling is applied before two fully-connected–ReLU–dropout combinations are employed to
yield the input into a fully connected layer which ﬁnally computes the unary potentials. We employ
pairwise potentials similar to Eq. (7) which now fully model the correlations between any pair of
8
Accepted as a workshop contribution at ICLR 2015
output variables. This amounts to a total of 57;182;408parameters 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:95and set= 1 andcr= 18r. We initialized the deep-net
parameters using a model pre-trained on ImageNet (Deng et al., 2009). Our error metric is the
classiﬁcation 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 beneﬁcial. 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.’
Efﬁciency of Blending: To illustrate that blending is indeed beneﬁcial 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 signiﬁcantly. For larger
graphical models, we expect the differences to be even more signiﬁcant.
4 D ISCUSSION & C ONCLUSION
Joint training of neural networks and graphical models: Neural Networks have been incorpo-
rated as unary potentials in graphical models. One of the earliest works by Bridle (1990) jointly opti-
mizes a system consisting of multilayer perceptrons and hidden Markov models for speech recogni-
tion. 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 con-
trast, 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 = 0. More recently, Li
& Zemel (2014) use a hinge loss to learn the unary term deﬁned as a neural net, but keep the pairwise
potentials ﬁxed ( 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 deﬁned 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 efﬁcient algorithm. Importantly any order of block-updates is possible. It remains an open
problem to ﬁnd the optimal tradeoff.
We have proposed an efﬁcient 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 classiﬁcation 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 strate-
gies. 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.
9
Accepted as a workshop contribution at ICLR 2015
ACKNOWLEDGMENTS
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
Bengio, Y ., Lamblin, P., Popovici, D., and Larochelle, H. Greedy Layer-Wise Training of Deep Networks. In
Proc. NIPS , 2007.
Bottou, L., Bengio, Y ., and LeCun, Y . Global training of document processing systems using graph transformer
networks. In Proc. CVPR , 1997.
Bridle, J. S. Training stochastic model recognition algorithms as networks can lead to maximum mutual infor-
mation estimation of parameters. In Proc. NIPS , 1990.
Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., and Kuksa, P. Natural language processing
(almost) from scratch. JMLR , 2011.
de Campos, T. E., Babu, B. R., and Varma, M. Character recognition in natural images. In Proc. VISAPP , 2009.
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image
database. In Proc. CVPR , 2009.
Deng, J., Ding, N., Jia, Y ., Frome, A., Murphy, K., Bengio, S., Li, Y ., Neven, H., and Adam, H. Large-Scale
Object Classiﬁcation using Label Relation Graphs. In Proc. ECCV , 2014.
Do, T.-M.-T. and Artieres, T. Neural conditional random ﬁelds. In Proc. AISTATS , 2010.
Domke, J. Structured Learning via Logistic Regression. In Proc. NIPS , 2013.
Eigen, D., Rolfe, J., Fergus, R., and LeCun, Y . Understanding Deep Architectures using a Recursive Convolu-
tional Network. In Proc. ICLR , 2014.
Girshick, R., Donahue, J., Darrell, T., and Malik, J. Rich feature hierarchies for accurate object detection and
semantic segmentation. In Proc. CVPR , 2014.
Hariharan, B., Arbel ´aez, P., Girshick, R., and Malik, J. Simultaneous detection and segmentation. In Proc.
ECCV , 2014.
Hazan, T. and Urtasun, R. A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Struc-
tured Prediction. In Proc. NIPS , 2010.
Hinton, G. E. and Salakhutdinov, R. R. Reducing the dimensionality of data with neural networks. Science ,
2006.
Hinton, G. E., Sejnowski, T. J., and Ackley, D. H. Boltzmann Machines: Constraint Satisfaction Networks that
Learn. Technical report, University of Toronto, 1984.
Jia, Y . Caffe: An Open Source Convolutional Architecture for Fast Feature Embedding. http://caffe.
berkeleyvision.org/ , 2013.
Koller, D. and Friedman, N. Probabilistic Graphical Models: Principles and Techniques . MIT Press, 2009.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. ImageNet Classiﬁcation with Deep Convolutional Neural
Networks. In Proc. NIPS , 2013.
Larochelle, H., Erhan, D., Courville, A., Bergstra, J., and Bengio, Y . An empirical evaluation of deep architec-
tures on problems with many factors of variation. In Proc. ICML , 2007.
LeCun, Y ., Bottou, L., Bengio, Y ., and Haffner, P. Gradient-based learning applied to document recognition.
Proceedings of the IEEE , 1998.
Lee, H., Grosse, R., Ranganath, R., and Ng, A. Y . Convolutional deep belief networks for scalable unsupervised
learning of hierarchical representations. In Proc. ICML , 2009.
Li, Y . and Zemel, R. High Order Regularization for Semi-Supervised Learning of Structured Output Problems.
InProc. ICML , 2014.
10
Accepted as a workshop contribution at ICLR 2015
Ma, J., Peng, J., Wang, S., and Xu, J. A conditional neural ﬁelds model for protein threading. Bioinformatics ,
2012.
Meltzer, T., Globerson, A., and Weiss, Y . Convergent Message Passing Algorithms: a unifying view. In Proc.
UAI, 2009.
Meshi, O., Sontag, D., Jaakkola, T., and Globerson, A. Learning Efﬁciently with Approximate inference via
Dual Losses. In Proc. ICML , 2010.
Morris, J. and Fosler-Lussier, E. Conditional random ﬁelds for integrating local discriminative classiﬁers. IEEE
Trans. Audio, Speech, and Language Processing , 2008.
Nowozin, S., Rother, C., Bagon, S., Sharp, T., Yao, B., and Kohli, P. Decision tree ﬁelds. In Proc. ICCV , 2011.
Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann,
1988.
Peng, J., Bo, L., and Xu, J. Conditional Neural Fields. In Proc. NIPS , 2009.
Prabhavalkar, R. and Fosler-Lussier, E. Backpropagation training for multilayer conditional random ﬁeld based
phone recognition. In Proc. ICASSP , 2010.
Salakhutdinov, R. R. and Hinton, G. E. An Efﬁcient Learning Procedure for Deep Boltzmann Machines. Neural
Computation , 2012.
Schwing, A. G. Inference and Learning Algorithms with Applications to 3D Indoor Scene Understanding . PhD
thesis, ETH Zurich, 2013.
Socher, R., Huval, B., Bhat, B., Manning, C. D., and Ng, A. Y . Convolutional-Recursive Deep Learning for 3D
Object Classiﬁcation. In Proc. NIPS , 2012.
Tompson, J., Jain, A., LeCun, Y ., and Bregler, C. Joint Training of a Convolutional Network and a Graphical
Model for Human Pose Estimation. In Proc. NIPS , 2014.
Wainwright, M. J. and Jordan, M. I. Graphical Models, Exponential Families and Variational Inference . Foun-
dations and Trends in Machine Learning, 2008.
Wainwright, M. J., Jaakkola, T., and Willsky, A. S. A new class of upper bounds on the log partition function.
Trans. Information Theory , 2005.
Weiss, Y ., Yanover, C., and Meltzer, T. MAP Estimation, Linear Programming and Belief Propagation with
Convex Free Energies. In Proc. UAI , 2007.
Wiegerinck, W. and Heskes, T. Fractional belief propagation. In Proc. NIPS , 2003.
Xu, J., Schwing, A. G., and Urtasun, R. Tell me what you see and I will show you where it is. In Proc. CVPR ,
2014.
Yedidia, J. S., Freeman, W. T., and Weiss, Y . Constructing free-energy approximations and generalized belief
propagation algorithms. Trans. Information Theory , 2005.
Zeiler, M. D. and Fergus, R. Visualizing and Understanding Convolutional Networks. In Proc. ECCV , 2014.
11