Feature Hashing for Large Scale Multitask Learning

Kilian Weinberger; Anirban Dasgupta; Josh Attenberg; John Langford; Alex Smola

Source-linked AI summary

Feature Hashing for Large Scale Multitask Learning

Kilian Weinberger, Anirban Dasgupta, Josh Attenberg, John Langford, Alex Smola

arXiv:0902.2206v5Feb 12, 2009cs.AI

TL;DR

Large-scale learning can make high-dimensional representations and multitask parameter storage infeasible. The paper develops unbiased feature hashing with exponential concentration guarantees and analyzes interference between task-specific hashed subspaces, then demonstrates the approach on collaborative spam filtering with hundreds of thousands of tasks.

Problem
High-dimensional inputs and many task-specific predictors can exceed feasible memory limits in large-scale multitask learning.
Method
The paper uses signed, unbiased feature hashing and different hash functions for tasks mapped into one joint lower-dimensional space.
Results
The empirical results show strong spam-classification performance with very many tasks and features mapped into a joint lower-dimensional hash space.
Takeaways & Limitations
Feature hashing makes large-scale multitask learning feasible with finite memory guarantees and little interference between task subspaces.
Takeaways & Limitations
The concentration guarantees depend crucially on the maximum coordinate magnitude, and absolute classification error rates are not reported.

Abstract

from arXiv · show

Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case -- multitask learning with hundreds of thousands of tasks.

1. Introduction

The paper addresses memory and dimensionality challenges in high-dimensional learning by using feature hashing to compress representations while preserving useful structure. It develops theoretical guarantees and demonstrates multitask collaborative spam filtering with many users.

Large training sets and high-dimensional inputs can make storing kernel matrices infeasible even when the original space is nearly linearly separable.The problem arises when handcrafted nonlinear features already provide separability but memory limits prevent kernel-matrix storage.
The hashing-trick maps high-dimensional inputs into Rm, where m ≪ n and m ≪ d, while preserving sparsity without storing projection matrices.Classifier parameters therefore live in a compressed feature space rather than the original or kernel-induced space.
Different hash functions can map task-specific feature spaces into one joint space with little interference, enabling compressed multitask learning.The paper applies this idea to collaborative email spam filtering with hundreds of thousands of users.
Collaborative spam filtering gives each user a personalized classifier while sharing labels across a very large task set.The feature space spans the union of vocabularies across users.
The paper introduces unbiased hash kernels and exponential tail bounds for their distortion.These results are intended to explain strong empirical performance of hashed feature representations.

2. Hash Functions

The paper modifies hash kernels by adding signed feature contributions, yielding an unbiased estimate of inner products. It defines hash functions over feature indices and extends the mapping to task-instance pairs.

The signed hash-kernel variant replaces the original unsigned sum with a signed sum of hashed features.The modification produces an unbiased estimate used in the subsequent analysis.
Definition 1 uses h:N→{1,...,m} to assign features to hash bins and ξ:N→{±1} to assign signs.The hashed feature map and corresponding inner product are defined from these two hash functions.
Finite-length strings can be handled by representing each string with a unique natural number.Thus the natural-number definition also covers practical string-valued features.
Two hash maps differ when either their binning function h or sign function ξ differs.The binary sign hash removes the bias inherent in the earlier unsigned hash kernel.
For multitask data, the map is extended to task-instance pairs through φu(x)=φ(x,u).Each task can therefore use its task-specific hashed representation.

3. Analysis

The analysis establishes unbiased hashing, concentration and tail bounds, and weak interaction between independently hashed task subspaces. It also identifies how feature magnitudes affect distortion and supports large-scale multitask learning.

