Multi-modal Dependency Tree for Video Captioning
Year: 2022

Abstract:
Generating fluent and relevant language to describe visual content is critical for the video captioning task. Many existing methods generate captions using sequence models that predict words in a left-to-right order. In this paper, we investigate a graph structured model by explicitly modeling the hierarchical structure in the sentences to further improve the fluency and relevance of the generated captions. To this end, we propose a novel video captioning method that generates a sentence by first constructing a multi-modal dependency tree and then traversing the constructed tree, where the syntactic structure and semantic relationship in the sentence are represented by the tree topology. To take full advantage of the information from both vision and language, both the visual and textual representation features are encoded into each tree node. Different from existing dependency parsing methods that generate uni-modal dependency trees for language understanding, our method constructs multi-modal dependency trees for language generation of videos. We also propose a tree-structured reinforcement learning algorithm to effectively optimize the captioning model, where a novel reward is designed by evaluating the semantic consistency between the generated sub-trees and the ground-truth tree. Extensive experiments on several video captioning datasets demonstrate the effectiveness of the proposed method.

heading: 1 Introduction
text: Video captioning has received extensive attention from researchers in both computer vision and natural language processing. It is a challenging task since it requires not only understanding the visual content but also generating fluent and relevant sentences. With the success of deep neural networks in natural language processing, many existing video captioning methods [1, 2] use recurrent neural network (RNN) to generate sentences, which processes sequences by updating hidden states. Several recent studies [3–6] apply Transformer [7], which relates the words in the sequences using a self-attention mechanism, to video captioning. All these methods treat each sentence as a word sequence and generate words in a predefined left-to-right order by capturing the relatively close contextual relationship between words in the sentence.
In this paper, we investigate a graph structured model for video captioning to explicitly model the hierarchical structure in the sentence and capture the long-range dependency between words. With this in mind, we propose to generate a sentence by first constructing a multi-modal dependency tree in a top-down and depth-first order, and then traversing the tree in a recursive manner, as shown in Figure 1. Each node of the tree is represented by a multi-modal embedding representation that integrates the information from both visual and textual modalities. During the tree construction, each
∗Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
newly generated node receives the multi-modal embeddings from its parent and sibling nodes, and these multi-modal embeddings are used to predict the attention weights of the input features and the word. The attended visual feature and the predicted word are fused to generate the multi-modal embedding of the new node.
Different from existing sequence models that tend to focus on the dependency between each word and its close preceding words, our tree model sufficiently captures the global dependency structure in the sentence to further improve the fluency of the generated sentences. In contrast to the unimodal dependency tree widely used in dependency parsing for language analysis, our multi-modal dependency tree effectively integrates both the visual and linguistic information, improving the relevance of the output sentence to the visual input.
To effectively optimize the captioning model, we propose a tree-structured reinforcement learning algorithm and a novel node-level reward tailor-made for the tree construction process. By evaluating the consistency between the parent-child node pairs in the constructed tree and those in the ground truth trees, the tree node-level reward enables the model to capture the topological structure of the ground-truth dependency trees. Compared to the sequence-level rewards in existing methods, our node-level reward recognizes the contribution of each node to the multi-modal dependency tree and avoids the reward ambiguity problem [8].
To evaluate the effectiveness of the proposed method, we conduct experiments on two difficult video captioning datasets, the ActivityNet Captions dataset and Charades Captions dataset. We also perform experiments on two most widely-used datasets, namely the MSVD dataset and MSR-VTT dataset. Compared to MSVD and MSR-VTT, the sentences in the ActivityNet Captions dataset and Charades Captions dataset are typically longer and describe more complex activities in the videos. The experiments on these datasets demonstrate that our method not only generates long and complex sentences with high fluency and relevancy, but is also effective for relatively simple sentences.
The main contributions of this paper are as follows:
• We propose a multi-modal dependency tree construction method for video captioning. With the help of tree topology, our model generates more fluent and relevant sentences by effectively capturing the syntactic and semantic dependencies in natural language, especially when generating long and complex sentences. • We develop a novel tree-structured reinforcement learning algorithm that optimizes the
captioning model using a node-level reward, which facilitates learning the topology of the dependency trees and alleviates the reward ambiguity problem.

