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