Source-linked AI summary
Hashing Algorithms for Large-Scale Learning
Ping Li, Anshumali Shrivastava, Joshua Moore, Arnd Christian Konig
TL;DR
Large-scale, high-dimensional datasets create storage and training challenges, particularly when they exceed memory. The paper integrates b-bit minwise hashing with SVM and logistic regression through a linear feature expansion, finding improved accuracy over VW at equal storage and further training-speed gains when combined with VW.
Problem
Large-scale, high-dimensional data create storage and training challenges, especially when datasets exceed single-machine memory.
Method
The paper uses b-bit minwise hashing as a compact representation, converts the resemblance kernel into a linear feature representation, and integrates it with SVM and logistic regression.
Results
b-bit minwise hashing is usually significantly more accurate than VW at the same storage for binary data and can further improve training speed when combined with VW at large b.
Takeaways & Limitations
The method provides a compact learning approach for massive, extremely high-dimensional datasets, including settings where data do not fit in memory.
Takeaways & Limitations
Preprocessing can matter when new documents require immediate responses, although disk I/O may mask its cost.
Abstract
from arXiv · showhide
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.
1 Introduction
Large-scale, high-dimensional datasets strain both machine-learning storage and training, especially when they exceed single-machine memory. This paper uses b-bit minwise hashing to compact binary data and integrate it with linear learning methods.
- Industrial datasets can reach 16 trillion unique features or average 10^11 items and 10^9 distinct features.
- Similarity-search techniques motivate compact representations that support efficient approximate distance computation when exact distances become prohibitive.
- b-bit minwise hashing computes resemblances efficiently in time and space for extremely high-dimensional binary vectors and integrates with linear SVM and logistic regression.
- The approach targets binary, very high-dimensional, relatively sparse data such as text documents represented through shingles.
- The paper addresses positive definiteness, nonlinear-to-linear conversion, and comparisons with random projections, Count-Min sketches, and Vowpal Wabbit.
- Unlike block-loading methods, this approach is presented as complementary rather than a direct competitor for problems whose data do not fit in memory.
2 Review Minwise Hashing and b-Bit Minwise Hashing
Minwise hashing estimates resemblance between binary sets through permutation collisions, while b-bit hashing reduces storage by retaining only the lowest bits of hashed values. The paper applies this compact representation without explicitly estimating resemblance.
- Minwise hashing is widely used for efficiently computing set similarities, especially in search.
- For binary sets, resemblance is a normalized similarity measure based on intersection and union sizes.
- A random permutation produces a collision probability equal to the sets’ resemblance, allowing unbiased estimation from k independent permutations.
- Standard minwise hashing stores each hashed value using 64 bits, creating prohibitive storage and computational costs at large scale.
- b-bit minwise hashing stores only the lowest b bits of each minimum permuted value instead of the full hash.
- The learning procedure uses b-bit hashing directly rather than explicitly estimating resemblance from the estimator formula.
3 Kernels from Minwise Hashing and b-Bit Minwise Hashing
The paper proves that resemblance, minwise-hashing, and b-bit minwise-hashing matrices are positive definite. This proof supplies a feature expansion that converts the nonlinear resemblance kernel into a linear inner-product representation.
- Resemblance, minwise-hashing, and b-bit minwise-hashing matrices are all positive definite.
- The construction begins with one permutation applied to each set and defines minimum permuted values whose matching low bits form the b-bit matrix.
- Positive definiteness is grounded in representing the relevant matrices through inner products of vectors.
- The resemblance matrix is positive definite because its entries are expectations of elements from a positive definite minwise-hashing matrix.
- The proof yields a linearizing expansion in which k hashed vectors are concatenated into a binary vector of dimension 2b × k with exactly k ones.
4 Integrating b-Bit Minwise Hashing with (Linear) Learning Algorithms
The method stores hashed feature vectors compactly, expands them into sparse binary vectors, and feeds those vectors to linear SVM or logistic-regression solvers. It avoids explicitly estimating resemblance during learning.
- Linear SVM and logistic regression are the target learning algorithms for the b-bit hashing representation.
- The penalty parameter C is varied over a range, with cross-validation assumed to identify the best achievable performance.
- The representation stores k lowest b-bit hash values for each feature vector, requiring only nbk bits, then expands each point into a 2b × k-length vector.
- For k = 3 and b = 2, the hashed values expand into a length-12 binary feature vector supplied to the solver.
- Each expanded data vector has exactly k ones, while total storage remains nbk bits.
- The procedure does not explicitly estimate resemblance R using the estimator formula.
5 Experimental Results on Webspam Dataset
On the webspam dataset, b-bit minwise hashing preserved SVM and logistic-regression accuracy while substantially reducing training, testing, and data-loading costs. Results were generally stable across repetitions, with strongest trade-offs around b=8 and k≥150.
- Experimental setup: 20% of webspam samples were held out for testing, with 80% used for training; the dataset contains n=350000 and D=16609143.Experiments used the public webspam dataset and followed prior experimental settings.
- Linear SVM accuracy: With b≥8 and k≥150, b-bit hashing achieved about the same linear-SVM test accuracy as the original data.Accuracy was averaged over 50 repetitions, and standard deviations were especially small for b≥4.
- Linear SVM efficiency: Linear-SVM training took about 3–7 seconds with hashing near C=1 versus about 100 seconds on the original data.Loading time also fell from about 12 minutes for the original data to about 10 seconds for hashed data.
- Linear SVM efficiency: Linear-SVM testing took about 1–2 seconds with hashing versus about 100–200 seconds using the original data.The reported testing time includes both data loading and computation.
- Logistic regression accuracy: For logistic regression, b-bit hashing achieved the same test accuracies as the original data with k≥150 or even k≥100 and b≥8.Repeated experiments also indicated stable predictions.
- Efficiency trade-offs: Using b=16 can substantially increase training time relative to b≤8, while combining b-bit hashing with VW can further reduce training time, especially for large b.This trade-off reflects the interaction between storage precision and the sparsity of the expanded vectors.
6 Random Projections and Vowpal Wabbit (VW)
This section analyzes random projections and VW for estimating inner products, showing that bias correction requires the two-point ±1 distribution and yields variance matching random projections.
- Random Projections: Random projections multiply data vectors by a random matrix to produce lower-dimensional vectors for inner-product estimation.The matrix entries are sampled independently from a distribution parameterized by s.
- Random Projections: s = 1 achieves the smallest variance, and the equal-probability distribution on {−1, 1} is the elementary distribution satisfying this choice.The paper identifies this distribution as the relevant two-point construction.
- Vowpal Wabbit: The original Count-Min sketch is severely biased for inner-product estimation, although that bias may be less problematic for sparse recovery and heavy-hitter detection.Its count-min correction step does not remove the bias and complicates variance analysis.
- Vowpal Wabbit: VW corrects Count-Min bias by element-wise multiplying data with random ±1 values before hashing.The paper analyzes a more general family using random variables with mean zero and variance s.
- Variance Comparison: For s > 1, an additional variance term remains even as k →∞; with s = 1, VW has the same variance as random projections.Thus the equal-probability ±1 distribution is effectively required for unbiased estimation with this pre-multiplication scheme.
7 Comparing b-Bit Minwise Hashing with VW
The experiments compare b-bit minwise hashing with VW across regularization settings and show that b-bit hashing is more accurate and faster at comparable storage or accuracy targets.
- Empirical Comparison: 8-bit minwise hashing with k = 200 achieves about the same test accuracy as VW with k = 10^6.The comparison uses the same webspam dataset and stores only VW’s hashed nonzeros.
- Empirical Comparison: At the same sample size k, b-bit minwise hashing is substantially more accurate and requires significantly less training time to reach the same accuracy as VW.The paper attributes this pattern to b-bit hashing’s usually smaller variance.
- Storage Comparison: At equal storage, b-bit hashing usually improves VW by 10- to 100-fold when each VW sample uses 32 bits.If VW uses 16 bits per sample, the reported improvement is 5- to 50-fold.
- Sparsity and Scope: When k ≪ c, VW’s hashed vectors become dense, where c is the number of nonzeros in the original vector.This limits VW’s sparsity advantage in the data-reduction regime emphasized by the paper.
- Sparsity and Scope: VW remains useful when c ≪ k because its sparsity-preserving property supports compact indexing with very large k.The paper distinguishes this indexing regime from data reduction.
8 Combining b-Bit Minwise Hashing with VW
The paper adds VW hashing after b-bit expansion to estimate inner products more quickly, with the clearest speed benefit for larger b and sufficiently large VW sample size m.
- Combined Method: After b-bit hashing expands each point into a sparse binary vector of length 2bk with exactly k ones, VW can hash that vector at runtime.The resulting representation uses nbk stored bits, while the expanded vectors are processed transiently.
- Combined Method: The combined estimator applies VW hashing with size m to the b-bit binary vector before estimating resemblance, introducing additional randomness.Its theoretical variance is analyzed using conditional expectation and conditional variance.
- Parameter Choice: The analysis recommends m ≫ k but m ≪ 2^bk to reduce added variance without making the VW step unnecessary.For b = 16, the paper identifies m = 2^8k as a possible trade-off.
- Empirical Results: For b = 16 and m = 2^8k, VW on top of b-bit hashing achieves the same test accuracies as direct b-bit hashing while considerably reducing training time near C ≈ 1.Figure 9 reports this pattern for k = 200 and b = 16.
- Empirical Results: With b = 8, choosing m = 2^8k reaches similar accuracies but does not improve training speed without hurting accuracy.The paper relates this result to the variance analysis in Lemma 2.
9 Practical Considerations
The paper argues that b-bit minwise hashing is practical for large-scale learning because preprocessing is generally offline and parallelizable, while acknowledging cases where preprocessing time matters and VW may be preferable.
- Practical benefits: Preprocessing typically requires one scan of the data and is suitable for offline or trivially parallel execution.Hashed data can then be reused for supervised learning, clustering, duplicate detection, and near-neighbor search.
- Practical benefits: Hashed datasets can reduce memory consumption enough to store more examples in memory and avoid or minimize disk I/O.This can be useful when repeated cross-validation or parameter tuning reuses the same dataset.
- Limitations: Preprocessing can become a concern when an unprocessed document requires an immediate learning response.Generating n-grams also takes time, and disk I/O during the session may mask the hashing preprocessing cost.
- Limitations: VW may be preferable when preprocessing time matters more than storage cost or test accuracy.The paper states that VW preprocessing can be substantially faster.
10 Conclusion
The conclusion places the method in the context of growing datasets that exceed single-server resources, presents b-bit minwise hashing as a compact learning representation, and reports substantial accuracy advantages over VW and random projections for binary data.
- Conclusion: Growing datasets increasingly exceed the memory and computational resources of a single server, while scaling out or partitioning can be expensive.This motivates compact representations for large-scale learning.
- Conclusion: The paper proposes a compact representation of sparse binary datasets using b-bit minwise hashing.Its estimators are used as positive definite kernels integrated with learning algorithms such as SVM and logistic regression.
- Conclusion: Theoretical analysis reports absolute approximation errors below 0.01, 0.001, and 0.0004 for D = 20, 200, and 500, respectively.The approximation is highly accurate even for small D, although the exact probability can be computed by exhaustive enumeration there.
- Conclusion: The VW algorithm is presented as a bias-corrected Count-Min sketch approach based on hashed data samples.The supplied derivation develops its expectation and variance properties.
C Comparing b-Bit Minwise Hashing with VW Random Projections
The paper compares b-bit minwise hashing with VW and random projections by converting resemblance variance into inner-product variance and normalizing accuracy by storage. Across binary-data settings, b-bit minwise hashing is usually substantially more accurate at the same storage.
- Comparison setup: The comparison evaluates VW and random projections against b-bit minwise hashing for estimating inner products on binary data.The analysis assumes VW is used for data reduction, with k small relative to the numbers of nonzeros.
- Comparison setup: The paper converts b-bit resemblance variance into variance for estimating the inner product before comparing the methods.The estimated inner product is obtained from the estimated resemblance and feature counts.
- Storage comparison: b-bit minwise hashing stores each sample using b bits, whereas VW and random projections are assumed to use 32 bits per sample.The 32-bit assumption is justified by the precision needed for VW samples and inner-product computation.
- Storage comparison: When Gvw > 1, b-bit minwise hashing is more accurate than binary random projections and requires less storage for the same variance.Gvw is defined as a variance ratio comparing the two methods.
- Results: Across b = 8, 4, 2, and 1, the reported ratios are usually 10 to 100, indicating a substantial advantage over random projections.The paper states that b = 4 or even 8 is needed to achieve high learning accuracies.
- Results: Theoretical analysis concludes that b-bit minwise hashing often improves over VW and random projections by 10- to 100-fold for binary data.The comparison is described as essentially independent of D under the large-dimensional binary-data approximation.