2
$\begingroup$

I have been reading a lot of papers about nlp which use the hashing trick, and I came across a lot of sentences like : "We take k hashing functions to hash words or bi-grams".

And after that they never mention what functions they use exactly, and without open implementation I can't check on my own.

Is there some convention about hashing function that I'm not aware of (meaning the k-functions should be obvious for the reader), for example is there any canonical hashing function which makes the reference optional ? Or is this a critical design problem which is intendedly (or not) avoided ? Or finally is this a choice without much impact on the result (I think this is unlikely).

$\endgroup$
4
  • $\begingroup$ With good hashing functions, it is relatively easy to obtain many hashing functions. For instance, if $H$ is a hashing function, you can consider $H_{k}(x) = H(H(x)+k)$, or $H_{k}(x) = H^{(k)}(x)$. $\endgroup$
    – Arthur B.
    Commented Nov 10, 2014 at 14:38
  • $\begingroup$ Sure, I agree with that, but in this case it doesn't tell me what the initial one is $\endgroup$
    – Bertrand R
    Commented Nov 10, 2014 at 15:15
  • $\begingroup$ Take your pick. Google's CityHash (code.google.com/p/cityhash) is very fast and though not cryptographically secure probably mixes well enough for your purpose. As long as the hash function is good enough, it doesn't matter which one you pick. $\endgroup$
    – Arthur B.
    Commented Nov 10, 2014 at 15:22
  • $\begingroup$ By experience I realized that the hashing function - as long as it's a "good" one, e.g. murmurhash3 - does not count that much. Of course, the better the hashing function, the fewer collisions. But when you have huge dimensions (e.g. 20,000) then you almost have no collision and a single collision doesn't account for that much in the result... $\endgroup$
    – Vince.Bdn
    Commented Jan 22, 2016 at 21:24

1 Answer 1

1
$\begingroup$

To complete this question I write this answer.

Is there some convention about hashing function that I'm not aware of (meaning the k-functions should be obvious for the reader), for example is there any canonical hashing function which makes the reference optional?

I think what matters when we consider a hash function is how rarely the collisions would appear, then the instantiation of the hash function would be of little use. You can implement one with a certain range(integers) you decide according to the probable size of your vocabulary.

You can refer to the digest package or this repository.

Or is this a critical design problem which is intendedly (or not) avoided ?

The critical design is the idea of the hashing trick itself, not its implementation.

Or finally is this a choice without much impact on the result (I think this is unlikely).

Yes, when you choose a good hash function yourself. Using the hashing trick you don't need to retrain your model when your vocabulary changes because the unknown words(or unknown n-grams) matter.

And you don't need a vocabulary actually when you don't need to reverse the lookup from the hash to the word(or n-gram). You need to reverse the lookup when you do generation.

$\endgroup$

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.