Structured Prediction with Output Embeddings
for Semantic Image Annotation
Ariadna Quattoni1 , Arnau Ramisa2 , Pranava Swaroop Madhyastha3
Edgar Simo-Serra4 , Francesc Moreno-Noguer2
1 Xerox Research Center Europe, ariadna.quattoni@xrce.xerox.com
2 Institut de Robòtica i Informàtica Industrial (CSIC-UPC), {aramisa,fmoreno}@iri.upc.edu
3 TALP Research Center, Universitat Politècnica de Catalunya, pranava@cs.upc.edu
4 Waseda University, esimo@aoni.waseda.jp

Abstract
We address the task of annotating images withsemantic tuples. Solving this problem requires
an algorithm able to deal with hundreds ofclasses for each argument of the tuple. In
such contexts, data sparsity becomes a key
challenge. We propose handling this sparsity by incorporating feature representationsof both the inputs (images) and outputs (argument classes) into a factorized log-linear
model.

1

Introduction

Many important problems in machine learning canbe framed as structured prediction tasks where thegoal is to learn functions that map inputs to structured outputs such as sequences, trees or generalgraphs. A wide range of applications involve learning over large state spaces, e.g., if the output is alabeled graph, each node of the graph may take values over a potentially large set of labels. Data sparsity then becomes a challenge, as there will be many
classes with very few training examples.
Within this context, we are interested in the taskof predicting semantic tuples for images. That is,given an input image we seek to predict what are
the events or actions (referred here as predicates),
who and what are the participants (referred here as
actors) of the actions and where is the action taking
place (referred here as locatives). For example, animage might be annotated with the semantic tuples:
hrun, dog, parki and hplay, dog, grassi. We calleach field of a tuple an argument.
To handle the data sparsity challenge imposed by
the large state space, we will leverage an approachthat has proven to be useful in multiclass and multilabel prediction tasks (Weston et al., 2010; Akata
et al., 2013). The idea is to represent a value foran argument a using a feature vector representation
φ ∈ IRn . We will integrate this argument representation into the structured prediction model.
In summary, our main contribution is to propose an approach that incorporates feature representations of the outputs into a structured prediction
model, and apply it to the problem of annotating
images with semantic tuples. We present an experimental study using different output feature representations and analyze how they affect performance fordifferent argument types.

2

Semantic Tuple Image Annotation

Task: We will address the task of predicting semantic tuples for images. Following Farhadi et al.
(2010), we will focus on a simple semantic representation that considers three basic arguments: predicate, actors and locatives. For example, in the tuple
hplay, dog, grassi, “play” is the predicate, “dog” isthe actor and “grass” is the locative.
Given this representation, we can formally define our problem as that of learning a function
θ : X × P × A × L → IR that scores thecompatibility between images and semantic tuples.
Here X is the space of images; P , A and L are discrete sets of predicate, actor and locative arguments
respectively, and hp a li is a specific tuple instance.
The overall learning process is illustrated in Fig. 1.
Dataset: For our experiments we used a subsetof the Flickr8k dataset, proposed in Hodosh et al.
(2013). This dataset (subset B in Fig. 1) consistsof 8,000 images from Flickr of people and animals

Training'Data'
U) (Imagenet):) Images) annotated) with)keywords) (cheap,) exploits) readily) available)
dataset))Q) (Flickr8K):) Images) annotated) with)descripJve) sentences) (relaJvely) cheap,)
exploits)readily)available)resources))L) (SPMDataset):) Images) annotated) with)descripJve) sentences) and) semanJc) tuples)(this) is) a) small) subset) of) Q,) expensive)
annotaJon,)requires)experJse))

Convolu2onal'NN'(Trained)using)U)))
Training'Image'x (From!Q)'
Image'Features'< ϕA(x), ϕP(x), ϕL(x) >Training'Senten2al'Descrip2ons'(From'Q)'

Seman2c'Tuples'A)brown)dog)is)running)in)a)grassy)plain.)A)brown)dog)runs)along)a)path)in)the)grass.)
Dog)running)in)ﬁeld.))Dog)running)in)narrow)dirt)path.)The)dog)is)running)through)the)uncut)grass.)<act=dog,)pre=run,)loc=plain>)<act=dog,)pre=run,)loc=grass>)<act=dog,)pre=run,)loc=ﬁeld>)<act=dog,)pre=run,)loc=path>)<act=dog,)pre=run,)loc=grass>))

Embedded'CRF''(Implicitly)induces)embedding)of)image)features)and)arguments))

