{'fraction_non_alphanumeric': 0.02679845884714039, 'fraction_numerical': 0.01026004271440377, 'mean_word_length': 4.777047554095108, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Learning Applied to Image and Text Matching

The ability to describe images with natural language sentences is the hallmark for image and language understanding. Such a system has wide ranging applications such as annotating images and using natural sentences to search for images.In this project we focus on the task of bidirectional image retrieval: such asystem is capable of retrieving an image based on a sentence (image search) andretrieve sentence based on an image query (image annotation). We present asystem based on a global ranking objective function which uses a combinationof convolutional neural networks (CNN) and multi layer perceptrons (MLP).It takes a pair of image and sentence and processes them in different channels,finally embedding it into a common multimodal vector space. These embeddingsencode abstract semantic information about the two inputs and can be comparedusing traditional information retrieval approaches. For each such pair, the modelreturns a score which is interpretted as a similarity metric. If this score is high,the image and sentence are likely to convey similar meaning, and if the score is low then they are likely not to. The visual input is modeled via deep convolutional neural network. On theother hand we explore three models for the textual module. The first one isbag of words with an MLP. The second one uses n-grams (bigram, trigrams,and a combination of trigram&skip-grams) with an MLP. The third is morespecialized deep network specific for modeling variable length sequences (SSE).We report comparable performance to recent work in the field, even though ouroverall model is simpler. We also show that the training time choice of how wecan generate our negative samples has a significant impact on performance, and can be used to specialize the bi-directional system in one particular task.


Abstract
The ability to describe images with natural language sentences is the hallmark for image and language understanding. Such a system has wide ranging applications such as annotating images and using natural sentences to search for images.
In this project we focus on the task of bidirectional image retrieval: such a system is capable of retrieving an image based on a sentence (image search) and retrieve sentence based on an image query (image annotation). We present a system based on a global ranking objective function which uses a combination of convolutional neural networks (CNN) and multi layer perceptrons (MLP). It takes a pair of image and sentence and processes them in different channels, finally embedding it into a common multimodal vector space. These embeddings encode abstract semantic information about the two inputs and can be compared using traditional information retrieval approaches. For each such pair, the model returns a score which is interpretted as a similarity metric. If this score is high, the image and sentence are likely to convey similar meaning, and if the score is low then they are likely not to. The visual input is modeled via deep convolutional neural network. On the other hand we explore three models for the textual module. The first one is bag of words with an MLP. The second one uses n-grams (bigram, trigrams, and a combination of trigram & skip-grams) with an MLP. The third is more specialized deep network specific for modeling variable length sequences (SSE). We report comparable performance to recent work in the field, even though our overall model is simpler. We also show that the training time choice of how we can generate our negative samples has a significant impact on performance, and can be used to specialize the bi-directional system in one particular task.

Introduction
The ability to describe images with natural language sentences is the hallmark for image and language understanding. It has significant applications such as searching images with natural sentences, and automatic captioning of images. Currently, commercially available image searching systems search the text adjacent to an image, instead of searching the content of the image itself. This is a severe bottleneck on the performance of these systems. Advances in this field will have far-reaching effects since images are ubiquitous on the Internet and we are always interacting with them.
Humans can describe an image with relative ease. However, for computers this is not a trivial task. The difficulty arises mainly because the two input modalities have very different statistical properties, and cannot be directly compared. For example, images have spacial dependency, while sentences have temporal dependency (sequence). But, even for humans, the task is of highly subjective nature, and various forms of descriptions exist. Different descriptions could focus on different aspects, or different objects in the image, they could also have different level of detail in describing the content, and they could be abstract like describing the mood or concrete like describing objects. All of these could be correct simultaneously correct, yet very different. Modeling this variance is very important for machine learning systems, and it is achieved in high-quality data sets by having multiple humans describe the same image.
The recent work in this field has focus on two approaches: Multimodal retrieval and sentence generation. Multimodal retrieval deals with the tasks of retrieving sentences from image queries (or image captioning) and retrieving images from sentence queries (or image search). On the other hand, image based sentence generation systems focus on creating natural and fluent sentences directly from the image, which describe the contents of the image.
In our work, we focus on the former approach: multimodal retrieval. We design our system taking motivation from traditional retrieval systems, in particular the supervised semantic indexing (SSI) [Bai et al., 2009] system at NEC used for document retrieval. We expand on the system by using separate, specialized textual and visual models. We use these models to extract semantic information from the input sentence and image, and then transform it into a common vector space, where we can easily compare the two modalities using traditional information retrieval approaches.
The goal of our project is to explore and understand the significance of deep learning techniques in this task. We use deep learning architectures and concepts within the individual text and image modules. For the visual component we experiment using deep convolutional neural networks, which have become synonymous with image recognition [Krizhevsky et al., 2012,LeCun et al., 1998]. For the textual component we experiment with different features and network architectures. We try bag of word approach, n-gram models, tf-idf features and convolutional neural network for sequence embedding. In contrast to other previous work, our model is simpler since we don't use more complicated models like recurrent neural networks [Karpathy and Fei-Fei, 2014] or recursive neural networks [Socher et al., 2014]. However, even with the simpler approach, our model achieves comparable performance to some recent work in the field.

Organization of report
The rest of the thesis report is organized as follows. In Chapter 2 we present a through overview of available scientific literature in the field. We start with deep learning from a historical perspective and discuss its main ideas and significance, first in the image community and then in text processing. Finally we discuss the recent previous work in the combined field of images and texts as a multimodal input.
Following this, In Chapter 3 we briefly describe some of the important resources used in our project. This includes data sets we trained and tested our model on and some publicly available tools we used in our larger model.
In Chapter 4 we provide an overview of research methodology and time line of experiments we conducted. This chapter serves as an optional section. So the reader can skip over it without loosing necessary information in understanding our final models and experiments (reference to the chapter will be made whenever we make a point which needs support from there). The material covers our experience with the problem how it influenced the way we approached the task (including the set backs we faced).
Chapter 5 presents an overview and description of the model we use in our retrieval system including flow charts and mathematical description. It also explains some interesting features of the model, and how does it compare with recent work.
Moving forward, Chapter 6 deals with the bulk of the experimentation done on our model, and the results we get. We start off by discussing the preprocessing, then give details on the evaluation metrics used and meta parameters selected. Finally we conduct several experiments and report their results.
In Chapter 7 we sum up our results by comparing them with other recent models. We then discuss the significance of our results and possible future work in this direction.
Finally, in Appendix, we give a brief overview of the software environment we used to train and test our models, and some additional resources we used which did not become part of our final model.

Literature Review
In this section we will provide a summary of important research conducted in the field of deep learning during the last decade. The literature review will comprise of three parts: 1. Deep learning in images and computer vision.

Deep learning in text and NLP.
3. Deep learning in image and text multimodal modeling.
The last part is most relevant to our task, but we feel a background discussion is important to understand and appreciate the workings of it.

Deep learning in images and computer vision
An important aspect of deep learning is to use end-to-end automatically trainable systems which do not rely on human-designed heuristics. Traditional machine learning systems are divided into two modules. First, the f eatureextractor module transforms the input data into low dimensional vectors which can be easily matched and compared, and which are relatively invariant to distortions. These are then fed into the classif ier module, which is general-purpose and trainable. A major problem with this approach is that performance is largely determined by human input, and the feature extractor part is task-specific so it needs to be redone for every little task. Countering this traditional approach, [LeCun et al., 1998] showed that handcrafted feature extraction can be advantageously replaced with automatic learning algorithms which operate directly on raw input data. The individual modules can thus be replaced by unified system which optimizes a global performance criterion.
Computer vision, and especially object recognition, has a long history of using deep multi-layered neural networks. [LeCun et al., 1995] did a comparison of hand-written digit recognition on the MNIST data set, in which they compare the performance of a multi-layered (deep) convolutional neural network (CNN) with traditional machine learning approaches like linear classifier (logistic regression), principal component analysis, and nearest neighbour classifier. The comparison shows that deep CNNs outperform the traditional algorithms on object recognition tasks, and reach state-of-the-art.
The convolutional neural networks are one of the first used deep learning models, and they are biologically inspired variants of the ANN. [Hubel and Wiesel, 1968] found the existence of receptive fields (small sub-regions in the visual field) in the visual cortex of brain, and CNNs (among other models) try to emulate this behaviour. In other words, they are specialized network architectures specifically designed to recognize two dimensional objects, while being invariant to exact position of the pattern and distortions. In the CNN each unit takes its input from a local receptive field on the layer below forcing it to extract local features. Furthermore units within a plane or f eaturemap are constrained to share a single set of weights, this makes the operations performed by a feature map to be shift invariant [Le Cun et al., 1990]. The weight − sharing technique also reduce the number of free parameters, thereby reducing the memory requirements and training complexity of the networks.
Complete CNNs are formed by stacking together multiple convolutional layers (each with f eaturemap planes and local receptivef ields). Sub-sampling layers are also added improving invariance to shift and distortions. The entire network is trainable with gradient descent using the back-propagation procedure. [LeCun et al., 1998] popularized the LeNet-5 which is a CNN architecture performing state-of-the-art on MNIST hand writing recognition at the time it was published.
Even during 1990's it was evident that deeper and larger networks have the tendency to perform better. However, this potential was overshadowed by the outrageous time and memory which took to train larger networks -and was not possible during that time. Moreover, larger networks -being more powerful at modeling -also easily overfit to training data, and there were not efficient techniques to combat this annoyance. Even though near human performance was reached for simple task like hand written recognition, but this was not reciprocated to objects recognition in realistic settings which exhibit considerable variability.
In 2009 [Deng et al., 2009] released teh ImageNet data set comprising over 15 million high-resolution images labeled into more than 22,000 categories. It has been well understood that training complicated data with high variability using very few examples leads to severe overfitting in the CNNs, so the release of this large-scale data set was a big step for object recognition problem. By this time computer hardware technology had also progressed enough to train much larger and deeper networks in reasonable amount of time. [Krizhevsky et al., 2012] used graphical processor units (GPUs) for a very fast an efficient implementation of their CNN, which has 650,000 neurons and 60 million parameters (in contrast the LeNet-5 had 60,000 free parameters). They entered their neural network in the ILSVRC-2012 competition and achieved a winning top-5 test error rate of 15.3%, which was considerably better than the state of the art (second-best entry had 26.2% error rate).
Besides larger data set and larger networks, they also empirically showed the importance of some useful techniques for avoiding overfitting. The easiest illustrated way is to use data augmentation to increase the size of data set. They take five different patches of the original image (along with their horizontal reflections) thus increasing the training data by a factor of 10 -although the additional images are very close the original one. They also also alter intensities of the colour channels to add further data augmentation. These techniques are useful for adding more shift, inversion, illumination, and colour invariance to our model. Dropout [Hinton et al., 2012] is another technique for combating overfitting, by reducing complex-co adaptions of neurons. Therefore a single neuron is forced to learn more robust features without relying on other neighbouring neurons. Pretraining the neural network in a greedy layer-by-layer fashion with an unsupervised objective function is another popular technique [Hinton et al., 2006, Schölkopf et al., ]. The intuition behind this idea is that unsupervised training will give a good initialization of weights for the neural network based on the actual statistical properties of the data it will be used for (e.g. object images, human speech, etc.) instead of random initializations which often get stuck in poor local minimas. Following this the network can be f ine − tuned on a supervised task such as object recognition.
Mathematically speaking, the CNN transforms the into a low dimensional feature vector representation. In this way a good CNN model can also act as a good feature extractor for images, and the resulting images can be used in more complicated tasks. [Sermanet et al., 2014] display this concept for object localization. They train a CNN for classification on the ImageNet data set, and for localization take they replace the final classification layer with a regressionnetwork. This regression network is simply an MLP with two hidden layers of 4,096 and 1,024 units, connected finally to the output layer of 4 units which predicts the coordinates of the bounding boxes. The final layer is class-specific having 1,000 versions (one for each class) while the rest of the regression network shares weights. During localization only the regression net-work's weights are updated, and the remaining larger network only acts as a feature extractor. They run the classifier and the regressor simultaneously since they share most of the network, in this way they get a bounding box for each class along with a confidence number based on classification confidence.

Deep learning in text and NLP
A seminal paper in the domain of statistical learning applied to natural language processing (NLP) was written by [Bengio et al., 2003]. Classical machine learning approaches to NLP calculate n-gram conditional probabilities based simply on the co-occurrence frequencies of words in a document. These models construct tables of of conditional probabilities for a next given a fixed context (of previous n − 1 words). A fundamental problem with this is the curse of dimensionality, meaning that the possible combinations of contexts grows exponentially with n, thus making the models quickly intractable. Another problem is that as the size of context increases, the occurrence of sequences gets extremely rare in a document, thus undermining the statistical relevance of their probability distributions.
The authors of the paper attempt to solve this problem by using a neural network to to learn distributed representation of words. This distributed representation, which is sometimes termed word embedding in modern literature, is feature vector which conveys semantic and syntactic meaning of the word. In other words, all the words in the vocabulary can be transformed into a vector representation of a fixed dimension (usually much smaller than the original size of the vocabulary). Furthermore the joint probability of the entire sequence (of arbitrary length) can be expressed as a function of these feature vectors. In this paper they propose to use feed forward neural networks to compute the probability of the next word in the sequence given the previous n words (in the form of these word vectors) . The advantage of neural networks is that they can be trained in trained to jointly learn the word feature vectors (first layer of the neural network) and the parameters of the probability function (free parameters of the network) using a common global objective function (maximizing log likelihood).
The advantage of using these word vectors is that it would escape the curse of dimensionality. The words would now be represented in a fixed real-valued (comparatively) low-dimensional vector, and similar words would have similar meanings. An example given by the paper is that the sentences "A cat is walking in the bedroom" would have similar representation to "The dog was running in a room", since the model would learn the similarity of the individual words in the sequence (dog, cat), (the,a), (bedroom, room), etc. It is noteworthy that they report 24% and 8% improvements in terms of perplexity over the best n-gram results for the task of predicting the next word in a sequence performed on two large scale data sets. The idea of using neural networks for language modeling in fact dates back to [Miikkulainen and Dyer, 1991], however the authors of the paper under discussion were the first to propose a large scale statistical model which learns distributed dense representations of words in a sequence and using them to automatically estimate the joint probability function.
Building on to this, [Collobert and Weston, 2008] propose a single unified convolutional neural network architecture that performs well for various challenging NLP tasks, such as part-of-speech tagging, chunking, named entity recognition, and semantic role labeling. Traditional approaches analyze these tasks separately, using hand-crafted features specific for each task which makes this approach intractable for complicated tasks. The model they propose -in contrast -has a deep architecture composing of many layers which can be trained in an end-to-end fashion. The first layer extracts features for each word (word embeddings, or distributed word representations). The second layer extracts features form the sentence treating it as a sequence with structure. Variable length inputs are incorporated by passing a convolutional neural network over the word features and then performing max-pooling over each resulting dimension to give a fix length vector. The following layers are classical NN layers (fully connected).
Since all of these tasks are related , they argue that it would make sense to share some features between these tasks in order to improve the generalization of the network, and so they propose multitask learning approach to jointly train the model on all these tasks. They design their network architecture to share the layers closer to the input (these layers would encode word embeddings, which should intuitively be common to all language-related tasks). As we go deeper into the network, the features extracted become more complex and abstract, and so the last layers of the network are task specific.
They also pretrain their network with unlabeled training data , since it is available in much vast quantities as compared to labeled data. They train a language model with an unsupervised ranking criterion, which would predict if the middle word in the sequence is related to the context or not. For positive examples they took fixed length phrases from wikipedia, and they generated the negative examples by substituting the middle word in a valid phrase by any other random word. They demonstrated that this approach trains a powerful language model by showing that word vectors which are close to one another in the embedding space are also close in semantic meaning. For example "France", "Spain" and "Italy" have close vector representations to one another, as well as "scratched", "smashed" and "ripped". [Mikolov et al., 2013a] propose yet another unsupervised approach of learn-ing vector representations of word. They propose a skip gram model, which predicts the surrounding words in the window given the center word. This is directly opposite of earlier approaches which predict the centre word giver the context window. Given a sequence of training words, the objective criterion is to maximize the average log probability of the words in surrounding, conditional on the centre word. One interesting feature about their model is that it preserves linear regularities among the learned representations. This makes it possible to perform interesting analogical reasoning using simple vector arithmetic. For example, the result of the vector calculation: vec("king") -vec("man") + vec("woman") is closest to vec("queen"). Also, vec("russia") + vec("river") is close to vec("volga_river").
Furthermore, [Mikolov et al., 2013b] extends the previous model to include vector representations for phrases as well. They based their work on the insight that idiomatic phrases like "Boston Globe" and "Air Canada" can be semantically understood well by combining the individual words within the phrases. Therefore they treated phrases as individual tokens (just like words), but limiting their vocabulary to only those phrases which appear frequently together, and infrequently in other contexts. They train vector embeddings of dimensionality 300 for these words and phrases, and release the on the internet for public use 1 .

Deep learning in image and text multimodal models
There has been a lot of progress in multi-label classification problem of associating images with individual words or tags. However, the more challenging problem of associating images with complete natural sentences has only recently started to gain attention. The research in this area has focused primarily on two tasks, namely: 1. Mapping images and sentences into a combined space 2. Generating descriptions of images in terms of complete and natural sentences.
The first poses it as an information retrieval problem, while the later treats tit as a natural language generation problem. [Hodosh et al., 2013] have written one of the seminal papers in this field, providing an interesting discussion on the problem statement, an in-depth comparison of the available data sets (including what kind of data is required for good modeling), an analysis of modeling techniques employed in the early stages of this field, and a detailed discussion of the various evaluation metrics used in different previous related works. [Hodosh et al., 2013] go into the philosophy of image description by arguing that there are three different kinds of image descriptions:

Introduction
1. Conceptual descriptions identify what is being depicted in the image. They are concerned with the concrete descriptions of the depicted scenes and entities, their attributes and relations, as well as events they participate in.
2. Non-visual descriptions provide additional background information that cannot be obtained from the image alone, e.g about the situation, time or location in which the picture was taken.
3. Perceptual descriptions capture low-level visual properties of images, e.g if it is a photograph or a sketch, or what colors or shades dominate.
They argue that out of these three, conceptual descriptions are the most relevant for image understanding tasks. They observe that using user generated captions uploaded with images in popular image-sharing websites (such as Flickr.com) do not serve as good training data because people tend to provide information that could not be easily obtained just from looking at the image itself. For example, the kind of description our models require is "Three people setting up a tent" while people tend to provide captions like "Our trip to the Olympic Peninsula". Hence they establish a need of data collected purposefully for this specific task.
Most of good quality data sets are collected visa crowdsourcing (for example using Amazon Mechanical Turk) in which multiple descriptive captions are assigned to each image. Pascal1K [Farhadi et al., 2010], Flickr8K [Rashtchian et al., 2010], Flickr30K [Young et al., 2014], and MS-COCO [Lin et al., 2014] are examples of such good quality data sets.
Some of the earliest work in this field used shallow learning techniques and fixed (as opposed to learn-able) image and text features. [Makadia et al., 2010, Ordonez et al., 2011 use nearest neighbour search kNN! (kNN!) for image annotation and image description respectively. On the other hand, [Hodosh et al., 2013] use kernel canonical correlation analysis kernel conanical correlation analysis (KCCA). KCCA [Bach and Jordan, 2003] is technique which takes training data consisting of pairs of corresponding items drawn from two different modalities and finds maximally correlated linear projections of each set of items (by first mapping the original items into higher-order spaces) into a newly induced common space. Similarly, popular shallow image features include SIFT descriptors [Lowe, 2004] and simple bag if words (BoW) kernel.

Evaluation Metrics
Since image description is a subjective task, the ideal setting for evaluating a system would be averaged human judgement. However, since human judgement is expensive and slow, there have been a number of metrics employed in evaluating these systems. These metrics can be divided into two categories: • metrics for text generation systems.
• metrics for ranking systems.
BLEU [Papineni et al., 2002] and ROUGE [Lin, 2004] scores are popular metrics in the automatics image description generation systems. Originally, they are standard metrics for machine translation and summarization respectively, but have been used to evaluate multiple caption generation systems [Vinyals et al., 2014, Ordonez et al., 2011,Gupta et al., 2012. Given a caption c and an image i with a set of reference captions R i , the BLEU score of a proposed image-caption pair (i, s) is based on the n-gram precision of s against R i , while ROUGE is based on corresponding n-gram recall. If c s (w) is the number of times word w occurs in s, they are defined as: [Hodosh et al., 2013] try to compare BLEU and ROUGE scores against human judgements, and examine to what extents do these both agree. Based on results they question these metrics' usefulness for evaluating caption generation systems. [Reiter and Belz, 2009] also argue that they are more useful as metrics for fluency, but poor measures of content quality of language generation. However, unless a more suited metric is devised, these score are continue to be used for evaluating modern caption generation systems.
Next, we will touch upon metrics which can be used to evaluate the quality of a ranked list in information retrieval tasks. Recall@K (R@K) is the percentage of test queries for which a model returns the correct result among the top k results. It is especially useful in the context of search where a user may be satisfied with the first k results containing a single relevant item. Conversely, median rank is equal to the value of k for which the R@K is equal to 50%. The k in R@K typically varies between k = 1, 10. [Hodosh et al., 2013] consider k = 1 as a very strict threshold and, after comparing it with human judgement, view it as a lower bound on actual performance.
In our systems queries can have multiple (variable number) of relevant answers since each test image may be associated with multiple relevant captions, and each test caption may deem fit for multiple images besides the one it was originally written for. R-precision [] is the metric of choice in these conditions, since it is a single number which allows us to rank models according to their overall performance (no threshold like k) The R-precision of a system with query q i and known relevant results r i is defined as its precision at rank r i . In simpler terms it is the percentage of relevant items among the top r i responses returned by the system. [Frome et al., 2013] were one of the first ones to use deep learning in ranking images with text.They call their model DeViSE or deep visual-semantic embedding. Their original task was to improve performance of their image classification system for large number of object categories and for labels on which the visual system was not trained (zero shot prediction). They propose to leverage information from textual information of image to improve their object classification performance.

Image and text mapping
They begin by pre-training an efficient deep convolutional neural network (CNN) for visual object recognition, based on the architecture by [Krizhevsky et al., 2012]. In parallel, they pretrain a simple neural language model wellsuited for learning semantically-meaningful vector representations of individual words (word embeddings) using skip-gram text modeling architecture [Mikolov et al., 2013a, Mikolov et al., 2013b. Following this, they construct the DeViSE model by chopping of the top layers of the CNN and re-training it to predict the word embedding vector of the corresponding image label.
They used hinge margin ranking loss criterion in the second phase of their training, and observe significant improvements over using L 2 loss criterion. Although they never trained or tested their system for natural image descriptions, but they did influence a lot of work in this field. [Karpathy et al., 2014] implemented their model for image and sentence mapping to compare performance against their own system. [Gong et al., 2014] use CNN for modeling images in their image based sentence retrieval system. They first embed image and sentence into a common space and then use it to rank the pair. They perform a comparison between using 4,096 CNN activations (trained on ImageNet [Deng et al., 2009]) as image features versus KCCA with 4,000 dimension fixed features. There was a reported 9.5% improvement in Recall@10 for CNN over KCCA, even when the CNN activations remained fixed and it was not fine-tuned on image-text data set.
Unlike previous work, [Karpathy et al., 2014] go on a finer level and map fragments of images (objects) and fragments of sentences (dependency tree relations) into a common embedding space. Their model works for bi-directional retrieval: image given a text query, and text given an image query. They interpret an image being made up of multiple entities, and therefore propose to break it down into more manageable fragments.artificial neural network (ANN)s are used to compute vector representation of these image and sentence fragments in a multimodal embedding space, and the dot product between a pair of these vectors (one image fragment and one sentence fragment) are interpretted as a compatibility score. The global image-sentence compatibility score is computed as a fixed function of their fragments.
Their image model comprises of a Region convolutional neural network (RCNN) which detects objects in the images and returns their bounding boxes. For image fragments they use the top 19 locations detected by the RCNN and the complete image, so each image is broken down into 20 fragments. Following this another CNN is applied on each of these fragments to return a 4,096 dimensional embedding vector representing the image fragment. The architecture of this CNN closely resembles that by [Krizhevsky et al., 2012]. On the other hand, the sentence fragments are considered as edges of the sentence's dependency tree. Therefore, each sentence fragment consists of two words which are joined in any stage of the dependency tree. Each word in the dictionary of 400,000 is represented using 1-of-k encoding, and vector embeddings for the words are obtained through an unsupervised objective and fixed throughout the training. The sentence fragment score is calculated using these word embeddings as well as separate embeddings which represent the type of relation between the words.
They plot a matrix where the rows represent the image fragments and the columns represent the sentence fragments. Each element of the matrix (or box) shows the dot product score between those two multimodal fragments. They define two kinds of objective functions to train their models: • Fragment alignment objective: This objective explicitly learns the representation of sentence fragments in the visual domain. It encodes the intuition that if a sentence fragment is contained in an image, at least one of the boxes should give a high score with that sentence fragment, while all other boxes corresponding to images which do not contain this sentence fragment (in their descriptions) should have a low score with this fragment.
It also favours that there should be at least one high scoring box in each column of the matrix (meaning every sentence fragment should be matched by at least one image fragment).
• Global ranking objective: This objective tries to enforce that the imagesentence similarities are consistent with the ground-truth. First the global similarity score is computed by averaging the pairwise fragment scores. After this the entire system is trained in an end-to-end fashion with the margin ranking loss criterion.
The model improves performance when using a combination of these two objective functions. They also report that dividing image in fragments has performance improvement versus treating the entire image as a single fragment, and that dependency tree sentence fragments perform consistently better than bag of words (BoW) and bigram features. Finally they found that fine-tuning the image score calculating CNN on image-text data further improves results. [Socher et al., 2014] go one step ahead and use the entire sentence dependency tree -as opposed to only its edges as sentence fragments -to model the sentences using DT-RNN (dependency tree recursive neural networks). They argue this is important for accurately representing complicated sentences in the visual domain. They test their model against other recurisive and recurrent neural networks, KCCA and BoW baseline, concluding that DT-RNN out performs all of these in the task of image and sentence mapping. DT-RNN also give similar vector representations to multiple captions which describe the same image, adding more weight to their model. The DT-RNN is different from other previous recursive neural network models [Socher et al., 2011] which are based on constituency tree (CT-RNN). They report that the sentence vectors computed by DT-RNN are more apt at capturing the meaning of the sentence in terms of "visual representation". Moreover DT-RNN vector embeddings are more robust to changes in syntactic structure or word order as opposed to CT-RNNs or recurrent neural networks. The final sentence embedding is a vector of length 50.
For the image side, they train a deep CNN first using unsupervised objective: reconstruct the input keeping the neurons sparse, followed by supervised learning on classifying 14 Million images of ImageNet into 22,000 categories. The CNN used was particularly large, with 1.36 billion parameters, and they achieved 18.3% precision@1 on the full ImageNet data set. Following the CNN training, they chop off the last layer to get 4,096 dimensional vector embeddings for the images.
During the multimodal mapping, the 4096 they transform the image representation vector to the same size as sentence vector. Following this -like other similar works -they take a dot product of these to produce a compatibility score and back propagate error using margin ranking loss criterion. However, the 4,096 dimensional image vector and 50 dimensional sentence vector are fixed and are not updates during this phase. They report improved results over the Pascal1K data set [Farhadi et al., 2010] compared to bag of words (BoW), CT-RNN, recurrent ANN and KCCA models. [Karpathy and Fei-Fei, 2014] build upon their prior work on image text matching using fragments of image and sentence [Karpathy et al., 2014] (discussed above), add a new features to increase the modeling capacity of their model. Their initial approach translated words directly into vector embeddings, and did not consider word ordering and context. To address this problem they use a bi-directional recurrent neural network (BRNN) to model the input text sequence and convert it into a complete sentence embedding. They report significant improvements using this approach.
Taking a somewhat different approach, [Srivastava and Salakhutdinov, 2012] use multimodal deep boltzmann machines (DBM) for this task. The model learns joint probability density over the space of multimodal inputs. Missing modalities can be filled in by sampling from the conditional distributions over them. For example we can learn the joint probability P (v img , v txt | θ) ,where v img is the vector representation of an image and v txt is the vector representation of a text sentence. Once this distribution is estimated we can draw samples from the conditional probabilities to fill in the missing modalities: drawing samples from P (v txt | v img , θ) to give the missing text sentence, and vice versa.
A multimodal DBM is an extension of an DBM to model multimodal inputs. A DBM is formed by stacking together RBMs, in other words a multilayer RBM, which are usually trained in a greedy layer-wise strategy. They construct two independent DBMs: an image-specific DBM and a text-specific DBM. Next these two are connected together via another RBM layer to construct the multimodal DBM. In other words, the outputs of the two DBMs are connected to a another layer of binary hidden units on top of them, called the "joint representation". The intuition behind this model is that each data modality has very different statistical properties which make it difficult for a single hidden layer model to directly find correlations across modalities. This difficulty is overcome by putting layers of hidden units between the inputs of both modalities (the separate DBMs) They evaluate their model on information retrieval for multimodal and unimodal queries. In multimodal query, the aim is to give higher similarity score to the image and text pairs belonging to the same instance, over false pairings. While in unimodal query, either text or image is provided, and the model predicts the missing modality out of a pool of possible options.

sentence generation from images
Now we will briefly touch upon the related task of generating natural sentences from images. Although it is not the focus of our project, but it is still to interesting to see the approach taken in that area, especially since there has been a growing interest in it recently. [Kiros et al., 2014] present a model in which they use a convolutional neural network (CNN) for this task. The CNN has four input pathways, one for an image and the remaining three for words. The idea is that, given an image and three previous words, the model learns to predict the next word in the sequence. In this way they learn a joint "multimodal language model".
Recurrent neural networks (RNN) are quite popular for text generation, and so many researchers use them in this task, albeit in different settings Fei-Fei, 2014, Vinyals et al., 2014]. [Vinyals et al., 2014] are influenced by modern ANN based machine translation systems, and they employ a encoderdecoder type architecture for their model. Specifically, they use a CNN as an encoder and an RNN as a decoder. The CNN encodes the input image in vector space feature embeddings which are are input to the RNN. The RNN takes the image encoding as input and the word generated in the current time step to generate a complete sentence one word at a time. Special words have been marked to tell the model that it is the starting word and for predicting the finishing word. They also use long short term memory (LSTM) inside the RNN so that it has some memory of older generated words. They train their model to directly optimize the log likelihood of the target sentence given the input image.
Using a similar approach, [Karpathy and Fei-Fei, 2014] also use an RNN trained on multimodal inputs. For each input image feature vector, and the current generated word (starting at a fixed word) it learns to predict the next word in a sequence (ending at a fixed word).

Chapter 3 Resources
We employed various data sets and resources in our research and experimentation. Below we will provide a brief description for them. Most of the high quality data set is collected through crowd sourcing methods, labeled by human input. Although some large-scale automatically generated data sets exist (for example using user provided annotations when uploading images on photo-sharing websites). However, [Hodosh et al., 2013] makes a convincing case about the lack of pertinence of these captions with the objectives of our task, and hence we do not use them (like many researchers in the domain).

Flickr8K
Flickr8K 1 is a data set comprising of 8,092 images collected from the Flickr website [Rashtchian et al., 2010]. Each image has five captions along with it, which describe the contents of the image. The images in this data set focus on people or animals (mainly dogs) performing some action. The images tend not to contain well known locations, but are manually selected to depict a variety of scenes and situations. The images are captioned by human captioners (five for each image) using crowdsourcing via Amazon's Mechanical Turk 2 .
In order to avoid grammar mistakes, the captioners (who were only from US) had to pass a brief quality control test based on spelling and grammar. Following this, they were asked to write sentences that describe the depicted scenes, situations, events and entities (people, animals, other objects). Multiple captions were collected to model the inherent variability of different humans in describing the same image. As a consequence, the captions of the same images are often not direct paraphrases of each other: the same entity or event or situation can be described in multiple ways (man vs. bike rider, doing tricks vs. jumping), and while everybody mentions the bike rider, not everybody mentions the crowd or the ramp.
It is worth mentioning that when accessing the data set, we found out that several of the images had been removed from Flicker (the authors gave links redirecting to the original images 3 ) so we could only get download 6,793 out of the total 7,678 images. Therefore, although we can use to judge the performance of our algorithm on the data set, we cannot use it in comparison to previous work.

Flickr30K
Flickr30K 4 is an extension over the Flickr8K data set, comprising of 31,783 images collected by [Young et al., 2014]. Similar to its counterpart, each image is associated with five captions written by humans using the Amazon's Mechanical Turk. The images consists of everyday activities, events, and scenes.
It is important that the annotators are not familiar with the specific entities and circumstances depicted in them, to avoid that they give overly specific annotations. For example the annotations "Three people setting up a tent" are more relevant to the task as compared to "Our trip to the Olympic peninsula" (for the same image -the latter is likely an annotation given by a person familiar with the significance of the image). Moreover different annotators use different levels of specificity, from describing the overall situation (performing a musical piece) to specific actions (bowing on a violin).This variety of descriptions associated with the image is necessary to induce similarities between expressions that are not trivially related by syntactic rewrite rules.

OverFeat
OverFeat 5 is a publicly available visual feature extractor based on the convolutional neural network submitted by [Sermanet et al., 2014] to ILSVRC-2013 large-scale object recognition competition. At the time of its release it ranked 4 th in classification, 1 st in localization, and 1 st in detection tasks of ILSVRC-13 data sets. We use the accurate version of their model which has 144 million free parameters and 5.4 billion connections, and reaches performance of 14.18% on the competition validation set. Their network architecture is similar to the architecture by [Krizhevsky et al., 2012], with the addition that it is trained on images at multiple scales, and it has improved inference step.

Word2vec
Word2vec 6 is a publicly available tool which provides an efficient implementation of learning continuous bag of word, and skip-gram based vector representations for words. The model and implementation is based on the work of and released by [Mikolov et al., 2013b]. In addition to the implementation, they also provide vector representations of words and phrases which they learned by training this model on Google News Dataset (about 100 billion words). These are 300-dimensional vectors for 3 million words and phrases. An interesting feature of these vector representations are that they capture linear regularities in the language. For example the result of the vector calculation: vec("Madrid")vec("Spain") + vec("France") is closest to vec("Paris").

Chapter 4 Research Methodology
This section will provide an overview of research methodology and time line of experiments we conducted. Most of the experiments mentioned in this chapter are not directly involved in our final results, and so the reader can skip over this chapter if they wish to. Any material which is deemed necessary to understand our model will be reiterated in the next chapter. The reason for this chapter's inclusion is to make the reader understand how our experience with the problem influenced the way we approached the task (including the set backs we faced), and how we arrived to our final model.
We decided to treat the problem of image descriptions as an information retrieval task, and decided to follow a ranking approach for matching images and sentences. This decision was influenced by prior work at NEC relating to SSI (supervised semantic indexing) [Bai et al., 2009] which is a system for document retrieval based on a query sentence. The basic idea is to generate vector embeddings for different texts (query and document) which contain semantic information about the original text. These embeddings act as abstraction of the content in text, and can be used for similarity comparisons between different texts.
SSI is quite similar to our problem, with the difference that our inputs are multimodal. In SSI both query and result are of textual nature, while for us, one is text and the other is image. The presence of multimodal inputs makes our task much more challenging, therefore we would need to change the architecture to cater for this complexity.
We are interested in making our model bi-directional, meaning that it would be able to retrieve an image for a textual sentence query (image search) and a sentence for an image query (image annotation). Following this goal, we aim to make our model different in two significant ways from the SSI architecture: 1. We will divide our network into a visual model and a textual model.
The visual model will be fed with images and the input for textual model will be images. The goal of each model will be to efficiently extract semantic features from their respective input signals.
2. We will make the overall architecture deeper. Since both our inputs belong to different modalities and differ in statistical properties, transforming them into a common embedding space would be more challenging and we would need the modeling power of deeper networks (with more non linear layers) We follow the above guidelines to design our model. For the visual model we use a CNN (convolutional neural network) initialized from random weights. For the textual model we use a simple MLP with a single hidden layer, and we treat the sentence as a bag of words (BoW). We trained this model in an endto-end fashion with margin ranking criterion. The objective of the criterion is to maximize the distance between a positive and a negative example (giving higher score to the positive example and lower to a negative). A negative example is generated by making a random false pairing with a sentence and image from our training examples (whose ground truth we know). At each iteration we give a positive example and a randomly generated negative example. The gradient is back propagated through the entire network to train it in an end-to-end manner.
However the model failed to perform well when trained on Fickr8K data set. The training error decreased with increasing number of epochs, but the error on validation set error seem to remain very close to random, as illustrated in Figure  4. 1 We tried to analyze our results and investigate into a possible reason for failure. Changing different hyper parameters like learning rate, hidden layers and hidden units did not seem to produce any significant effect. Since SSI has a similar architecture and it seems to perform well on only textual input data, so we could think of three possible reasons of the models failure: 1. More training data required as the model seems to start over-fitting.

our CNN not powerful enough to produce good visual representations.
3. Our model architecture not well suited for the task.
The CNN we used was made out of 5 convolutional blocks followed by 2 fully connected layers. Each convolution block had a convolution layer, non-linearity layer, sub-sampling layer, dropout layer and (subtractive) normalization layer. We decided to first verify if the CNN was working as expected by testing it in isolation. We did this by using it for a much simpler task: classification of handwritten digits from the MNIST data base. The model seemed to perform well without tweeking much parameters, verifying that it was at least functioning properly (refer to Figure 4.2 for classification results).
Following this we tried to use it on a more complicated task: classification of objects into 256 categories from Caltech256 data set. However, the model failed to perform well on this task, as illustrated in Figure 4.3. We concluded that the reason for bad performance on the Flickr30K ranking task and Caltech256 classification task was due to the same reason. Our CNN was not able to model the complicated data set well enough. In other words, since the number of images was relatively limited and the amount of variation in the images was rather high (especially true for Flickr30K data set), the CNN was not able to generalize, and model the relevant statistical properties well enough. Therefore we concluded that we needed to pre-train our network with larger data set before attempting to train it on these problems. The advantage of pre-training would be that the model would have very good initialization, and would be able to extract good visual features from the images which could be used for our task. Instead of wasting scarce time to pretrain our network from scratch on a much larger data set (Which could take weeks), we decided to use a publicly available CNN: OverFeat 1 . For details of this model refer to Chapter 3.3. However, before plugging OverFeat network directly into our original task we decided to first test it on classifying Caltech256 data (on which our CNN failed). We chopped off the last softmax layer of OverFeat and replaced it with a small neural network (1,000 unit linear layer, relu non-linearity, another 1,000 unit linear layer, and finally a 256 unit softmax layer). The parameters of CNN were fixed and not fine-tuned on the new data, and the parameters of the small network on top were only updated. This model managed to classify Caltech256 significantly better than our original randomly initialized CNN (classification results in 4.4).
We also decided to do a small toy experiment to test the image and text multimodal ranking approach based on Caltech256 data set. For the textual input we used the class labels corresponding to each image, which are incorporated easily since it is a simple bag of words model. Often the label were hyphenated like "baseball-bat" and "bear-mug"; in these cases we decided to break into individual words (so images belonging to these images would have two word inputs instead of the usual one). The total vocabulary size was 322 words. To our satisfaction, the this toy ranking task also performed well, reinforcing our confidence in the model. The results are shown in 4.5. Therefore, we finally decided to do further experiments with OverFeat CNN model.   OverFeat CNN performed well on the ranking task on Caltech256 data set. Error is the percentage of samples for which the model gives higher score to the positive sample over the negative sample. 50% error specifies random performance.

Abstract Architecture
Our model is inspired by the previous work at NEC of SSI (supervised semantic indexing) [Bai et al., 2009] which is a textual retrieval system. We aim to extend this model to multimodal inputs: in particular images and text. We will focus on bidirectional retrieval. In other words, retrieving images based on a sentence query (image search) and retrieving sentences based on an image query (image annotation). The sentences are complete and natural, constructed by human annotators, as opposed to individual and isolated tags.
The overall abstract-level architecture of our complete model is illustrated in Figure 5.1. The two sub-models P osN et and N egN et have identical architecture and they share weights. For a pair of text and image input, they calculate the score s, which is a measure of the similarity between the corresponding text and image (based on cosine distance). Here S pos is the similarity score of the positive input pair and s n eg is the similarity score of negative input pair. Positive pair means that the sentence positively describes the image (As determined by human judgement). Negative pair means that the image and sentence are not related, and the pair is generated by simply replacing the sentence (or the image) in a positive pair by another random sentence (or image).
At each iteration we simultaneously present a positive pair and a negative pair to the P osN et and N egN et respectively. The objective criterion penalizes if S pos is not greater than a certain threshold above S neg . Intuitively it means that the system is trained to give high score to similar pair or sentence and image, and a low score to a dissimilar pair. Therefore the network learns to score semantic relevance between the pair of multimodal inputs.
As discussed previously, in our data set there are five sentences corresponding to each image. Each one of them is labeled by a different person, in order to model natural variance within descriptions. We use all five sentences during the training process, so each image is samples five times during one full epoch (in a random order). We believe it is extremely important to use all five sentences to make the model more robust to variance in natural language. They generate a score s based on similarity (and semantic relevance) between a given pair of text (txt) and image (img) input

Pos Net
Next we will go one lower level of abstraction and discuss the inside of the model which makes P osN et and N egN et. This is illustrated (again in an abstract manner) in Figure 5.2. In our system the textual model and visual model are replaces by ANN (artificial neural networks). Given a sentence and an image, these ANNs are trained to transform them into low dimensional high-quality vector embeddings. V t xt signifies the vector embedding generated from the textual input, and V i mg is the vector embedding from visual (image) input.
By high-quality we mean that the vectors are embedded in a common embedding space which encodes high level semantic information about the contents of the image and text while ignoring feature level details (for example that one is text and one is input). The advantage is that once multimodal input is em-bedded in a common space we can apply standard vector operations to measure their similarity and use it for retrieval task.
These high quality embeddings are learned through a global ranking objective function. Below we will briefly discuss some of the mathematical details of our model, including the objective function.
Where, f img (.) signifies the visual model and f txt (.) signifies the textual model(refer to Figure 5.2). Additionally img i and txt i are the i th image and sentence (text) inputs respectively.
The error i denotes the global objective function. For a given margin threshold (∆), if the positive input score S i,pos is not at least ∆ bigger than the negative input score S i,pos , then the error gradient propagates throughout the architecture. This is shown in the equation below:

Details Visual and Textual models
Following the deep learning approach we use neural networks for both visual and textual models. This is because ANNs can be trained in an end-to-end manner, optimizing the global objective function, and require minimal preprocessing. Also, as discussed in Chapter 2, various ANN architectures achieve state of the art results in various machine learning tasks. We hope to reciprocate these results for our task.
For the visual model we use a convolutional neural network (CNN), since they have become ubiquitous with image recognition tasks. As discussed in Chapter 4, we experimented with training a CNN from scratch (with random initialization) on our data set, but that failed to achieve good results. After some experiments we were convinced of the need of pretraining the CNN with large image database like the ImageNet. However, doing that from scratch and achieving state of the art results would take us a very long time, so we decided to explore publicly available CNN models. In all our experiments we use the OverFeat convolutional neural network (refer to 3), which is a competition winner from ILSVRC-2013. We chop off the last softmax layer of OverFeat which leaves us with 4096-dimensional feature vector. Since this is very deep inside the network, we argue that the features would be high-level and abstract (not spatially dependent and with semantic information) and we can use them directly in out model. Therefore we don't update the weights and parameters of the OverFeat network, and treat is as a feature extractor. Instead we build our own smaller fully connected ANN which takes OverFeat feature vector as input and generates the multimodal image embeddings. Results show good performance with this approach and we stick with it throughout our experimentation.

Textual Model
For the textual model we experimented with different architectures and input features. A brief overview of these is given below. Details of these will come in the next chapter when we discuss experiments.
1. The first and simplest model we try is a fully-connected MLP with unigram bag of words (BoW) features of dictionary size 5,000. The size of the input layer is equal to the vocabulary size, with each index mapping to an individual word. Next there are one or two optional hidden layers with non-linearity, for greater modeling strength. Finally the last layer gives the feature vector V t xt for the entire textual input, and it is of size n emb . It is also noteworthy that the first layer would encode information about individual words, and thus we experiment initializing it with good publicly available word embeddings called word2vec (refer to Chapter 3) 2. A major problem with the BoW model is that it looses all sense of structure in the sentence (all words are treated equally and there is no information if a word came before or after another). There are many ways to preserve this syntactic information in the sentence, and in this model we try the simplest approach: n-grams. We extend our textual model to include bi-gram, trigram, and tri-grams with skip-grams as inputs. The vocabulary size (and thus the input layer of MLP) is now increased to 50,000 units (based on the most frequently occurring n-grams). Although our model still as a whole treats each n-gram as a unit inside a bag (with no connection to other n-grams in the sentence). But, there is still some syntactic information present inside the individual n-gram unit, and so we hope to gain some performance due to increased syntactic information in our textual input. We also tried experimenting with using tf-idf features instead of binary word presence features.
3. We also tried experimenting with the supervised semantic embedding (SSE) architecture [Bespalov et al., 2011] as the textual model. SSE uses a specialized ANN architecture to deal with variable length sentences and temporal dependencies within the text. It has been successfully applied to applications like sentiment analysis from customer reviews at NEC, which led to our motivation in using it.
The architecture for SSE consists of three parts. An embedding layer (lookup table) embeds each word into an M -dimensional vector. K kernels are then convolved over the sequence of word embeddings to give K sequences of fixed length (phrase level embeddings). Finally an averaging layer averages over the length, reducing the sequence to a K-dimensional vector, which encodes semantic information about the complete sentence. Further layers can be added on top depending on the required functionality.

Unique training methodology
As we explained above, we generate a negative sample by fist taking a positive sample and then replacing the sentence (or the image) with another random sentence (or image). So in effect we can take two approaches: replacing the sentence with another sentence (while keeping the image) or replacing the image with another image (while keeping the sentence). It turns out that this choice makes a difference in the evaluation results, so from now on we will refer to this choice as the training methodology. This choice is explained in the mathematical forumalism below (refer to Figure 5.1 in connection to the equations below) I2T approach: img 1 = img 2 , txt 1 = txt 2 T2I approach: txt 1 = txt 2 , img 1 = img 2 We will discuss the effects of these with empirical results in the next chapter. However, we would briefly mention here that the I2T approach gives higher performance for image annotation systems, while T2I approach gives higher performance for image search systems. Therefore, this methodology of generating negative samples can be used to specialize the system towards a particular task (although the system is inherently bi-directional and can still perform the other task with reasonable accuracy).

Comparison to other models
Deep CNNs have now becoming ubiquitous with image recognition and feature extraction, achieving state of the art in many major computer vision tasks. Therefore, like most other recent work, we also stick with CNNs for our visual model. However instead of training the the network from scratch, we use a publicly available model OverFeat which achieved very good performance in ILSVRC-2013. Our initial reason for doing this was to not waste extra time training the model from scratch on large data sets like ImageNet. They train the model with various special tricks like multiple-image fragments, multiple-scales, maximizing image localization, introducing color and translation invariance with data augmentation. Because of this the model provides excellent feature vector representation of images, and we feel that our good results on our task are partly because of the high modeling strength and accuracy of our visual model.
As explained above, we try several approaches with the textual model: simple BoW model, n-gram model, and SSE model. However our approach is much simpler than many researchers who have recently started using recurrent or recursive neural networks to model sentences [Socher et al., 2014, Karpathy andFei-Fei, 2014]. Also, unlike [Karpathy et al., 2014] we don't divide our images and sentences into fragments, but treat them as whole. With our results we show that these complicated models, which are also harder to train and slower, are not necessary to achieve good performance on the task of image-sentence bidirectional retrieval.
Furthermore, we show an important feature of these bi-directional retrieval models: that they can be specialized to one task (either image search or image retrieval). We use empirical results to show that the methodology of generating negative sample (hereby referred to as training methodology) has a significant on the final performance of the model (see Section 5.3). If we use the I2T approach the model specializes in image annotation, and if we use T2I it specializes in image search. Note that it still remains bi-directional and gives good performance for the other task as well.

Chapter 6
Experiments and Results

Preprocessing
The images were all scaled to a constant dimension of 221 × 221, since the ANN needs to have a constant sized input. This is also the input dimension of the OverFeat CNN which we utilize in our model. We do not crop image to make sure that a visually significant object is not cropped unintentionally, which will make it harder to identify it.
We convert all sentences into lower-case, then remove punctuation and any other non-alphanumeric character from them, and tokenize them into a sequence of individual words. We filter out the articles "a", "an", and "the" since we believe they will not contribute to the semantic value of the sentence. Finally we limit the word vocabulary by number of occurrences. For unigram BoW, our vocabulary contains 5,000 words, while for bi-grams and tri-grams we use 50,000 vocabulary size. We experiment with treating these n-gram as both binary features and tf-idf (term frequency -inverse document frequency) features. The equation for calculating tf-idf is below: Here, count(w, d) is the occurrence frequency of word w in a document d, while count(w, D) is the number of documents containing the word w. |d| is the size of the vocabulary, while |D| is the total number of documents. Tf-idf values have the advantage of storing relevance information, for example if a word is frequent in all documents it gets a low tf-idf score. This can be used to filter out stop words.

Evaluation Metrics
In this sections below we will report the results of our models on sets of mainly Flickr30K data set and occasionally FLickr8K .Recall@K (R@K) is the most widely used metric in this domain.It is defined as the percentage of test queries for which a model returns the positive item among the top k results. It is useful in the context of search where a user may be satisfied with the first k results containing a single relevant item.
However, this definition is ambiguous if there are more than one positive results for each test query. This is true for imageannotation in our case, since each image corresponds with 5 sentences. Some researchers only consider the first out of 5 sentences in test cases (e.g. [Hodosh et al., 2013,Gong et al., 2014) while others include all 5 (e.g. [Karpathy et al., 2014]). We will take both into account, and report the following evaluation metrics: • R@K 1 st _txt: This is the Recall@K taking into consideration only the first out of five sentences for each image • R@K rnd_txt: This is the Recall@K taking into consideration one random sentence (determined at test time) for each image.
• R@K avg_txt: This is the Recall@K taking into consideration all five of the sentences for each image one by one (iteratively), and then taking average over them. This is the most robust metric, since it does not depend on the relative position of sentence, and takes all sentences into account. Hence we use it for comparing our models.
• R@K any_txt: This is the Recall@K taking into consideration any one of the five sentences. It returns a match if the image matches any one of the five sentences. This is only valid for imagecaption because it needs multiple positive results for each query.
• med r: It is the value of k for which the R@K is equal to 50%. In search intuition, it is the number of results to be displayed for making the probability of correct result appearing in the search results exactly 50%.
When calculating med r we use Recall@K: avg_txt.
• rPrecision(5): It is the percentage of relevant items among the top 5 responses returned by the system. We select 5 because that is the maximum number of positive responses for imageannotation. Since image search has only one relevant result, this metric is not relevant for it.

Training Details
We train our model in an end-to-end fashion using stochastic gradient descent (SGD) without momentum and weight decay terms. In all our experiments we fix the parameters of OverFeat network so its weights don't update with back propagation. In general it takes 1-2 days (depending on the size of the model) to fully train our model on the Flickr30K data set, using a CPU with 8 cores (16 threads). Typically the network runs for 50 epochs before termination. Out of the Flickr8K and FLickr30K data set we separate random 1000 images (And corresponding sentences) as the test set, and 5% of the remaining examples as a held-out validation set for model selection. We tried several models and selected the meta-parameters based on performance on the held-out validation set. We select the parameters mentioned in 6.1 for all our experiments for fair comparison.

Experimental Results
First of all, we would give a figure to show the error performance during training. Figure 6.1 shows that our model performs well on the validation set (with error going below 6%). This is in comparison to our very first model which failed to generalize on the validation set, as seen in Figure 4.1. We can also see that the performance on validation set saturates around the 20 th epoch, and we only save the networks to the point that the performance does not saturate yet on the validation set. This is done to minimize the chance of overfitting on the training set.

I2T and T2I training approach
As explained in Chapter 5.3 we tried to methodologies for generating negative samples at training time, namely: I2T and T2I. We notice that this choice actually does impact the performance of our system in a peculiar way; it specializes it to a particular task. As is apparent from Table 6.2, using I2T methodology gives higher performance for image annotation tasks and T2I methodology gives higher performance for image annotation task. We compare the performance across several models architectures and consistently notice the same phenomenon. Hence for all future results, whenever we refer to image annotation we report I2T results, and for image search we report T2I results.
Intuitively, the reason for this specialization is that I2T approach more closely matches with image annotation and T2I with image search. In I2T the images in both positive and negative samples are the same, while the sentences are different, so the system learns to be better at recognizing changes in sentences and hence ultimately performs better at image annotation. Vice versa holds for T2I and image search. It is, however, important to note that even after this specialization the each individually trained system is bi-directional and can do both tasks with reasonable accuracy (as seen from Table 5.3. To all look at more results (and other evaluation metrics for comparison) for comparing I2T and T2I methodology, please look at

Results of BoW model
First we will report the results of our BoW model, in which our textual model is simply an MLP with unigram word features. All information about temporal dependency in the sentence is lost and we use a dictionary size of 5,000 most frequently words (after removing "a", "an" and "the"). We also use binary features so there is no information about multiple occurrences of words in a sentence. The hidden layer of textual model is fixed to 300 units, since the word2vec embeddings have dimensionality of 300. We fixed the hidden layer of the trainable visual model to 1,000 units, and the size of multimodal embedding vector is also fixed to 1,000. Table 6.3 shows the results on Flickr8K test set, and Table  6.4 shows results on Flickr30K test set (both of size 1,000 images). We use this model named as our model: BoW when comparing results in Chapter 7.
Inspecting the tables, the results look quite promising, and we are ready to explore more architectures and parameters.

Word2Vec results
Next we investigate the effect of Word2Vec embeddings. As stated earlier, we used these as a way to have good initialization of our textual model. Since we initialization. R@K is Recall@K (high is good). Med r is the median rank (low is good). rPrecision(5) is the precision at rank 5 (high is good).
don't train our model on a large corpus of text, we speculate word2vec would be helpful. We repeat the experiment on Flickr30K using BoW model, with the only difference that we use randomly initialized network. Doing this experiment is useful because we suggested using n-gram models as a second step onto BoW model, however we are aware of no such publicly available n-gram embeddings.
The results of the experiment are shown in Table 6.5 which we can compare with Table 6.4. A quick comparison between the performance metrics in these two tables shows that although word2vec initialization does help in improving the accuracy of the system, but the effects are not extremely drastic. For example R@10:avg_txt for image annotation increases by 3.3% while for image search increases by 3.86%.
The results are significant in suggesting the importance of using word2vec for initializing our models, but we feel that the gap may be bridged with using more complicated models without this initialization.  Table 6.5: Flickr30K experiments without Word2Vec initialization. R@K is Re-call@K (high is good). Med r is the median rank (low is good). rPrecision(5) is the precision at rank 5 (high is good).

Results of n-gram models
We replaced the BoW textual model with n-gram model. N-gram models conserve some sentence-order information and so theoretically they act as better features. In our experiments we tried bigrams (2g), trigrams (3g) and trigrams + skip grams (tk3). In all these cases the vocabulary size is fixed to 50,000 which is the size of input layer of textual model MLP. Table 6.6 shows a comparison between these three different kind of models for our task.
The results show that both bigrams and trigrams perform better in different settings, while inclusion of skip grams in trigram model consistently resulted in worst performance.  Table 6.6: Comparison between different n-gram models, on Flickr30K data. 2g is bi-gram, 3g is trigram and tk3 is combination of tri-gram and skip-gram features. In all case size of input vocabulary is 50,000 and all rest model parameters are similar. The bold figures show best results in the specific row. n hu is the hidden layer in the textual model, while n emb is the size of embedding dimension.

n-gram model comparison
Following this we also experimented on using either binary or tf-idf valued features. Intuition suggests that tf-idf encode more information and so should perform better than binary features. However, empirical evidence suggests otherwise as binary features performed better in most of our models. Hence for future models we stick with binary features. The results are shown in Finally we select the best performing model as having 1,000 unit hidden layers in both textual and trainable visual models, and also 1,000 unit multimodal embedding vector. The results of this model on Flickr30K are shown in Figure  6.8, and we notice significant improvements over the BoW model. We use this model named as our model: n-gram when comparing results in Chapter 7.

Are deep textual models necessary
Now we will, investigate if a deep network is really necessary in the textual model. We explored several shallow single layered architectures, where the input n-gram input is linearly transformed into the embedding vector. Surprisingly, almost all of the networks we tried reached performance close to the ones we achieved with a deeper network with non-linearities. In addition to performing well, these shallow models were approximately 3× faster to train (ignoring the time required for OverFeat feature vector generation -since it is not fine tuned, it is equivalent to only single time pass) We reached the best performance using a 300 dimensional embedding (linearly connected with 5,000 input units). The small trainable visual network also  Table 6.9: Flickr30K experiments with bigram model and binary inputs. R@K is Recall@K (high is good). Med r is the median rank (low is good). rPrecision(5) is the precision at rank 5 (high is good).
Lastly, we also explored using the SSE (semantic sequence embedding) module as our textual model. Details of architecture are given in Chapter 5. It has specialized architecture for modeling sequence inside variable length sentences, and similar architectures have achieved good performance in task such as language modeling [Collobert and Weston, 2008] and review based sentiment analysis [Bespalov et al., 2011]. We were hopeful that it would result in performance boost on our task as well.
However, empirical results show another story and the model performs not as well as other previously discussed models. The results of the best model architecture are shown in Table 6.10. The architecture has context window of size 5 and both word level and phrase level embeddings of 300 dimensions. This model is initialized with word2vec, and it is important to note that if we did not use word2vec initialization the performance fell staggeringly to about half the current performance.
We feel a possible reason of the failure of SSE as our textual module is because there isn't enough textual training data. Our data set is limited to 150,000 sentences (5 sentences for each of approximately 30,000 images). This makes a total of approximately 1.5-2 million words. In contrast [Collobert and Weston, 2008] use 631 million words to train their language model with similar architecture. The SSE architecture is much deeper and has more parameters than other textual models we tried, it has 4 distinct layers: lookup table with individual word embeddings (which we initialized with word2vec), CNN with fixed window for phrase level embeddings, averaging layer for complete sentence layer embedding and finally a non-linearity followed by a linear layer for greater modeling capacity. Because of this deep architecture, it is not unlikely that it needs more multimodal data to train well.
Secondly, the fact that it word2vec boosts its performance (validation error at train time saturates at about 15% if not using word2vec and at about 8% if using word2vec in most models) also means that it is unable to learn good word embeddings if initialized from random. In contrast when we initialized our BoW model without word2vec, the difference in performance was not much slighter. This again reinforces our opinion that more data is needed.

Comparison with existing systems
We would like to compare the performance of our model with existing state of the art systems. However, we noted in Chapter 6.2 that there is inherent ambiguity in the way the most common evaluation metric (Recall@K) is defined for this task. In addition to this, researchers often differ how they present the results. We use all 5 sentences while evaluating our system. For comparing image annotation task we will report R@K avg_txt and for comparing image search task we will report R@K any_txt. Here we will follow the standard by [Karpathy et al., 2014], and this is how they report it to the best of our knowledge.  Table 6.11: Comparison between existing image text matching systems. R@K is Recall@K (high is good). In our models, for image annotation we report R@K: any_txt and for image search we report R@K: avg_txt.  [Socher et al., 2014] use SDT-RNN which is dependency-tree based recursive neural network. They also try other types of recurrent and recursive neural networks. Besides this [Karpathy et al., 2014] use dependency tree edges to fragment their sentences, and so on. In contrast we use simple textual model and achieve comparable results. The bulk of our model's strength comes from the visual model and the training methodology which specializes the performance towards a particular task boosting its performance. In our experiments we notice that temporal dependency (or information about word order) modeled with simple bi-grams or tri-grams is enough to achieve good results.

Chapter 7 Conclusion
The goal of the project was to explore deep learning architectures in the context of multimodal image and text modeling. Our task was based on bi-directional retrieval. This means that our model would support retrieving images based on a text query, and also retrieving text sentences based on an image query. Applications of such a system would include automatic image annotation, and sentence based image retrieval. To design our system we use the ranking approach which is common to many traditional information retrieval systems. At each iteration we feed our image with a positive pair and a negative pair of training input. A positive input is a matched pair of image and sentence (as labeled by a human), while a negative input is simply a mismatched pair. The model assigns a score to the positive input and to the negative input, and the objective function is to make the positive sample score higher than the negative sample. In this way the model will learn to rank related pair of image and text higher than an arbitrary unrelated pair.
Since images and text have very different statistical properties, it is necessary to model two different sub-models for them. The idea is that if both sub-models extract underlying semantic information (such as information about the content) and encode it into a distributed vector embedding, then a ranking objective function could align these two embeddings into a common multimodal space. Once this is the case, we can simply compute the distance betwen the two vectors as a measure of similarity. For the visual model we explored using deep convolutional neural network (CNN). Our initial model was initialized from random weights and it failed to perform well on our tasks. We did some experiments on different but related task of image recognition on MNIST and Caltech256, and were able to conclude lack of pretraining as a reason why the network failed. Following this we adopted OverFeat into our visual model, which is a publicly available CNN which achieved high performance on ILSVRC 2013. With just this change the network stats to work well on the task, which confirms our initial suspicion.
For our textual module we tried various models and features -some simple and some more complicated. We explored using bag of words approach as well as n-grams (bigrams, trigrams and skip grams), and tried binary and tf-idf features. We experimented with using shallow linear architectures, intermediate architecture like MLP and deeper architectures with word embeddings and convolutional neural network (for modeling variable length sentence by averaging over a fixed window).
We evaluate the performance of our models by testing them on Flickr8K and Flickr30K training sets. A comparison with recent work in the field shows that even though our models are simpler, we achieve performance comparable to some of the top results. We believe that a major reason for our good performance is the performance of the CNN, which extracts very powerful and semantically relevant features. Although like other approaches, OverFeat is trained on the ImageNet data base, but it is trained with special tricks like multiple-image fragments, multiple-scales, maximizing image localization, introducing color and translation invariance with data augmentation. Because of this the network achieves excellent performance on ILSVRC 2013 [Sermanet et al., 2014] challenge, and this also increases the quality of feature vectors extracted by the model.
For the textual module we observed that even a very shallow module with a single linear layer achieves very good performance. Although using hidden layers and increasing the dimensionality of the embedding layer does enhance the performance, but performance is still good with a simple linear layer. This provides an interesting contrast between the visual module and the textual module. Since only a very well pretrained CNN was able to train on the task. However a more specialized and deeper architecture (SSE) does not perform so well on the textual side. This provides a fundamental question of how essential is deep learning in this task? We think that the only reason CNN performs well is that it was pretrained with a lot of data to extract semantic features from images. So in order to make a textual model work well we either need a very large scale image-text data base, or we need to pretrain the deeper textual model on tasks which allow it to extract semantic information from sentences. An example of such a task could be document classification.
Finally, we show an important feature of our bi-directional retrieval models: that they can be specialized to one task (either image search or image retrieval). We use empirical results to show that the methodology of generating negative sample has a significant on the final performance of the model. If we use the I2T approach the model specializes in image annotation, and if we use T2I it specializes in image search. Note that it still remains bi-directional and gives good performance for the other task as well.

Future work
The simplest addition to our model would be to turn on updating for our CNN while we are training on the image-text data set. This is called finetuning, since the CNN is pretrained on image data alone. We expect to achieve performance improvement by this finetuning, as reported by [Karpathy et al., 2014] and seen in the Table 6.11. However this will come at a cost of significantly additional training time, hence it is a trade off.
As noted in Chapter 6.5, we experimented with a more promising model SSE but experienced a performance drop to our surprise. We hypothesize that this is because the complicated and deeper model needs a larger training data to perform well, something which is far from true with our Flickr30K and Flickr8K data sets. Interestingly, this problem is similar to what we faced initially with our visual model and explained in Chapter 4. Our uninitialized CNN failed at the tasks miserably, which convinced us to use a CNN pretrained on ImageNet. We similarly feel that an SSE module trained on large relevant data would significantly improve our results. We experienced a portion of this when -as we reported -initializing the first layer of the SSE with word2vec caused the accuracy of the model to almost double (albeit still lesser than our simpler models). This means that although word2vec are good word embeddings, but they are not enough for the task of multimodal learning since they were initially learned on just a unimodal language model. The best approach would be to use a large image-text data base to train our models, however a high quality large scale data base does not exist in this task yet. Regeradless, there are some data sets that we aim to use in the future.
MS-COCO 1 is a data set which provides high quality captions labeled by 5 different humans, for more than 100,000 images. Although still not an extremely large data set, it is the first we hope to try our models on. Some other larger data sets exist but their usability in image text mapping systems has been questioned. Flickr1M 2 is an example of such data set which contains 1 million images from Flickr website associated with captions added by people uploading the images. [Hodosh et al., 2013] argue that such captions do not act in good association with images, since humans tend to describe the aspects of the images which are not so apparent from the image itself. In contrast, our system only wants to know what is apparent inside the image. [Gong et al., 2014] explored using a good quality dataset (Flickr30K) to improve performance on a low quality annotated data sets (SBU1M and Flickr1M). We propose that it would be interesting to explore the opposite: to pretrain our model with large amount of weakly annotated text and then finetuning it on data sets like Flickr30K and MS-COCO.
Another exciting area to explore is using data augmentation similar to how it is being used in visual models for image recognition. In other words we could artificially augment the textual data (number of sentences) matching each image in our training set. There can be three ways of doing this. Firstly we could use the original human labeled sentences as seeds and use text based information retrieval systems to retrieve similar sentences from a large textual corpus. Secondly we could design a language model to generate more sentences similar to the one it is given as input. Thirdly, we could use an image-based sentence generation system to generate additional relevant sentences and use these when training our retrieval system. Once we have a larger amount of text corresponding to images we can better train deeper and high-capacity models, and also better model inherent variance in describing an image. The next step is to expand the system with some ideas presented above. These include, finetuning our CNN, pretraining entire system on a weekly annotated large scale data set, and artificially augmenting textual data. This is our first experimentation with image text multimodal modeling system, and we aim to keep on improving it.

B.4 Pascal VOC 2008
This was the first publicly available data set purposefully collected for the image text ranking task by [Farhadi et al., 2010] This data set consists of 1,000 images from PASCAL VOC-2008 object recognition challenge. 50 images are randomly selected belonging to each of the 20 categories. Each image is annotated with 5 descriptive captions using Amazon's Mechanical Turk, resulting in 5,000 sentences.
Although, being the first specific data set, it suffers from a number of shortcomings which limit its usefulness. The domain of its images is very limited and the captions are relatively simple and sometimes containing grammatical and spelling errors [Hodosh et al., 2013].