[WIP] allow nearest neighbors algorithm to be an estimator (v2) #8999

rth · 2017-06-06T11:51:50Z

This PR continues work in PR #3922 and aims to allow the algorithm parameter of NearestNeighbors to be an estimator.

For instance, the prototype could be,

class MyKNNAlgorithm(object):
     def fit(self, X): 
         self._fitted = True
  
     def query(self, X, k, return_distance=True)
         # optional method
         # [some KNN implementation]
         return ind, dist
     
    
     def query_radius(self, X, r, return_distance=True):
         # optional method
         # [some radius KNN implementation]
         return ind, dist

nn = NearestNeighbors(n_neighbors=1, algorithm=MyKNNAlgorithm())

Since DBSCAN, LocallyLinearEmbedding, KNeighborsClassifier, RadiusNeighborsClassifier, Isomap, KNeighborsRegressor rely on nearest neighbors, such custom algorithm backend could also be used there.

A direct application, is that external ANN implementations could be used with scikit-learn methods, by writing a wrapper around their API. The illustration could be done either with a wrapper around brute force nearest neighbors, or some popular ANN library such as annoy.

While the original PR #3922 focused on illustrating the usage of custom backend with LSHForest, it's no longer the case here, since LSHForest would be deprecated (cf discussion in #8996 )

This is still work in progress and several tests fail. I opened this PR to make sure that such approach would be compatible with other work in progress on adding ANN to scikit-learn. If there are some conflicts please let me know, so I can work on something else instead.

@jnothman @lesteve @ogrisel @amueller What do you think?

Provide methods kneighbors and radius_neighbors on BinaryTree classes. Also, ensure array of arrays returned from radius_neighbors.

jnothman · 2017-06-06T12:41:03Z

I've not looked again at code, but I still think this is worthwhile. Not sure that query and query_radius are more appropriate than kneighbors and radius_neighbors. There is an API inconsistency between the more public NearestNeighbors family and the underlying BinaryTree. The former has kneighbors and radius_neighbors, which return (dist, ind), and the latter has query, query_radius returning (ind, dist). Yuck!

https://github.com/erikbern/ann-benchmarks seems to adopt the latter, but I'd be inclined towards the former, maybe even renaming the methods in BinaryTree.

rth · 2017-06-06T13:14:35Z

Not sure that query and query_radius are more appropriate than kneighbors and radius_neighbors. There is an API inconsistency between the more public NearestNeighbors family and the underlying BinaryTree. The former has kneighbors and radius_neighbors, which return (dist, ind), and the latter has query, query_radius returning (ind, dist). Yuck!

Yeah, that's not ideal. The pro and cons of each API choice are below,

BinaryTree like API
- (+) Same API as KDTree, BallTree and scipy.spatial.KDTree
- (+)
  
  https://github.com/erikbern/ann-benchmarks seems to adopt the latter [this one],
- (-) Not an estimator: does not have a fit method and fit happens during init. Which means that it couldn't be used directly as is in this PR. Using a BinaryTree like API with a fit method would create yet a 3rd type of NN API...
NearestNeigbors like API
- (-) NearestNeigbors is the only class that uses it.
- (-/+) If custom algorithm is a NearestNeigbors like object, on some level it feels strange and awkward for NearestNeigbors(algorithm=algorithm) to return a NearestNeigbour wrapper around a NearesNeigbor object. It would have been much simpler to have NearestNeigbors(algorithm=algorithm) return algorithm directly (which would involved adding a __new__ method to NearestNeigbors and would allow to simplify this PR significantly, I think).
- (+) +1 from Joel

Will wait for more feedback and change the API accordingly. Thanks @jnothman !

jnothman · 2017-06-06T13:23:01Z

I don't think NearestNeighbors(algorithm=x) is the application. KNeighborsClassifier(algorithm=x), radius_neighbors_graph(algorithm=x), etc. are. So I do get what you mean about wrapping something with something similar. The problem is actually that KNeighborsClassifier shouldn't be exposing kneighbors and radius_neighbors from an API purist perspective.

…