Image'to'
Seman2c'Tuple'
Predictor'

Seman2c'Tuple'Extractor'(Trained)using)L)))

Figure 1: Overview of our approach. First, images x ∈ A are represented using image features φs (x), and semantic tuples are
obtained applying our semantic tuple extractor (learned from the subset C) to their corresponding captions. The resulting enlarged
training set, is used to train our embedded CRF model that maps images to semantic tuples.

(mostly dogs) performing some action, with fivecrowd-sourced descriptive captions for each one.
We first manually annotated 1,544 captions, corresponding to 311 images (approximately one thirdof the development set (subset C in Fig. 1), producing more than 2,000 semantic tuples of predicate, actor and locative. For the experiments we partitioned
the images and annotations into training, validationand test sets of 150, 50 and 100 images respectively.
Data augmentation: To enlarge the manually annotated dataset we trained a model able to predict
semantic tuples from captions using standard shallow and deep linguistic features (e.g., POS tags, dependency parsing, semantic role labeling). We extract the predicates by looking at the words tagged
as verbs by the POS tagger. Then, the extraction ofarguments for each predicate is resolved as a classification problem.
More specifically, for each detected predicate in a
sentence we regard each noun as a positive or negative training example of a given relation depending on whether the candidate noun is or is not anargument of the predicate. We use these examples
to train a SVM classifier that predicts if a candidate
noun is an argument of a given predicate based on
several linguistic features computed over the syntactic path of the dependency tree that connects them.
We run the learned tuple predictor model on all thecaptions of the Fickr8k dataset to obtain a larger
dataset of 8,000 images paired with semantic tuples.

3

Bilinear Models with Output Features

In this section we explain how we incorporate output feature representations into a factorized linear
model. For simplicity, we will consider factorized

sequence models over sequences of fixed length.
However, it should not be hard to see that all theideas presented here can be easily generalized toother structured prediction settings.
Let y = [y1 . . .yT ] be a set of labels and S =[S1 , . . ., ST ] be the set of possible label values,
where yi ∈Si . We are interested in learning a modelthat computes P (y|x), i.e., the conditional probability of a sequence y given some input x. We willconsider factorized log-linear models that take theform:expθ(x,y)
P (y|x) = P(1)
θ(x,y)y exp
The scoring function θ(x, y) is modeled as a sum of
unary and binary bilinear potentials and is definedas:θ(x, y) =TX
t=1

vy>t Wt φ(x, t) +T
Xvy>t Zt vyt+1 (2)t=1where vyt ∈ IRnt is a nt −dimensional feature representation of label arguments yt ∈St and φ(x, t) ∈IRdt is a dt −dimensional feature representation of
the tth input factor of x.
The first set of terms in the above equation areusually referred as unary potentials and measure thecompatibility between a single state at t and the feature representation of input factor t. The second setof terms are the binary potentials and measure thecompatibility between pairs of states at adjacent factors. The scoring θ(x, y) function is fully parameterized by the unary parameter matrices Wt ∈IRnt ×dt
and the binary parameter matrices Zt ∈IRnt ×nt .
The main idea is to define a feature space where
semantically similar labels will be close. Like in themultilabel scenario (Weston et al., 2010; Akata etal., 2013), having full feature representations for arguments will allow us to share information acrossdifferent classes and generalize better. With a good
output feature representation, our model should be
able to make sensible predictions about pairs of arguments that it has not observed at training. This iseasy to see: consider a case were we have a pair ofarguments represented with feature vectors a1 anda2 and suppose that we have not observed the factor
a1 , a2 in our training data but we have observed thefactor b1 , b2 . Then if a1 is close in the feature space
to argument b1 and a2 is close to b2 our model will
predict that a1 and a2 are compatible. That is it willassign probability to the factor a1 , a2 which seems
a natural generalization from the observed trainingdata.
Now we show that the rank of W and Z have useful interpretations. Let W = U ΣV be the singularvalue decomposition of W . We can then write unarypotentials: vy> W φ(x, t) as: vy> U Σ [V φ(x, t)] Thus
we can regard the bilinear form as a function computing a weighted inner product over some real embedding vy> U representing state y and some real embedding [V φ(x, t)] representing input factor t. The
rank of W gives us the intrinsic dimensionality ofthe embedding. Thus if we want to induce shared
low-dimensional embeddings across different states
it seems reasonable to impose a low rank penalty on
W . Similarly, let Z = U ΣV be now the singularvalue decomposition of Z. We can write the binary
potentials vy> Zvy0 as: vy> U Σ V vy0 and thus the binary potentials compute a weighted inner productbetween a real embedding of state y and a real embedding of state y 0 . As before, the rank of Z gives us
the intrinsic dimensionality of the embedding and,to induce a low dimensional embedding for binary
potentials, we will impose a low rank penalty on Z.
After having described the type of scoring functions we are interested in, we now turn our attention to the learning problem. That is, given
a training set D = {hx yi} of pairs of inputs x and output sequences y we need to learn
the parameters {W } and {Z}. For this purpose
we will do standard max-likelihood estimation andfind the parameters that minimize the conditional
negative log-likelihood of the data in D. Thatis, we will find the {W } and {Z} that mini-mize
P the following loss function L(D, {W }, {Z}):− hx yi∈D logP (y|x; {W }, {Z}) Recall that weare interested in learning low-rank unary and binary
potentials. To achieve this we take a common approach which is to use as the nuclear norm |W |∗ and|Z|∗ as a convex approximation of the rank function,
the final optimization problem becomes:
X
α|Wt |∗ + β|Zt |∗ (3)min{W } L(D, {W }) +tP

where L(D, {W }) =d∈D loss(d, {W }) is thenegative log likelihood function and α and β are
two constants that control the trade off between
minimizing the loss and the implicit dimensionalityof the embeddings. We use a simple optimization
scheme known as Forward Backward Splitting, or
FOBOS (Duchi and Singer, 2009).
For our task we will consider a simple factorized scoring function: θ(x, hp a li) that has one
factor associated with the locative-predicate pairand one factor associated with the predicate-actor
pair. Since this corresponds to a chain structure,argmaxt∈T θ(x; hp a li) can be efficiently computed
using Viterbi decoding in time O(N 2 ), where N =max(|P |, |A|, |L|). Similarly, we can also find the
top k predictions in O(kN 2 ). Thus for this application the scoring function of the bilinear CRF willtake the form of:θ(x, hp a li) = λloc (l)> Wloc φloc (l)+λpre (p)> Wpre φpre (p)+λact (a)> Wact φact (a)loc+φloc (l)> Wpre
φpre (p)pre+φpre (p)> Wact
φact (a) (4)The unary potentials measure the compatibility between an image and a semantic argument, the firstbinary potential measures the compatibility between
a locative and a predicate, and the second binary potential measures the compatibility between a predicate and an actor. The scoring function is fully parameterized by the unary parameter matrices Wloc ∈IRdl ×nl , Wpre ∈ IRdp ×np and Wa ∈ IRda ×na andloc ∈ IRnl ×np andthe binary parameter matrices Wpre
pre
Wact ∈ IRnp ×na . Where, nl , np and na are the dimensionality of the locatives, predicates and actors
feature representations, respectively and dl , dp andda are the dimensionality of the image representations. Notice that if we let the argument representation φt (r) ∈ IR|St | be an indicator vector for label
argument t, we obtain the usual parametrization ofa standard factorized linear model, while having a
dense feature representations for arguments insteadof indicator vectors will allow us to share information across different classes.

4

Representing Semantic Arguments

We will conduct experiments with two different feature representations: 1) Fully unsupervised
Skip-Gram based Continuous Word Representations(SCWR) representation (Mikolov et al., 2013) and
2) A feature representation computed using thehcaption, semantic-tuplesi pairs, that we call Semantic Equivalence Representation (SER).
We decided to exploit the dataset of captions
paired with semantic tuples to induce a useful feature representation for arguments. The idea is quite
simple: we wish to leverage the fact that any pairof semantic tuples associated with the same image
will be likely describing the same event. Thus,
they are in essence different ways of lexicalizing
the same underlying concept. Let’s look at a concrete example. Imagine that we have an image annotated with the tuples: hplay, dog, wateri andhplay, dog, riveri. Since both tuples describe thesame image, it is quite likely that both “river” and“water” refer to the same real world entity, i.e,
“river” and “water” are ’semantically equivalent’for this image. Using this idea we can build a representation φloc (i) ∈ IR|L| where the j-th dimension corresponds to the number of times the argument j has been semantically equivalent to argument i. More precisely, we compute the probability that argument j can be exchanged with argumentsri as: P[i,j]Where [i, j]sr is the number of times
j [i,j]srthat i and j have appeared as annotations of the sameimage and with the same other arguments. For example, for the actor arguments [i, j]sr represents thenumber of time that actor i and actor j have appearedwith the same locative and predicate as descriptionsof the same image.

