A Neural Compositional Paradigm for Image Captioning

Mainstream captioning models often follow a sequential structure to generate captions, leading to issues such as introduction of irrelevant semantics, lack of diversity in the generated captions, and inadequate generalization performance. In this paper, we present an alternative paradigm for image captioning, which factorizes the captioning procedure into two stages: (1) extracting an explicit semantic representation from the given image; and (2) constructing the caption based on a recursive compositional procedure in a bottom-up manner. Compared to conventional ones, our paradigm better preserves the semantic content through an explicit factorization of semantics and syntax. By using the compositional generation procedure, caption construction follows a recursive structure, which naturally fits the properties of human language. Moreover, the proposed compositional procedure requires less data to train, generalizes better, and yields more diverse captions.

Introduction
Image captioning, the task to generate short descriptions for given images, has received increasing attention in recent years. State-of-the-art models [1,2,3,4] mostly adopt the encoder-decoder paradigm [3], where the content of the given image is first encoded via a convolutional network into a feature vector, which is then decoded into a caption via a recurrent network. In particular, the words in the caption are produced in a sequential manner -the choice of each word depends on both the preceding word and the image feature. Despite its simplicity and the effectiveness shown on various benchmarks [5,6], the sequential model has a fundamental problem. Specifically, it could not reflect the inherent hierarchical structures of natural languages [7,8] in image captioning and other generation tasks, although it could implicitly capture such structures in tasks taking the complete sentences as input, e.g. parsing [9], and classification [10].
As a result, sequential models have several significant drawbacks. First, they rely excessively on n-gram statistics rather than hierarchical dependencies among words in a caption. Second, such models usually favor the frequent n-grams [11] in the training set, which, as shown in Figure 1, may lead to captions that are only correct syntactically but not semantically, containing semantic concepts that are irrelevant to the conditioned image. Third, the entanglement of syntactic rules and semantics obscures the dependency structure and makes sequential models difficult to generalize.
To tackle these issues, we propose a new paradigm for image captioning, where the extraction of semantics (i.e. what to say) and the construction of syntactically correct captions (i.e. how to say) are decomposed into two stages. Specifically, it derives an explicit representation of the semantic content of the given image, which comprises a set of noun-phrases, e.g. a white cat, a cloudy sky or two men. With these noun-phrases as the basis, it then proceeds to construct the caption through recursive composition until a complete caption is obtained. In particular, at each step of the composition, a higher-level phrase is formed by joining two selected sub-phrases via a connecting phrase. It is a large building with a clock tower a building with a clock on the side of it a building with a clock on the side of it Figure 1: This figure shows three test images in MS-COCO [5] with captions generated by the neural image captioner [3], which contain n-gram building with a clock that appeared frequently in the training set but is not semantically correct for these images.
noteworthy that the compositional procedure described above is not a hand-crafted algorithm. Instead, it consists of two parametric modular nets, a connecting module for phrase composition and an evaluation module for deciding the completeness of phrases.
The proposed paradigm has several key advantages compared to conventional captioning models: (1) The factorization of semantics and syntax not only better preserves the semantic content of the given image but also makes caption generation easy to interpret and control. (2) The recursive composition procedure naturally reflects the inherent structures of natural language and allows the hierarchical dependencies among words and phrases to be captured. Through a series of ablative studies, we show that the proposed paradigm can effectively increase the diversity of the generated captions while preserving semantic correctness. It also generalizes better to new data and can maintain reasonably good performance when the number of available training data is small.

