Memory Error : Locally Linear Embedding

[ncherel]

Locally Linear Embedding (LLE) encounters a memory error when using a large matrix (10000x10000) and a large number of neighbors (>500).

The memory error occurs with the standard option after the nearest neighbors have been computed in barycenter_kneighbors_graph()
https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/manifold/locally_linear.py#L99

knn = NearestNeighbors(n_neighbors + 1, n_jobs=n_jobs).fit(X)
X = knn._fit_X
n_samples = X.shape[0]
ind = knn.kneighbors(X, return_distance=False)[:, 1:]
data = barycenter_weights(X, X[ind], reg=reg)

X[ind] creates a matrix of size (n_samples x n_neighbors x n_dim) but the algorithm is then only using the neighbors sequentially in barycenter_weights() https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/manifold/locally_linear.py#L20

barycenter_weights() could be modified to take ind as input and avoid this issue.

[jnothman]

thanks for the report. are you saying B is larger than it needs to be, or that the processing could be done in small batches? I've not got time to look right now

[ncherel]

B is larger than it needs to be.

[jnothman]

A patch is welcome, IMO.

[pinakinathc]

hi can i take this up?

[jnothman]

perhaps work through #10457 first. Have you looked at how to fix this?

…

On 23 January 2018 at 20:55, Pinaki Nath Chowdhury ***@***.*** > wrote: hi can i take this up? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#10493 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEz65p8r6Tu1IFH-bBLHjvhG5Ga36gOks5tNayMgaJpZM4RiBTI> .

[maykulkarni]

I would like to take it up. I have an idea to fix this.

[wxnudt]

I think I also meet the same problem. have you fixed it? @maykulkarni

[marimeireles]

@jnothman I'm gonna give a try on this one. I'll post here if I get stuck!
I'm taking this bug as part of the #WiMLDS_Berlin sprint =)

[marimeireles]

@sammsc is also working on this with me :)

[marimeireles]

Okay... So I tried to replicate the error on my computer but when I try to add 500 neighbors to each part of the matrix my computer just can't do it.
Any idea on how I can replicate it?
I tried:

    X = np.random.rand(12000, 12000)
    print("Just finished to create the matrix")
    A = barycenter_kneighbors_graph(X, 500)

And my program gets stuck in the last line.
Thanks!