Interpretable Embedding for Ad-Hoc Video Search

We use the same architecture as dual encoding network (Dong et al., 2019) to extract multi-level video and text features. The visual encoding network has three sub-networks. The first sub-network captures the global information of a video segment by mean pooling its CNN features over the video frames. The second sub-network extracts the temporal information of video by mean pooling the features of the bidirectional GRU (Cho et al., 2014) (biGRU) across all time steps. The final sub-network further extracts the local information in the temporal sequence of video by performing 1-d CNN on the top of the biGRU features from the second sub-network. A multi-level video feature is formed by concatenating the global, temporal and local information extracted from these sub-networks. The visual embedding is denoted as

where $f_{v}^{(i)}\ (i=1,2,3)$ denotes the feature extracted from the first, second and third sub-networks for a video $v$. The video feature $f(v)$ is further mapped to the common space of $d$ dimensions by using a fully connected layer (FC) and a batch normalization layer (BN) as following

where BN($\cdot$) denotes the batch normalized layer. The matrix $\mathbf{W}_{v}$ and the vector $b_{v}$ are weight and bias of the fully connected layer in the visual encoding network.

The query $q$ is encoded similarly using the texture encoding network. Each word in $q$ is represented as a one-hot vector $m_{i}$ and then concatenated as a matrix $\mathbf{M}_{q}=\{m_{1},m_{2},...,m_{i},...,m_{n}\}$ to represent the sentence $q$. The first level feature $f_{q}^{(1)}$ is obtained by taking the mean value of the matrix $\mathbf{M}_{q}$ over all the vectors of sentence words. A denser vector is further generated for every word by multiplying its one-hot vector with a pre-trained Word2Vec matrix. The second-level feature of the query $f_{q}^{(2)}$ is obtained by mean pooling of the features output by each stage of biGRU (Cho et al., 2014) over the sequence of dense vectors. The third-level feature $f_{q}^{(3)}$ is extracted by conducting 1-d CNN over the biGRU features obtained from the second level. Finally, a multi-level feature for the query $q$ is formed by concatenating all of the features as

The feature is subsequently mapped to the common space as the video feature by a fully connected layer and a batch normalize layer

where $\mathbf{W}_{q}$ and $b_{q}$ are the weight and bias of the fully connected layer in the textual encoding network. The textual embedding has the same output dimension $d$ as visual embedding.

Finally, the similarity of the input query $q$ and the video $v$ is computed as $S(v,q)=sim(\phi(v),\tau(q))$. The visual-textual embedding matching task is trained in an end-to-end manner by using improved marginal ranking loss (Faghri et al., 2018). The loss in this matching task is defined as

where $c$ is the margin. The visual-text pair is indicated by the notations $v$ and $q$ respectively. The query $q$ is associated with a negative sample $v-$, and similarly $v$ is associated with a negative query $q-$. The visual-textual embedding matching task is trained to minimize this loss.

Video content is multi-perspective. The content can be narrated from different perspectives depending on the subjects or contexts of interest in the topic of discussion. Even for one perspective, there exists a variety of ways expressing the same semantics using different words. Hence, given a video, Task-2 is to train a decoder such that all the words in its descriptions are activated with high probability. The activated words that are absent from the descriptions do not necessarily belong to false positives. Instead, these words may be just not mentioned than being classified incorrectly. In general, the challenge of training such a decoder is beyond concept prediction as in the conventional CNN. The novelty of Task-2 is the design of a loss function to maximize the intersection between the classified concepts of a video embedding and the words mentioned in the captions.

The visual decoding network is comprised of a fully connected layer and a batch normalization layer. The output is denoted as

where $\mathbf{W}_{d}$ and $b_{d}$ are weight and bias of the network. The sigmoid function is performed over the output to obtain the probability distribution $\hat{y}_{v}$ for a video embedding $g(v)$