Related Work
Literature in image captioning is vast, with the increased interest received in the neural network era. The early approaches were bottom-up and detection based, where a set of visual concepts such as objects and attributes were extracted from images [12,13]. These concepts were then assembled into captions by filling the blanks in pre-defined templates [13,14], learned templates [15], or served as anchors to retrieve the most similar captions from the training set [16,12].
Recent works on image captioning adopt an alternative paradigm, which applies convolutional neural networks [17] as image representation, followed by recurrent neural networks [18] for caption generation. Specifically, Vinyals et al [3] proposed the neural image captioner, which represents the input image with a single feature vector, and uses an LSTM [18] conditioned on this vector to generate words one by one. Xu et al [4] extended their work by representing the input image with a set of feature vectors, and applied an attention mechanism to these vectors at every time step of the recurrent decoder in order to extract the most relevant image information. Lu et al [1] adjusted the attention computation to also attend to the already generated text. Anderson et al [2] added an additional LSTM to better control the attention computation. Dai et al [19] reformulated the latent states as 2D maps to better capture the semantic information in the input image. Some of the recent approaches directly extract phrases or semantic words from the input image. Yao et al [20] predicted the occurrences of frequent training words, where the prediction is fed into the LSTM as an additional feature vector. Tan et al [21] treated noun-phrases as hyper-words and added them into the vocabulary, such that the decoder was able to produce a full noun-phrase in one time step instead of a single word. In [22], the authors proposed a hierarchical approach where one LSTM decides on the phrases to produce, while the second-level LSTM produced words for each phrase.
Despite the improvement over the model architectures, all these approaches generate captions sequentially. This tends to favor frequent n-grams [11,23], leading to issues such as incorrect semantic coverage, and lack of diversity. On the contrary, our proposed paradigm proceeds in a bottom-up manner, by representing the input image with a set of noun-phrases, and then constructs captions according to a recursive composition procedure. With such explicit disentanglement between semantics and syntax, the recursive composition procedure preserves semantics more effectively, requires less data to learn, and also leads to more diverse captions.
Work conceptually related to ours is by Kuznetsova et al [24], which mines four types of phrases including noun-phrases from the training captions, and generates captions by selecting one phrase from each category and composes them via dynamic programming. Since the composition procedure is not recursive, it can only generate captions containing a single object, thus limiting the versatile  Figure 2: An overview of the proposed compositional paradigm. A set of noun-phrases is extracted from the input image first, serving as the initial pool of phrases for the compositional generation procedure. The procedure then recursively uses a connecting module to compose two phrases from the pool into a longer phrase, until an evaluation module determines that a complete caption is obtained.
nature of image description. In our work, any number of phrases can be composed, and we exploit powerful neural networks to learn plausible compositions.

Compositional Captioning
The structure of natural language is inherently hierarchical [8,7], where the typical parsing of a sentence takes the form of trees [25,26,27]. Hence, it's natural to produce captions following such a hierarchical structure. Specifically, we propose a two-stage framework for image captioning, as shown in Figure 2. Given an image, we first derive a set of noun-phrases as an explicit semantic representation. We then construct the caption in a bottom-up manner, via a recursive compositional procedure which we refer to as CompCap. This procedure can be considered as an inverse of the sentence parsing process. Unlike mainstream captioning models that primarily rely on the n-gram statistics among consecutive words, CompCap can take into account the nonsequential dependencies among words and phrases of a sentence. In what follows, we will present these two stages in more detail.

Explicit Representation of Semantics
Conventional captioning methods usually encode the content of the given image into feature vectors, which are often difficult to interpret. In our framework, we represent the image semantics explicitly by a set of noun-phrases, e.g. "a black cat", "a cloudy sky" and "two boys". These noun-phrases can capture not only the object categories but also the associated attributes.
Next, we briefly introduce how we extract such noun-phrases from the input image. It's worth noting that extracting such explicit representation for an image is essentially related to tasks of visual understanding. While more sophisticated techniques can be applied such as object detection [28] and attribute recognition [29], we present our approach here in order to complete the paradigm.
In our study, we found that the number of distinct noun-phrases in a dataset is significantly smaller than the number of images. For example, MS-COCO [5] contains 120K images but only about 3K distinct noun-phrases in the associated captions. Given this observation, it is reasonable to formalize the task of noun-phrase extraction as a multi-label classification problem.
Specifically, we derive a list of distinct noun-phrases {N P 1 , N P 2 , ..., N P K } from the training captions by parsing the captions and selecting those noun-phrases that occur for more than 50 times. We treat each selected noun-phrase as a class. Given an image I, we first extract the visual feature v via a Convolutional Neural Network as v = CNN(I), and further encode it via two fully-connected layers as x = F (v). We then perform binary classification for each noun-phrase where w k is the weight vector corresponding to the class N P k and σ denotes the sigmoid function.
Given {S C (N P k |I)} k , the scores for individual noun-phrases, we choose to represent the input image using n of them with top scores. While the selected noun-phrases may contain semantically similar concepts, we further prune this set through Semantic Non-Maximum Suppression, where only those noun-phrases whose scores are the maximum among similar phrases are retained.