3. Analysis: The hash kernel is unbiased, and its typical deviation from the target inner product concentrates near O(1/m).Chebyshev’s inequality and Talagrand-based arguments are used to obtain exponential tail bounds.
3.1. Concentration of Measure Bounds: Hashed feature maps preserve vector lengths with high probability under suitable dimensionality and maximum-coordinate conditions.Theorem 3 assumes ∥x∥2=1, ∥x∥∞≤ε, and m≥72 log(1/δ)/ε^2.
3.1. Concentration of Measure Bounds: For collections of vectors, the number of observations enters the concentration analysis only logarithmically.The maximal-distortion result applies across all pairwise distances under an infinity-norm condition.
3.2. Multiple Hashing: Large coordinate magnitudes can make a single hash collision produce significant distortion.The paper mitigates this by trading sparsity for variance through repeated hashing of large-magnitude components.
3.3. Approximate Orthogonality: Theorem 7 bounds the influence of parameter vectors from unrelated tasks on an instance in another task.This approximate orthogonality supports the use of many task-specific hash functions in one shared space.

4. Applications

Feature hashing compresses large parameter spaces while preserving sparsity, and independently hashed task subspaces can share one compact representation with little interference. The paper applies this framework to personalization, multiclass classification, and collaborative filtering.

Feature hashing: Feature hashing reduces parameter storage from O(d) to O(m) while preserving sparsity and avoiding projection-matrix multiplications.The hashed classifier can be learned directly in the compressed space.
Personalization: Theorem 7 supports hashing multiple task classifiers into one feature space with little interaction.Each task can use a different hash function while sharing the joint representation.
Personalization: Personalized spam filtering combines a global predictor with user-specific predictors, avoiding O(d × (|U| + 1)) storage for all classifiers.This setting addresses hundreds of thousands of users and vocabularies of millions of tokens.
Personalization: Predictions use the hashed global and user-specific feature maps, with distortion and interference from collisions as the two hashing errors.The paper bounds interference by applying its multitask result to the other users’ hashed weight vectors.
Massively multiclass estimation: Massively multiclass classification is treated as multitask learning by assigning a different hash function to each class.The same framework extends beyond user personalization.
Collaborative filtering: Hashing compresses collaborative-filtering factor matrices so their elements can be approximated and the resulting matrix representation stored efficiently.Independent hash functions compress U and W before approximating Mij = [U^⊤W]ij.

5. Results

The experiments evaluate hashed personalization on 3.2 million emails from 433,167 users, using relative uncaught-spam rates against a global hashed baseline. Personalization improves spam filtering despite aggressive compression, including for users with little or no training data.

Experimental setup: 3.2 million emails from 433,167 users and 40 million unique words form the proprietary spam-classification dataset.The first 10 of 14 collection days were used for training and the remaining 4 for testing.
Experimental setup: 1% not-spam misclassification is fixed when setting the test-time classification threshold.Results report uncaught spam relative to the baseline rather than absolute error rates.
Average results: 2^22 hash keys yield a 30% spam reduction for personalized classification despite a feature space otherwise containing 16 trillion possible personalized features.The global-hashed classifier converges early, indicating negligible collision impact at that point.
User clustering: Up to 65% spam reduction occurs for users with larger training buckets, while users with no training contribution obtain almost 20% reduction.Users are grouped into exponentially growing buckets by training-email count.
User clustering: Users with none or very little training data benefit because local classifiers absorb individual labeling preferences while the global classifier represents the common spam definition.The global component consequently obtains better generalization properties across users.

6. Related Work

Related work covers random-feature approximations, sparse representations, random projections, sketches, and prior hash kernels. The paper positions feature hashing as a sparse, computationally efficient compression method with new theoretical and multitask-learning results.

Random features and projections: Random-feature methods approximate kernel inner products efficiently, but their representations are dense.This contrasts with the sparsity-preserving hashing approach.
Sparse representations: Sparse-feature reduction methods decrease nonzero terms but do not resolve the remaining high dimensionality of the feature representation.The cited approach therefore requires a dual representation when the weight vector is not compact.
Random features and projections: Random-projection methods reduce dimensionality through matrix-vector multiplication, whereas sparse code matrices lower computational cost.The paper notes that some of its bounds can be derived from prior random-projection results.
Sketches: CountMin sketch stores counts in replicated hash tables and provides concentration inequalities for range and point queries.It is presented as a related hashing construction rather than the paper’s feature map.
Hash kernels: Prior hash kernels compress high-dimensional vectors by summing coordinates with the same hash value, requiring work proportional to the number of nonzero terms.The paper extends this computationally efficient line with exponential tail bounds and multitask applications.

