8
$\begingroup$

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 Google/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.

Dimesion from Google/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 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)?

$\endgroup$
  • 1
    $\begingroup$ Have you tried Internet search? That should be enough. $\endgroup$ – Aleksandr Blekh May 6 '15 at 4:09
  • 1
    $\begingroup$ yes, i had google but that's surely isn't enough, see the updated question. $\endgroup$ – alvas May 6 '15 at 4:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Aleksandr Blekh May 6 '15 at 4:39
21
$\begingroup$

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:

enter image description here

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:

enter image description here

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()
$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are there cases where high dimensionality doesn't uncrinkle to a manifold? $\endgroup$ – alvas May 7 '15 at 7:00
  • $\begingroup$ 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. $\endgroup$ – Jordan A May 8 '15 at 0:03
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How is dimensionality reduction related to manifold? $\endgroup$ – alvas May 7 '15 at 7:00
  • $\begingroup$ It is a way of picking out everything on the manifold and excluding everything else. $\endgroup$ – SeanOCVN May 7 '15 at 14:43
  • $\begingroup$ 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. $\endgroup$ – Ryan J. Smith May 10 '15 at 17:44
  • $\begingroup$ 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”. $\endgroup$ – pds Mar 12 at 9:25

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.