PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Hashing

Long-Kai Huang, Qiang Yang, Wei-Shi Zheng

arXiv:1704.01897v1cs.CVcs.LG

TL;DR

Most hash models are learned offline, although incoming data may be sequential and require online updates. This paper proposes a pairwise, passive-aggressive online hashing method and extends it to multiple models; MMOH leads mAP on GIST 1M for code lengths above 16 bits, but is not best on the other three datasets.

  • Problem

    Most hash models assume data are available in advance, leaving a need for methods that handle sequential data and new arrivals.

    Source: §1 · p. 2

  • Method

    Online Hashing updates a structured hash model from incoming data pairs using pairwise similarity loss and a passive-aggressive update that preserves information from prior rounds.

    Source: §1 · p. 2, §3.1 · pp. 4–5

  • Results

    MMOH has the highest mAP on GIST 1M for code lengths above 16 bits, but is not best on the other three datasets and outperforms KLSH and ITQ there.

    Source: §7.3.4 · pp. 12–13

  • Takeaways & Limitations

    MMOH is developed for more robust online hashing by learning diverse models that can fit different data pairs locally.

    Source: §6 · p. 8, §8 · p. 13

    When all labeled data are available at once, OH and MMOH are not the best choice compared with batch-mode supervised hashing methods.

    Source: §7.3.4 · p. 13

Abstract

from arXiv · show

Although hash function learning algorithms have achieved great success in recent years, most existing hash models are off-line, which are not suitable for processing sequential or online data. To address this problem, this work proposes an online hash model to accommodate data coming in stream for online learning. Specifically, a new loss function is proposed to measure the similarity loss between a pair of data samples in hamming space. Then, a structured hash model is derived and optimized in a passive-aggressive way. Theoretical analysis on the upper bound of the cumulative loss for the proposed online hash model is provided. Furthermore, we extend our online hashing from a single-model to a multi-model online hashing that trains multiple models so as to retain diverse online hashing models in order to avoid biased update. The competitive efficiency and effectiveness of the proposed online hash models are verified through extensive experiments on several large-scale datasets as compared to related hashing methods.

1 INTRODUCTION

The paper addresses the mismatch between batch hash learning and sequential data by proposing online hashing that updates from incoming pairs. It also introduces multiple complementary models to reduce bias from updates driven by the current round.

1 INTRODUCTION

  • Compact binary codes support large-scale storage and fast similarity computation, while hashing research spans data-independent, data-dependent, and other specialized approaches.Data-dependent methods include unsupervised, supervised, and semi-supervised models, alongside multi-view, multi-modal, and active hashing.Source: §1 · p. 2
  • Most existing hash models assume all training data are available in advance, limiting their fit to sequential data and new arrivals.Batch learning can also require retaining all data in memory, with costly storage and intolerable training time on large datasets.Source: §1 · p. 2
  • Online Hashing updates a hash model from each new pair using pairwise similarity, without requiring exact data labels.Its passive-aggressive update retains information from previous rounds, and the paper derives an upper bound on cumulative similarity loss.Source: §1 · p. 2
  • MMOH trains multiple complementary models to suit diverse data pairs and alleviate bias from one-pass updates.The models are selectively updated, and the paper also provides a cumulative similarity-loss bound for the multi-model strategy.Source: §1 · pp. 2–3

2 RELATED WORK

Prior online hashing approaches adapt existing learning strategies, but face challenges around nondifferentiable hash functions, loss guarantees, and stream adaptation. The paper positions its approach against gradient-based and sketch-based methods and notes additions to its earlier conference version.

2 RELATED WORK

  • Prior online-learning methods are difficult to apply to hash learning because the sign function is nondifferentiable, while differentiable approximations obstruct deriving a loss bound.Related approaches include online LSH, SGD-based methods, and matrix-sketch methods.Source: §2 · p. 3
  • Existing online hashing work includes online LSH, SGD-based methods, and matrix-sketch methods, but some do not directly optimize compact binary hash functions online.Online LSH applies metric learning to a data-independent model, while the other cited methods use SGD or matrix sketching.Source: §2 · p. 3
  • MLH's loss upper bound may grow with the number of historical samples, and its zero-mean input assumption is difficult to satisfy when data arrive sequentially.MLH relies on stochastic-gradient updates, but its centering requirement assumes access to all samples in advance.Source: §2 · p. 3
  • Gradient-based online hash methods enable updates, but the cited SGD approaches do not guarantee a constant loss upper bound.OECC replaces a 0-1 loss with a convex loss and drops the sign function; AdaptHash approximates the hash function with a differentiable sigmoid.Source: §2 · p. 3
  • OSH and SSBC use matrix sketching to preserve information from stream data, but SSBC's retained global information may limit adaptation to later samples.OSH sketches samples into a small matrix that approximates data covariance before applying PCA hashing.Source: §2 · p. 3
  • This journal version adds a modified similarity loss, a multi-model strategy, revised zero-loss-code inference, and more experiments beyond the preliminary version.The paper describes these as changes from its earlier conference version.Source: §2 · p. 3

