Feature Hashing for Unbounded Streams

A click stream's feature space has no size. A new advertiser ID appears, then a user-agent string nobody has seen, then a query bigram that was coined this morning. Batch pipelines handle this with a vocabulary pass: scan the data, assign each feature an index, store the dictionary. A stream offers no second pass, no end, and no moment at which the vocabulary is final. Half the unique features in a large production click model occur exactly once (McMahan et al., 2013, Ad Click Prediction: a View from the Trenches, KDD).

Signed hashing

The hashing trick replaces the dictionary with a hash function into \(m\) buckets, usually \(m = 2^b\). For a hash \(h\) and a sign hash \(\xi\) taking values in \(\{-1, +1\}\):

The signs matter more than they look. Without them, two colliding features always reinforce each other and the hashed inner product is a biased estimate of the true one. With independent signs, collisions cancel in expectation, so the hashed inner product is unbiased and collisions contribute variance rather than bias. Weinberger and colleagues derive exponential tail bounds on that variance and show the interference between random subspaces is negligible with high probability, modifying the earlier unsigned hash kernel specifically to get the sign (Weinberger, Dasgupta, Attenberg, Langford and Smola, 2009, Feature Hashing for Large Scale Multitask Learning, ICML, arXiv:0902.2206).

For streaming systems the operational consequence is larger than the statistical one. The weight vector has a fixed size chosen before the first example. There is no dictionary to grow, no dictionary to ship from trainer to server, no index to synchronise between them, and no branch for an unseen category. Both sides hash the raw string and arrive at the same bucket.

How often features actually collide

Collisions are not rare, and the arithmetic is worth doing once. With \(m = 2^{18} = 262{,}144\) buckets and \(n = 50{,}000\) features active in a window, the expected number of colliding pairs is

and the chance that a given feature shares its bucket with at least one other is \(1 - (1 - 1/m)^{n-1} \approx 1 - e^{-0.19} \approx 17\%\). So roughly one feature in six is contaminated, which sounds fatal and is not, because the damage is wildly unequal. A rare feature colliding with a heavy one gets a weight dominated by its neighbour's gradient and is effectively destroyed. The reverse barely registers: the heavy feature's weight moves by whatever a handful of rare examples contribute. Hashing degrades the tail first, and the tail is where the single-occurrence features live anyway.

The alternative: keep a dictionary, admit fewer features

If the problem is that rare features consume memory, deleting them is the direct solution. Google's CTR system admits a feature to the model only once it has been seen enough: Bloom-filter inclusion with a count threshold of 2 saved 66 percent of RAM for a 0.008 percent AucLoss increase, and Poisson inclusion at \(p = 0.03\) saved 60 percent for 0.020 percent (McMahan et al., 2013). That paper also lists aggressive feature hashing among the directions that did not pay off for them, which is a useful corrective to the trick's reputation: at the scale where you have the engineering to maintain a dictionary, keeping one and being selective about what enters it measured better than discarding the identity of everything.

Hashing earns its place where the dictionary itself is the problem: many small models, a model that must run in fixed memory on a device, or a trainer and server that cannot share state.

When it breaks

There is no inverse. Given bucket 148,302 you cannot recover what hashed into it. Feature importance, debugging a single bad prediction, auditing which inputs a decision used, and complying with a request to explain one all become hard or impossible. Keeping a side dictionary for inspection reintroduces exactly the structure hashing removed.

Regularisation now applies to buckets. L1 sparsity, per-coordinate adaptive learning rates and feature-level clipping all act on a bucket that may hold several unrelated features. A penalty intended to delete a useless feature deletes its roommates too.

The load factor rises silently. Collision rates depend on how many features are active, and that grows as the stream runs. A model sized correctly at launch degrades gradually, with no error and no alert. The fix is cheap and usually missing: track occupied buckets against \(m\) and treat the ratio as a monitored metric.

The hash function is part of the artefact. Change the hash, the seed, or the string encoding, and every learned weight points at the wrong bucket. A library upgrade that swaps the default hash silently invalidates the model, so the function and seed belong in the model version alongside the weights.