0
$\begingroup$

Is this known as a fact or from some analysis that the MNIST data-set is almost as if its sampled from some low (~10?) dimensional manifold? Is there a locally linear embedding to a low-dimensional space? Of course I don't expect the data will be exactly on some low dimensional manifold; there will be some noise.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by LLE? Can you edit the question to spell out the acronym? What exactly do you mean by "sampled from"? Certainly the digits don't come from a space of dimension 10; there's more variation than that, even among instances of the same digit -- so you'd somehow have to account for randomness, noise, and variation among digits. You could choose a more descriptive title. Also, what have you tried so far? $\endgroup$ – D.W. Jun 14 '16 at 5:26
  • $\begingroup$ I have the same questions ad D.W. However, I would like to add that MNIST is extremely well studied. So no matter what you mean, the answer is likely to be "yes, somebody already did / tried that" on MNIST. $\endgroup$ – Martin Thoma Jun 14 '16 at 6:17
  • $\begingroup$ I mean does "effectively" the MNIST dataset behave like its sampled from some low dimensional manifold? (..it at least does seem that a 10 dimensional PCA captures almost all the variance..) I guess doing a "Local Linear Embedding" (LLE) on this dataset will reveal an effective manifold dimension of this dataset and I am wondering if someone has tried that. Ofcourse the data does not have to exactly be on some low dimensional manifold and there will be some noise. $\endgroup$ – Anirbit Jun 14 '16 at 14:32
  • $\begingroup$ Please edit the question to include this information. Don't just leave clarifications in the comments -- we want questions to be self-contained, so people don't have to read the comments to understand what you're asking. $\endgroup$ – D.W. Jun 15 '16 at 0:58
2
$\begingroup$

The short answer is: I don't know.

Visualizations

There's been lots of work on visualizing the MNIST data set, in 2 dimensions, and even in 3 dimensions.

For instance, here's an embedding into 2D space using a neighbor embedding visualization technique (a highly nonlinear embedding):

NE embedding

Credit: Zhirong Yang, Jaakko Peltonen, and Samuel Kaski. See their page on MNIST visualization.

However, the NE embedding is not linear. It doesn't try to be a linear map from the image space ($\mathbb{R}^{768}$) to the plot ($\mathbb{R}^2$). Rather, it tries to preserve the topology: it tries to make images that are nearby (e.g., in L2 metric) be near each other in the visualization.


See also this blog article for exploration of different ways of embedding MNIST into two or three dimensions, including both linear embeddings (e.g., PCA) and nonlinear embeddings.

Here's another visualization of doing PCA to 2 dimensions on MNIST:

PCA on MNIST

Credit: taken from this nice blog post

One thing that is clear from those visualizations is that if you do PCA onto two or three dimensions, the result is not linearly separable. It's not even close to linearly separable.

Even if you look at just two different digits and apply 2-dimensional PCA to project linearly onto the two principal components, the result is again not even close to linearly separable:

PCA of 4 vs 9

Credit: the same blog post

So at least 2 dimensions don't seem to be enough to distinguish 4's from 9's.

In contrast, PCA onto 2 dimensions does give you something that's pretty close to linearly separable: it's enough to distinguish some other pairs of digits pretty well with a linear classifier, but not perfectly -- to get best accuracy, you need more than a linear classifier and more than 2 dimensions.

Read the rest of that blog post to see what happens when you try to do a locally linear embedding to project all MNIST digits onto 2 dimensions. You'll see that, while there are some commonalities, the result doesn't look good enough to get high accuracy.

A note of caution

We need to be careful about what you mean by "lay on a manifold". Of course, if you consider all the ways to write a 7 (say), those 7's will all lie on some manifold in $\mathbb{R}^{768}$. I doubt that manifold is going to be a linear subspace (i.e., a hyperplane).

If you allow arbitrarily nonlinear manifolds, it's not clear that it is useful or meaningful to ask what is the dimension of this manifold. For instance, consider a mapping that maps each digit to $\mathbb{R}$ (1 dimension), e.g., all 0 digits get mapped to 0, all 1 digits get mapped to 1, all 2 digits get mapped to 2, and so on. This is clearly possible in principle, but the mapping is extremely nonlinear. Would you consider this evidence that the digits lie on a 1-dimensional manifold? Probably not. This highlights the challenge in making our intuition more precise.

So you need to make sure you are asking the right question.

Measuring dimensionality by learning

One way to think about this is to look for an embedding $f:\mathbb{R}^{768} \to \mathbb{R}^d$ into some lower-dimensional space ($d$-dimensional space), with the two properties that:

  1. The embedding $f$ is "nice" in some fashion -- it need not be linear, but hopefully it is continuous or locally linear or something like that.

  2. Enough information is preserved that we can still classify which digit it is, based on the result of the embedding. In other words, given an image $x$ of an image, we should be able to tell which image it is given only $f(x)$: the result $f(x)$ of the embedding should be enough for a classifier to tell which digit it is, with about as high accuracy as would be possible given the original image.

People have studied this. For instance, people have built autoencoders, which are basically a way to use a deep neural network to build an embedding $f$ such that you can still reconstruct the image with reasonable accuracy. You can train an autoencoder on the MNIST digits to build an embedding $f$ that maps to a lower-dimensional space, then train a classifier that tries to label the digits based on the result of the embedding. The following paper looks at one approach to that, on the MNIST data set:

Wei Wang, Yan Huang, Yizhou Wang, Liang Wang. Generalized Autoencoder: A Neural Network Framework for Dimensionality Reduction. IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp.490--497.

They build autoencoders that map to a 30-dimensional data space, and where a simple classifier achieve an error rate of 4-5%. For MNIST, 4-5% error rate is very high: the state of the art is an error rate of 0.5% or so, when training a classifier on the original images. So this means that, as far as we know, if you try to map down to 30 dimensions, a lot of information is still preserved, but a significant amount is lost: you lose enough information that the classifier's error rate increases by an order of magnitude.

In short, 30 dimensions doesn't seem to be enough, at least for an embedding built in this way.

The other caveat is that the embeddings built in this way use a multi-linear neural network, and thus might still be fairly nonlinear. If you demand a particularly "smooth"/"nice" embedding, this result might not be relevant.

$\endgroup$
  • $\begingroup$ Thanks for this amazing answer! But I don't understand what you mean by a "linear manifold". Could you kindly define this concept? Currently I am not interested in finding a lower dimensional embedding which will somehow optimize the classification efficiency. Currently all I want to know is if inside this $\mathbb{R}^{768}$ there is some $k-$manifold with $k < 768$ such that all the vectors are "almost" on this manifold. Maybe there exists this manifold embedded inside this $\mathbb{R}^{768}$ but that is maybe still not the embedding which maximizes the classification accuracy. $\endgroup$ – Anirbit Jun 15 '16 at 15:12
  • $\begingroup$ @Anirbit, I just mean a linear subspace (hyperplane). $\endgroup$ – D.W. Jun 15 '16 at 15:48
  • $\begingroup$ Okay! So its not known if there is a linear subspace into which all of the data fits? $\endgroup$ – Anirbit Jun 15 '16 at 23:56
  • $\begingroup$ @Anirbit, I think it's very unlikely that all the data fits into a low-dimensional linear subspace (e.g., due to noise), but I don't know if that's known. Why don't you try it? Download MNIST and try looking for the linear space they span -- that's "just" linear algebra. $\endgroup$ – D.W. Jun 15 '16 at 23:58
  • $\begingroup$ Since we do see that a 10 PCA captures almost the whole variance isn't 10 as the dimension of this space a good guess? $\endgroup$ – Anirbit Jun 16 '16 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.