Automatic discovery of query-class-dependent models for multimodal search

Lyndon S. Kennedy, Apostol Natsev, Shih-Fu ChangACM Multimedia 2005 · DOI

TL;DR

This paper introduces a novel framework for automatically discovering "query classes" that optimize multimodal search strategies. By clustering queries based on their performance across different search methods and their semantic content, they achieve a significant improvement in search accuracy compared to manually defined classes, paving the way for more adaptable and efficient multimodal search systems.

What Problem Does This Paper Address?

In multimodal search (like searching for videos using text and example images), simply combining results from different search methods (e.g., text search, image search) with a single, fixed strategy often leads to suboptimal performance. This is because different types of queries benefit from different combinations of search methods. While "query-class-dependent" models, which use different strategies for different query types, offer a solution, the challenge has been how to define these query classes effectively. Previous approaches relied on manual, semantic-based classification, which didn't guarantee that queries within a class would actually perform similarly across various search methods. This paper addresses the critical gap of how to automatically discover query classes that are not only semantically meaningful but also performance-consistent, leading to better fusion strategies.

Methods

The core of this paper is a novel framework for discovering query classes by clustering queries in a "joint performance/semantic space."

  • Performance Space: This space represents each query by its performance (e.g., average precision) across a set of unimodal search methods. Queries with similar performance profiles across these methods are grouped together.
  • Semantic Space: This space represents each query by its linguistic features (e.g., nouns, verbs, named entities) extracted from the text query, and also incorporates semantic similarity using WordNet. This allows for mapping new, unseen queries.
  • Joint Performance/Semantic Space: By combining these two spaces, the authors create a richer representation that allows for clustering queries that are both semantically similar and perform similarly across search methods.
  • Clustering: Hierarchical clustering is used to group queries in this joint space. The optimal number of clusters is determined by maximizing retrieval performance on a held-out validation set.
  • Fusion Strategy Learning: For each discovered query class, optimal weights for combining the scores from different unimodal search methods are learned.
  • Query Classification: For new, unseen queries, their semantic features are used to map them to the most appropriate discovered query class, and the corresponding fusion strategy is applied.

Datasets

  • Training Data: The TRECVID 2003 development set, augmented with 143 newly defined queries derived from a log of BBC video archive requests. This resulted in a training set of 112 queries with pooled ground truth relevance labels.
  • Evaluation Data: The TRECVID 2004 automatic video search task, which involves 23 multimodal queries.

Key Insights and Ideas

  • Performance-driven clustering is key: The most significant insight is that clustering queries based on their performance across different search methods, rather than solely on semantics, leads to more effective query classes for multimodal fusion.
  • Joint space offers the best of both worlds: Combining performance and semantic information in a joint space for clustering is crucial. Pure performance-based clustering makes it hard to classify new queries, while pure semantic clustering doesn't guarantee performance consistency.
  • Hand-defined classes are often suboptimal: The study reveals that some manually defined classes (like "Named Object") are too broad and should be split, while others (like "Sports" and "Named Person") are indeed well-formed and consistent.
  • Automatic discovery alleviates human bias: The data-driven approach removes the subjectivity and potential errors associated with manual query class definition.
  • SVM classification struggles with small datasets: While SVMs are powerful, they underperform in this specific scenario due to the limited size of the training set, highlighting the importance of data scale for complex classifiers.

Key Results

  • The proposed framework achieved a Mean Average Precision (MAP) of 0.0711 on the TRECVID 2004 search task using automatically discovered query classes.
  • This represents an 18% improvement in MAP compared to using hand-defined query classes (MAP of 0.0605).
  • Query-class-dependent models significantly outperformed query-independent models (MAP of 0.0595).
  • Clustering in the joint performance/semantic space (specifically P+Q+WN) with shortest distance classification yielded the best results.
  • Performance-only clustering with Oracle classification (knowing the true class) showed high potential (MAP: 0.769), but was not recoverable with real classifiers.

Limitations and Future Work

  • Limited number of search methods: The study used only six unimodal search methods to keep the performance space dimensionality manageable. Exploring a larger set of more sophisticated search methods could further improve performance.
  • Simple fusion strategy: Linear weighting of search scores was used. More complex fusion strategies could potentially yield better results.
  • SVM classification performance: The SVM classifier's poor performance on unseen queries is attributed to the small training set size. Future work could explore larger datasets or alternative classification methods.
  • Exploration of semantic features: While WordNet and basic linguistic features were used, more advanced semantic representations could be explored.
  • Automatic discovery of search methods and fusion strategies: The authors suggest that similar performance-based metrics could be used to automatically discover optimal search methods and fusion strategies, extending the current framework.

Summary updated

BibTeX
@inproceedings{kennedy2005automatic,
  author = {Lyndon S. Kennedy and Apostol Natsev and Shih-Fu Chang},
  title = {{Automatic discovery of query-class-dependent models for multimodal search}},
  booktitle = {ACM Multimedia},
  year = {2005},
  doi = {10.1145/1101149.1101339},
}
Figure