Tree-Augmented Cross-Modal Encoding for Complex-Query Video Retrieval

Xun Yang, Jianfeng Dong, Yixin Cao, Xun Wang, Meng Wang, Tat-Seng Chua

Introduction

As video content explodes online, the demand for sophisticated search tools has shifted from simple keyword matching to understanding complex, natural language descriptions. While current systems handle queries like "playing basketball" with ease, they often struggle with intricate, multi-step scenarios such as "Two girls are laughing together and then another throws her folded laundry around the room." This paper introduces TCE (Tree-augmented Cross-modal Encoding), a framework designed to bridge the gap between hierarchical linguistic structures and the temporal dynamics of video.

The Challenge: Beyond Flat Embeddings

Traditional video retrieval methods typically fall into two categories: concept-based and embedding-based. Concept-based systems decompose queries into individual tags (e.g., "puppy," "grass"), often losing the logical "who did what to whom" relationship. Conversely, standard embedding-based systems map entire sentences into single vectors, frequently treating language as a flat sequence and ignoring the inherent hierarchy that defines complex actions.

TCE addresses these limitations by explicitly modeling the syntactic structure of queries and the temporal flow of videos within a unified joint embedding space.

Visualization of the joint embedding space where video and text features are aligned.

The TCE Framework

The core of TCE is its ability to learn a Latent Semantic Tree (LST) of a query without requiring manual syntactic labels. The framework consists of three primary modules:

  1. Latent Semantic Tree (LST): Utilizing a Tree-structured LSTM, the model recursively constructs a binary tree of the query. A novel memory-augmented node scoring mechanism uses the global context of the sentence to determine which words or phrases should be merged, ensuring the resulting tree reflects the overall semantic intent.
  2. Tree-augmented Query Encoder: Instead of relying solely on the root node, the encoder uses an attention mechanism to weigh various constituent nodes (phrases) within the tree. This allows the model to prioritize the most visually descriptive segments of a complex sentence.
  3. Temporal-Attentive Video Encoder: On the video side, a GRU captures sequential flow, while multi-head self-attention models interactions between distant frames. A final temporal attention layer identifies the most informative "action" frames, distinguishing them from static backgrounds.

Key Results and Insights

The authors evaluated TCE on the MSR-VTT and LSMDC benchmarks, achieving state-of-the-art (SOTA) performance. On MSR-VTT, TCE reached a Recall@1 (R@1) of 17.1% on specific splits, significantly outperforming previous models like DualEncoding.

  • Structural Importance: The performance gap between TCE and flat models widens as query length increases, proving that hierarchical modeling is essential for handling complexity.
  • Latent Robustness: By learning the tree structure end-to-end rather than using a fixed off-the-shelf parser, the model remains robust to the informal language often found in web queries.
  • Attention Filtering: Qualitative analysis shows the model successfully ignores linguistic "noise" (like "at a" or "in front of") to focus on high-signal actions.

Conclusion

TCE demonstrates that treating linguistic structure as a first-class citizen is vital for complex video retrieval. By aligning latent semantic trees with temporal video features, the model captures the nuances of human language more effectively than traditional sequential approaches. Future work may extend this tree-based logic to video moment retrieval and the integration of external knowledge bases.

Summary updated

BibTeX
@inproceedings{yang2020tree,
  author = {Xun Yang and Jianfeng Dong and Yixin Cao and Xun Wang and Meng Wang and Tat-Seng Chua},
  title = {{Tree-Augmented Cross-Modal Encoding for Complex-Query Video Retrieval}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2020},
  url = {https://openreview.net/forum?id=olxnHoR6FE},
}
Figure