[MRG+1] Locality Sensitive Hashing for approximate nearest neighbor search by maheshakya · Pull Request #3894 · scikit-learn/scikit-learn

maheshakya · 2014-11-27T04:37:32Z

New PR created from #3304

Rewritten _bisect_right with numpy searchsorted. Updated examples.

…t test group.

Replaced numpy searchsorted in _bisect_right with the previous version.

Insert operation allows to insert new data points into the fitted set of trees. (Can be used in incremental learning? ) Changed parameter m to n_neighbors. Changed parameter m to n_neighbors.

For _bisect_right() function, a transformed x is passed. The transformation will replace the characters after h hash length with '1's. Used random_projections module. GuassianRandomProjections in random_projections module is used to perform the hashing for Random projections LSH method.

GuassianRandomProjections in random_projections module is used to perform the hashing for Random projections LSH method.

Removed lshashinng in feature extraction and add that funtionality in the LSHForest class. If other hashing algorithms are to be implemented, a separate lshashing class may be required.

maheshakya · 2014-12-02T05:59:39Z

All right.

To identify the actual error which raises the warning.

maheshakya · 2014-12-16T18:33:57Z

Raising the warning with stacklevel=2 doesn't seem to provide any more information about the warning.

GaelVaroquaux · 2014-12-16T19:04:28Z

Raising the warning with stacklevel=2 doesn't seem to provide any more
information about the warning.

No, that's not what stacklevel does.

jnothman · 2014-12-17T03:23:50Z

It might give you a better indication of which function call results in the warning, though.

maheshakya · 2014-12-17T03:55:10Z

Yes. it's _fast_dot in extmath where numpy version is less than 1.7.2. Failure occurs in the configuration where numpy version = 1.6.2. The dot product is done in the transformation of query to hashed query using GaussianRandomProjectionHash.transform. In this, transformed queries have dtype=uint32. But _fast_dot only allows dtypes of 32 and 64 bit float. This is the reason for this warning. But dtype needs to be uint32 for the algorithm to work. What can we do about this?

maheshakya · 2014-12-17T03:58:14Z

And this is happened before the expected warning in _get_candidates method.

jnothman · 2014-12-17T04:03:18Z

Surely the dot product is happening in the random projection process, not in the transformation to a hash? And even if the LHS of the dot product is integer queries, the RHS should be a gaussian-distributed hyperplane matrix, i.e. float-valued. So this must be a fixed bug in numpy that should cast the input to compatible types before calling BLAS. The correct solution in this case should be to modify assert_warns_message so that its behaviour is like that of assert_warns: it shouldn't care about order.

maheshakya · 2014-12-17T04:11:14Z

Seems like that. I'll fix assert_warns_message.

coveralls · 2014-12-17T08:21:04Z

Coverage increased (+0.04%) when pulling 7802214 on maheshakya:lsh_forest into 15157f9 on scikit-learn:master.

jnothman · 2014-12-17T12:08:54Z

sklearn/utils/testing.py

This should be if not message_found:

maheshakya · 2014-12-18T07:46:17Z

@jnothman shall I change this to [MRG+1]?

jnothman · 2014-12-18T12:27:36Z

Yes!

maheshakya · 2014-12-18T12:39:01Z

Thanks.

larsmans · 2014-12-18T16:20:46Z

benchmarks/bench_plot_approximate_neighbors.py

There's no /tmp on Windows machines, probably.

larsmans · 2014-12-18T16:51:44Z

I'm rebasing this. I figured I could just merge this despite the number of commits, but some of the log messages (e.g. 802ed5f) don't reflect the changes made in the commits.

larsmans · 2014-12-18T18:52:10Z

Squashed to 62 commits and merged as #3980. Fixed the issues that @GaelVaroquaux and I found. Thanks @maheshakya!

maheshakya · 2014-12-19T01:47:31Z

You are welcome @larsmans

jnothman · 2014-12-20T10:12:46Z

Congrats @maheshakya!!

maheshakya · 2014-12-21T07:16:38Z

Thank you @jnothman , I'm really grateful to you for reviewing and suggestions for improvements and for the support.

maheshakya added 30 commits June 21, 2014 13:02

Implemented LSH algorithms: Random projections

757803f

Implemented LSH forest

8c396e7

Fixed typos

7cae820

Rewritten _bisect_right with numpy searchsorted. Updated examples.

Rewritten _bisect_right with numpy searchsorted. Updated examples.

