Learning hashing with affinity-based loss functions using auxiliary coordinates

Ramin Raziperchikolaei, Miguel Á. Carreira-PerpiñánarXiv 2015 · OpenReview

TL;DR

This paper introduces a novel framework called Method of Auxiliary Coordinates (MAC) for optimizing affinity-based binary hashing. By jointly optimizing the hash function and the binary codes, MAC achieves better retrieval performance and lower objective function values compared to existing two-step methods, without significantly increasing computational cost.

What Problem Does This Paper Address?

Fast image retrieval often relies on binary hashing, which maps high-dimensional image features to compact binary codes. The challenge lies in learning an effective hash function that preserves similarity relationships from the original feature space in the binary code space. Traditional approaches often involve a suboptimal two-step process: first learning continuous codes and then fitting a hash function to these codes. This separation leads to a mismatch between the learned codes and the hash function's capabilities, resulting in suboptimal performance. The paper aims to bridge this gap by proposing a method that jointly optimizes both the hash function and the binary codes.

Methods

The core contribution is the Method of Auxiliary Coordinates (MAC). This meta-algorithm tackles the nested optimization problem of learning hash functions and binary codes by:

  1. Introducing Auxiliary Coordinates: New binary variables (auxiliary coordinates) are introduced for each data point, constrained to be equal to the output of the hash function for that point. This transforms the problem into a constrained optimization.
  2. Penalty Method: A quadratic penalty is used to enforce the equality constraints, creating a new objective function that is minimized iteratively. The penalty parameter ($\mu$) is gradually increased.
  3. Alternating Optimization: The algorithm then alternates between two steps:
  4. Optimize Binary Codes (Z step): Given the current hash function, the binary codes are optimized to minimize the affinity-based loss function, while also being encouraged to be close to the hash function's output. This step is still NP-complete but is addressed using practical approaches like quadratic surrogates or GraphCut.
  5. Optimize Hash Function (h step): Given the binary codes, the hash function parameters are optimized. This is framed as a standard binary classification problem for each bit of the hash code.

This iterative process gradually enforces the constraint that the learned binary codes must be realizable by the hash function, leading to a better overall solution.

Datasets

The paper evaluates its framework on the following datasets:

  • CIFAR: Contains 60,000 images with 320 GIST features. Used for training and testing.
  • Infinite MNIST: A large dataset generated from MNIST with elastic deformations, containing 1,000,000 training images and 2,000 test images, each represented by 784 raw pixel features.
  • SIFT1M: A dataset of 1,000,000 high-resolution images with 128 SIFT features. Used for both supervised (with pseudolabels) and unsupervised experiments.

Key Insights and Ideas

  • Joint Optimization is Crucial: The paper strongly advocates for jointly optimizing the hash function and binary codes, rather than treating them as separate problems. This "closes the loop" and leads to better performance.
  • Auxiliary Coordinates Decouple Complexity: The MAC framework effectively decouples the complex, nested optimization problem into manageable alternating steps, making it easier to optimize.
  • Gradual Constraint Enforcement: The gradual increase of the penalty parameter ($\mu$) allows the algorithm to first find "free" binary codes that minimize the loss and then progressively enforce that these codes are realizable by the hash function.
  • "Filter" vs. "Wrapper" Analogy: The paper draws an analogy to feature selection, where MAC acts like a "wrapper" approach (optimizing features and classifier together) rather than a "filter" approach (optimizing features independently).
  • Flexibility in Loss and Hash Functions: The framework is general and can accommodate various affinity-based loss functions and hash function types (linear, kernel SVMs) with minimal modifications.

Key Results

  • Improved Performance: MAC consistently achieves lower objective function values and significantly better precision/recall compared to existing two-step methods (like "cut" and "quad") across various datasets, loss functions, and numbers of bits.
  • Competitive with State-of-the-Art: MAC methods (MACcut and MACquad) often outperform other established binary hashing methods, sometimes by a large margin.
  • Efficiency: The MAC algorithm is not much slower than the two-step approaches, with iterations being comparable to a single run of the two-step method, and subsequent iterations being warm-started.
  • Gain for Linear Hash Functions: The improvements are particularly noticeable when using linear hash functions, suggesting that MAC helps linear models better approximate complex code structures.

Limitations and Future Work

  • NP-Completeness of Z Step: While MAC provides a practical approach, the Z step (optimizing binary codes) remains an NP-complete problem. The paper acknowledges that finding reliable algorithms that scale to very large datasets for this step is an important area for future research.
  • Learning More Sophisticated Hash Functions: The paper suggests exploring more advanced hash function learning techniques beyond simple classifiers, potentially incorporating learned features or invariance properties.
  • Out-of-Sample Mapping: The MAC framework can also be extended to learn out-of-sample mappings for continuous embeddings, which is a related but distinct problem.
  • Binary Autoencoders: The paper briefly mentions applying MAC to binary autoencoders, noting that this objective decouples more easily per data point, leading to faster Z steps but potentially less direct relation to retrieval goals.

Summary updated

Abstract

In supervised binary hashing, one wants to learn a function that maps a high-dimensional feature vector to a vector of binary codes, for application to fast image retrieval. This typically results in a difficult optimization problem, nonconvex and nonsmooth, because of the discrete variables involved. Much work has simply relaxed the problem during training, solving a continuous optimization, and truncating the codes a posteriori. This gives reasonable results but is quite suboptimal. Recent work has tried to optimize the objective directly over the binary codes and achieved better results, but the hash function was still learned a posteriori, which remains suboptimal. We propose a general framework for learning hash functions using affinity-based loss functions that uses auxiliary coordinates. This closes the loop and optimizes jointly over the hash functions and the binary codes so that they gradually match each other. The resulting algorithm can be seen as a corrected, iterated version of the procedure of optimizing first over the codes and then learning the hash function. Compared to this, our optimization is guaranteed to obtain better hash functions while being not much slower, as demonstrated experimentally in various supervised datasets. In addition, our framework facilitates the design of optimization algorithms for arbitrary types of loss and hash functions.
BibTeX
@misc{raziperchikolaei2015learning,
  author = {Ramin Raziperchikolaei and Miguel Á. Carreira-Perpiñán},
  title = {{Learning hashing with affinity-based loss functions using auxiliary coordinates}},
  year = {2015},
  eprint = {1501.05352},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1501.05352},
}
Figure