where $\hat{y}_{v}=[\hat{y}_{v1},\hat{y}_{v2},...,\hat{y}_{vi},...,\hat{y}_{vm}]\ (\hat{y}_{vi}\in\mathbb{R}^{+})$ for $m=11,147$ numbers of concept classes. The value of $m$ is compiled from the training set, by including the words that appear in at least five descriptions and removing the words in the NLTK stopword list. For a video $v$, the words that appear in its captions are labeled as ground-truth $y_{v}=[y_{v1},y_{v2},...,y_{vi},...,y_{vm}]$, where $y_{vi}\in\{0,1\}$ indicates whether a word is present in the captions of $v$.

Binary cross entropy (BCE) loss is widely adopted for multi-label classification task. However, BCE cannot be directly applied for treating each class equally by penalizing the predictions different from the ground-truth labels. In general, the number of words used to describe a video is much smaller than the total number of concepts. Using BCE will cause the amount of loss being dominated by the words not mentioned in video captions. The decoder trained in this way will play trick to predict almost all classes as zero in order to get an overall low BCE loss. Thus, a class-sensitive loss is proposed, by computing the loss of mentioned words separately from those that do not appear in the captions, as following

Eq. (9) is the BCE loss function that computes the binary cross-entropy for a class $i$. The proposed function in Eq. (8) is the summation of two BCE terms. The first term computes the losses of those classes mentioned in the captions, i.e., $y_{vi}=1$ in the ground truth of a video. The second term computes the losses of the remaining classes, i.e., $y_{vi}=0$. Note that the proportion of concepts involved in the first and second terms is highly imbalanced. Eq. (8) effectively assigns higher weights to the mentioned concepts. In this way, the decoder is trained to play a more active role in maximizing the overlap between the predicted and ground-truth concepts. Nevertheless, to avoid an excessive number of concepts being predicted as positive, a hyper parameter $\lambda\in[0,1]$ is required to keep a balance between activating mentioned words and suppressing irrelevant concepts. When $\lambda$ equals to 1 or 0, it represents the extreme case of whether to penalize only the concepts being mentioned (i.e., $\lambda=1$) or vice versa (i.e., $\lambda=0$). In practice, the value of $\lambda$ should bias towards the second term to restrict the number of activated concepts. This is also justified in the experiment, where the value is learnt as $\lambda=0.2$, when verified using validation set. The multi-class classification is trained in an end-to-end manner to minimize the $loss_{classification}$.

We have designed one loss for each task and they are $loss_{matching}$ and $loss_{classification}$. The dual-task loss is set as

In the training stage, we compute the average dual-task loss over all input video-text pairs in a batch and update all the parameters of the model simultaneously by using this loss.

In the inference stage, we have two trained models for video search. One model is from the visual-textual embedding matching task (denoted as $DT_{embedding}$) and the other model comes from the multi-label video concept classification task (denoted as $DT_{concept}$). The embedding model $DT_{embedding}$ and the concept model $DT_{concept}$ have the same parameters in the visual encoding network. For all videos in the collection, we first use the trained visual encoding network to extract their visual embeddings and apply the trained visual decoding network of $DT_{concept}$ to get their predicted concepts offline. As a result, each video $v$ in the dataset is indexed with an embedding $\phi(v)\in\mathbb{R}^{d}$ and a predicted concept vector $\hat{y}_{v}\in\mathbb{R}^{m+}$. Given a test query, the embedding model $DT_{embedding}$ applies its textual encoding network to encode the test query as a textual embedding $\tau(q)\in\mathbb{R}^{d}$. Then, $DT_{embedding}$ will give each video $v$ a score ($score(v,q)_{embedding}$) according to the similarity of its embedding with the textual embedding of the query $q$

$DT_{embedding}$ will output a list of videos for the query ranked according to the scores. The top-1 in the list has the highest score which represents the video best matches the input query. Meanwhile, the concept model $DT_{concept}$ will generate a one-hot vector for the given test query. It maps the query sentence $q$ over the constructed concept list from the classification task to get a one-hot query vector $c_{q}=[c_{q1},c_{q2},...,c_{qi},...c_{qm}],c_{qi}\in\{1,0\}$. If $c_{qi}=1$, it means that $i$th concept of the concept list is wanted by the query. Then, $DT_{concept}$ will also give each video $v$ a score ($score(v,q)_{concept})$ based on the similarity of its predicted concept vector $\hat{y}_{v}$ and the query vector $c_{q}$.