heading: 2 Related Work

heading: 2.1 Video Captioning
text: Thanks to the recent advances in computer vision and natural language processing, many video captioning methods based on the encoder-decoder framework have been proposed. The pioneers of video captioning methods [9] employ a convolutional neural network (CNN) to extract visual features and a recurrent neural network (RNN) to generate the words in the sentences in a sequential manner. To further improve the performance of video captioning, some methods [10, 11] apply the attention mechanism in video captioning, which enables the model to focus on different temporal segments when generating the sentences. Inspired by the advances in natural language processing, some methods [12, 13] propose to learn better syntax representations with the help of part-of-speech
tags. In order to provide richer semantic information to video captioning models, Rahman et al. [14] attempt to utilize the audio information.
Motivated by the advances in neural machine translation, several recent methods [3, 4, 6] investigate the application of Transformer [7] to video captioning, which uses multi-head self-attention mechanism to yield more expressive representations of the input. Some methods [15, 16] focus on optimizing video captioning models using reinforcement learning, where the rewards are calculated based on the n-gram statistics.
Instead of directly generating a word sequence, our method generates a sentence by first constructing a dependency tree and then traversing the tree. Compared to the sequence generation models, our method explicitly models the grammatical structure with tree topology and better preserves the semantic relationship by incorporating both visual and linguistic information into the dependency tree.

heading: 2.2 Tree-structured Language Generation
text: In recent years, tree-structured language generation methods are proposed for various natural language processing tasks, including program generation [17], generating math equation [18] and machine translation [19]. Alvarez et al. [17] generate the tree nodes in depth-first search order using doublyrecurrent neural network, which combines the hidden states from the parent node and the last sibling node when predicting the label for a new node. A dependency tree generation method is proposed by [19] to generate target sentences in machine translation. Instead of directly constructing the tree structure, this method generates canonizalized ternary trees where each node has a fixed number of child nodes. Liu et al. [18] propose to generate abstract syntax trees of math expressions to solve math problems described in natural language.
The work closest to our method is [20] that generates image captions by constructing canonicalized dependency trees. Different from this method that generates trees with only linguistic information, our method constructs multi-modal dependency trees that contain both visual and linguistic information to capture richer contextual information.

heading: 3 Our Method

heading: 3.1 Overview
text: In this section, we introduce the proposed multi-modal dependency tree generation framework. The training data is formulated as D = {(xj , Tj)|j}, where xj denotes the j-th video, and Tj denotes the dependency tree of the corresponding sentence. Our model follows the encoder-decoder paradigm, where both the encoder and the decoder are stacks of N self-attention layers. Given an input video, the encoder of our model takes a set of d-dimensional visual features F = {f1,f2, ...,fM} as input,
where fi ∈ Rd. The decoder firstly generates a multi-modal dependency tree T = {U,E}, where U and E denote the node set and edge set, respectively. Each node ui ∈ U corresponds to a word in the sentence, and a directed edge 〈uj , ui〉 ∈ E indicates that the node ui is dependent on its parent node uj . Then we use a recursive algorithm to traverse the tree T and recover the order of the words in the output sentence y = {w1, w2, ..., wL}, where L denotes the length of the sentence and wi denotes the i-th word. The overview of our framework is illustrated in Figure 2.

heading: 3.2 Tree Generation Process
text: Our tree generation model follows a step-by-step generation process. In the i-th step, a node ui is added to the tree, and the corresponding word wi is predicted. Formally, given a video x, the probability of generating a tree T is given by
p(T |x) = ∏ ui∈T p(ui|x, Ti−1), (1)
where Ti−1 denotes the sub-tree that has been generated in the (i− 1)-th step. Since the structure of the dependency tree is unknown in the tree generation process, our model also predicts the topological information related to each node. For each node ui, we define three topological labels: tsi ∈ {0, 1}, tci ∈ {0, 1} and tei ∈ {0, 1}. tsi indicates whether node ui has another sibling node. If tsi = 1, another sibling node of ui will be added to the tree in the following steps. tci decides whether ui have child nodes, and least one child node of ui will be added when t c i = 1. tei = 0 indicates that the node ui is the left child of its parent node uj , namely the word wi appears on the left of wj in the output sentence, and tei = 1 indicates that ui is the right child of uj .