Recursive Composition of Captions
Starting with a set of noun-phrases, we construct the caption through a recursive compositional procedure called CompCap. We first provide an overview, and describe details of all the components in the following paragraphs.
At each step, CompCap maintains a phrase pool P, and scans all ordered pairs of phrases from P. For each ordered pair P (l) and P (r) , a Connecting Module (C-Module) is applied to generate a sequence of words, denoted as P (m) , to connect the two phrases in a plausible way. This yields a longer phrase in the form of P (l) ⊕ P (m) ⊕ P (r) , where ⊕ denotes the operation of sequence concatenation. The C-Module also computes a score for P (l) ⊕ P (m) ⊕ P (r) . Among all phrases that can be composed from scanned pairs, we choose the one with the maximum connecting score as the new phrase P new . A parametric module could also be used to determine P new .
Subsequently, we apply an Evaluation Module (E-Module) to assess whether P new is a complete caption. If P new is determined to be complete, we take it as the resulting caption; otherwise, we update the pool P by replacing the corresponding constituents P (l) and P (r) with P new , and invoke the pair selection and connection process again based on the updated pool. The procedure continues until a complete caption is obtained or only a single phrase remains in P.
We next introduce the connecting and the evaluation module, respectively.
The Connecting Module. The Connecting Module (C-Module) aims to select a connecting phrase P (m) given both the left and right phrases P (l) and P (r) , and to evaluate the connecting score S(P (m) | P (l) , P (r) , I). While this task is closely related to the task of filling in the blanks of captions [30], we empirically found that the conventional way of using an LSTM to decode the intermediate words fails. One possible reason is that inputs in [30] are always prefix and suffix of a complete caption. The C-Module, by contrast, mainly deals with incomplete ones, constituting a significantly larger space. In this work, we adopt an alternative strategy, namely, to treat the generation of connecting phrases as a classification problem. This is motivated by the observation that the number of distinct connecting phrases is actually limited in the proposed paradigm, since semantic words such as nouns and adjectives are not involved in the connecting phrases. For example, in MS-COCO [5], there are over 1 million samples collected for the connecting module, which contain only about 1, 000 distinct connecting phrases.
Specifically, we mine a set of distinct connecting sequences from the training captions, denoted as {P L }, and treat them as different classes. This can be done by walking along the parsing trees of captions. We then define the connecting module as a classifier, which takes the left and right phrases P (l) and P (r) as input and outputs a normalized score S(P In particular, we adopt a two-level LSTM model [2] to encode P (l) and P (r) respectively, as shown in Figure 3. Here, x t is the word embedding for t-th word, and v and {u 1 , ..., u M } are, respectively, global and regional image features extracted from a Convolutional Neural Network. In this model, the low-level LSTM controls the attention while interacting with the visual features, and the high-level LSTM drives the evolution of the encoded state. The encoders for P (l) and P (r) share the same structure but have different parameters, as one phrase should be encoded differently based on its place in the ordered pair. Their encodings, denoted by z (l) and z (r) , go through two fully-connected layers followed by a softmax layer, as | P (l) , P (r) , I), are then used as the connecting scores, and the connecting phrase that yields the highest connecting score is chosen to connect P (l) and P (r) .
While not all pairs of P (l) and P (r) can be connected into a longer phrase, in practice a virtual connecting phrase P (m) neg is added to serve as a negative class. Based on the C-Module, we compute the score for a phrase as follow. For each noun-phrase P in the initial set, we set its score to be the binary classification score S C (P |I) obtained in the phrasefrom-image stage. For each longer phrase produced via the C-Module, its score is computed as The Evaluation Module. The Evaluation Module (E-Module) is used to determine whether a phrase is a complete caption. Specifically, given an input phrase P , the E-Module encodes it into a vector z e , using a two-level LSTM model as described above, and then evaluates the probability of P being a complete caption as It's worth noting that other properties could also be checked by the E-Module besides the completeness. e.g. using a caption evaluator [11] to check the quality of captions.
Extensions. Instead of following the greedy search strategy described above, we can extend the framework for generating diverse captions for a given image, via beam search or probabilistic sampling. Particularly, we can retain multiple ordered pairs at each step and multiple connecting sequences for each retained pair. In this way, we can form multiple beams for beam search, and thus avoid being stuck in local minima. Another possibility is to generate diverse captions via probabilistic sampling, e.g. sampling a part of the ordered pairs for pair selection instead of using all of them, or sampling the connecting sequences based on their normalized scores instead of choosing the one that yields the highest score.
The framework can also be extended to incorporate user preferences or other conditions, as it consists of operations that are interpretable and controllable. For example, one can influence the resultant captions by filtering the initial noun phrases or modulating their scores. Such control is much easier to implement on an explicit representation, i.e. a set of noun phrases, than on an encoded feature vector. We show examples in the Experimental section.