Another ranked list is output by the concept model $DT_{concept}$ based on this score. A linear function is used to combine two models together. We give a combined score ($score(v,q)_{combined}$) for each video $v$ with respect to the input query $q$ as

where $\theta$ is a hyper parameter to control the contributions of the embedding model $DT_{emebdding}$ and the concept model $DT_{concept}$ to the final retrieval score. We denote the model which uses the $score(v,q)_{combined}$ for video search as $DT_{combined}$. Normally, we use the combined model $DT_{combined}$ to retrieve videos for an input query in the experiments.

$\mathbf{Datasets}$. Table 1 lists the datasets used in the experiments. The proposed model is trained and validated on the captioning datasets. These datasets are also used by other approaches such as W2VV++ (Li et al., 2019a) and dual coding (Dong et al., 2019). The number of captions per video varies from 2 in TV2016TRAIN (Awad et al., 2016) to as many as 40 in MSVD (Chen and Dolan, 2011). The performance of AVS is evaluated on two large video collections. Both are TRECVid benchmarked datasets, where IACC.3 (Awad et al., 2016) is used during the years 2016 to 2018 and V3C1(Berns et al., 2019) in the year 2019. As TRECVid evaluates 30 query topics per year, a total of 120 queries are involved in the evaluation. For convenience, we name the query sets as tv16, tv17, tv18 and tv19, and each set contains the 30 queries being evaluated on that year. The full set of queries is listed in the supplementary document.

$\mathbf{Evaluation\ metric}$. We use extended inferred average precision (xinfAP) to evaluate ad-hoc video search results (Awad et al., 2019). For the overall performance of a search system, we report the mean xinfAP of all test queries as results.

$\mathbf{Implementation\ details}$. We use the PyTorch code provided by the dual coding model (Dong et al., 2019) to set up the basic architecture of visual encoding network and textual encoding network. Following (Dong et al., 2019), we set the output dimension of both networks as $d=2,048$, and the margin in the triplet loss function (Eq. (5)) as $c=0.2$. We use the pre-trained ResNet-152 (Dong et al., 2017) and ResNext-101 (Snoek et al., 2017) to extract a feature of 4,096 dimensions for each video frame. For the visual decoding network, the concept list is composed of $m=11,147$ words, compiling from the captions of TGIF and MSR-VTT. We use a learning rate of 0.0001 and Adam optimizer to train the model. The batch size is 128. The hyper-parameter is set as $\lambda=0.2$ (Eq. (8)) based on validation set, and we report $\theta=0.3$ (Eq. (13)) as our combined model.

BCE loss. We first compare the proposed class-sensitive loss (Eq. (8)) to the normal BCE in the design of multi-label concept decoder. The evaluation is conducted by counting the number of classified concepts that are mentioned in video captions. On MSVD dataset (Chen and Dolan, 2011) with 1,907 video clips, the proposed BCE loss attains recall@10=0.532. In other words, on average there are more than 50% of concepts in the top-10 list are mentioned by the video captions. This performance is significantly better than the normal BCE loss which only manages to reach recall@10=0.293.

Figure 2 further contrasts the retrieval performances between the proposed class-sensitive and normal loss functions on four sets of TRECVid queries. Note that in the figure, two groups of performances are shown for each query set. Each group separately lists three performances for using embedding feature only (i.e., $DT_{embedding}$), concept only (i.e., $DT_{concept}$) and late fusion of them (i.e., $DT_{combined}$). The performances based on the models trained with normal and proposed BCE losses are visualized with bars of lighter and darker colors respectively. As shown in the figure, the models trained with the proposed class-sensitive loss function show consistently better retrieval rate across all the four query sets. For concept-only retrieval, the average performance over 120 queries is five times higher than the model trained with normal BCE. We attribute the performance gain due to higher accuracy in concept prediction. The result indicates the merit of the new BCE loss function for dual-task learning. With class-sensitive loss, the performance of $DT_{embedding}$ also improves. The performance difference is almost double (xinfAP =0.170) when comparing to the model trained by the normal BCE (xinfAP = 0.091). Furthermore, by using the proposed BCE loss, the late fusion of concept-only and embedding-only features always leads to performance boost across the four query sets. In contrast, the model trained with normal BCE only manages to show improvement on tv19.

