precomputed k-nn with metric = "precomputed"

[kimartin]

Hi, just a small question: is it possible (or sensible) to use a precomputed k-nn when using metric = "precomputed"?

In my use case I computed the distance matrix ahead of time (as I use DTW for distance between spectrograms, it was easier to optimise without trying to make it usable inside UMAP).

I want to test several parameter combinations for UMAP, and I saw the 'Precomputed k-nn' documentation that may possibly help accelerate UMAP computation.
However:
when I pre-compute the k-nn graph using umap.umap_.nearest_neighbors:

        knn_graph = nearest_neighbors(distance_matrix, 
                                      n_neighbors=max_n_neighbors,
                                      metric="precomputed",
                                      metric_kwds=None,
                                      angular=False,
                                      random_state=None)

then pass knn_graph to UMAP, I get the following error:

ValueError: precomputed_knn[2] (knn_search_index) must be an NNDescent object.

Turns out that nearest_neighbors returns None for its last output when 'metric = "precomputed".

Would it be sensible to try to work around that somehow? Or am I not going to gain anything because metric="precomputed"?

[lmcinnes]

Mostly what you will lose (should you work around it) is the ability to transform new data -- you need the pynndescent index for that. So you can likely fudge your way past that error and have a basic fit_transform work, but other things such as transform and inverse transform will likely break in strange ways if you were to try and use them. On the other hand there are some DTW distance implementations that may work with UMAP. There's this one: https://gist.github.com/kylemcdonald/76b6f18fb4026e01196282b59bd31e7e, and the softdtw library uses JAX which I think you can make play nice with numba. Finally, if you do have a good DTW implementation you like we can try to get it suitably numba jitted and included in pynndescent so you can just use ``metric="DTW"`` in future.

…

On Sun, Jul 10, 2022 at 7:27 AM kimartin ***@***.***> wrote: Hi, just a small question: is it possible (or sensible) to use a precomputed k-nn when using metric = "precomputed"? In my use case I computed the distance matrix ahead of time (as I use DTW for distance between spectrograms, it was easier to optimise without trying to make it usable inside UMAP). I want to test several parameter combinations for UMAP, and I saw the 'Precomputed k-nn' documentation that may possibly help accelerate UMAP computation. However: when I pre-compute the k-nn graph using umap.umap_.nearest_neighbors: knn_graph = nearest_neighbors(distance_matrix, n_neighbors=max_n_neighbors, metric="precomputed", metric_kwds=None, angular=False, random_state=None) then pass knn_graph to UMAP, I get the following error: ValueError: precomputed_knn[2] (knn_search_index) must be an NNDescent object. Turns out that nearest_neighbors returns None for its last output when 'metric = "precomputed". Would it be sensible to try to work around that somehow? Or am I not going to gain anything because metric="precomputed"? — Reply to this email directly, view it on GitHub <#888>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AC3IUBNS2ZTDCLRDSZEYQJDVTKXQPANCNFSM53E32KZA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[kimartin]

Thank you for the fast reply!

For now I don't really need to be able to transform or inverser_transform as I just want to check what works better on my current data.

As for the DTW implementation I'm more limited by my data than anything else, as I have spectrograms of different lengths (Im trying to cluster bird vocalisations) so I can't pass them to UMAP as a single array. My actual implementation is pretty much a tweaked version of the one you linked, still numba jitted. The major difference is I removed the assumption of a single shape for all the samples, as that doesn't work with my data.

[lmcinnes]

Ah, that makes a lot of sense. One day I would actually like to be able to handle ragged arrays like that. Notionally I know how to do it in PyNNDescent (which would pretty much make it accessible to UMAP, modulo a suitable API), but I haven't had the time to sit down and get it all coded up properly. It would be nice to be able to handle variable length signals with DTW, or Wasserstein, and various string edit style distances for variable length strings, etc. So I do definitely have your use case in mind -- it just isn't available quite yet; sorry.