Source-linked AI summary
Fast Supervised Hashing with Decision Trees for High-Dimensional Data
Guosheng Lin, Chunhua Shen, Qinfeng Shi, Anton van den Hengel, David Suter
TL;DR
Supervised hashing needs compact codes that preserve label-based similarity, while nonlinear kernel hash functions are costly on high-dimensional data. The paper combines decision-tree hash functions with sub-modular GraphCut-based code inference and reports higher retrieval precision with substantially faster training, especially for high-dimensional data.
Problem
Supervised hashing requires scalable nonlinear hash functions because kernel-based methods are expensive to train and evaluate on high-dimensional features.
Method
The method infers binary codes with sub-modular GraphCut-based block search, then trains boosted decision trees as hash functions fitting those codes.
Results
The method significantly outperforms many state-of-the-art methods in retrieval precision and is orders of magnitude faster to train on high-dimensional data.
Takeaways & Limitations
Decision-tree hash functions and GraphCut-based inference provide a practical supervised hashing approach for large-scale image retrieval with high-dimensional features.
Takeaways & Limitations
Many compared methods require large memory for matrix multiplications on large datasets.
Abstract
from arXiv · showhide
Supervised hashing aims to map the original features to compact binary codes that are able to preserve label based similarity in the Hamming space. Non-linear hash functions have demonstrated the advantage over linear ones due to their powerful generalization capability. In the literature, kernel functions are typically used to achieve non-linearity in hashing, which achieve encouraging retrieval performance at the price of slow evaluation and training time. Here we propose to use boosted decision trees for achieving non-linearity in hashing, which are fast to train and evaluate, hence more suitable for hashing with high dimensional data. In our approach, we first propose sub-modular formulations for the hashing binary code inference problem and an efficient GraphCut based block search method for solving large-scale inference. Then we learn hash functions by training boosted decision trees to fit the binary codes. Experiments demonstrate that our proposed method significantly outperforms most state-of-the-art methods in retrieval precision and training time. Especially for high-dimensional data, our method is orders of magnitude faster than many methods in terms of training time.
1. Introduction
Supervised hashing preserves label-based similarity in compact Hamming-space codes, but nonlinear kernel methods are costly on high-dimensional data. The paper addresses this with decision-tree hash functions and scalable GraphCut-based code inference.
- Motivation: Supervised hashing maps features to compact binary codes that preserve label-based similarity for efficient Hamming-space search and storage.Applications include image retrieval and large-scale object detection.
- Motivation: Nonlinear kernel hash functions improve performance over linear functions but are expensive to train and evaluate on high-dimensional features.The paper identifies scalable nonlinear supervised hashing as a practical need.
- Contributions: The proposed method uses ensembles of decision trees as nonlinear hash functions for high-dimensional supervised hashing.The authors describe this as the first general hashing method using decision trees as hash functions.
- Contributions: Binary code inference is formulated with sub-modular objectives and solved through an efficient GraphCut-based block search.Blocks are constructed from training points and affinity information for large-scale inference.
- Contributions: The learning strategy separates binary code inference from binary classification training of decision trees.This decomposes the overall learning problem into two simpler tasks.
- Contributions: The method significantly improves retrieval precision and is orders of magnitude faster to train on high-dimensional data than many existing methods.Prior spectral inference and kernel-based approaches are described as poorly scalable for large or high-dimensional training sets.
2. The proposed method
FastHash learns supervised non-linear hash functions through alternating binary-code inference and boosted decision-tree training. Its Block GraphCut inference handles large-scale optimization, while decision-tree hash functions provide non-linear fitting for high-dimensional data.
- Hashing formulation: The method represents each data point with m-bit binary codes whose Hamming affinity preserves label-based similarity.Similar pairs receive positive affinity, dissimilar pairs negative affinity, and undefined pairwise relations are excluded through |yij|.
- Boosted-tree hash functions: Each hash function is a linear combination of binary-output decision trees trained with AdaBoost and exponential loss.Decision-tree stumps select feature dimensions and thresholds while minimizing weighted classification error, combining feature selection with hash-function learning.
- Two-step learning: Auxiliary binary variables decompose hashing into binary code inference and binary classification for learning each hash function.This turns complicated joint decision-tree learning into two relatively simpler tasks.
- Binary code inference: FastHash sequentially optimizes one bit at a time while conditioning on previous bits, so current optimization accounts for losses from earlier bits.The bit length is set to k when solving the k-th bit, rather than optimizing all m bits simultaneously.
- Binary code inference: Block GraphCut groups data points into blocks and optimizes one block while conditioning on the remaining variables, using sub-modular formulations solvable by GraphCut.Blocks can overlap and must collectively cover all variables; the construction ensures the block objective is sub-modular under the stated similarity condition.
- FastHash procedure: The alternating FastHash procedure updates each bit with its learned hash function, feeding that output back into inference for the next bit.The method alternates inference and tree training for each bit; the table caption reports advantages over KSH in training time, encoding time, and retrieval precision.
3. Experiments
Experiments compare FastHash with supervised and unsupervised hashing methods across feature dimensionalities, inference strategies, and dataset scales. FastHash consistently achieves stronger retrieval performance and substantially faster training, especially for high-dimensional data.
- Experimental setup: Experiments evaluate training time, binary encoding time, and retrieval precision using low-dimensional GIST and high-dimensional codebook features.The study includes multiple supervised and unsupervised hashing baselines across several image datasets.
- Binary code inference: Block-GC achieves lower objective values and shorter inference time than TSH’s spectral method as training sets grow.Block-GC is also evaluated with block size one, which reduces it to ICM.
- Hash functions and inference: Decision-tree hash functions outperform linear SVM hash functions, while FastHash outperforms TSH using the same hash-function type.These comparisons use 11200-dimensional codebook features and vary the number of bits.
- Feature comparisons: FastHash and FastHash-Full outperform comparison methods on both GIST and codebook features, with orders-of-magnitude faster training on high-dimensional codebook features.The results are summarized in Table 3 and plotted for codebook features in Figure 2.
- Dimension reduction: After PCA reduces comparison methods to 500 dimensions, FastHash still significantly outperforms them while using the original high-dimensional features.The decision-tree hash functions perform feature selection and hash-function learning simultaneously.
- Scalability: FastHash scales to 22400-dimensional features and 1024-bit codes, with training and binary coding time increasing linearly with bit length.On SUN397, FastHash also trains to 1024 bits on more than 100,000 examples, while competing methods are impractically slow.
4. Conclusion
The paper proposes supervised hashing with decision-tree-based hash functions and GraphCut-based binary code inference. Experiments report advantages in retrieval performance and fast training for high-dimensional data, indicating practical significance for applications such as large-scale image retrieval.
- The method uses decision-tree-based hash functions and GraphCut-based binary code inference.
- Experiments show advantages in retrieval performance and fast training for high-dimensional data.
- The reported results indicate practical significance for applications such as large-scale image retrieval.