# Sampled Image Tagging and Retrieval Methods on User Generated Content

Karl Ni, Kyle Zaragoza
Yonas Tesfaye, Alex Gude
_Lab41, In-Q-Tel_
<EMAIL_ADDRESS>Charles Foster
_Stanford University_
<EMAIL_ADDRESS>Carmen Carrano, Barry Chen
_Lawrence Livermore_
_National Laboratory_
<EMAIL_ADDRESS>
###### Abstract

Traditional image tagging and retrieval algorithms have limited value as a
result of being trained with heavily curated datasets. These limitations are
most evident when arbitrary search words are used that do not intersect with
training set labels. Weak labels from user generated content (UGC) found in
the wild (e.g., Google Photos, FlickR, etc.) have an almost unlimited number
of unique words in the metadata tags. Prior work on word embeddings
successfully leveraged unstructured text with large vocabularies, and our
proposed method seeks to apply similar cost functions to open source imagery.
Specifically, we train a deep learning image tagging and retrieval system on
large-scale, user generated content (UGC) using sampling methods and joint
optimization of word embeddings. By using the Yahoo! FlickR Creative Commons
(YFCC100M) dataset, such an approach builds robustness to common unstructured
data issues that include but are not limited to irrelevant tags, misspellings,
multiple languages, polysemy, and tag imbalance. As a result, the final
proposed algorithm will not only yield comparable results to state of the art
in conventional image tagging, but will enable new capability to train
algorithms on large, scale unstructured text in the YFCC100M dataset and
outperform cited work in zero-shot capability.

##  1 Introduction

Automated approaches to tag and retrieve images, while distinct from image
detection and localization, have benefited from some of the techniques
developed for detection and localization competitions [26, 5, 16] such as the
rise of convolutional neural networks (CNNs) [30, 27, 14]. Such algorithms
work well because the dataset is well-curated but are unfortunately limited by
the number of keywords that can be used to tag and retrieve images due to a
small training label set. To be useful, deep learning approaches need to
accommodate open vocabulary search, which a practical implementation would
require the extension of training label set to be orders of magnitude larger.

Extending curated datasets requires supervision, where developed algorithms
would need to be tolerant of inevitable labeling errors. Conversely, open
source imagery datasets from Google Photos or FlickR that are created with
user generated content (UGC) have an almost unlimited number and variety of
unique tags that cover much of the vocabulary of the English language. The
problem with metadata tags in such datasets like the Visual Genome project
[13] and to a larger extent the YFCC100M dataset [31] is that they also
include noise in the form of misspellings, unevenly distributed numbers of
tags (including auto-generated ones), different languages, irrelevant and
unduly specific tags, just to name a few problems. Our approach to remedy the
so-called “weak labels” in UGC is to statistically overcome the inherent noise
with the sheer scale of the data.