7. Conclusion

The paper analyzes the hashing-trick theoretically and empirically, deriving exponential tail bounds and showing that random hashed subspaces are likely not to interact. Experiments validate the approach for multitask spam filtering with many tasks and features in a lower-dimensional joint space.

The paper combines theoretical and empirical analysis of the hashing-trick for dimensionality reduction.
Random subspaces of the hashed space are likely not to interact, enabling multitask learning with many tasks.
Empirical results validate the approach on real-world spam filtering.
A joint lower-dimensional hash-space supports classification with a very large number of tasks and features under a finite memory guarantee.

A. Mean and Variance

The proof computes the expectation and variance of hashed inner products by expanding the relevant expressions and using the signed-hash variables’ moment structure. The resulting expansion separates the variance into two terms.

The expectation of the hashed inner product is computed by expanding the expression and observing that only terms with i = j have nonzero value.
The variance is obtained by expanding the squared hashed inner product and computing its expectation.
The signed-hash variables satisfy a fourth-moment identity involving Kronecker deltas.
Passing the expectation through the sum breaks the variance expansion into two terms.

B. Concentration of Measure

The concentration analysis combines a Johnson–Lindenstrauss-style result with a weighted balls-and-bins bound to control hashed-vector norms. Applying these bounds yields a high-probability norm-preservation statement.

The analysis uses a Johnson–Lindenstrauss concentration result with m = c log(1/δ)/ε^2 for sufficiently large c.
A weighted balls-and-bins inequality controls the hash-bucket quantities used in the concentration argument.
The proof represents hashing through a bucket matrix A and a random sign diagonal matrix Ds, with ∥x∥φ = ∥ADsx∥2.
The resulting bound states that Pr[|∥ADsx∥2 − 1| ≥ ε] ≤ δ.
The proof combines the error probabilities from the component lemmas to obtain the final result.

C. Inner Product

The inner-product argument applies a standard inner-product inequality to hashed representations and combines multiple bounds using a union bound. With probability 1 − 3δ, the relevant terms are simultaneously bounded.

The argument uses the standard inner-product inequality for the hashed representation.
A union bound combines the three error events in the analysis.
With probability 1 − 3δ, each of the relevant terms is bounded using Theorem 3.

D. Refutation of the Previous Incorrect Proof

The paper identifies fatal and minor errors in the previous proof of Theorem 3, showing that its main theorem is false and cannot be repaired as stated. The contradiction arises because the claimed hashing guarantee would violate Alon’s lower bound on embedding dimensionality.

The main theorem of Weinberger et al. (2009) is false because its claimed error probability contradicts Alon’s lower bound.The error could be made arbitrarily small without increasing the embedding dimension by decreasing η through preprocessing.
With m = 128 and δ = 1/2, the claimed corollary would preserve pairwise distances for n + 1 simplex vertices within a 1 ± 1/4 multiplicative factor.The construction uses a replication-based preconditioner and applies the disputed corollary to the transformed vertices.
Such a transformation requires Ω(log n) dimensions by Alon’s lower bound, contradicting the claimed fixed target dimension m = 128.The contradiction shows that the theorem’s missing dependence on n is essential.
The proof of Theorem 3 contains a fatal error in an observation involving hash functions h and h′.The paper states that the observation is false and that its consequences cannot be rectified even if the claim had the right form.
A second proof error is locally fixable, but the resulting modified claim remains false and still contradicts Alon’s lower bound.The corrected estimate changes the claim without restoring the necessary Ω(log n) dependence in the target dimensionality.