3 ONLINE MODELLING FOR HASH FUNCTION LEARNING

Online Hashing (OH) learns hash projections from sequential data pairs, using similarity and prediction losses to guide passive-aggressive updates. The section also describes a kernelized variant for nonlinear modeling.

3 ONLINE MODELLING FOR HASH FUNCTION LEARNING

  • The hash model maps each data vector to an r-bit binary code, and structured prediction reformulates the sign-based hash function to address its nondifferentiability.The structured prediction score measures how well a candidate binary code matches the hash code.Source: §3 · pp. 3–4

3.1 Formulation

  • OH uses pairwise Hamming-space similarity loss and a prediction loss to guide updates that stay close to the previous projection while limiting prediction loss.The update objective uses a slack variable and margin parameter C; a zero-loss prediction leaves the projection unchanged.Source: §3.1 · pp. 4–5

3.2 Optimization

  • The optimization derives a closed-form projection update and applies it when the current pair has positive similarity loss.When the current projection predicts zero loss, the solution is to retain it; the algorithm obtains a zero-loss code pair before updating.Source: §3.2 · pp. 5–6

3.3 Kernelization

  • The kernelized OH variant maps data into a feature space using m anchor points and a Gaussian RBF kernel.Learning waits until at least m data points are available to serve as anchors; the RBF kernel uses σ = 1.Source: §3.3 · p. 6

4 ZERO-LOSS BINARY CODE PAIR INFERENCE

The section constructs a zero-similarity-loss code pair by changing as few hash bits as possible, choosing bits with the smallest potential prediction loss.

Dissimilar pairs

  • For dissimilar pairs, the target code pair must have Hamming distance at least βr; the method changes the minimum required number of bits to reach that threshold.It selects bits from K0 with the smallest potential loss and flips them; other bits remain unchanged.Source: §4 · pp. 6–7

Zero-loss code pair inference

  • The bit-selection rule favors small potential losses because large online updates may not suit previously seen data; minimizing changed bits also limits projection updates.The initialization uses LSH because zero projection vectors would yield zero potential losses and prevent bit selection.Source: §4 · pp. 6–7

Similar pairs

  • For similar pairs, the target Hamming distance is at most α, so the method changes the minimum number of bits needed to meet that threshold.It selects the bits from K1 with the smallest potential loss and flips them.Source: §4 · p. 7

5 ANALYSIS

The analysis bounds OH's cumulative similarity loss under stated conditions and gives its training and space complexities. It also relates a constant cumulative-loss bound to convergence toward an optimal model.

5.1 Bounds for Similarity Loss and Prediction Loss

  • If the update norm is bounded by F² and the margin parameter C is set to the stated upper bound, Theorem 2 bounds cumulative similarity loss for any comparator matrix U.The section states that when a zero-loss comparator exists, cumulative similarity loss is bounded by a constant that does not grow with the number of rounds, and the model can converge to an optimal model after adequate updates.Source: §5.1 · pp. 7–8

5.2 Time and Space Complexity

  • Training n pairs takes O((dr + rlogr)n) time and O(dr) space, with space independent of the number of training samples.The per-round time is O(dr + rlogr), and space stores the data pairs and projection matrix.Source: §5.2 · p. 8

6 MULTI-MODEL ONLINE HASHING

The multi-model method trains distinct hash models and selectively updates them according to pairwise similarity loss. The paper also provides an upper bound for cumulative multi-model similarity loss.

