# Dimensionality and Manifold

A commonly heard sentence in unsupervised Machine learning is

High dimensional inputs typically live on or near a low dimensional manifold

What is a dimension? What is a manifold? What is the difference?

Can you give an example to describe both?

In mathematics, a manifold is a topological space that resembles Euclidean space near each point. More precisely, each point of an n-dimensional manifold has a neighbourhood that is homeomorphic to the Euclidean space of dimension n.

In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it.

What does the Google/Wikipedia even mean in layman terms? It sounds like some bizarre definition like most machine learning definition?

They are both spaces, so what's the difference between a Euclidean space (i.e. Manifold) and a dimension space (i.e. feature-based)?

• Have you tried Internet search? That should be enough. – Aleksandr Blekh May 6 '15 at 4:09
• yes, i had google but that's surely isn't enough, see the updated question. – alvas May 6 '15 at 4:34
• I'm not sure that it's such a good idea to seek explanation of complex machine learning concepts "in layman terms". Also, you should widen your search beyond just Wikipedia. – Aleksandr Blekh May 6 '15 at 4:39

What is a dimension?

To put it simply, if you have a tabular data set with m rows and n columns, then the dimensionality of your data is n:

What is a manifold?

The simplest example is our planet Earth. For us it looks flat, but it really is a sphere. So it's sort of a 2d manifold embedded in the 3d space.

What is the difference?

To answer this question, consider another example of a manifold: This is so-called "swiss roll". The data points are in 3d, but they all lie on 2d manifold, so the dimensionality of the manifold is 2, while the dimensionality of the input space is 3.

There are many techniques to "unwrap" these manifolds. One of them is called Locally Linear Embedding, and this is how it would do that: Here's a scikit-learn snippet for doing that:

from sklearn.manifold import LocallyLinearEmbedding

lle = LocallyLinearEmbedding(n_neighbors=k, n_components=2)
X_lle = lle.fit_transform(data)
plt.scatter(X_lle[:, 0], X_lle[:, 1], c=color)
plt.show()


The dimensionality of a dataset is the number of variables used to represent it. For example, if we were interested in describing people in terms of their height and weight, our "people" dataset would have 2 dimensions. If instead we had a dataset of images, and each image is a million pixels, then the dimensionality of the dataset would be a million. In fact, in many modern machine learning applications, the dimensionality of a dataset could be massive.

When dimensionality is very large (larger than the number of the samples in the dataset), we could run into some serious problems. Consider a simple classification algorithm that seeks to find a set of weights w such that when dotted with a sample x, gives a negative number for one class and a positive number for another. w will have a length equal to the dimensionality of the data, so it will have more parameters than there are samples in the entire dataset. This means that a learner will be able to overfit the data, and consequently won't generalize well to other samples unseen during training.

A manifold is an object of dimensionality d that is embedded in some higher dimensional space. Imagine a set of points on a sheet of paper. If we crinkle up the paper, the points are now in 3 dimensions. Many manifold learning algorithms seek to "uncrinkle" the sheet of paper to put the data back into 2 dimensions. Even if we aren't concerned with overfitting our model, a non-linear manifold learner can produce a space that makes classification and regression problems easier.

• Are there cases where high dimensionality doesn't uncrinkle to a manifold? – alvas May 7 '15 at 7:00
• Definitely! Sometimes, data already lies in it's intrinsic space. In that case, trying to reduce dimensionality will probably be deleterious for classification performance. In these cases, you should find that the features in the dataset you are using are largely statistically independent from each other. – Jordan A May 8 '15 at 0:03

One way of doing dimensional reduction is to do feature hashing. This was known about in the 1960's. So for example if your data is a sparse set of points in 3 dimensions (x,y,z) you create a (good) hash function h(x,y,z). You can use that of course for a hash table or a Bloom filter lookup. This is a good form of data compression. I don't know why the AI community doesn't use it. It is much more to the point than a neural net.

• How is dimensionality reduction related to manifold? – alvas May 7 '15 at 7:00
• It is a way of picking out everything on the manifold and excluding everything else. – SeanOCVN May 7 '15 at 14:43
• I think @alvas has a point here. It's not immediately clear how this relates to the original question regarding an explanation of manifolds and dimensions. – Ryan J. Smith May 10 '15 at 17:44
• To help resolve the missing link of SeanOCVN’s answer and alvas comment: A manifold (in a topological space) is the output of executing the (or a) Locally Linear Embedding algorithm with input data in an embedded space. The result is that the input data dimension quantity is higher than the output data dimension quantity. The extraction of a new data representation (mappable to the original data representation) is referred to as “feature extraction”; which is a subtype of “dimensionality reduction”. – pds Mar 12 '19 at 9:25

• I would like to provide you with an example that helped me understand the significance of the manifold intuitively.
• Elaborating on that, I would like to clarify the "resembling of Euclidian space" a little bit.

# Intuitive Example

Imagine we would work on a collection of (black and white) HDready images (1280 * 720 pixels). Those pictures live in a 921,600 dimensional world; Every picture is defined by individual values of pixels.

Now imagine that we would construct these images by filling in each pixel in sequence by rolling a 256-sided die.

The resulting image would probably look a little something like this: Not very interesting, but we could keep doing that until we hit something we would like to keep. Very tiring but we could automate this in a few lines of Python.

If the space of meaningful (let alone realistic) images would even be remotely as large as the entire feature space, we would soon see something interesting. Maybe we would see a baby picture of you or a news article from an alternative timeline. Hey, how about we add a time component, and we could even get lucky and generate Back to th Future with an alternative ending

In fact we used to have machines that would do exactly this: Old TV's that weren't tuned right. Now I remember seeing those and never have I ever seen anything that even had any structure.

Why does this happen? Well: Images we find interesting are in fact high resolution projections of phenomena and they are governed by things that are much less high dimensional. For instance: Brightness of the scene, which is close to a one dimensional phenomenon, dominates almost a million dimensions in this case.

This means that there is a subspace (the manifold), in this case (but not not per definition) controlled by hidden variables, that contains the instances of interest to us

# Local Euclidian behaviour

Euclidian behaviour means that behaviour has geometrical properties. In the case of the brightness that is very obvious: If you increase it along "it's axis" the resulting pictures become continuously brighter.

But this is where it get's interesting: That Euclidian behaviour also works on more abstract dimensions in our Manifold space. Consider this example out of Deep Learning by Goodfellow, Bengio and Courville Left: The 2-D map of the Frey faces manifold. One dimension that has been discovered (horizontal) mostly corresponds to a rotation of the face, while the other (vertical) corresponds to the emotional expression. Right: The 2-D map of theMNIST manifold

One reason why deep learning is so successful in application involving images is because it incorporates a very efficient form of manifold learning. Which is one of the reasons why it is applicable to image recognition, and compression, as well as image manipulation.