Dual-task learning. Next, we verify the merit of dual-task learning versus training two single tasks independently. Specifically, the encoders for Task-1 (visual-text embedding) and the encoder-decoder for Task-2 (multi-level concept classification) are trained separately. For notation convenience, we call the two single-task models as $ST_{concept}$ and $ST_{embedding}$ respectively. As shown in Table 2, consistent improvement is noticeable for dual-task model when performing retrieval using either concept-only or embedding-only feature. $DT_{embedding}$ improves 69 out of 120 queries over $ST_{embedding}$. Using query-556 Find shots of a person wearing a blue shirt as an example, xinfAP is significantly boosted from 0.144 to 0.198. Benefited from dual-task learning, true positives are ranked at higher positions in $DT_{embedding}$. At xinfAP@100, the average improvement of $DT_{embedding}$ over $ST_{embedding}$ is 18.3%. Similar trend of improvement is also observed in $DT_{concept}$, where xinfAP is boosted for 66 out of 120 queries. Benefited from $DT_{embedding}$, some true positives originally out of the search depth of 1,000 are ranked high. Examples include query-577 Find shots of two or more people wearing coats, where $DT_{concept}$ brings forward more than 100 positive videos. As a consequence, xinfAP is boosted for 173% from 0.1793 to 0.4898 for query-577. Nevertheless, there are 19 queries drop for both $DT_{embedding}$ and $DT_{concept}$. These are the queries where either $ST_{concept}$ or $ST_{embedding}$ performs poorly. As training is conducted using video captioning datasets, dual-task learning may have been confused if the results of both tasks are in conflict with each other.

Late fusion. In general, concept-only search performs better when a query topic can be uniquely described by a few concepts independently. In contrast, embedding-only search is superior for complex queries, such as query-543 Find shots of a person communicating using sign language, where collective understanding of query terms is required. As both search methodologies are complementary, late fusion is employed. Figure 3 shows the sensitivity of hyper-parameter $\theta$ (Eq. (13)) that linearly combines the rank lists of both methods. The extreme values represents retrieval by embedding-only (i.e., $\theta=0$) and concept-only (i.e., $\theta=1.0$). As observed, the retrieval performance varies slightly when $\theta$ is set in the range of $[0.2,0.4]$. Considering the capability of answering complex queries, we set $\theta=0.3$ to bias embedding-only more than concept-only retrieval in the late fusion. The detailed performances of our models on every query are list in the supplementary material.

We compare dual-task model to the existing methods based on embedding-only, concept-only and hybrid search. Embedding-only search includes W2VV++ (Li et al., 2019a) and dual coding (Dong et al., 2019), which report the state-of-the-art performance on TRECVid datasets. Concept-based search includes mainly (Markatopoulou et al., 2017; Ueki et al., 2016, 2017, 2018, 2019). QKR (query and keyframe representation) (Markatopoulou et al., 2017) performs linguistic analysis to select concepts for queries. Through word2vec (Mikolov et al., 2013), the concept lists of queries and keyframes are projected into an embedding space for similarity comparison. Large concept bank (ConBank) composed of about 55,000 words is leveraged in (Ueki et al., 2017, 2018, 2019). Multi-level query analysis from words, phrases to sentences is conducted for concept mapping. As this process is error-prone, manual selection of query words and phrases for mapping with concepts is also performed in (Ueki et al., 2016, 2017, 2018, 2019) to contrast the performances between automatic and manual searches. The performances of hybrid approaches are mostly reported in TRECVid benchmarking only. For reference, the top-3 performances benchmarked in TRECVid are listed for comparison.