On 6 June 2017 at 23:14, Roman Yurchak ***@***.***> wrote: Not sure that query and query_radius are more appropriate than kneighbors and radius_neighbors. There is an API inconsistency between the more public NearestNeighbors family and the underlying BinaryTree. The former has kneighbors and radius_neighbors, which return (dist, ind), and the latter has query, query_radius returning (ind, dist). Yuck! Yeah, that's not ideal. The pro and cons of each API choices are below, 1. *BinaryTree* like API - (+) Same API as KDTree, BallTree and scipy.spatial.KDTree - (+) https://github.com/erikbern/ann-benchmarks seems to adopt the latter [this one], - (-) Not an estimator: does not have a fit method and fit happens during init. Which means that it couldn't be used directly as is in this PR. Using a BinaryTree like API with a fit method would create yet a 3rd type of NN API... 2. *NearestNeigbors* like API - (-) *NearestNeigbors* is the only class that uses it. - (-/+) If custom algorithm is a NearestNeigbors like object, on some level it feels strange and awkward for NearestNeigbors(algorithm=algorithm) to return a NearestNeigbour wrapper around a NearesNeigbor object. It would have been much simpler to have NearestNeigbors(algorithm=algorithm) return algorithm directly (which would involved adding a __new__ method <https://stackoverflow.com/a/3209240/1791279> to NearestNeigbors and would allow to simplify this PR significantly, I think). - (+) +1 from Joel Will wait for more feedback and change the API accordingly. Thanks @jnothman <https://github.com/jnothman> ! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#8999 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEz69jHT2vIP8knrdfs50XgT1-43urkks5sBVC9gaJpZM4NxO8i> .

rth · 2017-06-06T15:27:36Z

I don't think NearestNeighbors(algorithm=x) is the application.
KNeighborsClassifier(algorithm=x), radius_neighbors_graph(algorithm=x),
etc. are.

Definitely, my point is that there are two ways of achieving the desired behavior:

First is roughly what is done in this PR (e.g. making sure that NearestNeighbors can handle an algorithm that's an estimator)

Define NearestNeighbors as something along the lines of,

 import sklearn.neighbors
 
 class NearestNeighbors(sklearn.neighbors.NearestNeighbors):
     def __new__(cls, *args, **kwargs):
         algorithm = kwargs.get('algorithm', None)
         if not algorithm and len(args) >= 3:
             algorithm = args[3] 
         if algorithm is not None and hasattr(algorithm, 'fit'):
             print('Using custom NN backend')
             # check that custom NN algorithm is picklable
             pickle.loads(pickle.dumps(self.algorithm))  
             # some other tests could be added here
             return algorithm
         else:
             return super(cls, NearestNeighbors).__new__(cls)

Since radius_neighbors_graph or DBSCAN, etc. internally call NearestNeighbors(algorithm=x) and do something with the returned object, the second choice might allows to have one less level of indirection and achieve the results with very little changes to the code base. But it might have other issues. Not sure what's the best way.

In any case, KNeighborsClassifier doesn't call NearestNeighbors internally and so it would need to be handled separately.

What do you think?

The problem is actually that KNeighborsClassifier shouldn't be
exposing kneighbors and radius_neighbors from an API purist perspective.

So in the current case, those would be accessible via KNeighborsClassifier.algorithm.kneighbors . Are you saying that it shouldn't be the case?

lesteve · 2017-06-06T16:31:26Z

Looks like the failures on Travis are genuine.

rth · 2017-06-06T16:40:56Z

Looks like the failures on Travis are genuine.

@lesteve They are. I just wanted to discuss the general direction of this PR and fix the API before spending time on making everything work fully, particularly as there were talk in #8996 (comment) that @ogrisel or you were already working on related topics...

jnothman · 2017-06-06T23:59:09Z

In any case, KNeighborsClassifier doesn't call NearestNeighbors internally

and so it would need to be handled separately. But we're modifying NeighborsBase which affects both. I'm not sure what you're trying to get at, except if you're talking about the special case of someone calling NearestNeighbors(algorithm=MyNeighborFinder()) which I think is not helpful in user code, and the indirection matters little in library code (except insofar as validation is concerned: we should minimise data validation in NeighborsBase when an alternative algorithm is provided). Implementing __new__ is not a good solution to anything. Rather, the role of NeighborsBase becomes handling parameters and initialising attributes. I could imagine NeighborsBase doing something like self.index_ = _fit_algorithm(...) which returns a fitted object with kneighbors and radius_neighbors. This may be a BallTree, a _BruteForceIndex, an LSHForest, or a MissingValueNearestNeighbor (not yet sure if this is useful).

…

On 7 June 2017 at 02:41, Roman Yurchak ***@***.***> wrote: Looks like the failures on Travis are genuine. @lesteve <https://github.com/lesteve> They are. I just wanted to discuss the general direction of this PR and fix the API before spending time on making everything work fully, particularly as there were talk in #8996 (comment) <#8996 (comment)> that @ogrisel <https://github.com/ogrisel> or you were already working on related topics... — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#8999 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEz6_9vJhhrr-ItOO5bBZUTzQ_I5e_Tks5sBYEcgaJpZM4NxO8i> .

jnothman · 2017-08-30T13:36:54Z

Do you want someone else to work on this, @rth? @SebastinSanty may be keen.

rth · 2017-08-30T14:26:28Z

@jnothman Sorry this is taking a while. If someone is eager to work on this they can feel free to take over this PR. @lesteve Might have also worked on related topics as far as I understood. In the other case, I will get back to this, but it would take some time..

rth · 2017-10-02T09:50:20Z

On 01/10/17 05:18, Joel Nothman wrote:

Would you mind completing someone else's work? @rth
has a few that he is currently unavailable to
complete. (Not that I've asked him if he'd like to donate them to a new
contributor...) I also think they might be quite challenging still for
you.

Realistically, I don't have much time for this PR at the moment so anyone can feel free to take it over, as mentioned above #8999 (comment). It may take some work. If not I will try to find some time for it over the next few months. cc @vrishank97

jnothman · 2017-10-02T10:02:43Z

Yes, this is what I'd been thinking of.

thechargedneutron · 2018-01-08T20:43:32Z

@rth @jnothman Since this is in the 0.20 milestone, is this up for grabs? The 0.20 deadline is near ;) but I am not very sure how strict the deadline is.

jnothman · 2018-01-08T21:43:36Z

Our milestones are unfortunately fairly meaningless unless close to release. Release is not as soon as that deadline. This remains something good to have, and I suspect @rth will happily mentor the work, but not a priority. It's the kind of functionality where most users don't know what they're missing, and even once it's implemented will be hard for all but advanced users to get into.

rth · 2018-01-08T22:56:59Z

It would be nice to have. @thechargedneutron feel free to take the PR over. Please ping me if you want a review of the continued PR.

thechargedneutron · 2018-01-09T10:21:02Z

@rth Yes, I need a brief review of what has been done so far. It would be good if you comment on this PR what the particular patch does. Can't think of an easier way to convey the progress to me.

rth · 2018-01-09T18:45:10Z

Yes, I need a brief review of what has been done so far. It would be good if you comment on this PR what the particular patch does. Can't think of an easier way to convey the progress to me.

@thechargedneutron There isn't really much additional information outside of what is written in the description, comments and the parent PR. As far as I remember, the general status of this was prototyping and in the process of fixing unit tests. The API was still not fully fixed and may need to be re-discussed again. I synched with master to make the changes more up to date. Hope this helps.

thechargedneutron

Ping @rth

thechargedneutron · 2018-01-14T19:28:27Z

sklearn/neighbors/tests/test_neighbors.py

+        # check algorithm is queried and parameter is passed
+        dist, ind = est.radius_neighbors([[0]], radius=radius,
+                                         return_distance=True)
+        assert_array_equal(dist[0][0], radius)


How is it supposed to be equal to radius?
Doesn't dist[0][0] mean minimum distance between [[0]] and [[0],[1]] provided radius is bigger than distance?

That part came from the parent PR. This was just intended to be a consistency test, I think. If some part of it doesn't make sense to you, you should change it )

thechargedneutron · 2018-01-14T19:30:51Z

sklearn/neighbors/tests/test_neighbors.py

+    def fit(self, X):
+        self._fitted = True
+
+    def query_radius(self, X, r, return_distance=True):


This function is not using parameters passed in fit function. How will it compute points from fit function?
It would be okay of you describe the motivation behind this function and the below assert condition (other reviewed part)

@thechargedneutron Sorry for the late reply. Yes, you are right it should take an X from fit. The idea was to prototype the simplest possible example of a custom NN search class with an API similar to KDTree.

jnothman · 2018-01-14T20:18:13Z

Note there is also discussion at #10463 about whether enabling using nearest neighbors as a transformer, together with sparse precomputed distance matrices, means we don't need this functionality most of the time.

jnothman · 2018-01-22T21:34:19Z

I should note that the conversation around #10463 suggests we may not even need this. Allowing nearest neighbours estimators to transform into a sparse nearest neighbourhood graph should be sufficient for moist applications.

rth · 2018-01-22T21:50:22Z

I should note that the conversation around #10463 suggests we may not even need this.

Agreed, that discussion/work looks quite interesting. (My response to comments wasn't intended to imply that this PR is still needed).

thechargedneutron · 2018-01-23T04:46:03Z

Thanks for informing that this issue needs no further work. Thanks :)

TomDLT · 2019-09-18T23:15:20Z

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[WIP] allow nearest neighbors algorithm to be an estimator (v2) #8999

[WIP] allow nearest neighbors algorithm to be an estimator (v2) #8999

rth commented Jun 6, 2017 •

edited

Loading

jnothman commented Jun 6, 2017

rth commented Jun 6, 2017 •

edited

Loading

jnothman commented Jun 6, 2017 via email

rth commented Jun 6, 2017

lesteve commented Jun 6, 2017

rth commented Jun 6, 2017

jnothman commented Jun 6, 2017 via email

jnothman commented Aug 30, 2017 •

edited

Loading

rth commented Aug 30, 2017

rth commented Oct 2, 2017

jnothman commented Oct 2, 2017

thechargedneutron commented Jan 8, 2018

jnothman commented Jan 8, 2018

rth commented Jan 8, 2018

thechargedneutron commented Jan 9, 2018

rth commented Jan 9, 2018 •

edited

Loading

thechargedneutron left a comment

thechargedneutron Jan 14, 2018

rth Jan 21, 2018

thechargedneutron Jan 14, 2018

rth Jan 21, 2018

jnothman commented Jan 14, 2018

jnothman commented Jan 22, 2018

rth commented Jan 22, 2018 •

edited

Loading

thechargedneutron commented Jan 23, 2018

TomDLT commented Sep 18, 2019

[WIP] allow nearest neighbors algorithm to be an estimator (v2) #8999

[WIP] allow nearest neighbors algorithm to be an estimator (v2) #8999

Conversation

rth commented Jun 6, 2017 • edited Loading

jnothman commented Jun 6, 2017

rth commented Jun 6, 2017 • edited Loading

jnothman commented Jun 6, 2017 via email

rth commented Jun 6, 2017

lesteve commented Jun 6, 2017

rth commented Jun 6, 2017

jnothman commented Jun 6, 2017 via email

jnothman commented Aug 30, 2017 • edited Loading

rth commented Aug 30, 2017

rth commented Oct 2, 2017

jnothman commented Oct 2, 2017

thechargedneutron commented Jan 8, 2018

jnothman commented Jan 8, 2018

rth commented Jan 8, 2018

thechargedneutron commented Jan 9, 2018

rth commented Jan 9, 2018 • edited Loading

thechargedneutron left a comment

Choose a reason for hiding this comment

thechargedneutron Jan 14, 2018

Choose a reason for hiding this comment

rth Jan 21, 2018

Choose a reason for hiding this comment

thechargedneutron Jan 14, 2018

Choose a reason for hiding this comment

rth Jan 21, 2018

Choose a reason for hiding this comment

jnothman commented Jan 14, 2018

jnothman commented Jan 22, 2018

rth commented Jan 22, 2018 • edited Loading

thechargedneutron commented Jan 23, 2018

TomDLT commented Sep 18, 2019

rth commented Jun 6, 2017 •

edited

Loading

rth commented Jun 6, 2017 •

edited

Loading

jnothman commented Aug 30, 2017 •

edited

Loading

rth commented Jan 9, 2018 •

edited

Loading

rth commented Jan 22, 2018 •

edited

Loading