Large-Scale Supervised Multimodal Hashing with Semantic Correlation Maximization

Dongqing Zhang, Wu-Jun LiAAAI 2014 · OpenReview

Abstract

Due to its low storage cost and fast query speed, hashing has been widely adopted for similarity search in multimedia data. In particular, more and more attention has been paid to multimodal hashing for search in multimedia data with multiple modalities, such as images with tags. Typically, supervised information of semantic labels is also available for the data points in many real applications. Hence, many supervised multimodal hashing (SMH) methods have been proposed to utilize such semantic labels to further improve the search accuracy. However, the training time complexity of most existing SMH methods is too high, which makes them unscalable to large-scale datasets. In this paper, a novel SMH method, called semantic correlation maximization (SCM), is proposed to seamlessly integrate semantic labels into the hashing learning procedure for large-scale data modeling. Experimental results on two real-world datasets show that SCM can significantly outperform the state-of-the-art SMH methods, in terms of both accuracy and scalability.

Introduction

In the era of big data, we often deal with "multimodal" information—such as a social media post containing both an image and a set of tags. To search through millions of these items quickly, researchers use hashing, which maps high-dimensional data into short binary codes. This allows for lightning-fast similarity searches in Hamming space.

The primary challenge lies in Supervised Multimodal Hashing (SMH). While using semantic labels (like "dog" or "sunset") significantly improves search accuracy, most existing SMH algorithms have a training complexity of at least $O(n^2)$, where $n$ is the number of data points. On a dataset with 1 million items, $n^2$ operations become computationally prohibitive. Consequently, older methods were often forced to use tiny subsets of data, discarding valuable information and hurting performance.

The SCM Method

The authors propose Semantic Correlation Maximization (SCM) to bridge the gap between accuracy and scalability. Their approach focuses on Cross-Modal Hashing (CMH), where a query in one modality (e.g., text) retrieves results from another (e.g., images).

Key Innovations

  1. Linear Complexity: The authors define a semantic similarity matrix based on the cosine similarity of label vectors. Instead of explicitly computing this $n \times n$ matrix, they use algebraic identities to maximize the correlation between modalities directly, keeping the complexity linear ($O(n)$).
  2. Sequential Learning (SCM-Seq): While the authors also developed a simultaneous learning flavor (SCM-Orth), SCM-Seq learns hash bits one by one. Each new bit tries to minimize the error left by previous bits. This non-orthogonal approach is more robust and typically yields higher accuracy.
  3. Closed-Form Solutions: Unlike many machine learning models that require iterative gradient descent, SCM provides a closed-form solution for each bit, eliminating the need for hyperparameter tuning like learning rates.
MAP performance vs. training set size for image-to-text (a) and text-to-image (b) retrieval.

Experimental Results and Scalability

The authors evaluated SCM on standard benchmarks, including the large-scale NUS-WIDE dataset (~186,000 image-tag pairs).

Accuracy

SCM-Seq consistently outperformed baselines like CVH, CRH, and MLBE. As shown in the performance curves, SCM-Seq's Mean Average Precision (MAP) improves steadily as more training data is added, whereas other methods often plateau or fail to scale. On NUS-WIDE, SCM-Seq achieved a MAP of approximately 0.54, significantly higher than its nearest competitors.

Scalability

The most striking result is the training efficiency. On the NUS-WIDE dataset, SCM-Seq trained on 20,000 points in about 230 seconds. In contrast, the MLBE method took over 35 hours just for 1,000 points and became completely unfeasible for larger sets. This linear scaling allows SCM to utilize the entire training set rather than a small sample, providing a massive boost in performance.

Comparison of training time (in seconds) across different methods and training set sizes.

Conclusion

SCM demonstrates that forcing hash bits to be strictly orthogonal is often a mistake in supervised settings. By prioritizing high-variance directions through sequential learning and avoiding the $O(n^2)$ complexity trap, SCM provides a practical solution for large-scale multimodal retrieval. While modern deep learning has since moved toward end-to-end neural architectures, the mathematical principles of semantic correlation maximization remain a foundational approach for efficient cross-modal search.

Summary updated

Abstract

Due to its low storage cost and fast query speed, hashing has been widely adopted for similarity search in multimedia data. In particular, more and more attentions have been payed to multimodal hashing for search in multimedia data with multiple modalities, such as images with tags. Typically, supervised information of semantic labels is also available for the data points in many real applications. Hence, many supervised multimodal hashing (SMH) methods have been proposed to utilize such semantic labels to further improve the search accuracy. However, the training time complexity of most existing SMH methods is too high, which makes them unscalable to large-scale datasets. In this paper, a novel SMH method, called semantic correlation maximization (SCM), is proposed to seamlessly integrate semantic labels into the hashing learning procedure for large-scale data modeling. Experimental results on two real-world datasets show that SCM can significantly outperform the state-of-the-art SMH methods, in terms of both accuracy and scalability.
BibTeX
@inproceedings{zhang2014large,
  author = {Dongqing Zhang and Wu-Jun Li},
  title = {{Large-Scale Supervised Multimodal Hashing with Semantic Correlation Maximization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  url = {https://openreview.net/forum?id=r1Z6vTlubH},
}
Figure