We address the tasks of image classi cation and tagging through a transductive approach that automatically learns to project the di erent images onto a common latent space. This learned representation is then used to classify the images. We construst a graph between images and concepts using the deep representations given by ImageCLEF and WordNet database, and we exploit the idea that two connected nodes will tend to have a similar latent representation. This assumption allows us to learn correlations between the labels of connected images.
The ImageCLEF 2015[
The system we propose is based on a model [?] that projects nodes of a graph
within a vector space (typically, of dimension 100-200). This model requires
that some nodes be labeled, and uses this information within the embedding
process. To leverage ImageNet data, where no relationship links images together,
we had to build a graph. We experimented with di erent ways to construct a
simple graph based on the output of the ImageNET CNN representations and
the WordNet database[
The article is organized as follows: Section 2 presents an overview of our model and how we construct the graph based on the images and the WordNet database, Section 3 the representation and the classi er learning, Section 4 our algorithm, and Section 5 outlines our results and conclusions.
We propose a solution that relies on the exploitation of the correlations that exists between images that have a similar 1000 dimensional activations of the fc8 layer of Oxford VGGs 16-layer Convolutional Neural Network model (OVCNN) given in the ImageCLEF challenge. It aims at taking directly into account the correlations between the CNN-labels of connected images. The underlying idea of this model is the following: { We construct a graph mixing images and concepts based on the CNNrepresentation and the WordNet database. { Each node is mapped onto a latent representation in a vectorial space RZ .
The latent space is common to all node types (images and concepts). { This latent representation de nes a metric in RZ such that two connected nodes tend to have a close representation (smoothness assumption ). { All the nodes and relations are not equal w.r.t. their position in the graph, their number of neighbors, etc. We use two functions, i and i;j , to model the importance of nodes and the relationships in the embedding process. { A classi cation function is learned for the images. It takes as input a latent image representation and computes associated class labels.
All the notation used in this working note are summarized in Table 1.
xi Ak zi x` zcopy i T T ti r(i; j) i !r j R N x1 Njr E Er CYtt yi yic
Node of the graph 1000 dimensional activations of the fc8 layer of an image k Latent representation of node xi Numerical copy of zi Set of possible nodes types Number of nodes types Type of node xi Relation type between node xi and xj Relation of type r from i to j Number of relation's type Number of nodes Labeled nodes used for the classi cation task Number of neighbors of xj considering the relation r Total number of edges Total number of edges of type r Set of categories associated to the type of node t Cardinality of Yt Vector of categories for the node xi Value of category c for the node xi To apply our method, we need to construct a graph. The resulting graph is composed of nodes of two types, images and (WordNet) concepts. To construct the graph, we connect images to a subset of the concepts and then enrich this graph using Wordnet relationships between concepts.
We rst directly use the representation Ak of an image, i.e. the 1000 dimensional activations of the OV-CNN. Each dimension of this vector corresponds to a label, and we suppose that an image is labeled by the ith label if its corresponding component is above a threshold 2 R. In that case, each label being a precise WordNet concept, we connect the image to the corresponding concept in the graph.
We then use WordNet to connect concepts together. We selected two relationships that may be important when trying to label images: the hypernymhyponym relationship (\is-a") and the meronymy relationship (\part of"). In order to keep the graph size manageable, we started from the concepts of the CNN representation and added all the concepts that would be necessary to link the di erent concepts together. For example, in the gure below, we have four images. Two are classi ed "bomber" by the VO-CNN two "jet plane". Both concepts are hyponyms of airplane. We thus have the corresponding graph : bomber
jet plane airplane
The nal graph has 25,730,835 image-concept edges and 4,309 concept-concept edges. 2.2
The initial training set for subtask 1 contains 1,979 labeled images (there are 500,000 images in the entire dataset) for 250 concepts. That give us 7.9 images per concept on average, which is a relatively small number.
To increase the number of training examples, we again used the Ak representation and the corresponding OV-CNN concepts. We used another threshold 2 R to determine when an image should be labeled with a given OV-CNN concept. In practice, given an image k, if the i-th component of Ak is bigger than we check if the corresponding OV-CNN concept is an hypernym of an ImageCLEF concept Cclef . If then, we add the image k to the training set labeled with Cclef .
When = 20, the labeled images in our training set contains 43.970 images (175.9 images per concept), and when = 10, 446.130 images (1784.5 images per concept). 3 3.1
The mapping onto the latent space is learned so that the labels for each type of node can be predicted from the latent representations. For that, we consider a linear classi cation function for each type of node k denoted by f k. This function takes as input a node representation and outputs the predicted label(s).
The f -functions can be learned by minimizing a loss on labeled data as follows:
` X i (f ti (zi); yi) i=1 (1) where (f ti (zix); yi) is the loss of predicting labels f ti (zi) instead of observed labels yi. Here i represents the relative importance of node i in the graph. For example, i = 1=N would de ne a model where all nodes have the same importance.
In our case, in order to set the value of i, we think our model should consider that all nodes have not the same importance, so we should be able to emphasis on more central nodes with regard to di erent relations. To do so, we use what makes a node more important is it has many neighbors of di erent types : i = R1 PR Nir
r=1 Er In our implementation, we use a hinge-loss function for :
Ct (f t(z); y) = X max(0; 1 k=1 ykf t;k(z)) (2) where yk is the desired score of category k for node x ( 1 or +1) and f t;k(z) is the predicted score of category k by the model. 3.2
Let us denote by zi 2 RZ the hidden representation of node xi which is a vector of size Z. When updating zi, in order to capture the graph metric in the X j i;j jjzi zj0 jj2 We are using an L2 norm in the latent space, but other metrics could be used as well. Furthermore, i;j aims at considering the importance of an edge w.r.t. the hole graph and the shape of it around this speci c edge.
We assume that all the edges of the graph should have the same impact 1 regardless of their predominance ( i;j / Er(i;j) ). Then, as in the PageRank algorithm, we assume that the information coming from a neighbor j of i should 1 be divided equally through his neighbors of the same type as i ( i;j / Nr(i;j) ). j Thus we set i;j =
1 RN r(i;j)Er(i;j) j (3) (4) latent space, we use the following loss which embodies the metric smoothness assumption and forces linked nodes to have similar representations: 4
Learning consists in minimizing the loss function de ned in Equation 4. Di erent optimization methods can be considered. We have used a Stochastic Gradient Descent Method to learn the latent representations.
Furthermore, we can remark that the i;j and i can also be understood as a speci c way of sampling during the SGD. Actually, if we rstly choose uniformly the type of edge then choose uniformly an edge given that type and pick the nodes from the chosen edge we update a given representation zi in expectation R1 PR r=1 NEirr times r=1 NEirr times for the classi cation term and R1 PR for the graph regularization one. Adding the PageRank division in the graph regularization, we nd out our previous assumptions. The algorithm is detailed below. 3.3
The nal expected objective loss of our model combines the classi cation and regularization losses 1 and 3:
` L(z; ) = X i=1 i (f ti (zi); yi) +
X i;j i;j jjzi zj0 jj2 The minimization of this function aims at nding a trade-o between the smoothness over the latent representations of correlated nodes Z and the predicted observed labels in Yk. Optimizing this loss allows us to learn: { The projection zi of each node xi in the latent space. { The classi cation functions f k for each nodes type k which transform the latent space to categories scores.
For a f i x e d n u m b e r of i t e r a t i o n s
C h o o s e r in R at r a n d o m .
Pick r a n d o m l y an edge i !r j .
If (i `) + r (f ti (zi); yi) zi + `) + r rzi (f ti (zi); yi)
(f tj (zj ); yj ) zi If (j zi zj zj
zj + zi + zj + rzi jjzi rzj jjzi rzj (f tj (zj ); yj ) zj jj2 zj jj2
The algorithm chooses iteratively, with the sampling method explained above, a pair of connected nodes and then make a gradient update over the parameters of the model. If one of the chosen nodes is part of the rst labeled training set, the algorithm rst performs an update according to the rst term of Equation 1. This update { lines 5-6 and 9-10 { consists in successively modifying the parameters of the classi cation function and of the latent representations zi and zj so as to minimize the classi cation loss term.
Here, is the gradient step, and is the trade-o between the classi cation and smoothness terms. 5
As our model is not able to localize a concept in a given image we only present the results of the mean average precision with zero overlap (MAP-0).
N = 250; = 10; = 50 N = 100; = 10; = 50 N = 250; = 10; = 150 N = 100; = 10; = 150 N = 250; = 20; = 150 N = 250; = 20; = 50
As we can see, the bigger the training set is ( is small) the better our model performs. As the graph has many edges our model needs a bigger dimension (N ) in order to adapt to the graph topology. Furthermore we can see that the more we constrain ( is big) the representations of two nodes to be close, the worst the performances get.
The results are quite low compared to other opproaches, but we did not exploit (at least directly) any image related feature. Compared to a random approach, we are still able to extract some information from a graph constructed using some basic information about the classi cation of an image and the relationship between the labels/concepts.
Our methodology would bene t from a real graph linking the images (e.g. a social network), and results would be much improved if using image-based features.
In future work, we will combine this approach with image features to check whether they can bring some further information.
Acknowledgments. This work was supported in part by a grant from the Research Agency ANR (Agence Nationale de la Recherche) under the MLVIS project.