Table 3 lists the performance comparison. Except on tv16, the proposed $DT_{embedding}$ shows better performances than its counterparts including W2VV++ and dual coding. Among the embedding-only approaches, $DT_{embedding}$ shows the highest xinfAP in 43 out of 120 queries. Through dual-task training, $DT_{embedding}$ shows higher ability in answering queries with unique concepts such as “scarf” in query-558 and “coats” in query-577. For concept-only search, $DT_{concept}$ outperforms most of its counterparts including QKR. Despite that the number of concepts is almost five times smaller than the large concept bank (Ueki et al., 2017, 2018, 2019), $DT_{concept}$ still shows competitive performance. Nevertheless, $DT_{concept}$ is not competent with (Ueki et al., 2016, 2017, 2018) when human intervention is allowed for concept selection. $DT_{combined}$, as a hybrid model, outperforms all the existing approaches, including the top performers benchmarked in TRECVid. The performance also surpasses (Ueki et al., 2016, 2017, 2018, 2019) which is based on manual search. Compared to the best reported result by dual coding (Dong et al., 2019), the xinfAP gain is as large as 12.1% and 21.7% on tv16 and tv19 respectively. To verify the performance is not by chance, we conduct randomization test (Smucker et al., 2007). At the $p$-value $\leq$ 0.01, the test shows that the dual-task model is significantly better than other approaches including dual coding, W2VV++ and the best reported performance in TRECVid.

In TRECVid (Awad et al., 2016), the 120 query topics are classified into 12 different types of complexities based on the composition of object, scene, action and location. Comparing to dual coding, $DT_{embedding}$ is better in answering person-related queries, especially, the combination of person, object and location. The performance of $DT_{embedding}$ exceeds dual coding on all queries in this kind, e.g., query-624 Find shots of a person in front of a curtain indoor. Compared with dual coding and W2VV++, $DT_{concept}$ has higher xinfAP on detecting object-only queries. For some queries such as query-512 Find shots of palm trees, xinfAP is as much as 167.8% better than W2VV++ and 82.7% than dual coding. The hybrid model, $DT_{combined}$ outperforms dual coding in 76 out of 120 queries, and the xinfAP gain ranges from 0.3% to 158.4%. These queries correspond to person-related or object-related queries, e.g., 121.8% gain on query-509 Find shots of a crowd demonstrating in a city street at night, and 100.0% gain on query-572 Find shots of two or more cats both visible simultaneously. The remaining queries suffering from xinfAP degradation mostly are those queries that $DT_{concept}$ fails miserably. The drop ranges from 0.2% to 87.5%. For example, dual coding has a xinfAP of 0.194 on query-514 Find shots of soldiers performing training or other military maneuvers, while $DT_{combined}$ only manages to attain xinfAP = 0.181. For this particular query, the performance gap between $DT_{embedding}$ (xinfAP=0.191) and $DT_{concept}$ (xinfAP=0.079) is relative large. Further late fusion hurts the overall retrieval rate.

To provide further insights, Figure 4 visualizes the composition of true positives in the rank lists of $DT_{combined}$. As observed, 72 out of 120 queries share more than 50% of true positives common between $DT_{embedding}$ and $DT_{concept}$. Among them, 50 queries show improvement in xinfAP due to elevation of ranking positions for true positions after score combination. Overall, performance improvement is more apparent for queries where true positives are separately contributed by embedding-only and concept-only searches. Finally, $DT_{combined}$ manages to pull true positives outside of 1,000 search depth from both $DT_{embedding}$ and $DT_{concept}$ for 76 queries, and the number ranges from 1 to 20. However, as these positives are still ranked low in the list, their contributions to overall xinfAP are not significant.

Concept-free search suffers from the black-box retrieval of results. With dual-task model, nevertheless, interpretation of search result is feasible by listing out the decoded concepts alongside the retrieved videos. Here, we conduct an experiment to verify the top-10 retrieved videos of $DT_{embedding}$ by the decoded concepts. A video is pruned from search list if the required keywords are not present among the list of decoded concepts. For example, the required keyword for query-625 Find shots of a person wearing a backpack is “backpack”. Any retrieved videos without the “backpack” concept will be eliminated from the search result.

