Dimensionality and Manifold

Question

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?

Manifold from Wikipedia:

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.

Dimension from Wikipedia:

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 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)?

Answer 1

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()

Answer 2

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.

Answer 3

@Alexey Grigorev already gave a very good answer, however I think that it could be helpful to add two things:

• 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.

Answer 4

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.