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
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