t-SNE results in errors when reducing dim to default 2

[kirk86]

Hi everyone, I was wondering whether anyone knows why t-SNE results into memory errors when reducing the dimension of the data to the default number, which is 2.
I have the mnist dataset and I apply some transformation on it. Resulting in a reduced mnist dataset.
Original: 60000x784
After transformation: 60000x200

When I apply t-SNE on transformed mnist 60000x200, I always get a memory error. Also I was wondering why doesn't the multicore option of n_jobs=-1 exist?

[lesteve]

Please post a stand-alone snippet reproducing the problem and the full stack-trace you get.

[kirk86]

@lesteve thanks for the reply
here's the output of a simple example

In [47]: X_train.shape
Out[47]: (60000, 200)

n [50]: X_train_reduced = TSNE(n_components=2, random_state=0).fit_transform(X_train)
---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)
<ipython-input-50-6848c4dfd81b> in <module>()
----> 1 X_train_reduced = TSNE(n_components=2, random_state=0).fit_transform(X_train)

/home/user/miniconda2/lib/python2.7/site-packages/sklearn/manifold/t_sne.pyc in fit_transform(self, X, y)
    882             Embedding of the training data in low-dimensional space.
    883         """
--> 884         embedding = self._fit(X)
    885         self.embedding_ = embedding
    886         return self.embedding_

/home/user/miniconda2/lib/python2.7/site-packages/sklearn/manifold/t_sne.pyc in _fit(self, X, skip_num_points)
    764                 neighbors_nn = neighbors_nn[:, 1:]
    765             P = _joint_probabilities_nn(distances, neighbors_nn,
--> 766                                         self.perplexity, self.verbose)
    767         else:
    768             P = _joint_probabilities(distances, self.perplexity, self.verbose)

/home/user/miniconda2/lib/python2.7/site-packages/sklearn/manifold/t_sne.pyc in _joint_probabilities_nn(distances, neighbors, desired_perplexity, verbose)
     96     m = "All probabilities should be finite"
     97     assert np.all(np.isfinite(conditional_P)), m
---> 98     P = conditional_P + conditional_P.T
     99     sum_P = np.maximum(np.sum(P), MACHINE_EPSILON)
    100     P = np.maximum(squareform(P) / sum_P, MACHINE_EPSILON)

MemoryError:

The above example was run on a PC with 24 cores and 64GB of ram and still get memory errors.

[kirk86]

@lesteve
Notice that also Isomap produces memory error even when running with default parameters.

 In [57]: X_train_iso = Isomap(n_jobs=-1).fit_transform(X_train)
---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)
<ipython-input-57-26dde712b79e> in <module>()
----> 1 X_train_iso = Isomap(n_jobs=-1).fit_transform(X_train)

/home/user/miniconda2/lib/python2.7/site-packages/sklearn/manifold/isomap.pyc in fit_transform(self, X, y)
    178         X_new: array-like, shape (n_samples, n_components)
    179         """
--> 180         self._fit_transform(X)
    181         return self.embedding_
    182

/home/user/miniconda2/lib/python2.7/site-packages/sklearn/manifold/isomap.pyc in _fit_transform(self, X)
    122         G *= -0.5
    123
--> 124         self.embedding_ = self.kernel_pca_.fit_transform(G)
    125
    126     def reconstruction_error(self):

/home/jmitro/miniconda2/lib/python2.7/site-packages/sklearn/decomposition/kernel_pca.pyc in fit_transform(self, X, y, **params)
    258         X_new: array-like, shape (n_samples, n_components)
    259         """
--> 260         self.fit(X, **params)
    261
    262         X_transformed = self.alphas_ * np.sqrt(self.lambdas_)

/home/user/miniconda2/lib/python2.7/site-packages/sklearn/decomposition/kernel_pca.pyc in fit(self, X, y)
    233             Returns the instance itself.
    234         """
--> 235         X = check_array(X, accept_sparse='csr', copy=self.copy_X)
    236         K = self._get_kernel(X)
    237         self._fit_transform(K)

/home/user/miniconda2/lib/python2.7/site-packages/sklearn/utils/validation.pyc in check_array(array, accept_sparse, dtype, order, copy, force_all_finite, ensure_2d, allow_nd, ensure_min_samples, ensure_min_features, warn_on_dtype, estimator)
    380                                       force_all_finite)
    381     else:
--> 382         array = np.array(array, dtype=dtype, order=order, copy=copy)
    383
    384         if ensure_2d:

MemoryError:

[jnothman]

It would be best if you could provide or generate some data that causes the failure.

…