5

Related WorkIn recent years, some works have tackled the problem of generating rich textual descriptions of images. One of the pioneers is (Kulkarni et al., 2011),

where a CRF model combines the output of several
vision systems to produce input for a language generation method. In Farhadi et al. (2010), the authors
find the similarity between sentences and images ina “meaning” space, represented by semantic tuples
which are very similar to our triplets. Other works
focus on a simplified problem: ranking of humangenerated captions for images. Hodosh et al. (2013)
propose to use Kernel Canonical Correlation Analysis to project images and their captions into a joint
representation space, in which images and captions
can be related and ranked to perform illustration andannotation tasks. Socher et al. (2014) also address
the ranking of images given a sentence and viceversa using a common subspace learned via Recursive Neural Networks. Other recent works also exploit deep networks to address the problem (Vinyals
et al., 2015; Karpathy and Fei-Fei, 2015). Using label embeddings combined with bilinear forms has
been previously proposed in the context of multiclass and multilabel image classification (Weston etal., 2010; Akata et al., 2013).

6

Experiments

For image features we use the 4,096-dimensional
second to last layer of BVLC implementation of‘AlexNet’ ImageNet model, a Convolutional Neural Network (CNN) as described in Jia et al. (2014).
To test our method we used the 100 test images thatwere annotated with ground-truth semantic tuples.
To measure performance we first predict the top tuple for each image and then measure accuracy foreach argument type (i.e. the number of correct predictions among the top 1 triplets). The regularization
parameters of each model were set using the validation set. We compare the performance of the following models: 1) Baseline Separate Predictors (SPred): We consider a baseline made of independent
predictors for each argument type.
More specifically we train one-vs-all SVMs (wealso tried multi-class SVMs but they did not improve performance) to independently predict locatives, predicates and actors. For each argument typeand candidate label we have a score computed by
the corresponding SVM. Given an image we generate the top tuples that maximize the sum of scores foreach argument type; 2) Baseline KCCA: This model
implements the Kernel Canonical Correlation Anal-<act=people,pre=perform,loc=air>33<act=people,pre=jump,loc=air>33<act=people,pre=wear,loc=air>33<act=people,pre=watch,loc=air>33<act=people,pre=perform,loc=pool>33<act=people,pre=sit,loc=air>33<act=people,pre=gather,loc=air>33<act=dog,pre=run,loc=water>3<act=boy,pre=play,loc=ﬁeld>3<act=dog,pre=run,loc=grass>3
TRAINING(SENTENCES(
A3guy3is3doing3a3skateboard3trick3in3front3of3a3crowd3
A3man3is3skateboarding3in3front3of3a3group3of3people.3
A3skateboarder3performs3a3trick3in3front3of3a3large3crowd3.3333
A3skateboarder3leaping3from3a3pool3in3front3of3a3crowd.333
Skateboarder3does3tricks3in3front3of3crowd3while3photographer33
watches3333<act=man,3pre=ride,3loc=street>3 <act=girl,pre=sit,loc=pool>3 <act=people,pre=sit,loc=camera>3
Incorrect(loca+ve(&(ac+on(

Incorrect(actor(

Incorrect(actor(

Incorrect(actor(&(ac+on(

Incorrect(actor(&(loca+ve(

eet>3<act=dog,3pre=run,3loc=water>3<act=dog,pre=stand,loc=ﬁeld>3 <act=dog,pre=perform,loc=air>3 <act=woman,pre=sit,loc=pool>3 <act=player,pre=hold,loc=football>3<act=doFigure 2: Samples of predicted tuples. Top-left: Examples of visually correct predictions. Bottom: Typical errors on one orseveral arguments. Top-right: Sample image and its top predicted tuples. The tuples in blue were not observed neither in the
SP-Dataset nor in the automatically enlarged dataset. Note that all of them are descriptive of what is occurring in the scene.

ysis approach of Hodosh et al. (2013). We first notethat this approach is able to rank a list of candidate
captions but cannot directly generate tuples. To generate tuples for test images, we first find the caption
in the training set that has the highest ranking score
for that image and then extract the corresponding semantic tuples from that caption; 3) Indicator Features (IND), this is a standard factorized log-linear
model that does not use any feature representation
for the outputs; 4) A model that uses the skip-gram
continuous word representation of outputs (SCWR);
5) A model that uses that semantic equivalence representation of outputs (SER); 6) A combined modelthat makes predictions using the best feature representation for each argument type (COMBO).

LOC
PRED
ACT
MEAN

S-Pred
15
11
30
18.6

KCCA
23
20
25
22.6

IND
32
24
52
36

SCWR
28
33
51
37.3

SER
33
25
50
36

COMBO

39.3

Table 1: Comparison of Output Feature Representation.

Table 1 shows the results. We observe that our
proposed method performs significantly better thanthe baselines. The second observation is that thebest performing output feature representation is different for different argument types, for the locatives
the best representation is SER, for the predicates is
the SCWR and for the actors using an output feature representation actually hurts performance. The

biggest improvement we get is on the predicate arguments, where we improve almost by 10% in average precision over the baseline using the skip-gramword representation. Overall, the model that uses
the best representation performs better than the indicator baseline.
Regarding the rank of the parameter matrices,
we observed that the learned models can work welleven if we drop the rank to 10% of its maximum
rank. This shows that the learned models are efficient in the sense that they can work well with lowdimensional projections of the features.

7

Conclusion

In this paper we have presented a framework for exploiting input and output embeddings in the context
of structured prediction. We have applied this framework to the problem of predicting compositional semantic descriptions of images. Our results show theadvantages of using output embeddings and inducing low-dimensional embeddings for handling large
state spaces in structured prediction problems. The
framework we propose is general enough to consider
additional sources of information.

8

Acknowledgments

This work was partly funded by the Spanish
MINECO project RobInstruct TIN2014-58178-R
and by the ERA-net CHISTERA projects VISEN
PCIN- 2013-047 and I-DRESS PCIN-2015-147.
The authors are grateful to the Nvidia donation program for its support with GPU cards.

References[Akata et al.2013] Zeynep Akata, Florent Perronnin, Zaid
Harchaoui, and Cordelia Schmid. 2013. Labelembedding for attribute-based classification. In Proc.
IEEE Conference on Computer Vision and Pattern
Recognition (CVPR).
[Duchi and Singer2009] John Duchi and Yoram Singer.
2009. Efficient online and batch learning using forward backward splitting. Journal of Machine Learning Research (JMLR), 10:2899–2934.
[Farhadi et al.2010] Ali Farhadi,
Mohsen Hejrati,
MohammadAmin Sadeghi, Peter Young, Cyrus
Rashtchian, Julia Hockenmaier, and David Forsyth.
2010. Every picture tells a story: Generating sentences from images. In Proc. European Conference
on Computer Vision (ECCV).
[Hodosh et al.2013] Micah Hodosh, Peter Young, and Julia Hockenmaier. 2013. Framing image description as a ranking task: Data, models and evaluation
metrics. Journal of Artificial Intelligence Research(JAIR), 47:853–899.
[Jia et al.2014] Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan Long, Ross Girshick,Sergio Guadarrama, and Trevor Darrell. 2014. Caffe:
Convolutional architecture for fast feature embedding.
arXiv preprint arXiv:1408.5093.
[Karpathy and Fei-Fei2015] Andrej Karpathy and Li FeiFei. 2015. Deep visual-semantic alignments for gen-erating image descriptions. In Proc. IEEE Conference
on Computer Vision and Pattern Recognition (CVPR).
[Kulkarni et al.2011] Girish Kulkarni, Visruth Premraj,
Sagnik Dhar, Siming Li, Yejin Choi, Alexander C
Berg, and Tamara L Berg. 2011. Baby talk: Understanding and generating image descriptions. In
Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
[Mikolov et al.2013] Tomas Mikolov, Kai Chen, Greg
Corrado, and Jeffrey Dean. 2013. Efficient estimationof word representations in vector space. In Proc. International Conference on Learning Representations(ICLR).
[Socher et al.2014] Richard Socher, Andrej Karpathy,
Quoc V. Le, Christopher D. Manning, and Andrew Y.
Ng. 2014. Grounded compositional semantics forfinding and describing images with sentences. Transactions of the Association of Computational Linguistics (TACL), 2:207–218.
[Vinyals et al.2015] Oriol Vinyals, Alexander Toshev,
Samy Bengio, and Dumitru Erhan. 2015. Show andtell: A neural image caption generator. In Proc. IEEE
Conference on Computer Vision and Pattern Recognition (CVPR).
[Weston et al.2010] Jason Weston, Samy Bengio, andNicolas Usunier. 2010. Large scale image annotation: Learning to rank with joint word-image embeddings. In Proc. European Conference on Computer
Vision (ECCV).