PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Hash with Binary Deep Neural Network

Thanh-Toan Do, Anh-Dzung Doan, Ngai-Man Cheung

arXiv:1607.05140v1cs.CV

TL;DR

The paper addresses the difficulty of learning compact binary hash codes without relying on post hoc thresholding that can yield inferior codes. It proposes unsupervised and supervised binary deep neural networks with direct binary outputs and strict code properties, optimized through alternating optimization and careful relaxation. Experiments on three benchmark datasets show favorable comparisons with state-of-the-art methods.

  • Problem

    Post hoc thresholding of relaxed continuous codes can be inferior to learning with binary constraints directly.

  • Method

    UH-BDNN and SH-BDNN directly output binary codes at one network layer while incorporating similarity preservation, independence, and balance through alternating optimization and careful relaxation.

  • Results

    Experiments on three benchmark datasets show that the proposed methods compare favorably with state-of-the-art hashing methods across reported retrieval evaluations.

  • Takeaways & Limitations

    Direct binary-code learning provides a neural approach for unsupervised and supervised hashing that retains the paper’s stated code-quality properties during optimization.

  • Takeaways & Limitations

    Constraining independence and balance directly makes the optimization very difficult.

Abstract

from arXiv · show

This work proposes deep network models and learning algorithms for unsupervised and supervised binary hashing. Our novel network design constrains one hidden layer to directly output the binary codes. This addresses a challenging issue in some previous works: optimizing non-smooth objective functions due to binarization. Moreover, we incorporate independence and balance properties in the direct and strict forms in the learning. Furthermore, we include similarity preserving property in our objective function. Our resulting optimization with these binary, independence, and balance constraints is difficult to solve. We propose to attack it with alternating optimization and careful relaxation. Experimental results on three benchmark datasets show that our proposed methods compare favorably with the state of the art.

1 Introduction

Binary hashing compresses high-dimensional visual data for efficient storage and search, but learning useful binary codes is difficult because binarization creates hard optimization constraints. The paper addresses this with neural models that directly produce binary codes while enforcing similarity, independence, and balance.

  • Motivation: Binary hashing maps high-dimensional vectors to compact binary codes, enabling more efficient storage and faster large-scale visual search.The codes have length L much smaller than the original dimensionality D.
  • Challenges: Binary constraints make hashing a generally NP-hard mixed-integer optimization problem.Many existing methods relax the constraint, learn continuous codes, and threshold them afterward.
  • Challenges: Thresholding relaxed continuous solutions can produce binary codes inferior to those learned with the binary constraint included directly.This motivates optimization procedures that retain the binary constraint during learning.
  • Desired code properties: Effective hash codes should preserve similarity while maintaining independent bits and balanced 50% usage of 1 and −1.Directly enforcing independence and balance can complicate learning, so prior approximations may degrade performance.
  • Optimization: The resulting constrained optimization is attacked with alternating optimization and careful relaxation rather than sgn or step-function binarization.The paper presents the approach as addressing non-differentiability and the difficulty of directly constrained optimization.
  • Proposed approach: The proposed UH-BDNN and SH-BDNN constrain one network layer to output binary codes directly and incorporate similarity, independence, and balance properties.The methods target unsupervised and supervised hashing, respectively.

2 Unsupervised Hashing with Binary Deep Neural Network (UH-BDNN)

UH-BDNN directly constrains a penultimate network layer to produce binary codes, uses reconstruction to preserve similarity, and enforces independence and balance in the objective. Because the resulting problem is NP-hard, the method uses auxiliary-variable reformulation and alternating optimization.

  • Network design: The network uses sigmoid activations in intermediate layers and identity activations at the penultimate and final layers, with penultimate outputs serving as binary codes.The penultimate layer has L units, while the final layer reconstructs the D-dimensional input.
  • Objective formulation: Reconstruction encourages similarity preservation because similar and dissimilar inputs are encouraged to map to correspondingly similar and dissimilar binary codes.The reconstruction term also forms the main data-fitting component of the objective.
  • Objective formulation: Direct binary constraints make the formulation a mixed-integer NP-hard problem, avoiding the nondifferentiability difficulties associated with sgn or step-function binarization.Earlier approaches often learned continuous codes first and thresholded them afterward, which could produce inferior binary codes.
  • Optimization: An auxiliary variable B separates the constrained optimization into subproblems over network parameters and codes, which are solved iteratively by alternating optimization.A quadratic penalty relaxes the equality linking B to the penultimate-layer outputs and penalizes constraint violations.
  • Code properties: Independence and balance are encoded directly and strictly in the binary outputs rather than through the relaxations or approximations used in earlier methods.The authors note that imposing these properties directly can make optimization difficult.
  • Optimization: The method alternates L-BFGS with backpropagation for network parameters and discrete cyclic coordinate descent for B, solving B row by row with closed-form updates.The algorithm initializes B with ITQ, then repeatedly fixes one variable block while optimizing the other.

