Source-linked AI summary
A General Two-Step Approach to Learning-Based Hashing
Guosheng Lin, Chunhua Shen, David Suter, Anton van den Hengel
TL;DR
Existing hashing methods tightly couple optimization to a chosen hash-function form, limiting flexibility and often creating difficult non-convex problems. The paper introduces Two-Step Hashing, which separates binary-code inference from per-bit hash-function classification and accommodates varied losses and classifiers. Experiments report that the framework is effective, flexible, and outperforms state-of-the-art methods.
Problem
Existing hashing methods tightly couple their optimization procedures to specific hash-function forms, limiting extension to other forms and often producing highly non-convex NP-hard problems.
Method
Two-Step Hashing first infers binary codes using unified binary quadratic problems for varied Hamming-affinity losses, then trains a standard binary classifier independently for each bit.
Results
Experiments show high-quality codes, strong testing performance across several datasets, and state-of-the-art performance, including parity with KSH on Flickr1M and Tiny580k.
Takeaways & Limitations
Separating code generation from hash-function learning provides a common framework for comparing hashing methods and developing new approaches with different losses and classifiers.
Abstract
from arXiv · showhide
Most existing approaches to hashing apply a single form of hash function, and an optimization process which is typically deeply coupled to this specific form. This tight coupling restricts the flexibility of the method to respond to the data, and can result in complex optimization problems that are difficult to solve. Here we propose a flexible yet simple framework that is able to accommodate different types of loss functions and hash functions. This framework allows a number of existing approaches to hashing to be placed in context, and simplifies the development of new problem-specific hashing methods. Our framework decomposes hashing learning problem into two steps: hash bit learning and hash function learning based on the learned bits. The first step can typically be formulated as binary quadratic problems, and the second step can be accomplished by training standard binary classifiers. Both problems have been extensively studied in the literature. Our extensive experiments demonstrate that the proposed framework is effective, flexible and outperforms the state-of-the-art.
1 Introduction
Existing hashing methods couple their loss optimization to a particular hash-function form, limiting flexibility and often producing difficult non-convex problems. The paper proposes separating binary-code learning from hash-function learning to support diverse losses and classifiers.
- Motivation: Hashing maps high-dimensional data into compact binary codes that enable fast Hamming-distance search and efficient large-scale storage.Applications include approximate nearest-neighbour search and computer vision tasks.
- Limitations of existing methods: Existing methods optimize losses based on Hamming distance or affinity while directly optimizing parameters for a single hash-function form.Common forms include linear perceptrons, kernels, and eigenfunctions.
- Limitations of existing methods: Different hash-function forms trade testing time against ranking accuracy, while their coupling to optimization can create highly non-convex problems that are difficult to optimize.Linear perceptrons are typically faster to evaluate than kernels but may have lower nearest-neighbour accuracy.
- Proposed framework: The proposed framework decomposes hashing into binary-code inference and hash-function learning, simplifying the latter into standard binary classification.The framework can use classifiers including linear or kernel SVMs, boosting, decision trees, and neural networks.
- Proposed framework: Binary-code inference with diverse Hamming-affinity losses can be solved as a unified series of binary quadratic problems using block coordinate descent.The formulation covers ℓ2, exponential, and hinge losses, including losses used in KSH, BRE, and MLH.
- Evaluation: Experiments evaluate multiple loss and hash-function types for image retrieval, and report that the method outperforms state-of-the-art approaches.The tested hash functions include linear SVM, kernel SVM, and AdaBoost with decision stumps.
2 Two-step hashing
Two-Step Hashing first learns binary codes from pairwise affinity relationships, then learns one hash function per bit from those codes. This separates code optimization from classifier choice and permits multiple classifier forms.
- Problem formulation: Hashing learns m-bit binary codes for training points while preserving affinity or distance relations specified by a ground-truth matrix.The relation values may come from labels or unsupervised distances and affinities.
- Problem formulation: The general objective weights pairwise losses by relation indicators, with the loss measuring how closely binary codes match expected affinities or distances.The indicator δij specifies whether a pairwise relation is defined.
- Two-step procedure: TSH separates learning into binary-code inference followed by hash-function learning, avoiding direct optimization of hash-function parameters in the original coupled objective.The first step learns a code matrix Z, and the second uses Z to train hash functions.
- Two-step procedure: Hash functions are learned independently for each bit by solving a binary classification problem using the binary labels obtained during code inference.The classifier minimizes a loss such as zero-one loss or a convex surrogate including hinge or logistic loss.
- Classifier choices: The resulting classifier can take many forms, including linear SVM perceptrons, RBF-kernel SVMs, and AdaBoost with decision trees.SVM-KF uses a linear SVM on kernel-transferred features as a kernel-hash implementation.
- Algorithm: Step 1 uses block coordinate descent to obtain binary codes, while Step 2 trains a binary classifier for each bit from those codes.The code-learning algorithm cycles through bits and solves a binary quadratic problem for each one.
3 Solving binary quadratic problems
The method converts pairwise hamming-based losses into binary quadratic problems and solves them iteratively with block coordinate descent, followed by relaxations for improved solutions. It supports multiple loss functions, including those associated with KSH, BRE, MLH, SPLH, EE, and ExpH.
- Any pairwise hamming affinity or distance loss can be equivalently formulated as a binary quadratic problem at each iteration.The framework covers losses such as ℓ2, exponential, and hinge loss.
- Block coordinate descent optimizes one hash bit at a time in a cyclic fashion rather than the entire binary code matrix simultaneously.
- The quadratic reformulation relies on binary pair inputs having only identical or distinct cases, represented by two loss outputs.The proposition defines a quadratic function equal to the original loss for all possible binary inputs.
- Spectral relaxation supplies an initial solution by dropping binary constraints and using the eigenvector associated with the minimum eigenvalue of matrix A.
- A tighter relaxation is initialized with the spectral solution and optimized using LBFGS-B, although random initialization is also possible.
- Using 32-bit codes across three datasets, TSH outperforms competing methods on training data and by a large margin on testing data.The table compares multiple TSH loss functions with supervised and unsupervised baselines; its upper and lower parts report training and testing results, respectively.
4 Experiments
Experiments across five image datasets evaluate TSH with multiple losses, hash functions, supervised settings, and scales. TSH generally delivers strong retrieval quality, efficient training, and a tunable accuracy–speed trade-off.
- Experimental setup: Experiments use five image datasets, including CIFAR10, MNIST, LabelMe, Flickr1M, and Tiny580k, with supervised and unsupervised baselines.The evaluation includes three smaller datasets and two large-scale image datasets.
- Using different loss functions: TSH generates high-quality binary codes, matching ground-truth similarity perfectly on CIFAR10 and MNIST.The code-learning step outperforms competing methods by a large margin on the training data.
- Using different loss functions: TSH outperforms other methods in most testing cases, with especially large gains on the challenging CIFAR10 and LabelMe datasets.Supervised methods generally outperform unsupervised methods for preserving semantic similarity; TSH performs best overall.
- Efficiency: TSH is fast relative to state-of-the-art methods, and its second-stage binary-classification training can be easily parallelized.The reported training-time comparison includes both total time and the time spent inferring binary codes.
- Using different hash functions: Kernel hash functions achieve the best similarity-search performance, while linear hash functions test faster; TSH-KF trades speed for search quality.The evaluated variants include RBF-kernel SVM, kernel-transferred features, linear SVM, and decision-stump boosting.
- Large datasets: On Flickr1M and Tiny580k, TSH matches KSH and both significantly outperform other supervised and unsupervised methods.These datasets lack semantic ground truth, so similarity ground truth is generated using Euclidean distance.
5 Conclusion
The paper places diverse learning-based hashing methods in a common two-step framework that separates code generation from hash-function learning. Experiments validate the framework and show that the resulting approach outperforms the state-of-the-art.
- A common framework organizes diverse learning-based hashing methods and clarifies their strengths, weaknesses, and commonality.
- The framework separates code generation from hash-function learning, with the latter accurately formulated as a classification problem.
- This separation enables new hashing approaches, including the approach detailed in the paper.
- Experimental testing validates the approach and shows that it outperforms the state-of-the-art.