LSHForest performance

[erikbern]

I've been running some benchmarks of approximate nearest neighbor packages and LSHForest seems to perform very bad. See https://github.com/erikbern/ann-benchmarks

Compared to raw bruteforce it's not much faster but precision is less than 10% (whereas bruteforce is of course 100%)

There might be something wrong with my benchmark code but there might also be something weird going on with LSHForest.

[jnothman]

Yes, LSHForest is somewhat an under-performer and we probably merged it prematurely. More of it will need to be implemented in Cython, and even then I'm not sure where we'll find big improvements as long as we continue to use binary searches over arrays.

Also, I've got pretty good colour distinction ability, but you've got too many similar colours in there! Perhaps vary the markers or line styles too.

[erikbern]

Great. Good point about the colors, will update!

[amueller]

how does the ball tree compare to the rest?

[amueller]

Also, should we maybe deprecate and remove it? @ogrisel are you planning to work on it in the near future?

[jnothman]

Sorry, i had plans to work on its efficiency, but things have exploded on
my end.

On 13 July 2015 at 05:41, Andreas Mueller notifications@github.com wrote:

Also, should we maybe deprecate and remove it? @ogrisel
https://github.com/ogrisel are you planning to work on it in the near
future?

—
Reply to this email directly or view it on GitHub
#4917 (comment)
.

[ogrisel]

I have an intern that should join our team this summer and we might work on profiling this to understand what's going wrong.

[jnothman]

Btw, your code appears to be assuming that the default metric is euclidean. Currently LSHForest only supports cosine, so preprocessing by norming each vector isn't helpful!

[jnothman]

@maheshakya @daniel-vainsencher do you have any insight into why precision is so poor or what we could do about it? While we're trying (perhaps succeeding) to improve efficiency in #5099, the inability to obtain reasonable precision is a bit of a deal breaker. (Perhaps @amueller's right that this just hasn't been a success and we should cancel the project and instead ensure support / present examples of using external ANN packages in other scikit-learn algorithms.)

Obviously the fixed number of bits represented could be an issue. But the benchmark is over data with only 100 features, so 32 hyperplanes shouldn't be so bad, should it?

As I've said before, I suspect there are also problems with our definition of n_candidates, and a parameter like target_precision would be more helpful to the user. While the latter may make the system hard to control, I'm doubt it's responsible for the overall poor performance.

[maheshakya]

One major problem could be the generation of random hyper planes. At the moment, what we do is just call GaussianRandomProjection to generate hyper planes without considering anything about the data density and some of the hyper planes can be entirely useless. Maybe we should use some method to get hyperplanes where they could reside around the actual data points.

[jnothman]

Given that LSH has so frequently built on random hyperplanes (and it allows
your model to be unaffected by changes in the space over time), it seems
strange that the competing approaches should get their gain from non-random
hyperplanes.

On 13 September 2015 at 16:03, Maheshakya Wijewardena <
notifications@github.com> wrote:

One major problem could be the generation of random hyper planes. At the
moment, what we do is just call GaussianRandomProjection to generate
hyper plane without considering anything about the data density and some of
the hyper planes can be entirely useless. Maybe we should use some method
to get hyperplanes where they could reside around the actual data points.

—
Reply to this email directly or view it on GitHub
#4917 (comment)
.

[maheshakya]

But it could have an impact on the precision, all the searches the algorithm does can be useless if majority of data points are at the same side of the hyper planes, and there's a high probability that some of the neighbors it produces could be just random points.

[amueller]

somewhat OT: I didn't mean to imply this can't be made to work. My concern was only that we promise something to the user and don't deliver. And we should either deliver, which might mean a significant amount of work [that I can't commit] or remove the promise. If someone has the time and expertise to improve performance, great. I only followed what happened superficially but it seems to be tricky.

[maheshakya]

Was there any particular reason that we avoided vectorizing searchsorted in the binary search happening in _find_matching_indices function? It can be vectorized across queries AFAIK.

[daniel-vainsencher]

Sorry, I am missing some context. This is an approximate neatest
neighbour search datastructure, so presumably some level of error is
implied. Is there a particular benchmark (in high dimension) where we are
not on the pareto curve between precision and speed?
On Sep 12, 2015 7:19 PM, "Joel Nothman" notifications@github.com wrote:

@maheshakya https://github.com/maheshakya @daniel-vainsencher
https://github.com/daniel-vainsencher do you have any insight into why
precision is so poor or what we could do about it? While we're trying
(perhaps succeeding) to improve efficiency in #5099
#5099, the inability
to obtain reasonable precision is a bit of a deal breaker. (Perhaps
@amueller https://github.com/amueller's right that this just hasn't
been a success and we should cancel the project and instead ensure support
/ present examples of using external ANN packages in other scikit-learn
algorithms.)

Obviously the fixed number of bits represented could be an issue. But the
benchmark is over data with only 100 features, so 32 hyperplanes shouldn't
be so bad, should it?

As I've said before, I suspect there are also problems with our definition
of n_candidates, and a parameter like target_precision would be more
helpful to the user. While the latter may make the system hard to control,
I'm not sure it's responsible for the overall poor performance.

—
Reply to this email directly or view it on GitHub
#4917 (comment)
.

[daniel-vainsencher]

Sorry, now I see the benchmark. At gsoc time, I seem to recall Lshforest
was competitive with annoy at dimensions 500-1000: I considered that a
significant success. But the current benchmarks are around 100, where doing
fewer comparisons helps less.

Is the implementation tested competitive with the end of GSoC one? Have you
tuned the number of candidates and number of indices?

Also, I have offered an easy way to reduce the binary searches to one per
tree on the mailing list (just grab as many candidates as you need from
either side of the full length search). Have you tried it?

I proposed the algorithm for GSoC because it is a good fit for
implementation in python over arrays; binary search is actually a good
primitive here. Do you see specific significant costs that cython would
save? One candidate for cython is between choosing candidates using the
trees and calculating full distances to choose the top few by hamming
distance to the query.

If you are going to refuse anything that isn't in the lshforest paper, I
can't really help. Please keep in mind that algorithms published in
theoretical areas often abbreviate away some "merely practical" details.

Sorry I can't contribute coding time.
On Sep 14, 2015 8:25 AM, "Daniel Vainsencher" daniel.vainsencher@gmail.com
wrote:

Sorry, I am missing some context. This is an approximate neatest
neighbour search datastructure, so presumably some level of error is
implied. Is there a particular benchmark (in high dimension) where we are
not on the pareto curve between precision and speed?
On Sep 12, 2015 7:19 PM, "Joel Nothman" notifications@github.com wrote:

@maheshakya https://github.com/maheshakya @daniel-vainsencher
https://github.com/daniel-vainsencher do you have any insight into why
precision is so poor or what we could do about it? While we're trying
(perhaps succeeding) to improve efficiency in #5099
#5099, the inability
to obtain reasonable precision is a bit of a deal breaker. (Perhaps
@amueller https://github.com/amueller's right that this just hasn't
been a success and we should cancel the project and instead ensure support
/ present examples of using external ANN packages in other scikit-learn
algorithms.)

Obviously the fixed number of bits represented could be an issue. But the
benchmark is over data with only 100 features, so 32 hyperplanes shouldn't
be so bad, should it?

As I've said before, I suspect there are also problems with our
definition of n_candidates, and a parameter like target_precision would
be more helpful to the user. While the latter may make the system hard to
control, I'm not sure it's responsible for the overall poor performance.

—
Reply to this email directly or view it on GitHub
#4917 (comment)
.