heading: 3.3 Encoder
text: Given a set of visual features F = {f1,f2, ...,fM}, the encoder uses multiple self-attention operations to capture the relationships between video frames represented by the visual features. We first recall the scaled dot-product attention used by the self-attention layers, which operates on three sets of vectors Q, K and V :
Attention(Q,K,V ) = softmax( QK>√
d )V , (2)
where Q ∈ Rnq×d is a matrix consisting of nq query vectors, K ∈ Rnk×d and V ∈ Rnk×d are matrices containing nk key vectors and nk value vectors, respectively. The vectors in Q, K and V are with the same dimensionality d. In addition to the self-attention layer, each encoder layer contains a feed-forward network (FFN) consisting of two fully connected layers, which can be formulated as
FFN(X) = ReLU(XW1 + b1)W2 + b2, (3)
where W1,W2 ∈ Rd×d and b1, b2 ∈ Rd are learnable parameters. In each layer of the encoder, the queries, keys and values are obtained by linearly mapping the input features, and the output of the n-th encoding layer Xn is given by
X′n = Attention(W q nXn−1,W k nXn−1,W v nXn−1),Xn = FFN(X ′ n), (4)
where W qn ∈ Rd×d, W kn ∈ Rd×d and W vn ∈ Rd×d are learnable parameters, and Xn−1 is the output of the previous encoding layer. FFN represents the feed-forward network defined in Eq. 3. The visual features V are used as the input of the first encoding layer.

heading: 3.4 Tree Structured Decoder
text: The decoder is conditioned on both the output of the encoder and the previously generated sub-tree. In the i-th step, the decoder takes the encoded visual feature XN , the words in the sub-tree Ti−1 and the multi-modal embeddings of the nodes in Ti−1 as input, and predicts the word wi together with the topological labels tsi , t c i and t e i . The tree generation process terminates if the predicted word wi is a special token 〈eos〉 indicating the end of the sentence. Since the order of words may affect the semantics of the sentence, in each step, we traverse the tree Ti−1 using the algorithm that will be
described in Section 3.5 and obtain a node sequence uk1 , uk2 , ..., uki−1 before feeding the words that have been generated so far to the decoder, where ki indicates the index of the nodes.
Let Ei−1 ∈ R(i−1)×d denote the embeddings of the previously generated (i− 1) words. The decoder acquires the multi-modal embedding of the current node ai by firstly attending to the visual features and the embeddings of the previously generated words using self-attention layers, and then fusing the output of the self-attention. The n-th decoding layer is formulated as:
Yn = FFN(Y vis n + Y word n )
= FFN(Attention(Yn−1,XN ,XN ) + Attention(Yn−1,Ei−1,Ei−1)). (5)
YN ∈ Rd represents the output of the last decoding layer and is used as the multi-modal embedding of the current node ui, i.e. ai = YN in the i-th step. The probability distribution of the word corresponding to ui is calculated using the multi-modal embedding:
pwi = Wwordai, (6)
where Wword ∈ R|D|×d is a learnable parameter, and |D| denotes the vocabulary size. After the word wi is determined by a sampling strategy (e.g. greedy sampling or beam search), the topological labels of the current node are predicted by
p(tsi = 1) = sigmoid(w > s [ai;Ewi ]), p(tci = 1) = sigmoid(w > c [ai;Ewi ]), p(tei = 1) = sigmoid(w > e [ai;Ewi ]),
(7)
where ws,wc,we ∈ R2d are learnable parameters, Ewi ∈ Rd denotes the embedding of word wi, respectively. The operator [; ] denotes the vector concatenation.

heading: 3.5 Tree Traversal Algorithm
text: We restore the word order and convert the tree to human-readable word sequence by traversing the tree. Given a generated dependency tree T , our tree traversal algorithm recursively processes each node in the tree, and restores the word order of the phrase represented by the node and its sub-trees. Since the tree is generated following the depth-first search, the generation order of the child nodes of each node is the same as the order of the corresponding words in the sentence. Thus, for an arbitary node ui in the dependency tree T , we sequentially traverse its left child nodes, the node ui and its right child nodes.

heading: 3.6 Model Training