Leveraging UGC with data scale is non-trivial for a variety of reasons. While
there is an abundance of work addressing _image_ scale in YFCC100M [22], the
focus of our work is on the scale of the _labels_ , which take the form of
noisy metadata tags. The challenge then becomes negotiating matrix operations
on any deep learning architecture that requires a final layer that is
proportional to the number of words. In fact, the number of weights in that
layer is (#hidden units $\times$ #unique tags), roughly 43M parameters in our
case. As reported in [11], the forward and backpropagation of a single batch
on this final layer alone (a final layer that is $\frac{1}{4}$ the size of
ours) takes 1.6 seconds, and certain heuristics must be employed. To put this
in perspective, not considering the rest of the neural network, a single run
through the YFCC100M dataset would take over two weeks.

Fortunately, unstructured text and large vocabulary is well-studied with now-
popular word embeddings [24, 20]. Several works [35, 15, 23] have consequently
sought to exploit word embeddings by projecting image features into the
resulting semantic space. Such efforts primarily focus on zero-shot learning.
Targeting word vectors instead of tags means that the final layer size is no
longer proportional to the number of words. By maintaining static word
vectors, these approaches assume that semantic and syntactic similarity
necessarily equates to visual similarity, which is often not the case as word
co-occurrence and parts of speech often have little to do with visual
appearance. As a result, projecting into word embedding space merely _uses_
the word vectors and do not scale to nor truly train on unstructured UGC.

The proposed method sidesteps this issue by jointly optimizing _both_ image
and word embeddings, while simultaneously addressing the scale issue through
the use of negative sampling and noise contrastive estimation [9] that have
pervaded the natural language processing community [20]. Specifically, we use
the traditional cross-entropy cost function and provide an analytical
comparison to ranking cost functions [35, 3], to which we also apply the
proposed sampling methods for fair comparison. In doing so, we train against
the largest UGC corpus currently available [31], and demonstrate that despite
the issues, automated tagging using a sampled cost function can produce
considerably more useful information than the original tags themselves. More
importantly, we enable the capability that the user can search for an almost
unlimited number of words and retrieve meaningful and relevant images.

##  2 Related Work

Methods for automatic image annotation have ranged from generative [1, 6, 34]
and discriminative models [10] for image tags to nearest neighbor search-based
approaches [18, 8, 32]. Helping to establish this line of research, Makadia et
al. [18] exceeded the state of the art with a simple $k$-nearest neighbor
algorithm combined with a greedy approach to prioritization of tags from
neighboring images. Subsequent work set the current standard for tag
prediction performance using probabilistic models for tag generation that
accounted for the nearness of an image’s neighbors and for the occurrence of
rare tags. The aforementioned studies relied on a set of 15 global and local
image features ([2, 8]; provided at
`http://lear.inrialpes.fr/people/guillaumin/data.php`) that have formed the
basis of subsequent tag prediction research. As datasets grew larger, these
non-parametric approaches became untenable despite producing the best
quantitative retrieval results because complexity intimately relied on the
number of images in the training set, deferring to dual projection methods
[2].

Subsequently, researchers began to focus more attention on the features
themselves. Feature selection [32] on manual features through metric learning
provided an adequate analysis of which manual features provided the most
amount of information. Given their success in image classification [26] and
other domains [36], investigations into combinations of features started to
include deeply learning features [27, 30, 14]. This prompted conflicting
studies, where findings [21] initially favored heavily tuned manual features.
Successive and more thorough/complete studies [19] demonstrated that deep
features not only provided value to feature combinations, but can often
outperform traditional methods on their own. The conclusions have given rise
to demonstrations of the predictive performance in the image tagging problem,
where Kiros and Szepesvari [12] learned binary codes with real-valued image
features derived from an unsupervised, autoencoder-based approach. The
experiments presented in this work opt for pre-trained features111We did,
indeed, do the full backpropagation through the entire neural network, to
little benefit. with our best results coming from _Inception_ features [30],
though we are feature-agnostic and can use any fixed-dimensional vector
representation.

Until recently, the related work in image tagging and retrieval has centered
around earlier, smaller datasets [7, 33] (approximately 20k images, 300 unique
tags) to recently released larger datasets [13, 4] (over 100k/200k images, 5k
object tags). The fact that the maximum vocabulary size of these curated
datasets is on the order of thousands is of particular note since the Oxford
English Dictionary places the count of unique, non-domain specific words in
common use at roughly 170k.222There are 615k definitions (which include plural
forms, different conjugations, and other derivatives of the original word),
and the number of total words in use in the English Language is closer to a
million. Moreover, these annotations have an overwhelming bias towards objects
rather than specific word concepts like actions, numbers, and more abstract
ideas like color.

To accommodate for training vocabulary shortcomings, zero-shot learning,
initially made popular through Socher’s recursive learning efforts [29],
provided an alternative by using the power of semantic information through
word embeddings [20, 24]. Later efforts typically involved some type of joint
embedding [23, 35]. In particular, Fast0Tag [35] identifies a principal
direction in the word embedding space to which to project an image feature.

Instead of zero-shot learning, the proposed algorithm focuses its energy on
one of the basic mantras of deep learning: that the proper way of overcoming
deficits in capability is to introduce more data and add more parameters. To
do so, our approach makes explicit use of the open source YFCC100M dataset
[31]. In contrast to the vocabulary in traditional tagging datasets, the
metadata in the YFCC100M data is seemingly unbounded, where the number of
unique tokens in the metadata tag exceeds 6M words over a variety of ideas.

The earliest work on unstructured imagery in the YFCC100M corpus using deep
learning [22] remained largely unsupervised and sidestepped the vocabulary
scale issue. Other algorithms in an effort led by Facebook [11] followed with
limited success by applying supervised approaches to the weak labels that the
metadata tags provide. The bottleneck, it appeared, was the ability of the
algorithms to train the final layer of the deep learning architecture on
unstructured text in a reasonable amount of time. Alternatively, the domain
that has been particularly successful in approaching the large vocabulary and
unstructured text problems are word vector optimizations like _Glove_ [24] and
_word2vec_ [20]. The proposed method leverages the sampling methods introduced
in _word2vec_ , while comparing a few cost functions. In contrast to
approaches that merely project image features into semantic space [35, 23], we
leverage the embedding cost function itself, using a neural network that
simultaneously optimizes over both words and images to produce a single vector
space that can represent both modalities.

##  3 Approach

Typical deep learning image classifiers target a single concept with a
_softmax_ layer in a neural network. This normalizes to create a probability
distribution that expects a single label for a given image. While the single
label assumption works for ImageNet’s iconic images, it does not apply to
images in the wild where they are coincident with several (probably noisy)
tags.

Figure 1: Training images and tags using “skip-image” optimization.

Instead, we turn to un-normalized cost functions observed by natural language
processing and use optimization strategies rooted in unsupervised and
embedding approaches. Most notably, Restricted Boltzmann Machines and word
embeddings like _word2vec_ rely on some variant of noise contrastive
estimation, where the distribution of foreground (e.g., the surrounding
context of a word) is separated from the distribution of the background (e.g.,
the probability distribution over all words in the corpora). In our case, the
context is the set of tags for each image, and negative samples can be
obtained by sampling from the tag distribution. It is then straightforward use
the skip-gram approach ( Fig. 1) with the following cost function:

$\mathcal{L}(\\{W_{i}\\},\boldsymbol{v}_{p,n})=\sum_{p}^{P}\log\mathbb{E}_{p}\left[\sigma(\boldsymbol{f}_{\\{W_{i}\\}}^{T}\boldsymbol{v}_{p})\right]+\\\
\sum_{n}^{N}\log\mathbb{E}_{n}\left[\sigma(-\boldsymbol{f}_{\\{W_{i}\\}}^{T}\boldsymbol{v}_{n})\right]+\\\
\alpha\sum_{p,p^{\prime}}\sigma(\boldsymbol{v}^{T}_{p}\boldsymbol{v}_{p^{\prime}})+\sum_{p,n}\sigma(-\boldsymbol{v}^{T}_{p}\boldsymbol{v}_{n}),$
(1)

where $\boldsymbol{v}_{p}$, are positively sampled vectors coming from words
the image has been tagged with, $\boldsymbol{v}_{n}$ are the negatively
sampled vectors from the probability distribution over all possible tags, $P$
is the number of positive samples, $N$ is the number of negative samples, and
the feature vector $\boldsymbol{f}$ is parameterized by the set of weights
$\\{W_{i}\\}$ from a neural network $h(\cdot,\\{W_{i}\\})$:

$\boldsymbol{f}_{\\{W_{i}\\}}=h(\boldsymbol{x},\\{W_{i}\\})$ (2)

with inputs being ILSVRC features $\boldsymbol{x}$.

Like _word2vec_ , the first term in (1) positively correlates the feature
vector with the metadata tags, pulling the image closer to the context through
backpropagation over $\\{W_{i}\\}$. The second term pushes the them away from
the background distribution. The final two terms, with $\alpha$ taken to be
small (we use 0.01), serves to promote similarity in co-occurring tags. These
final terms are only useful when we are optimizing over $\boldsymbol{v}$, of
which we provide an analysis later. Fig. 5 depicts the vector projection of
both images ($\boldsymbol{f}$) and text ($\boldsymbol{v}$) into the same joint
vector space using t-SNE dimensionality reduction.

The architecture of our neural network is very similar to that of [35], with
hidden units of

$\text{imfeats}\rightarrow 4096\rightarrow 8192\rightarrow 2048\rightarrow
300\rightarrow\text{wordvecs},$

and we try a variety of _Inception_ and _VGG_ features with a combination of
word vectors (_word2vec_ and _Glove_). Take note that (1) not only takes the
set of weights $\\{W_{i}\\}$ from the neural network $h(\cdot)$ for
parameters, but a key difference between the proposed method and most cited
work [15, 23, 35] is that it is also a function of $\boldsymbol{v}_{p,n}$.
That is, we are also optimizing the word vectors provided we have a large
enough vocabulary.

This makes sense when we note that word embeddings have a tendency to cluster
semantically similar concepts, but these concepts sometimes are not visually
similar. For example, every word embedding model that we have trained using
both _Glove_ and _word2vec_ almost universally place words like “red”,“green”,
and “yellow” very close together, which makes sense semantically. Their
context is the same, because one typically uses colors interchangeably, e.g.,
“I have a (red/yellow) car.” While semantically similar, these words are
visually discriminating. For example, stop signs and green lights portray very
different meanings despite their defining attribute being color. The same can
be said of many other words, including numbers and titles of persons.
Therefore, the word vectors $\boldsymbol{v}_{p}$ in (1) for such instances
should be somewhat separate from each other so that related image projections
$\boldsymbol{f}$ can remain visually distinct.

Inherent in (1) is the idea that positive and negative sampling can converge
to a meaningful result in expectation. A similar approach was initially
attempted [2] through single samples, though quickly abandoned due to updates
being too sparse. In practice, with proper initalization of the final layer
(i.e., using pre-trained word vectors) with a large corpus (we used New York
Times and Wikipedia [17]), reasonable image retrieval results begin appearing
and converging near a single pass through the YFCC100M data, at least for
frequently occurring words. To assess the efficiency of sampling, see Fig. 2
which was created using a smaller corpora where it is possible to use
traditional optimization in the cross-entropy loss function as a comparison
point with respect to sampled loss.

Figure 2: Top: Comparison in F1 optimization in the presence or absence of
sampling. Bottom: Comparison in objective function optimization with and
without joint optimization.

Because we use deep learning to optimize (1), our variables are tensors and we
require the number of samples to be consistent between images for batch
purposes. That is, we must fix $P$ and $N$. Unfortunately, the image metadata
have variable numbers of tags, and we choose a fixed number of positive
samples, chosen uniformly since we make no assumptions on tag ordering.
Although 69% of images in YFCC100M have an average of 7.07 tags, we found that
$P=5$ tags per image works well.

###  3.1 On the Cost Function

The proposed objective (1) stands in stark contrast to prior work based on
projections of images into semantic space based on ranking. Most notably, the
Fast0Tag objective which originates from RankNet can be rewritten to take the
form:

$\mathcal{L}=\beta\sum_{p}\sum_{n}\log\sigma\left(\boldsymbol{f}^{T}(\boldsymbol{v}_{p}-\boldsymbol{v}_{n})\right)$
(3)

At first glance, the form of (3) appears quite different from (1). With some
linear algebra and some simplifying assumptions, the contrasts are not as
great as one might assume. In this section, we quantify the differences, and
we highlight the pitfalls with respect to complexity and accuracy. On the
latter point, (1) can be shown to be analogous to (3) but for two additional
terms.

Let us ignore the last two terms in (1) for now, as they simply tweak
performance. It can be shown that comparisons with the first two terms of the
proposed objective turn out to be a sampled cross-entropy function. Therefore,
the word vectors are simply the last layer on a traditional neural network
where only a few columns actually matter. As discussed, we are sampling $P$
and $N$, but for sake of explanation, let us assume that $P=N$ (it does not),
remove the expectations, and for clarity, let’s assign $L=P=N$. Then,

$\displaystyle\mathcal{L}$ $\displaystyle=$
$\displaystyle\sum_{p}^{L}\log\sigma(\boldsymbol{v}_{p}^{T}\boldsymbol{f}_{n})+\sum_{n}^{L}\log\sigma(-\boldsymbol{v}_{n}^{T}\boldsymbol{f})$
$\displaystyle=$
$\displaystyle\sum_{p}^{L}\sum_{n}^{L}\frac{1}{L}\log\sigma(\boldsymbol{f}^{T}\boldsymbol{v}_{p})+\frac{1}{L}\log\sigma(-\boldsymbol{f}^{T}\boldsymbol{v}_{n})$
$\displaystyle=$
$\displaystyle\sum_{p}^{L}\sum_{n}^{L}\frac{1}{L}\log\left(\sigma(\boldsymbol{f}^{T}\boldsymbol{v}_{p})\sigma(-\boldsymbol{f}^{T}\boldsymbol{v}_{n})\right)$
$\displaystyle=$
$\displaystyle\beta^{\prime}\sum_{p}^{L}\sum_{n}^{L}\log\left(\sigma\left(\boldsymbol{f}^{T}(\boldsymbol{v}_{p}-\boldsymbol{v}_{n})\right)+e^{\boldsymbol{v}_{p}^{T}\boldsymbol{f}}+e^{-\boldsymbol{v}_{n}^{T}\boldsymbol{f}}\right)$

Besides scaling by $\beta^{\prime}=\frac{1}{L}$, the equivalence shown in
(LABEL:eq:derive) is directly comparable because the first term inside the
logarithm mirrors (3). Conceptually, the salient point arises from the idea
that (3) ranks the _difference_ between every positive example to every other
negative example. This inherently maps general vector directionality rather
than the actual correlation between the vectors themselves. Meanwhile, the
extra terms in (LABEL:eq:derive) are dot products between images and words to
maximize or minimize. The effect is essentially to sum nonlinear correlations
between individual images and its relevant individual tags. As is evident in
Table 3 in the results sections, it is these extra terms that lead to an
improvement in performance during conventional tagging. Secondly, such an
effort will also enable the objective function to improve with fewer
constraints, meaning that higher accuracy and quicker training times can be
achieved as seen in Fig. 2 and Table. 1. We compare both objective functions
with and without optimization and sampling in Sec. 5.

Timing Per Epoch
---
| 291 Labels | 925 Labels
| 17665 Images | 102709 Images
| Full | Sampled | Full | Sampled
Fast0Tag [35] | 2.12s | 0.39s | 43.6s | 3.22s
X-Ent | 1.21s | 0.32s | 9.3s | 1.94s
Opt+XE | 1.30s | 0.43s | 10.9 | 2.31s
Table 1: Timing Information.

Also, we are explaining away the non-trivial double sum to make a point, but
its presence is quite significant when considering computational complexity.
In reality, (1) is implemented with computational complexity
$\mathcal{O}(\max(P,N))$ per image. Because of the double sum over $p$ and
$n$, fast0tag has complexity (and memory since we’re using tensor
implementations) that scales according to $\mathcal{O}(PN)$ per image. Without
sampling, if there are more than a few labels per image, this balloons quite
significantly, particularly if there are large numbers of positive labels for
a single image. The issue is that the optimization is essentially ranking
every tag to every other tag for every single image in a minibatch. In the
absence of sampling, cross entropy turns out to be much faster. In our
experiments, transitioning to larger datasets using full optimization (without
sampling) from 291 tags (IAPR TC-12 [7] 2s/epoch) to 925 tags (NUS-WIDE [4],
43s/epoch) was significant, and from 925 tags to 13980 (Visual Genome [13])
was untenable on our TitanX GeForce NVIDIA card due to both memory and time.

###  3.2 Out of Vocabulary Updates

While the tag set in a UGC corpus like YFCC100M has a surprisingly extensive
coverage over the entire English language, it still does not include all
possible words that can be used for image search. As stated previously, we
pre-train on a text corpus, e.g. Wikipedia’s first 8 billion characters [17],
but the set difference between the word corpus and the metadata in the image
corpus is non-trivial. Because we only train on samples in the image corpus,
words in the set difference will never be updated when jointly optimizing in
Sec. 4. The relationship between optimized and unoptimized words quickly
devolves, and the dot product between optimized word vectors and un-optimized
word vectors becomes meaningless.

Figure 3: Jointly optimizing word vectors and image weights.

The approach that we take in Fig. 3 is to simply make a final optimization
pass after training the neural network on the image corpus. Note that this
step makes the most sense when performed _offline_ , simply snapping out-of-
vocabulary words into place. Assuming we have trained a word embedding
beforehand, we can then apply what we know of the semantic relationship
between the out-of-vocabulary words and the in-vocabulary words, i.e., words
that have been optimized when training the neural network.

Let $V_{W}$ be word vectors from the text corpus (e.g., Google News), and
$V_{I}$ be word vectors from the image corpus (e.g., YFCC100M). The set
difference is thus $\\{V_{D}\\}=\\{V_{W}\\}-\\{V_{I}\\}$. Without loss of
generality, let us assume that all words in the image corpus exist in the word
corpus, i.e. $\\{V_{I}\\}\subset\\{V_{W}\\}$ and furthermore, we can organize
$V_{\cup}$ to be ordered in the following manner:

$V_{\cup}=\left[V_{I}|V_{D}\right]$

Before training in Sec. 2, let us preserve the initial word vectors $V_{I}$
and $V_{D}$. Then for the sake of argument, we can write a nonlinear
correlation matrix333Note that for computational purposes, we do not
explicitly construct $C^{(i)}$, but rather store a subset of the original word
vectors and compute dot products online. for every word vector to every other
word vector as:

$C^{(i)}=\sigma\left(\begin{bmatrix}V_{I}^{T}V_{I}&V_{I}^{T}V_{D}\\\
V_{D}^{T}V_{I}&V_{D}^{T}V_{D}\end{bmatrix}\right),$ (5)

where the superscript $i$ denotes the initial semantic relationships of each
word to one another. After training with our image corpus, all the vectors in
$V_{I}$ will have changed while none of the vectors in $V_{D}$ will have been
updated. To update $V_{D}$ in the absence of any image information, we can
only rely on semantic information, which are specified by the relationships in
$C^{(i)}$ the lower and right-hand submatrices of $C^{(i)}$. Specifically, we
wish to match initial and final correlations from seen words to unseen words
and between the unseen words themselves:

$C^{(i)}_{d,m}\log\sigma(\boldsymbol{v}_{d}^{T}\boldsymbol{v}_{m})+(1-C^{(i)})\log\left(1-\sigma(\boldsymbol{v}_{d}^{T}\boldsymbol{v}_{m})\right)$
(6)

for $\boldsymbol{v}_{d}\in\\{V_{D}\\}$ and
$\boldsymbol{v}_{m}\in\\{V_{\cup}\\}$.

##  4 Implementation Issues

To replicate our work (code at `http://github.com/lab41/attalos`), nontrivial
details remain in the execution of the ideas in Sec. 2 due to the scale of the
data. Such considerations include pre-training the final layer of our neural
network, the partition of the architecture onto GPU/CPU memory, and additional
tricks that are necessary for sampling.

###  4.1 Pre-training the Final Layer

It is worth noting that even with 100M images, less popular concepts may occur
with relatively low frequency. Meanwhile, despite the data being sufficiently
“big”, the number of parameters in the final layer of our neural network
architecture is quite considerable. As the vocabulary is still somewhat
proportional to the number of images, pre-training will alleviate the concerns
that occur when initializing from scratch. Because each column of the final
weighting matrix is a vector corresponding to a unique word, we pre-train this
final layer with the a word corpus using _word2vec_ or _Glove_ 444We tried
both; _Glove_ tended to provide better results, though we did not explore too
many text corpora.. We pre-trained using several corpora that included Google
News, New York Times, and settled on Wikipedia 8B. The dimensionality of the
hidden layer before the final word embedding is 300, and thus, each word
vector is 300 dimensions, and this is stored in a $432213\times 300$ weight
matrix.

###  4.2 GPU/CPU Split

We would like to keep the algorithm and parameters in memory in order to
achieve quick training times, though we note that the latest computer vision
algorithms have made exclusive use of the GPU. Work in deep learning suggest
that negotiating GPU DRAM (memory) hampers the flexibility that a researcher
needs to fully explore a domain [25]. In all actuality, GPU memory capacity
and sharing have made remarkable advances in hardware. At least for now
though, servers with NVLink and multi-GPU nodes are expensive, onboard server
memory is ever more abundant, and so look to exploit onboard server memory,
instead.

Mikolov’s original _word2vec_ is trained using multi-threaded CPUs. Since his
work deals primarily with unstructured text, his neural network is wide rather
than deep, using a single hidden layer. For this reason, our algorithm makes
use of both CPU and GPU. We place the word embeddings (final layer of the
neural network) off GPU, and the corresponding gradient calculations in (1)
are done with the CPU. The backpropagation through the remainder of the neural
network (all the dense layers prior) are still done on the GPU using
Tensorflow. Such a split makes training times quicker and feasible.

###  4.3 Scaled Sampling

Like [20], we use words that occur with the highest frequencies and cut off
the number of words at 423k. To ensure consistent tensor dimensions, for each
image, we sampled 5-10 positive tags uniformly. 555In future implementations,
we imagine this would be some form of an inverse distribution of the tag
frequency. Unfortunately, sampling negative examples from a 432k dimensional
distribution is time consuming. In fact, our original code profile assessed
that 60% of time was spent in sampling.

To side-step this issue, we explored two options: (1) pre-sampling at each
epoch and (2) using the metadata from an adjacent image. The first option is
done by taking a random subset from the distribution of tags in the corpus at
each epoch. Then during backpropagation, we sample again from this random
subset. This sort of fast sampling may create inherent bias issues as the
chances of re-sampling frequently used words are likely. Because the images
are randomly ordered and selected at each epoch, the second option, to use the
metadata from the next image in the epoch as a negative sample avoids this
problem. Doing so reduced computation time to negligible rates.

Overall, by sampling, we can iterate through an entire epoch of YFCC100M in
under three hours. The bulk of our models converged to meaningful results
within a _single_ epoch. What follows in Sec. 5 were rapidly prototyped for 40
epochs through the YFCC dataset.

| NUS-Wide Dataset [4] | Multi-Corpora
---|---|---
| 925$\rightarrow$81 | 925$\rightarrow$1006 | IA$\rightarrow$ESP | VG$\rightarrow$ESP | YFCC$\rightarrow$ESP
| P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1 | P | R | F1
Fast0Tag | 16.2 | 39.3 | 22.9 | 15.6 | 14.9 | 15.2 | 15.7 | 6.9 | 9.6 | Will Not Scale | Will Not Scale
X-Ent | 21.2 | 36.3 | 26.9 | 17.1 | 14.8 | 16.3 | 16.2 | 6.1 | 9.4 | 14.1 | 17.9 | 15.7
Opt+X-Ent | 21.1 | 37.3 | 27.0 | 17.3 | 15.9 | 16.1 | 16.3 | 7.0 | 9.8 | 14.8 | 18.1 | 16.3
| Sampled Methods
S+Fast0Tag | 15.0 | 43.4 | 22.3 | 12.4 | 10.3 | 11.6 | 5.9 | 8.3 | 6.9 | 17.6 | 18.4 | 18.0 | 5.1 | 3.9 | 4.4
S+X-Ent | 15.9 | 44.2 | 22.9 | 13.0 | 11.3 | 12.1 | 10.0 | 5.2 | 7.1 | 16.6 | 19.8 | 18.1 | 17.4 | 17.6 | 17.5
S+Opt+X-Ent | 15.4 | 44.6 | 22.9 | 13.1 | 11.6 | 12.3 | 13.3 | 10.2 | 12.1 | 17.3 | 19.0 | 18.1 | 21.9 | 15.1 | 17.9
Table 2: Zero-shot and multi-corpus tagging top 5 results for
precision/recall/F1. Due to space constraints, we report at limited precision,
but the bolded results are the hightest results at full precision.

Figure 4: YFCC Image Retrieval and Truth Tags. Each pair of columns is a
search term, and the top six images are retrieved. To demonstrate how much we
rely on the statistical properties of the dataset, the metadata tags are also
shown next to each image retrieved. In many cases, the metadata is in a
different language (which we had to convert from URL encoded strings in
UTF-8.) On a side note, it is apparent that a significant portion of weddings
in the YFCC100M occur in Taiwan.

##  5 Results

While the primary objective is to train on UGC, we perform quantitative
metrics on cured, traditional corpora in order to compare against state of the
art. These include IAPR TC-12 (IA - 291 unique tags) [7], ESP-game (ESP - 288
tags, INRIA-LEAR’s version) [33], NUS-WIDE (using splits from [35],
81/925/1006 tags) [4], Visual Genome (VG 13980 unique tags) [13], and YFCC100M
[31] (millions, but we pruned to 432k tags) with both InceptionNet and
downloaded YFCC-VGG features [28].

To assess image tagging capability, we train, validate, and test against
proper splits from a single corpus. To assess generalization capability for a
variety of content and word tags, we perform cross-corpus evaluation: train on
a single dataset, then test on a totally different dataset. For example,
IA$\rightarrow$ESP is trained and validated on the IAPR TC-12
training/validation splits and tested on the ESP-game test split. For
YFCC100M, we only test on ESP-Game since YFCC100M$\rightarrow$YFCC100M
evaluation is not meaningful due to noisy truth data. Along with cited
algorithms in Table 3, neural network approaches (both sampled and unsampled)
using the cross-entropy function (with joint optimization) have run for a
total of 750 epochs of the data. The effect of sampling on accuracy can be
shown to be negligible during training while vastly improving running times as
previously shown in Table 1.

Figure 5: Qualitative example of jointly optimized vector space embedding,
where both images and text live in the vector space.

The proposed methods are denoted in Table 2 and Table 3 as X-Ent, Opt+X-Ent,
and S+Opt+X-Ent. The “Opt” stands for an optimized final word vector layer,
the “S” stands for the sampled version, and again, X-Ent essentially means a
cross-entropy cost function with a word vector final layer. We also include
“AvgWV” as a benchmark in Table 3, referring to an approach using the average
of an image’s tag vectors as a target for the deep neural network.

We use provided implementations of Fast0Tag [35] from the author as well as an
original implementation using sampling, denoted in the tables as S+Fast0Tag.
Such an implementation was able to achieve reasonable runtimes (on par with
cross-entropy) that plagued the original implementation, which is evident in
Table 1 in Sec. 2. We used the sampled code in place of the provided code for
larger datasets, where the provided code was incapable of performing due to
memory and complexity issues. It is important to note that many of the
algorithms compared against [8, 2], especially the nearest neighbor ones,
simply cannot address the large scale vocabulary in UGC nor the quantity of
images in a reasonable amount of time, either at inference time or during
training time.

Image Annotation
---
| IA [7] | ESP [33]
Top 5 | P | R | F1 | P | R | F1
least-squares | 40 | 19 | 26 | 35 | 19 | 25
Avg WV | 21 | 13 | 16 | 38 | 20 | 26
TagProp [8] | 45 | 34 | 39 | 39 | 27 | 32
FastTag [2] | 47 | 26 | 34 | 46 | 22 | 30
Fast0Tag [35] | 41 | 33 | 36 | 38 | 35 | 36
X-Ent | 44 | 34 | 39 | 38 | 36 | 37
Opt+XE | 43 | 36 | 39 | 38 | 36 | 37
| Using Sampling
S+Fast0Tag | 37 | 38 | 37 | 37 | 38 | 38
S+X-Ent | 38 | 39 | 38 | 37 | 37 | 37
S+Opt+XEnt | 38 | 39 | 38 | 37 | 39 | 38
Table 3: On the effect of using Fast0Tag and other methods versus the cross-
entropy cost function for a single corpus evaluation. We selected the higher
number at precision.

Across both Table 2 and Table 3, optimized cross-entropy outperforms Fast0Tag
[35], whether sampled or non-sampled. Although the goal in sampling was not to
achieve the highest accuracy but to deal with scale, in many cases, adding
sampling to the approach boosted recall for both conventional and cross-
corpora evaluation. Our explanation for this phenomenon is that sampling
helped to deal with noisy tagging.

Zero-shot capability is baked into the NUS-WIDE dataset with splits developed
by [35] and varying numbers of tags. The 925 tag split does not intersect with
81 tag splits, and the 1006 tag split is the union. We also include _cross-
corpora_ results where we train on one dataset and test on another dataset, of
which the tag sets overlap some. However, the goal of the proposed algorithm
is generalization using a large vocabulary. This was achieved through two
large datasets: to a lesser extent, the Visual Genome object dataset (a subset
of annotations distinct from the localization and captioning set) and to a
larger extent, the YFCC100M dataset. We perform some pre-processing, removing
images without any tags, and cutting off low-frequency words to achieve a tag
count of approximately 14k and 432k words, respectively.

We also assessed the qualitative merits of the approach. The joint vector
space embedding of $\boldsymbol{f}$ and $\boldsymbol{v}$ from (1) is shown in
Fig. 5, where the means to search between image and text modalities (tagging
vs retrieval) is conducted by finding the most similar vector via normalized
dot product. Meanwhile, results for image retrieval in Fig. 4 are conducted on
a held out set of YFCC100M alongside their true metadata to provide an idea of
the noise in the dataset. Of particular note is that we chose six terms to
search for at random, and most of the best images returned had meaningless
truth tags, which speaks to the power of our approach. The exhaustive top $N$
search was conducted in about 0.05 seconds per query on the CPU over a set of
roughly 1.7 million normalized featurized images, which were held out prior to
training.

##  6 Conclusions

We have proposed a method that can tag and retrieve images with UGC scale
vocabulary through joint image and word vector optimization and sampling
methods. We have demonstrated that our tagging mechaniscm can yield
considerably more useful information than the original tags themselves.

##  7 Acknowledgements

We would like to thank Yang Zhang [35] for his openness, conversations, and
help in replicating results on _fast0tag_ and related algorithms.
Additionally, our initial conversations with Christopher Re (Stanford
University) were very helpful. Patrick Callier (Lab41/IQT) had thoughtful
comments and contributed to the text. Sriram Chandresekar and Bob Gleichauf
provided useful direction and made the work possible.

## References

  * [1] D. M. Blei and M. I. Jordan.  Modeling annotated data.  In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, SIGIR ’03, pages 127–134, New York, NY, USA, 2003. ACM.
  * [2] M. Chen, A. Zheng, and K. Weinberger.  Fast image tagging.  In Proceedings of the 30th International Conference on Machine Learning (ICML 2013), 2013.
  * [3] W. Chen, T. yan Liu, Y. Lan, Z. ming Ma, and H. Li.  Ranking measures and loss functions in learning to rank.  In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 315–323. Curran Associates, Inc., 2009.
  * [4] T.-S. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y.-T. Zheng.  Nus-wide: A real-world web image database from national university of singapore.  In Proc. of ACM Conf. on Image and Video Retrieval (CIVR’09), Santorini, Greece., July 8-10, 2009.
  * [5] M. Everingham, L. Gool, C. K. Williams, J. Winn, and A. Zisserman.  The pascal visual object classes (voc) challenge.  Int. J. Comput. Vision, 88(2):303–338, June 2010.
  * [6] S. L. Feng, R. Manmatha, and V. Lavrenko.  Multiple bernoulli relevance models for image and video annotation.  In Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, volume 2, pages II–1002–II–1009 Vol.2, June 2004.
  * [7] M. Grubinger, P. Clough, H. Muller, and T. Deselaers.  The iapr benchmark: A new evaluation resource for visual information systems.  In Proceedings of the International Conference on Language Resources and Evaluation, 2006.
  * [8] M. Guillaumin, T. Mensink, J. Verbeek, and C. Schmid.  Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation.  In IEEE 12th International Conference on Computer Vision (ICCV 2009), 2009.
  * [9] M. U. Gutmann and A. Hyvärinen.  Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics.  J. Mach. Learn. Res., 13(1):307–361, Feb. 2012.
  * [10] S. S. H. Xiong and J. Piater.  Scalable, accurate image annotation with joint svms and output kernels.  Neurocomputing, 169:205–214, 2015.
  * [11] A. Joulin, L. van der Maaten, A. Jabri, and N. Vasilache.  Learning visual features from large weakly supervised data.  CoRR, abs/1511.02251, 2015.
  * [12] R. Kiros and C. Szepesvari.  Deep representations and codes for image auto-annotation.  Neural Information Processing Systems (NIPS), 2012.
  * [13] R. Krishna, Y. Zhu, O. Groth, J. Johnson, K. Hata, J. Kravitz, S. Chen, Y. Kalanditis, L.-J. Li, D. A. Shamma, M. Bernstein, and L. Fei-Fei.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  2016\.
  * [14] A. Krizhevsky, I. Sutskever, and G. Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in Neural Information Processing Systems 25 (NIPS 2012), 2012.
  * [15] X. Li, S. Liao, W. Lan, X. Du, and G. Yang.  Zero-shot image tagging by hierarchical semantic embedding.  In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’15, pages 879–882, New York, NY, USA, 2015. ACM.
  * [16] T. Lin, M. Maire, S. J. Belongie, L. D. Bourdev, R. B. Girshick, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick.  Microsoft COCO: common objects in context.  CoRR, abs/1405.0312, 2014.
  * [17] M. Mahoney.  Wikipedia 8 Billion Character Dataset.  http://mattmahoney.net/dc/text.html, 2006.
  * [18] A. Makadia, V. Pavlovic, and S. Kumar.  A new baseline for image annotation.  In Proceedings of the European Conference on Computer Vision (ECCV 2008), 2008.
  * [19] M. B. Mayhew, B. Chen, and K. S. Ni.  Assessing semantic information in convolutional neural network representations of images via image annotation.  In 2016 IEEE International Conference on Image Processing (ICIP), pages 2266–2270, Sept 2016.
  * [20] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean.  Distributed representations of words and phrases and their compositionality.  In Advances in Neural Information Processing Systems 26 (NIPS 2013), 2013.
  * [21] V. N. Murthy, S. Maji, and R. Manmatha.  Automatic image annotation using deep learning representations.  In Proceedings of the 5th ACM on International Conference on Multimedia Retrieval, ICMR ’15, pages 603–606, New York, NY, USA, 2015. ACM.
  * [22] K. Ni, R. A. Pearce, K. Boakye, B. V. Essen, D. Borth, B. Chen, and E. Wang.  Large-scale deep learning on the YFCC100M dataset.  CoRR, abs/1502.03409, 2015.
  * [23] M. Norouzi, T. Mikolov, S. Bengio, Y. Singer, J. Shlens, A. Frome, G. Corrado, and J. Dean.  Zero-shot learning by convex combination of semantic embeddings.  CoRR, abs/1312.5650, 2013.
  * [24] J. Pennington, R. Socher, and C. D. Manning.  Glove: Global vectors for word representation.  In Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543, 2014.
  * [25] M. Rhu, N. Gimelshein, J. Clemons, A. Zulfiqar, and S. W. Keckler.  Virtualizing deep neural networks for memory-efficient neural network design.  CoRR, abs/1602.08124, 2016.
  * [26] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge, 2014.
  * [27] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  CoRR, abs/1409.1556, 2014.
  * [28] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  CoRR, abs/1409.1556, 2014.
  * [29] R. Socher, M. Ganjoo, C. D. Manning, and A. Ng.  Zero-shot learning through cross-modal transfer.  In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 935–943. Curran Associates, Inc., 2013.
  * [30] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich.  Going deeper with convolutions.  CoRR, abs/1409.4842, 2014.
  * [31] B. Thomee, D. A. Shamma, G. Friedland, B. Elizalde, K. Ni, D. Poland, D. Borth, and L.-J. Li.  The new data and new challenges in multimedia research.  arXiv preprint arXiv:1503.01817, 2015.
  * [32] Y. Verma and C. V. Jawahar.  Image annotation using metric learning in semantic neighbourhoods.  In A. W. Fitzgibbon, S. Lazebnik, P. Perona, Y. Sato, and C. Schmid, editors, ECCV (3), volume 7574 of Lecture Notes in Computer Science, pages 836–849. Springer, 2012.
  * [33] I. Weber, S. Robertson, and M. Vojnović.  Rethinking the esp game.  In In CHI, pages 3937–3942, 2009.
  * [34] H. Xu, J. Wang, X.-S. Hua, and S. Li.  Tag refinement by regularized lda.  In Proceedings of the 17th ACM International Conference on Multimedia, MM ’09, pages 573–576, New York, NY, USA, 2009. ACM.
  * [35] Y. Zhang, B. Gong, and M. Shah.  Fast zero-shot image tagging.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [36] B. Zhou, L. Liu, A. Oliva, and A. Torralba.  Recognizing city identity via attribute analysis of geo-tagged images.  In Proceedings of the European Conference on Computer Vision (ECCV), 2014.