On 15 March 2017 at 08:08, kirk86 ***@***.***> wrote: @lesteve <https://github.com/lesteve> Notice that also Isomap produces memory error even when running with default parameters. In [57]: X_train_iso = Isomap(n_jobs=-1).fit_transform(X_train) --------------------------------------------------------------------------- MemoryError Traceback (most recent call last) <ipython-input-57-26dde712b79e> in <module>() ----> 1 X_train_iso = Isomap(n_jobs=-1).fit_transform(X_train) /home/user/miniconda2/lib/python2.7/site-packages/sklearn/manifold/isomap.pyc in fit_transform(self, X, y) 178 X_new: array-like, shape (n_samples, n_components) 179 """ --> 180 self._fit_transform(X) 181 return self.embedding_ 182 /home/user/miniconda2/lib/python2.7/site-packages/sklearn/manifold/isomap.pyc in _fit_transform(self, X) 122 G *= -0.5 123 --> 124 self.embedding_ = self.kernel_pca_.fit_transform(G) 125 126 def reconstruction_error(self): /home/jmitro/miniconda2/lib/python2.7/site-packages/sklearn/decomposition/kernel_pca.pyc in fit_transform(self, X, y, **params) 258 X_new: array-like, shape (n_samples, n_components) 259 """ --> 260 self.fit(X, **params) 261 262 X_transformed = self.alphas_ * np.sqrt(self.lambdas_) /home/user/miniconda2/lib/python2.7/site-packages/sklearn/decomposition/kernel_pca.pyc in fit(self, X, y) 233 Returns the instance itself. 234 """ --> 235 X = check_array(X, accept_sparse='csr', copy=self.copy_X) 236 K = self._get_kernel(X) 237 self._fit_transform(K) /home/user/miniconda2/lib/python2.7/site-packages/sklearn/utils/validation.pyc in check_array(array, accept_sparse, dtype, order, copy, force_all_finite, ensure_2d, allow_nd, ensure_min_samples, ensure_min_features, warn_on_dtype, estimator) 380 force_all_finite) 381 else: --> 382 array = np.array(array, dtype=dtype, order=order, copy=copy) 383 384 if ensure_2d: MemoryError: — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#8582 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEz6-qBbRaOWlW1QWB9wmQ9U93tlTXZks5rlwHUgaJpZM4Mbi9z> .

[kirk86]

@jnothman the data is simply the mnist dataset.
if you have keras installed is as simple as

from keras.datasets import mnist
(X_train, y_train), (X_test, y_test) = mnist.load_data()

otherwise you'd have to download and load the dataset manually

[jnothman]

So you don't need to transform it to get the memory error?

…

On 15 March 2017 at 10:27, kirk86 ***@***.***> wrote: @jnothman <https://github.com/jnothman> the data is simply the mnist dataset. if you have keras installed is as simple as from keras.datasets import mnist (X_train, y_train), (X_test, y_test) = mnist.load_data() otherwise you'd have to download and load the dataset manually — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#8582 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEz6zufh5_k8ogN5TJ-w6BbS1UeoSooks5rlyJugaJpZM4Mbi9z> .

[kirk86]

@jnothman the only thing that I've done is

X_train = X_train.reshape(-1, 784)
X_test = X_test.reshape(-1, 784)

X_train /= 255.
X_test /= 255.

Then feed that to isomap or tsne

[jnothman]

So when @lesteve suggested you post a standalone snippet, he hoped you would write:

from sklearn.manifold import TSNE
from keras.datasets import mnist
(X_train, y_train), (X_test, y_test) = mnist.load_data()
X_train = X_train.reshape(-1, 784)
X_train = X_train / 255.
X_train_reduced = TSNE(n_components=2, random_state=0).fit_transform(X_train)

Yes, this blows up in memory consumption.

[jnothman]

The line where the traceback reports the MemoryError should require (n_samples**2 * 2) floats, so roughly 55GB of memory, apart from the original distances matrix of the same n_samples**2 size. I find it strange that the docs suggest that barnes_hut can "scale to millions of examples" when there's this kind of quadratic memory consumption (@cemoody?).

Can the implementation be made to have a lower memory consumption?

[jnothman]

I am a bit surprised to see that barnes_hut computes all-pairs distances, when it could be using kneighbors_graph to sparsely calculate distances where a binary tree is appropriate.

[kirk86]

@jnothman I'm not really aware of the internals of sklearn but would you say that roughly the same amount of memory is also required if I use Isomap or LocallyLinearEmbedding since all of them blow up in terms of memory consumption.

[jnothman]

Isomap definitely has an n**2 floats consumption too. I can't see in LLE whether this is necessarily the case. I'm no expert on manifold learning.

I think in all cases it would be a good idea to transform only a sample of the dataset.

[kirk86]

@jnothman thanks a lot.

[rjurney]

So this makes the sklearn TSNE broken? Other implementations work without this in issue.