heading: 3.6.1 Pre-Training Stage
text: The training process of the multi-modal dependency generation model involves a pre-training stage and a fine-tuning stage. Since the model predicts both the word and the topology labels, we use a word loss Lw and a topological loss Lt in the pre-training stage. Formally, the word loss is defined as
Lw = − |T |∑ i=1 logp(wi|Ti−1, x), (8)
where p(wi|Ti−1, x) denotes the probability of predicting word wi given the previously generated tree Ti−1 and the visual input x, and |T | denotes the number of nodes in the tree T . The topological loss is defined as
Lt = Lbce(tsi , t̂si ),+Lbce(tci , t̂ci ) + Lbce(tei , t̂ei ),
Lbce(t, t̂) = − |T |∑ i=1 t̂ · log(p(t)) + (1− t̂) · log(1− p(t)), (9)
where t̂si , t̂ c i and t̂ e i are ground-truth topological labels and Lbce denotes the binary cross-entropy loss. The overall loss function in the pre-training stage is formulated by
Lpretrain = Lw + Lt (10)

heading: 3.6.2 Fine-tuning Stage
text: To effectively optimize the proposed model, we formulate the multi-modal dependency tree generation as a decision-making process and fine-tune the model with reinforcement learning. Specifically, the captioning model is regarded as the agent, the input video x and the generated dependency tree Ti−1 are regarded as the state of the environment, and the prediction of the word wi is regarded as the action. Instead of using the same sequence-level reward for all the actions, we design a novel node-level reward that estimates the contribution of each individual action. The reward r(wi) for the word wi is given by
r(wi) =λ1(CIDEr(Ti)− CIDEr(Ti−1)) + λ21(〈ui, up〉 ∈ E), (11)
where CIDEr(T ) denotes the CIDEr score of the word sequence represented by the nodes in T , up denotes the parent node of ui and 1(〈ui, up〉 ∈ E) indicates whether the edge 〈ui, up〉 is present in the ground-truth dependency tree. λ1 and λ2 are tunable hyper parameters. The discounted future reward for the agent is calculated by
R(wi) = r(wi) + ∞∑ k=1 γkr(wi+k), (12)
where γ denotes the discount factor. Let θ denote the parameters of the captioning model, and then the loss function in the fine-tuning stage is given by
Lrl = −Ewi∼π(θ)(R(wi)), (13)
where π(θ) denotes the policy defined by θ.

heading: 4 Experiments

heading: 4.1 Datasets
text: ActivityNet Captions is a dense video captioning dataset that contains 10,030 training videos, 4,926 validation videos and 5,044 test videos. Each video is annotated with an average of 3.65 sentences together with temporal annotation and the average length of the sentences is 13.7 words. We conduct the experiments on ActivityNet Captions with ground-truth proposals and the results are reported on the validation set.
Charades Captions is composed of 9,223 videos of indoor activities. Each video is annotated with 2-5 sentences, and the average length of the sentences is 24.13 words. Following [15], we split this dataset into 6,963 training videos, 500 validation videos and 1,760 test videos.
MSVD consists of 1,970 video clips collected from YouTube, each of which annotated with about 41 sentences and the average length of the sentences is 7.10 words. We follow [9] to split the dataset into 1,200 training videos, 100 validation videos and 670 testing videos.
MSR-VTT is a dataset collected for open-domain video captioning, which contains 10,000 video clips in total. Each video in the MSR-VTT dataset contains 20 human annotated captions. We use the splits provided by [15], where the training split, validatation split and test split contain 6,513 videos, 497 videos and 2,990 videos, respectively. The average length of the sentences in MSR-VTT is 9.28 words.

heading: 4.2 Evaluation Metrics
text: We report several widely-used automatic evaluation metrics for video captioning, including Bleu-n [21], METEOR [22], ROUGE-L [23] and CIDEr [24]. Nevertheless, these n-gram based evaluation metrics have some limitations, e.g., they penalize the phrases that are semantically correct but differ from ground-truth in the specific word choices [25]. To evaluate the quality of the sentences more effectively, we also report Improved BERTScore metric proposed by [26]. Compared with the n-gram based metrics, Improved BERTScore is computed using pre-trained BERT embeddings and has better correlation with human experts.

