Compositional Correlation Quantization for Large-Scale Multimodal Search

Mingsheng Long, Jianmin Wang, Philip S. Yu

Introduction

In the era of "Big Data," efficient multimodal search—such as using text tags to find images or using an image to find related articles—is a significant challenge. To perform these searches at scale, researchers utilize hashing, which converts high-dimensional data into compact binary codes (0s and 1s) that allow for lightning-fast comparisons.

However, most existing multimodal hashing methods follow a suboptimal "two-step pipeline." They first project different modalities into a shared continuous space and then binarize those values as an afterthought. This disjointed process leads to massive quantization error, as the initial mapping does not "know" it will eventually be compressed into binary form. This paper introduces Composite Correlation Quantization (CCQ), a framework that performs these steps simultaneously to drastically reduce information loss.

The CCQ Framework

CCQ moves away from the traditional two-step approach toward a seamless optimization framework. Its core innovation is the joint learning of three critical components: correlation-maximal mappings, composite quantizers, and binary codes.

The CCQ framework jointly learns mappings and quantizers to minimize information loss.

By including the quantization error directly in the training objective, the model finds a latent space that is inherently "binarization-friendly." Key features of the framework include:

  • Composite Quantizers: Instead of simple binary thresholding, CCQ uses multiple "codebooks." A data point is represented as a sum of several codewords, allowing for much higher precision while remaining computationally efficient.
  • Codebook Sharing: For paired data, CCQ forces different modalities to share the same binary code, ensuring semantic meaning is preserved across the modality gap.
  • Semi-Paired Data Handling: In real-world scenarios, perfect 1:1 mappings of images to text are rare. CCQ is designed to leverage "unpaired" data to improve the overall quality of the learned hash codes.

Experimental Results

The authors evaluated CCQ on three standard benchmarks: NUS-WIDE (~195,000 pairs), Wiki (~2,800 pairs), and the massive Flickr1M dataset.

Precision-Recall curves demonstrate CCQ's superior performance over state-of-the-art hashing methods.

Key Findings

  • Superior Accuracy: CCQ consistently outperformed unsupervised state-of-the-art methods (like CVH and IMH) and even surpassed some supervised methods. On NUS-WIDE, CCQ achieved a Mean Average Precision (MAP) of 0.5372 for image-to-text search, significantly higher than the 0.4740 achieved by the next best unsupervised method.
  • Binarization Efficiency: While other methods lose significant precision when converted to binary, CCQ's performance remains nearly identical to its continuous-space version due to its joint optimization strategy.
  • Linear Scalability: Despite the complex joint optimization, training time scales linearly ($O(N)$) with the number of data points, making it viable for million-scale search engine scenarios.

Conclusion and Future Work

CCQ demonstrates that accounting for quantization during the mapping phase is critical for high-performance multimodal retrieval. While the current model uses linear transformations, the authors suggest that integrating Deep Learning (such as deep autoencoders) could further boost performance for highly complex, non-linear data. Future iterations also aim to eliminate the need for an extra "norm byte" currently used for distance calculations, making the resulting codes even more compact.

Summary updated

BibTeX
@inproceedings{long2016compositional,
  author = {Mingsheng Long and Jianmin Wang and Philip S. Yu},
  title = {{Compositional Correlation Quantization for Large-Scale Multimodal Search}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2016},
  url = {https://openreview.net/forum?id=HkN87B-_Zr},
}
Figure