Experiment Settings
All experiments are conducted on MS-COCO [5] and Flickr30k [6]. There are 123, 287 images and 31, 783 images respectively in MS-COCO and Flickr30k, each of which has 5 ground-truth captions. We follow the splits in [31] for both datasets. In both datasets, the vocabulary is obtained by turning words to lowercase and removing words that have non-alphabet characters and appear less than 5 times. The removed words are replaced with a special token UNK, resulting in a vocabulary of size 9, 487 for MS-COCO, and 7, 000 for Flickr30k. In addition, training captions are truncated to have at most 18 words. To collect training data for the connecting module and the evaluation module, we further parse ground-truth captions into trees using NLPtookit [32].
In all experiments, C-Module and E-Module are separately trained as in two standard classification tasks. Consequently, the recursive compositional procedure is modularized, making it less sensitive to training statistics in terms of the composing order, and generalizes better. When testing, each step of the procedure is done via two forward passes (one for each module). We empirically found that a complete caption generally requires 2 or 3 steps to obtain.
Several representative methods are compared with CompCap. They are 1) Neural Image Captioner (NIC) [3], which is the backbone network for state-of-the-art captioning models. 2) AdapAtt [1] and 3) TopDown [2] are methods that apply the attention mechanism and obtain state-of-the-art performances. While all of these baselines encode images as semantical feature vectors, we also compare CompCap with 4) LSTM-A5 [20], which predicts the occurrence of semantical concepts as additional visual features. Subsequently, besides being used to extract noun-phrases that fed into CompCap, predictions of the noun-phrase classifiers also serve as additional features for LSTM-A5.
To ensure a fair comparsion, we have re-implemented all methods, and train all methods using the same hyperparameters. Specifically, we use ResNet-152 [17] pretrained on ImageNet [33] to extract image features, where activations of the last convolutional and fully-connected layer are used respectively as the regional and global feature vectors. During training, we fix ResNet-152 without finetuning, and set the learning rate to be 0.0001 for all methods. When testing, for all methods we select parameters that obtain best performance on the validation set to generate captions. Beam-search of size 3 is used for baselines. As for CompCap, we empirically select n = 7 noun-phrases with top scores to represent the input image, which is a trade-off between semantics and syntax, as shown in Figure 8. Beam-search of size 3 is used for pair selection, while no beam-search is used for connecting phrase selection.

Experiment Results
General Comparison. We compare the quality of the generated captions on the offline test set of MS-COCO and the test set of Flickr30k, in terms of SPICE (SP) [34], CIDEr (CD) [35], BLEU-4 (B4) [36], ROUGE (RG) [37], and METEOR (MT) [38]. As shown in Table 1, among all methods, CompCap with predicted noun-phrases obtains the best results under the SPICE metric, which has higher correlation with human judgements [34], but is inferior to baselines in terms of CIDEr, BLEU-4, ROUGE and METEOR. These results well reflect the properties of methods that generate captions sequentially and compositionally. Specifically, while SPICE focuses on semantical analysis, metrics including CIDEr, BLEU-4, ROUGE and METEOR are known to favor frequent training n-grams [11], which are more likely to appear when following a sequential generation procedure. On the contrary, the compositional generation procedure preserves semantic content more effectively, but may contain more n-grams that are not observed in the training set. An ablation study is also conducted on components of the proposed compositional paradigm, as shown in the last three rows of Table 1. In particular, we represented the input image with groundtruth noun-phrases collected from 5 associated captions, leading to a significant boost in terms of all metrics. This indicates that CompCap effectively preserves the semantic content, and the better the semantic understanding we have for the input image, CompCap is able to generate better captions for us. Moreover, we also randomly picked one ground-truth caption, and followed its composing order to integrate its noun-phrases into a complete caption, so that CompCap only accounts for connecting phrase selection. As a result, metrics except for SPICE obtain further boost, which is reasonable as we only use a part of all ground-truth noun-phrases, and frequent training n-grams are more likely to appear following some ground-truth composing order.
Generalization Analysis. As the proposed compositional paradigm disentangles semantics and syntax into two stages, and CompCap mainly accounts for composing semantics into a syntactically correct caption, CompCap is good at handling out-of-domain semantic content, and requires less data to learn. To verify this hypothesis, we conducted two studies. In the first experiment, we controlled the ratio of data used to train the baselines and modules of CompCap, while leaving the noun-phrase classifiers being trained on full data. The resulting curves in terms of SPICE and CIDEr are shown in   In the second study, we trained baselines and CompCap on MS-COCO/Flickr30k, and tested them on Flickr30k/MS-COCO. Again, the noun-phrase classifiers are trained with in-domain data. The results in terms of SPICE and CIDEr are shown in Figure 5, where significant drops are observed for the baselines. On the contrary, competitive results are obtained for CompCap trained using in-domain and out-of-domain data, which suggests the benefit of disentangling semantics and syntax, as the distribution of semantics often varies from dataset to dataset, but the distribution of syntax is relatively stable across datasets.
Diversity Analysis. One important property of CompCap is the ability to generate diverse captions, as these can be obtained by varying the involved noun-phrases or the composing order. To analyze the diversity of captions, we computed five metrics that evaluate the degree of diversity from various aspects. As shown in Table 2, we computed the ratio of novel captions and unique captions [39], which respectively account for the percentage of captions that are not observed in the training set, and the percentage of distinct captions among all generated captions. We further computed the percentage of words in the vocabulary that are used to generate captions, referred to as the vocabulary usage.
Finally, we quantify the diversity of a set of captions by averaging their pair-wise editing distances, which leads to two additional metrics. Specifically, when only a single caption is generated for each image, we report the average distance over captions of different images, which is defined as the diversity at the dataset level. If multiple captions are generated for each image, we then compute the average distance over captions of the same image, followed by another average over all images. The final average is reported as the diversity at the image level. The former measures how diverse the captions are for different images, and the latter measures how diverse the captions are for a single image. In practice, we use 5 captions with top scores in the beam search to compute the diversity at the image level, for each method.  CompCap obtained the best results in all metrics, which suggests that captions generated by CompCap are diverse and novel. We further show qualitative samples in Figure 6, where captions are generated following different composing orders, or using different noun-phrases.
Error Analysis. We include several failure cases in Figure 7, which share similar errors with the results listed in Figure 1. However, the causes are fundamentally different. Generally, errors in captions generated by CompCap mainly come from the misunderstanding of the input visual content, which could be fixed by applying more sophisticated techniques in the stage of noun-phrase extraction. It's, by contrast, an intrinsic property for sequential models to favor frequent n-grams. With a perfect understanding of the visual content, sequential models may still generate captions containing incorrect frequent n-grams.