8986078

LSH algorithms are not dafault constructable, therefore added to don'…

096283d

…t test group.

Corrected usage of random_state parameter.

08ab73a

Replaced numpy searchsorted in _bisect_right with the previous version.

Added insert operation into LSH Forest.

c94cb5d

Insert operation allows to insert new data points into the fitted set of trees. (Can be used in incremental learning? ) Changed parameter m to n_neighbors. Changed parameter m to n_neighbors.

Changed parameter m to n_neighbors.

802ed5f

Used random_projections module.

d8e521b

GuassianRandomProjections in random_projections module is used to perform the hashing for Random projections LSH method.

A minor change in lshashing

a9b49bb

Gaussian Random Projection is used in the LSHForest class.

eb4852d

Removed lshashinng in feature extraction and add that funtionality in the LSHForest class. If other hashing algorithms are to be implemented, a separate lshashing class may be required.

Remove Random projection from feature extraction _init

57d9412

Converted to integer representation.

b19ee99

Updated example

a7a5788

Added accuracy tests for c and n_trees variation.

6a0366a

Updated cache size to type int.

dcbe656

Added test_find_matching_indices

89bd389

Added test_kneighbors.

9ca238d

Added distance test

d8cb9b2

Added test_fit.

b611b62

Added test_insert.

45e9152

Modified test_common.py

426d436

Merge branch 'master' into lsh_forest

9f3a575

Updated cached hashes in LSHForest class.

cde73a4

Added cached hash into for loop.

8470bad

Added random point to test_kneighbors.

88fef94

Added radius_neighbors method to LSHForest.

d9c6f36

Added distance test for radius neighbors.

6dacb11

Added test_radius_neighbors.

c9010d4

maheshakya added 2 commits December 16, 2014 18:45

Merge branch 'master' into lsh_forest

e271321

Used stacklevel=2 in fast_dot warning.

751dac0

To identify the actual error which raises the warning.

maheshakya force-pushed the lsh_forest branch from 4583972 to 55e3149 Compare December 17, 2014 08:10

FIX Modified assert_warns_message to ignore order of warnings.

7802214

maheshakya force-pushed the lsh_forest branch from 55e3149 to 7802214 Compare December 17, 2014 08:13

jnothman reviewed Dec 17, 2014
View reviewed changes

sklearn/utils/testing.py Outdated

Copy link
Copy Markdown

Member

jnothman Dec 17, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This should be if not message_found:

Modified assert_warns_message.

1172db9

maheshakya changed the title ~~[MRG] Locality Sensitive Hashing for approximate nearest neighbor search~~ [MRG+1] Locality Sensitive Hashing for approximate nearest neighbor search Dec 18, 2014

larsmans reviewed Dec 18, 2014
View reviewed changes

benchmarks/bench_plot_approximate_neighbors.py

Copy link
Copy Markdown

Member

larsmans Dec 18, 2014

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There's no /tmp on Windows machines, probably.

larsmans mentioned this pull request Dec 18, 2014

LSH forest #3980

Merged

larsmans closed this Dec 18, 2014

maheshakya deleted the lsh_forest branch December 19, 2014 17:01

Uh oh!

Conversation

maheshakya commented Nov 27, 2014

Uh oh!

maheshakya commented Dec 2, 2014

Uh oh!

maheshakya commented Dec 16, 2014

Uh oh!

GaelVaroquaux commented Dec 16, 2014

Uh oh!

jnothman commented Dec 17, 2014

Uh oh!

maheshakya commented Dec 17, 2014

Uh oh!

maheshakya commented Dec 17, 2014

Uh oh!

jnothman commented Dec 17, 2014

Uh oh!

maheshakya commented Dec 17, 2014

Uh oh!

coveralls commented Dec 17, 2014

Uh oh!

jnothman Dec 17, 2014

Choose a reason for hiding this comment

Uh oh!

maheshakya commented Dec 18, 2014

Uh oh!

jnothman commented Dec 18, 2014

Uh oh!

maheshakya commented Dec 18, 2014

Uh oh!

larsmans Dec 18, 2014

Choose a reason for hiding this comment

Uh oh!

larsmans commented Dec 18, 2014

Uh oh!

larsmans commented Dec 18, 2014

Uh oh!

maheshakya commented Dec 19, 2014

Uh oh!

jnothman commented Dec 20, 2014

Uh oh!

maheshakya commented Dec 21, 2014

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants