Is the hashing-trick just a random clustering algorithm when used on e.g user-id?

Question

Say I have 1.000.000 user-ids and I choose to use the (signed) hashing-trick with a hash-vector length of 500.000. Wouldn't that effectively just mean that half of the time, we would have two different id's mapped to the same index i.e half of the time we have "grouped" two id's?

Lets take an example with 10 ids and an output-dimension of 5:

from hashlib import md5

def get_index(x, N_features):
    return int(md5(x.encode('utf-8')).hexdigest(), 16) % N_features 

ids = [0,1,2,3,4,5,6,7,8,9]
hashing_dimension = 5 

[get_index(str(uid),hashing_dimension ) for uid in ids]

#[0, 1, 2, 3, 0, 3, 2, 0, 1, 4]

which means that we don't know if the userid is 0, 4 or 7 (they are all mapped to the [1,0,0,0,0] vector).

Doesn't the "hashing trick" just perfom som random grouping on N_dimension/len(ids) part of the ids, and how would that be usefull and not throw away (a lot) of information?

Answer 1

Yes, you can think of hashing as random clustering/grouping.

A minor point on the numbers: with 1M ids and 0.5M hash dimension, you will have an average of two ids assigned to each index (not a collision for half the ids), or 0.5M collisions total.

how would that be usefull and not throw away (a lot) of information?

It is primarily useful computationally, not statistically. With the hash function doing the encoding, you don't need to save anywhere a list of user ids or their mapping to indices, and don't have to look those up when encoding test/production data.

It absolutely is throwing away information, a lot depending on the hash dimension. That said, the loss of information might not be so detrimental. A model built on the purer one-hot encoded data will tend to be overfit due to the high dimensionality. Of course, there are other ways to regularize that than randomly grouping. The wikipedia article lists two publications in which classification performance wasn't necessarily reduced (Ganchev and Dredze 2008) and actually improved (Weinberger et al. 2009) (but I haven't read either).