2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ I'm not entirely sure how there is a difference regarding your point with the numbers? $\endgroup$
    – CutePoison
    Mar 16, 2023 at 7:20
  • 1
    $\begingroup$ You said "half of the time we have 'grouped' two id's", but in a uniform setting every index will have two id's. It won't actually be uniform, so some id's won't be paired, but lots will, and some will be tripled/quadrupled/etc. $\endgroup$
    – Ben Reiniger
    Mar 16, 2023 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.