The experiment is conducted as follows. A total of 30 queries, where $DT_{concept}$ exhibits higher xinfAP values, are selected for experiment. The top-10 retrieval accuracy averaged over queries is 82%. Among these query topics, 1-3 keywords are manually specified as the required concepts to present in a retrieved video. Any videos without all the required keywords present within the list of top-30 decoded concepts will be marked as negative videos. The result shows that, by dual-task model, 44.27% of false positives retrieved by $DT_{embedding}$ can be successfully eliminated from the search list. Nevertheless, 10.67% of true positives are also being erroneously pruned. Generally, for queries involving unique concepts such as “helmet”, “plane”, “ballon”, the accuracy of pruning is high. Query-572 Find shots of two or more cats both visible simultaneously, by listing “two” and “cat” as keywords, more than 60% of false positives are removed. The method is relatively weak in interpreting queries with compositional concepts such as “bird in the tree” (query-638), only 20% of false positives can be pruned.

Note that the setting is realistic in the scenario of interactive search. Concretely, a searcher can specify a few keywords to quickly locate a small number of true positives among the search list. These true positives identified in a short period of time can serve multiple purposes. For example, the positives are leveraged for example-based video search (Rossetto et al., 2019), online training of classifier (Lu et al., 2017) and discovery of contextually relevant concepts for query refinement (Lokoč et al., 2019). We repeat the experiment by randomly sampling another 30 queries from the remaining 90 queries, where the performance of $DT_{embedding}$ is generally better than $DT_{concept}$. Among the top-10 retrieved videos, there are 168 true positives and 132 false positives, implying accuracy of 56.0%. By dual task model, 90 false positives are successfully pruned and 123 true positives are retained. The accuracy is boosted from 54% to 74.5%. With this, a searcher can potentially speed up the time, by skipping more than 50% of false positives, to identify a small number of true positives for subsequent search actions.

Boolean expression of query terms has been exploited in manual (Ueki et al., 2016) and interactive search (Nguyen et al., 2018). An example of query is Find shots of drinking beverage but not wine or beer. The performance of concept-free search are generally unpredictable when the entire Boolean query is embedded as a single vector (Li et al., 2019b). A feasible way is by decomposition of query into multiple sub-queries, such as “drinking beverage”, “wine” and “beer” as three separate sub-queries for retrieval. The results are then merged with Boolean combination. The experiment here aims to study the limit of dual-task model in answering Boolean queries by $DT_{embedding}$ and $DT_{concept}$.

As TRECVid queries are non-Boolean, we compile 15 Boolean queries for experiment, and conduct retrieval on V3C1 dataset (Berns et al., 2019). The list of queries is listed in supplementary document. For $DT_{embedding}$ and dual coding (Dong et al., 2019), we contrast their performances when a query is treated as a single vector and multiple vectors by query splitting. We also compare $DT_{concept}$ with the recent work in (Nguyen et al., 2018) which performs Boolean based concept search using a vocabulary size of 16,263 that is similar to dual-task model. We use the measures in (Nguyen et al., 2018) for late fusion of search lists from multiple sub-queries for all the compared methods. As shown in Table 4, both $DT_{embedding}$ and $DT_{concept}$ generally exhibit better performances than their respective counterparts. Concept-based search by $DT_{concept}$ shows higher xinfAP not only than (Nguyen et al., 2018) but also concept-free search when query is not split.

An interesting note is that, when query decomposition is performed, the performance of concept-free search is boosted significantly for queries with NOT operators. Query splitting is also helpful for queries with OR operator, but is likely to hurt the performance for queries with AND operator. Nevertheless, when a query involves not only NOT but also AND or OR, answering with multiple sub-queries will bring significant improvement in retrieval. In other words, concept-free approach fails to embed the semantics of NOT in the feature space. Explicit handling of NOT operator by multiple sub-queries processing is required. The performance trend is consistent for both $DT_{embedding}$ and dual coding.

The result gives clues of how to exploit concept-free and concept-based search for Boolean queries. For example, when the query terms are logically rather than linguistically compositional, concept-based is likely a better choice than concept-free search. When NOT operator is involved, however, concept-free with query splitting strategy should be adopted. As dual-task model is interpretable with the result of $DT_{embedding}$ being verified by $DT_{concept}$ (as in Section 4.4), appropriate search strategies can be flexibly implemented. For example, the result of concept-free search can be pruned by manually expressing the required concepts of a query with boolean expression. In general, these strategies are expected to be practical for interactive search.