6 MULTI-MODEL ONLINE HASHING

  • The T models are randomly initialized using LSH, and each model optimizes its own similarity loss.When T = 1, the strategy is described elsewhere as OH; this section states that each model has its own loss function.Source: §6 · pp. 8–9
  • For similar pairs, MMOH updates the model with the smallest similarity loss; for dissimilar pairs, it updates every model with nonzero loss.The selection is intended to fit similar pairs locally while requiring all models to address dissimilar pairs that would otherwise be incorrectly predicted.Source: §6 · p. 8
  • Theorem 3 gives an upper bound for cumulative multi-model similarity loss under stated assumptions, including a bound involving margin parameter C.The supplied theorem statement is incomplete, so its exact bound and full conditions are not specified here.Source: §6 · p. 9

7 EXPERIMENTS

The experiments assess the proposed online hashing models for metric-distance and semantic neighbor search. They evaluate the models on four selected large-scale datasets and compare them with related hashing models.

7 EXPERIMENTS

  • The experiments assess the proposed models along two search aspects: metric-distance neighbor search and semantic neighbor search.The section describes the experiments as testing both efficiency and effectiveness.Source: §7 · p. 9
  • The experimental program introduces four selected large-scale datasets before evaluating the proposed models.Dataset descriptions are assigned to Section 7.1, with evaluation in Section 7.2.Source: §7 · p. 9
  • The section concludes its described workflow with comparisons between the proposed algorithms and related hashing models.Those comparisons are assigned to Section 7.3.Source: §7 · p. 9

7.1 Datasets

The experiments use four large-scale datasets with dataset-specific representations, train-test partitions, and similarity-label construction. Performance is measured using mean average precision.

7.1 Datasets

  • Photo Tourism uses 104K Half Dome patches represented by 512-dimensional GIST features, with 98K training patches and 6K test patches.Pairs are labeled similar when patches match and dissimilar otherwise.Source: §7.1 · p. 9
  • 22K LabelMe contains 22,019 images represented by 512-dimensional GIST features, with 2K images randomly held out for testing.Pairs are similar when either image is among the other's top 5% nearest neighbors by Euclidean distance.Source: §7.1 · p. 9
  • GIST1M provides one million unlabeled 960-dimensional GIST vectors, with 500,000 used for training and 1,000 non-overlapping points for testing.Pseudo-labels treat each point's top 5% Euclidean neighbors, or 50,000 points, as true neighbors.Source: §7.1 · p. 9
  • CIFAR-10 contributes 60K images across 10 classes, represented by 2048-dimensional deep features; 59K train the model and 1K serve as queries.Queries search through the 80M Tiny Image collection.Source: §7.1 · p. 9
  • Mean average precision (mAP) measures algorithm performance, and the experiments ran on a Xeon X5650 server with 12 GB memory.The passage describes mAP as a better retrieval-quality measure than precision and recall.Source: §7.1 · p. 9

7.2 Evaluation of the Proposed Methods

The evaluation investigates the effects of dissimilarity threshold β, model count T, and margin parameter C. Results describe how these settings relate to mAP and cumulative similarity loss.

7.2 Evaluation of the Proposed Methods

  • The evaluation investigates β, C, and T, as well as the influence of the RBF kernel function.When varying one parameter, the others are set to defaults; the reported setup uses 64-bit codes and an RBF default kernel.Source: §7.2 · p. 9

7.2.1 Effect of Dissimilarity Ratio Threshold β

  • When β rises, OH mAP initially improves on all datasets, but further increases above 0.5 may degrade performance.A moderately large β is preferred on three datasets; defaults are 0.5 for Photo Tourism and 22K LabelMe, and 0.4 for GIST1M and CIFAR-10.Source: §7.2.1 · pp. 9–10, Figure 2 · p. 10

7.2.2 Effect of the Number of Multiple Models T

  • For MMOH, increasing T improves performance on most datasets except CIFAR-10, with clearer gains on 22K LabelMe and GIST1M.The paper reports less improvement on Photo Tourism and overall better, more stable performance with more models; T was varied from 1 to 4, and T = 1 is OH.Source: Figure 3 · p. 10, §7.2.2 · p. 10

7.2.3 Effect of Margin Parameter C

  • Across all datasets, OH mAP favors C = 1E −1; increasing C from 1E −5 to 1E −2 improves performance by a large margin, while further increases yield only slight gains.The slight gains from further increases are especially noted on Photo Tourism, 22K LabelMe, and Gist1M.Source: §7.2.3 · p. 10
  • On Photo Tourism, cumulative similarity loss is lowest at C = 0.1 across more than 10^6 loops, while loss grows strongly for C < 1E −3.The reported loss grows more slowly when C ≥ 1E −3; the experiment allowed duplication of training data.Source: §7.2.3 · pp. 10–11, Figure 5 · p. 11