heading: 4.3 Implementation Details
text: In the training process, in order to convert the sentences to dependency trees, we use the dependency parser in the SpaCy toolkit [27]. For the ActivityNet Captions dataset, we extract the visual features of the 16-frame video segments using the pre-trained C3D network. To compare our method with [3], we also extract the frame features using ResNet-200 [28], and extract the optical flow features using BN-Inception [29]. For the Charades Captions dataset, we sample the video frames at 3 fps and extract the feature of each frame using the pre-trained ResNet-152 network [28] following [15]. We use the Adam optimizer [30] in both pre-training and fine-tuning stages. The initial learning rate is set to 5× 10−5 and decays 0.8 times for every 3 epochs. The experiments are conducted using one NVIDIA RTX 2080Ti GPU.

heading: 4.4 Comparison with State-of-the-Art Methods
text: The results on ActivityNet Captions are shown in Table 1. We compare our method with DCE [31], DVC [32], SDVC [33], and Masked (which uses different video features) [3]. All these methods generate sentences using sequence models. The captioning models in [32, 33, 14] are implemented by RNN and the model proposed by [3] is based on Transformer.
All the results of these compared methods are directly quoted from their original papers. Our method achieves the best performance on the ActivityNet Captions dataset, demonstrating that by explicitly modeling the hierarchical structure of the sentences, our proposed method can generate long and complex sentences with higher fluency and relevance.
We compare our method with HRL [15] on the Charades Captions dataset. This method involves a manager network that designs sub-goals and a worker network that fulfills each sub-goal by predicting words, both of which are trained end-to-end using hierarchical reinforcement learning. The results are shown in Table 2. We observe that our method outperforms HRL, which evaluates the effectiveness of our method in generating complex video descriptions.
The results on the MSVD dataset and the MSR-VTT dataset are shown in Table 3. We compare our method with HRL [15], MARN [34], POS-CG [13], Joint [12] and RMN [35].All these methods generate sentences using sequence models implemented by RNN. All the results of these compared methods are directly quoted from their original papers. For fair comparison, we use the same visual features as these methods. From the results on MSVD and MSR-VTT, we observe that our method achieves comparable performance with the state-of-the-art methods when using different visual features, which demonstrates that our method is also effective for generating relatively simple sentences. Note that in such simple cases our proposed method is not expected to make much difference or perform better.

heading: 4.5 Ablation Studies
text: To analyze the effect of different components, we conduct ablation studies on the ActivityNet Captions dataset and the Charades Captions dataset. The following variants of our method are evaluated:
• w/o tree: To evaluate the advantage of the tree structure over the sequence structure, we replace the dependency trees with chain-structured trees, where the root node corresponds to the leftmost word in the sentence. For each non-leaf node, its only child node corresponds to the word on its right. This variant of our model is actually a sequence model that generates the words in the sentence in left-to-right order.
• w/o RL: To validate the effectiveness of reinforcement learning, we only optimize the model with the cross-entropy loss in pre-training stage. • w/o tree, RL: To evaluate the effect of using tree structure and reinforcement learning
simultaneously, we optimize a sequence model with only cross-entropy loss. • w/o visual embedding: To evaluate the effectiveness of the visual embeddings of the tree
nodes, we replace the attended visual feature Y visn defined in Eq. 5 with an all-zero matrix, and the node representations contains only linguistic information.
• sequence reward: To verify the contribution of the tree node-level reward, we replace it with the sequence-level reward, i.e. the reward of each node equals to the CIDEr score of the entire sentence.
The results of ablation studies on the ActivityNet Captions and Charades Captions datasets are shown in the middle part of Table 1 and Table 2, respectively. From these results, we make the following observations. First, by replacing the dependency tree with the chain-structured tree, the performance of our model degrades in terms of all the metrics, indicating that the hierarchical structure of the sentences is beneficial for generating sentences with high quality. Second, our full model outperforms “w/o visual embedding”, validating the superiority of the multi-modal representation of the tree node by taking full advantage of both visual and linguistic information. Third, when the fine-tuning stage
with reinforcement learning is removed, our model performs worse on all the metrics, which validates the contribution of our reinforcement learning algorithm. Our full model also outperforms “sequence reward”, which verifies that the node-level reward effectively guides the training process.

