Weakly-Supervised Online Hashing

Yu-Wei Zhan, Xin Luo, Yu Sun, Yongxin Wang, Zhen-Duo Chen, Xin-Shun Xu

TL;DR

Weakly-supervised Online Hashing (WOH) is a new framework designed to handle the "firehose" of social media images by learning compact hash codes from streaming data and noisy user-provided tags. By combining robust $\ell_{2,1}$-norm optimization with semantic word embeddings, WOH achieves state-of-the-art retrieval accuracy while remaining computationally efficient enough for real-time updates.

What Problem Does This Paper Address?

In the era of social media, images arrive as continuous streams, often accompanied by user-provided tags. To make these images searchable, researchers use hashing, which transforms high-dimensional image data into short binary strings. This allows for lightning-fast similarity searches with minimal storage.

However, existing hashing methods face a "trilemma":

  1. Batch-based methods are slow because they require retraining the entire model every time new data arrives.
  2. Unsupervised online methods are fast but ignore the rich semantic information hidden in user tags.
  3. Supervised online methods require high-quality, "clean" labels, which are rarely available in the wild.

The core challenge is that user tags are "weak"—they are often noisy, incomplete, or irrelevant. This paper introduces WOH to bridge the gap, enabling online learning that is robust to the imperfections of real-world social media metadata.

Methods

The authors propose a unified framework that integrates hash code learning, online updates, and "weak" information mining. Key technical components include:

  • Robust Tag Processing: Instead of treating tags as ground truth, WOH uses the $\ell_{2,1}$-norm for regression. This specific mathematical constraint is less sensitive to outliers, effectively "denoising" the user tags during the learning process.
  • Semantic Embedding: To handle missing tags (the "zero-shot" problem), the model uses pre-trained NLP tools (word2vec) to project tags into a continuous semantic space. These are aggregated via average pooling to create a high-level semantic representation of the image.
  • Discrete Online Optimization: Updating hash functions usually involves complex matrix inversions. The authors developed an iterative algorithm where the time complexity is linear relative to the size of the newly arriving data chunk, rather than the entire historical dataset.
  • Kernel Mapping: To capture non-linear relationships in the data, the model employs RBF kernel features, allowing it to learn more complex patterns than simple linear projections.

Datasets

The model was evaluated on two standard large-scale benchmarks for social image retrieval:

  • MIRFlickr: 25,000 images with 1,386 unique user tags.
  • NUS-WIDE: A larger dataset containing 269,648 images and 5,018 unique tags. For both datasets, the authors used the 4,096-dimensional output of a pre-trained VGG-F network as the base visual features.

Key Insights and Ideas

  • Tags as a Double-Edged Sword: The authors demonstrate that while tags are noisy, ignoring them (unsupervised learning) leads to significant information loss. The "aha moment" is that you don't need perfect labels if your optimization framework is mathematically designed to ignore outliers (via the $\ell_{2,1}$-norm).
  • Efficiency through Block Matrices: A major bottleneck in online learning is updating projection matrices. WOH uses block matrix properties to update these matrices incrementally, ensuring that the system doesn't slow down as the total database size grows.
  • Visual-Semantic Alignment: By considering both visual features and semantic tag embeddings simultaneously, the model can "fill in the gaps" when an image has very few tags, using the visual content to anchor the semantic search.

Key Results

WOH consistently outperformed seven state-of-the-art baselines (including both batch and online methods) across various hash code lengths (8 to 96 bits).

  • Accuracy: On the NUS-WIDE dataset (16-bit codes), WOH achieved a Mean Average Precision (MAP) of 0.5888, significantly higher than the next best online supervised method (SDH at 0.4910).
  • Convergence: The model converges very quickly, typically reaching peak performance within 5–10 iterations of a new data chunk.
  • Scalability: Training time remains stable as new data chunks arrive. For example, on MIRFlickr, processing each new chunk took roughly 1.7 seconds, regardless of how much "old" data had already been accumulated.

Limitations and Future Work

  • Fixed Visual Features: The current model relies on a pre-trained, static VGG-F network for visual features. It does not update the visual feature extractor itself in an online fashion.
  • Semantic Shift: While word2vec helps, the authors acknowledge a potential "semantic shift" between the general-purpose word2vec training corpus and the specific slang or context used in social media tags.
  • Deep Hashing: The authors note that while deep hashing (end-to-end learning) is powerful, it is currently too computationally expensive for true online streaming scenarios. Future work could explore "lightweight" deep online hashing.

Summary updated

Abstract

With the rapid development of social websites, recent years have witnessed an explosive growth of social images with user-provided tags. Most existing hashing methods for social image retrieval are batch-based which may violate the nature of social images, i.e., social images are usually generated periodically or collected in a stream fashion. Although there exist many online hashing methods, they either adopt unsupervised learning which ignore the relevant tags, or are designed in the supervised manner which needs high-quality labels. In this paper, to overcome the above limitations, we propose a new method named Weakly-supervised Online Hashing (WOH). In order to learn high-quality hash codes, WOH exploits the weak supervision, i.e., tags, by considering the semantics of tags and removing the noise. Besides, we develop a discrete online optimization algorithm, which is efficient and scalable. Extensive experiments conducted on two real-world datasets demonstrate the superiority of WOH.
BibTeX
@inproceedings{zhan2021weakly,
  author = {Yu-Wei Zhan and Xin Luo and Yu Sun and Yongxin Wang and Zhen-Duo Chen and Xin-Shun Xu},
  title = {{Weakly-Supervised Online Hashing}},
  booktitle = {ICME},
  year = {2021},
  url = {https://openreview.net/forum?id=DMhHqBEH4e},
}
Figure