3 Evaluation of Unsupervised Hashing with Binary Deep Neural Network (UH-BDNN)

UH-BDNN is evaluated against established unsupervised hashing methods on CIFAR10, MNIST, and SIFT1M using mAP and precision@2. It is comparable or better across code lengths, with clearer advantages at 24 and 32 bits and consistent gains over BA and DH.

  • Evaluation setup: UH-BDNN is compared with Spectral Hashing, ITQ, BA, SPH, and KMH on CIFAR10, MNIST, and SIFT1M.The experiments use author-provided implementations and suggested parameters for the compared methods.
  • Evaluation setup: The evaluation uses Euclidean nearest neighbors as ground truths, reporting mAP and precision@2.For SIFT1M, mAP is computed over the top 10,000 returned neighbors because full computation is slow.
  • Unsupervised retrieval results: UH-BDNN is comparable to or outperforms other methods in mAP at all code lengths across the three datasets.Its improvement is more clear at L = 24 and 32.
  • Unsupervised retrieval results: UH-BDNN consistently outperforms BA in mAP, while its precision@2 is comparable at L = 8, 16 and significantly better at L = 24, 32.BA is identified as the current state-of-the-art unsupervised hashing method in the comparison.
  • Comparison with DH: UH-BDNN outperforms DH at all code lengths in both mAP and precision at Hamming radius 2 on CIFAR10 and MNIST.The comparison uses experiments set up similarly to DH because its implementation was unavailable.

4 Supervised Hashing with Binary Deep Neural Network (SH-BDNN)

SH-BDNN extends the binary deep neural network to supervised hashing by replacing unsupervised reconstruction-based similarity preservation with label-based semantic similarity preservation. It retains binary, independence, and balance constraints and solves the resulting optimization by alternating updates of network parameters and binary codes.

  • Supervised hashing formulation: SH-BDNN leverages label information to enhance the discriminative power of binary codes.Its semantic objective follows KSH by encouraging within-class Hamming distances of 0 and between-class distances of L.
  • Supervised hashing formulation: SH-BDNN has a network structure similar to UH-BDNN but removes the final reconstruction-preserving layer.Semantic similarity preserving, independence, and balance are constrained on the outputs of the last layer.
  • Supervised hashing formulation: The supervised objective uses a pairwise label matrix and terms for semantic similarity preservation, independence, and balance.The formulation also enforces the binary constraint on the codes.
  • Optimization: Optimization alternates between network parameters (W, c) and binary codes B.With B fixed, L-BFGS and backpropagation optimize the parameters; with parameters fixed, the binary-code update is B = sgn(H(n)).
  • Optimization: Algorithm 2 initializes B with ITQ, initializes network parameters, and repeatedly performs B and (W, c) updates for T iterations.The final returned model is (W, c)(T).

5 Evaluation of Supervised Hashing with Binary Deep Neural Network (SH-BDNN)

The evaluation compares SH-BDNN with supervised hashing methods on CIFAR10 and MNIST using mAP and precision@2, including comparisons with CNN-based hashing methods. SH-BDNN performs strongly across datasets, code lengths, and compared baselines.

  • Evaluation setup: SH-BDNN is evaluated against SDH, ITQ-CCA, KSH, and BRE on CIFAR10 and MNIST.The evaluation reports mAP and precision@2, using author-provided implementations and suggested parameters for the compared methods.
  • Evaluation setup: The supervised evaluation uses 3,000 training samples from each class for SH-BDNN, KSH, and BRE, while ITQ-CCA and SDH use all training samples.Query ground truths are defined by dataset class labels.
  • Retrieval results: On CIFAR10, SH-BDNN outperforms all compared methods at every code length in both mAP and precision@2.The comparison is reported using Fig. 3(a) and Table 4.
  • Retrieval results: On MNIST, SH-BDNN significantly outperforms SDH at L = 8 and achieves similar performance to SDH as code length increases.Against KSH, ITQ-CCA, and BRE, SH-BDNN performs better by a large margin in both mAP and precision@2.
  • CNN-based comparisons: At the same code length on CIFAR10, SH-BDNN outperforms DSRH and DRSCH in both mAP and precision@2.The CNN-based hashing comparison uses AlexNet features as input for SH-BDNN under the comparison setting of the cited methods.

6 Conclusion

The paper proposes UH-BDNN and SH-BDNN for unsupervised and supervised hashing. Their direct binary-output network design incorporates similarity preservation, independence, and balance, and experiments show favorable comparison with the state of the art.

  • Conclusion: UH-BDNN and SH-BDNN are proposed for unsupervised and supervised hashing.The models directly produce binary codes at one network layer and are evaluated on three benchmark datasets.
  • Conclusion: The proposed methods compare favorably with the state of the art.The conclusion summarizes the experimental results across three benchmark datasets.
Loading 1607.05140v1…