Hashing Algorithms for Large-Scale Learning

Abstract

In this paper, we first demonstrate that b-bit minwise hashing, whose estimators are positive definite kernels, can be naturally integrated with learning algorithms such as SVM and logistic regression. We adopt a simple scheme to transform the nonlinear (resemblance) kernel into linear (inner product) kernel; and hence large-scale problems can be solved extremely efficiently. Our method provides a simple effective solution to large-scale learning in massive and extremely high-dimensional datasets, especially when data do not fit in memory. We then compare b-bit minwise hashing with the Vowpal Wabbit (VW) algorithm (which is related the Count-Min (CM) sketch). Interestingly, VW has the same variances as random projections. Our theoretical and empirical comparisons illustrate that usually $b$-bit minwise hashing is significantly more accurate (at the same storage) than VW (and random projections) in binary data. Furthermore, $b$-bit minwise hashing can be combined with VW to achieve further improvements in terms of training speed, especially when $b$ is large.

References in corpus (1)

• Accurate Estimators for Improving Minwise Hashing and b-Bit Minwise Hashing

Cited by in corpus (17)

• Circulant Binary Embedding
• Distributed Hierarchical GPU Parameter Server for Massive Scale Deep Learning Ads Systems
• Learning to Hash for Indexing Big Data - A Survey
• Optimal Densification for Fast and Accurate Minwise Hashing
• One Permutation Hashing for Efficient Search and Learning
• On Binary Embedding using Circulant Matrices
• b-Bit Minwise Hashing in Practice: Large-Scale Batch and Online Learning and Using GPUs for Fast Preprocessing with Simple Hash Functions
• Improved Consistent Weighted Sampling Revisited
• Training Logistic Regression and SVM on 200GB Data Using b-Bit Minwise Hashing and Comparisons with Vowpal Wabbit (VW)
• Climbing the WOL: Training for Cheaper Inference
• Randomized Kernel Multi-view Discriminant Analysis
• C-MinHash: Rigorously Reducing $K$ Permutations to Two
• Space-efficient Feature Maps for String Alignment Kernels
• A Filter of Minhash for Image Similarity Measures
• Learning Binary Codes and Binary Weights for Efficient Classification
• Real-time Bidding campaigns optimization using attribute selection
• Global Hashing System for Fast Image Search