heading: 4.6 Evaluation on Simple and Complex Subsets
text: To further evaluate the effect of the tree structure on generating simple sentences and complex sentences, we split the videos in the test sets of MSR-VTT and Charades Captions into a simple subset and a complex subset according to the average length of the ground-truth sentences. The data distributions of the two subsets and the evaluation results are shown in Table 4. From these results, we observe that by utilizing the tree structure, the performance of our model significantly increases on the complex subset, which demonstrates the proposed model’s capability in terms of generating complex sentences.

heading: 4.7 Results of Using Different Evaluation Metric in the Reward
text: To assess the impact of the evaluation metric used in the reward on the performance of the captioning model, we conduct additional experiments that replace the CIDEr score in the reward using other metrics (i.e. Bleu-4 and ROUGE-L) on the Charades Captions dataset. From the results in Table 5, we observe that when using Bleu-4 (or ROUGE-L) in the reward, the performance in terms of Bleu-4 (or ROUGE-L) increases when compared with using CIDEr in the reward. However, using CIDEr score in the reward leads to the best overall performance. Thus, we use CIDEr score in the reward in other experiments.

heading: 4.8 Qualitative Results
text: We show some examples of the generated sentences on Charades Captions and MSR-VTT in Figure 3. As shown in the figure, by utilizing the tree structure, our method generates sentences that not only describe the objects and the human actions more accurately but also possess correct grammatical structures.

heading: 4.9 Human Evaluation
text: To intuitively evaluate the effect of the tree structure on the quality of the generated sentences, we conduct human evaluation on the test splits of ActivityNet Captions and MSR-VTT. We randomly choose 200 videos from the test splits of ActivityNet Captions and MSR-VTT, respectively. The workers are given the original video as well as two sentences generated by “Ours” and “w/o tree”, and are asked to select the sentence that has better relevance to the video and the sentence with better fluency. For the two methods “Ours” and “w/o tree”, we report the percentage of sentences that have better relevance and the percentage of sentences that have better fluency. From the results in Table
6, we observe that the tree structure remarkably improves both the relevance and the fluency of the generated sentences.

heading: 5 Conclusions
text: We have presented a multi-modal dependency tree generation method for video captioning. Our model can explicitly model the hierarchical structure of natural language using tree topology to better capture both the syntactic structure and semantic relationship in sentences. Both visual and linguistic information are incorporated into the node embeddings to further improve the relevance of the generated sentence to the video. Moreover, we have developed a tree-structured reinforcement learning algorithm and designed a novel tree node-level reward to effectively optimize the captioning model. Our multi-modal dependency tree is capable of generating complex sentences with high fluency and relevance for videos. Extensive experiment on multiple challenging video captioning datasets have demonstrated the effectiveness of our method.
Funding Transparency Statement
This work was supported in part by the Natural Science Foundation of China (NSFC) under Grant No 62072041.

Review summaries:
This paper studies the task of video captioning. It proposes a structured approach where models generate a dependency tree for the caption, instead of just a sentence. The nodes of the dependency tree are words, and the tree is generated in depth-first order; thus, the sentence can be easily recovered by iterating through the tree.   The model is learned by a "pretraining stage"; where a left-to-right style loss is used (generating the next word, and the node in the tree, given previous nodes). In a "finetuning stage", the model is optimized using reinforcement learning with the improvement in CIDEr score as the reward (along with a reward as to whether the generated edge is in the ground truth tree or not). 

The paper addresses video captioning by generating captions in a tree structure. It stepwise constructs the multi-modal dependency tree and then traverses the constructed tree to obtain the captions. The supervision is performed on generated captions as well as the semantic consistency reward of the generated sub-trees. Experiments are conducted on several video captioning datasets.  

The paper proposes a new architecture that combines a multimodal dependency tree approach with a tree-structured reinforcement learning method to improve upon existing methods on the video captioning task. The authors conduct experiments to understand the impact of the two components on four datasets. Experiments are made with varying visual features, on settings of varying complexity, and based on human evaluation. The results and analysis show improvements over the state of the art and that adopting a multimodal tree structure is a promising area of research for this task.