7.3 Comparison with Related Methods

The section compares OH and MMOH with related hashing methods on mAP and training time, covering online and batch-mode baselines, evaluation settings, and code-length comparisons.

7.3 Comparison with Related Methods

  • The comparison evaluates related methods on both mAP and training time.The experiments use these two aspects to assess OH and MMOH against selected algorithms.Source: §7.3 · p. 11, §7.3.3 · p. 11

7.3.1 Compared Methods

  • The baselines include data-independent KLSH, five non-batch methods, and batch-mode ITQ, KSH, FastHash, and SDH.LEGO-LSH, MLH, SSBC, OSH, and AdaptHash make up the non-batch group; KSH, FastHash, and SDH are supervised batch methods.Source: §7.3.1 · p. 11
  • Figure 6 reports mAP comparison results among different online hash models, with the comparisons made with respect to different code lengths.Source: Figure 6 · p. 11

7.3.2 Settings

  • For MMOH, the number of models T is set to 4, and compared methods use parameters recommended in their respective papers.Pairwise methods receive randomly sampled training pairs in sequence; OSH processes sequential chunks of 1,000 samples.Source: §7.3.2 · p. 11

- mAP Comparisons

Across online methods, MMOH and OH generally lead the mAP comparisons as code length increases, with MMOH most often first and OH second.

- mAP Comparisons

  • MMOH achieves the best mAP and OH the second-best on almost all datasets for code lengths above 32, except that LEGO-LSH and OH perform similarly on Photo Tourism.The comparison covers LEGO-LSH, MLH, SSBC, OSH, OH, and MMOH.Source: - mAP Comparisons · p. 11
  • As code length increases, MMOH and OH improve on all datasets, and MMOH is significantly better than OSH and MLH.MMOH also outperforms LEGO-LSH on 22K LabelMe, GIST1M, and CIFAR-10.Source: - mAP Comparisons · p. 11
  • The advantage of MMOH over the compared methods is clearer on CIFAR-10 at longer code lengths.Source: - mAP Comparisons · p. 11

- Training Time Comparisons

OH and MMOH show low accumulated training time in the reported comparisons, while batch-mode results vary by baseline and dataset.

- Training Time Comparisons

  • OH updates each pair in 0.0015 seconds and has the least accumulated training time; at 80,000 samples, LEGO-LSH takes 10 times as long as MMOH and MLH.The sample-count experiment uses Photo Tourism and a fixed 64-bit code length; results average 10 single-thread runs.Source: - Training Time Comparisons · p. 12, Figure 7 · p. 12
  • As code length increases, accumulated training time rises slightly for all algorithms except LEGO-LSH; OH remains least, and OH and AdaptHash take about half the time of MLH and MMOH.MMOH takes slightly longer than MLH below 64 bits, then slightly less above 64 bits.Source: - Training Time Comparisons · p. 12, Figure 7 · p. 12

7.3.4 Comparison to Batch Mode Methods

  • Against batch methods, OH outperforms KLSH across datasets and ITQ above 32 bits; MMOH leads KSH and FastHash on GIST1M above 16 bits but is not best on the other three datasets.The paper notes that OH and MMOH address online stream learning, whereas the supervised batch methods assume labeled data are available at once.Source: §7.3.4 · pp. 12–13, Figure 8 · p. 13

8 CONCLUSION & DISCUSSION

The conclusion presents OH as a one-pass online hash learner with theoretical loss bounds and extends it to MMOH for more robust online hashing.

8 CONCLUSION & DISCUSSION

  • OH updates its hash model at each step from a pair of input samples using a structured-prediction formulation and prediction loss.The update is constrained by inferred optimal hash codes that achieve zero prediction loss.Source: §8 · p. 13
  • The proposed OH model has theoretical upper bounds on both similarity loss and prediction loss.Source: §8 · p. 13
  • The authors develop MMOH as a more robust multi-model extension, and report satisfactory mAP results and training-time efficiency across datasets.Source: §8 · p. 13
  • Updating multiple data pairs at once is future work, and the theoretical bound for that setting needs further investigation.Source: §8 · p. 13
Loading 1704.01897v1…