We've got two different concepts here:

• a hashed feature matrix as counts
• a hashed feature matrix as a compression of the input space

As counts, negative values don't make much sense. In the HashingVectorizer context. And you're right, I think there should be an option that disables the "hash collision resolution mechanism" as you say. I'd be happy to see that as a further option for non_negative, and perhaps that the current non_negative=True behaviour be deprecated. In the context of n-gram features, collisions are equivalent to creating new polysemy.

As a matrix compression, feature hashing is effectively an extreme form of sparse random projections. In this model, one gets theoretical guarantees about approximate equivalence of euclidean distance in the input and reduced spaces. The features are also centred on 0. Given that there is theoretical basis for this model, I don't think non_negative=True as a default is necessarily appropriate, although I appreciate that this model may be less pertinent with text than when hashing non-text features.

Note (@amueller) that an L2-norm on this reduced space means that vector products in the hashed space approximate cosine distance in the input space...

TLDR:

• +1 for having a non_negative='total'
• -1/2 for changing the non_negative=False default

Also, Caveat: I've not read Weinberger et al.

Very Interesting, thanks for pointing out the link with sparse random projection! I have only skimmed through Weinberger et al. (and I didn't understand all the practical implications), but I also had the impression that preserving the properties of the inner product was a major point.

The thing is though, that for a CountVectorizer applying the L2 norm makes the dot product calculate the cosine similarity. The same is true when hashing the keys, using the HashingVectorizer assuming that the n_features is large and there is little or no collisions. I would assume that this property of preserving inner product would becomes relevant only once there is a significant number of collisions (as otherwise that is approximately true anyway).

The default options for HashingVectorizer is Bag of Words with n_features=1048576 which certainly would produce almost no collisions. It does not make sense to also make default an option that would only be useful in the high collision cases. The whole spirit of the documentation is currently "get a hashing table big enough to avoid collisions" and I think that would be certainly the way it is mostly used.

The case of matrix compression is interesting, and I believe should be explicitly mentioned in the documentation of the HashingVectorizer, but IMO this should be something that users activate because they know what they are doing, not there by default. Currently HashingVectorizer is presented in the docs as just a CountVectorizer replacement for large document collections without the inverse transform, while more things are actually happening by default without the user being aware of it.

I'll try to run a few benchmarks on this as soon as I find some time.

(Yes, I meant that the inner product is cosine sim, not that it preserves cosine distance.)

Your argument is fair, and in reality there are many ways we can spin this. But changing a default value is a tricky deprecation and just not worth it where the case is not definitive or users are being frequently misled.

Will you offer a PR to extend / fix the behaviour of non_negative?

OK, I finally looked a bit more into this, here is the classification accuracy and the relative error between the inner product in the hashed space vs the one before hashing, as a function of the hashing table size, for 3 cases,

• non_negative=False: with the "alternating sign" / collision compensation mechanism
• non_negative=True: same as above + absolute value of the result
• non_negative="total": disabling this collision compensation mechanism
  
  the observations are the following,
• all this does not seem to matter for the text classification accuracy (here using Logistic Regression on the 2/20 newsgoups dataset), or if anything it can occasionally make it slightly worse
• the "alternating sign" mechanism does indeed allow to preserve the inner product much better, however,
  • this only matters for small hashing table sizes: n_features < 1000 with BOW, n_features < 10000 for 4-char ngrams, etc.
  • The inner product conservation still is mostly true even if we apply some other post normalization (e.g. L2 norm to compute the cosine similarity or TFIDF weights)
  • for binary counts, this algorithm has almost no impact
• Setting non_negative=True make the inner product conservation much worse
• The region where this "alternating sign" mechanism becomes relevant, is also the region where the classification accuracy drops (i.e. need bigger hashing table).

Full results are available here, run using the code from the PR #7565.

Thanks for this, and fair enough. The inner product preservation only seems
relevant to me in the case where features are not all positives, i.e. not
relevant for text.

I've looked at #909 where this was introduced. Apart from the case of
binary data, where it might be beneficial to preserve binarity (although
this can be done another way), I agree that it's better to avoid this sign
alternation when non-negativity is sought. I'd be happy to hear if
@larsmans disagrees.

Let's be bold and deprecate the current non_negative=True semantics. So:
add a option non_negative='total' then say that this will become the
meaning of non_negative=True in two versions' time, whenever a user
specifies non_negative=True. If someone objects upon seeing this warning,
hopefully we'll hear about it and can backtrack on this decision.

On 8 October 2016 at 05:11, Roman Yurchak notifications@github.com wrote:

OK, I finally looked a bit more into this, here is the classification
accuracy and the relative error between the inner product in the hashed
space vs the one before hashing, as a function of the hashing table size,
for 3 cases,

• non_negative=False: with the "alternating sign" / collision
  compensation mechanism
• non_negative=True: same as above + absolute value of the result
• non_negative="total": disabling this hash compensation mechanism [image:
  index]
  https://cloud.githubusercontent.com/assets/630936/19200076/5ec7bcfe-8cc7-11e6-8b45-acf7768a665b.png
  the observations are the following,
• all this does not seem to matter for the text classification
  accuracy (here using 2/20 newsgoups dataset), or if anything it can
  occasionally make it slightly worse
• the "alternating sign" mechanism does indeed allow to conserve the
  inner product much better, however,
  • this only matters for small hashing table sizes: n_features < 1000
    with BOW, n_features < 10000 for 4-char ngrams, etc.
  • The inner product conservation still is mostly true even if we
    apply some other post normalization (e.g. L2 norm to compute the cosine
    similarity or TFIDF weights)
  • for binary counts, this algorithm has almost no impact
• Setting non_negative=True make the inner product conservation much
  worse
• The region where this "alternating sign" mechanism becomes relevant,
  is also the region where the classification accuracy drops (i.e. need
  bigger hashing table).

Full results are available here
https://github.com/rth/notebooks/blob/master/sklearn/HashingVectorizer_collisions.ipynb
run using the code from the PR #7565
#7565.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#7513 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAEz6yRvaIP3BCcnMdz63NvG3uuEpqNjks5qxos7gaJpZM4KJAmN
.