Conclusion
In this paper, we propose a novel paradigm for image captioning. While the typical existing approaches encode images using feature vectors and generate captions sequentially, the proposed method generates captions in a compositional manner. In particular, our approach factorizes the captioning procedure into two stages. In the first stage, an explicit representation of the input image, consisting of noun-phrases, is extracted. In the second stage, a recursive compositional procedure is applied to assemble extracted noun-phrases into a caption. As a result, caption generation follows a hierarchical structure, which naturally fits the properties of human language. On two datasets, the proposed compositional procedure is shown to preserve semantics more effectively, require less data to train, generalize better across datasets, and yield more diverse captions.

A Semantic Non-Maximum Suppression for Noun Phrases
The key for suppression is to find semantically similar noun-phrases. To do that, we first compare the central nouns in noun-phrases, where if two central nouns are synonyms, or plurals of synonyms, we then regard their corresponding noun-phrases as semantically similar. On the other hand, two noun-phrases that do not have synonymic central nouns are also likely to be semantically similar, conditioned on the input image. e.g. a man and a cook conditioned on an image of somebody in a kitchen. To suppressing noun-phrases in such cases, we use encoders in the C-Module (See sec 3.2 of the main content) to get two encodings z (l) and z (r) for each noun-phrase. Intuitively, if two noun-phrases are semantically similar conditioned on the input image, the normalized euclidean distance between their encodings should be small. As a result, we compute the normalized euclidean distances respectively for z (l) and z (r) of two noun-phrases, and take the sum of two distances as the measurement, which is more robust than using a single encoding. Finally, if the sum of distances is less than we then regard the corresponding noun-phrases as semantically similar, conditioned on the input image. In practice, we use = 0.002, which is obtained by grid search on the evaluation set. As mentioned in the main content, the C-Module contains two encoders, respectively for P (l) and P (r) of an ordered pair. While these encoders share the same structure, we let them have independent parameters as the same phrase should have different encodings according to its position in the ordered pair. To show that, we compared C-Modules that have encoders with shared parameters or not, as shown in Table 3. The results support our hypothesis, where the C-Module that has encoders with independent parameters leads to better performance.

C Hyperparameters
Several additional hyperparameters can be tuned for CompCap, the size of beam search for pair selection and the size of beam search for connecting phrase selection. While we respectively set them to be 10 and 1 for experiments in the main content, here we show the curves of adjusting these hyperparameters, one at a time. The curves are shown in Figure 9, where the size of beam search for pair selection and connecting phrase selection have minor influence on the performance of CompCap.