Signed Feature Hashing

Signed Feature Hashing

Feature hashing (the hashing trick) reduces the dimensionality of categorical or high-dimensional features by applying a hash function to feature indices. To unbiasedly preserve inner products, signed feature hashing introduces an additional sign hash function.

Experiment

Explore how different sign patterns and hash sizes affect collision errors. See the interactive Signed Feature Hashing module.

1. Change the Vectors input to see how sparsity and correlation affect expected values.
2. Adjust the Hash map to scramble the feature indices and see different collisions.
3. Modify the Signs pattern or the number of Buckets.
4. Observe the Signed collision error and the changes in the visual mapping diagram.

Worked Example

Let vectors be x = [1, 0, 2, 0, 0, -1] and y = [0, 1, 2, 0, -1, 1]. Using a hash map to 3 buckets h(i) = i mod 3 and alternating signs s = [1, -1, 1, -1, 1, -1]:

1. Set Vectors to Sparse.
2. Set Hash map to Index.
3. Set Signs to Alternating.
4. Set Buckets to 3.
5. Observe that the Hashed inner product is exactly 3.

True Inner Product = 1*0 + 0*1 + 2*2 + 0*0 + 0*(-1) + (-1)*1 = 3
Hashed x = [1(1) + 0(-1), 0(-1) + 0(1), 2(1) + (-1)(-1)] = [1, 0, 3]
Hashed y = [0(1) + 0(-1), 1(-1) + (-1)(1), 2(1) + 1(-1)] = [0, -2, 1]
Hashed Inner Product = 1*0 + 0*(-2) + 3*1 = 3

Limitations

While inner products are preserved in expectation, individual hashes can still suffer from large collision errors if the number of buckets is too small or if features have highly correlated hash and sign assignments.

References

The primary reference detailing this methodology and its analytical properties is:

• Weinberger, K. Q., Dasgupta, A., Langford, J., Smola, A., & Attenberg, J. (2009). Feature Hashing for Large Scale Multitask Learning. ICML.