I am trying to figure out what the manifold assumption means in semi-supervised learning. Can anyone explain in a simple way? I cannot get the intuition behind it.

It says that your data lie on a low-dimensional manifold embedded in a higher-dimensional space. I didn't get what that means.

up vote 33 down vote accepted

Imagine that you have a bunch of seeds fastened on a glass plate, which is resting horizontally on a table. Because of the way we typically think about space, it would be safe to say that these seeds live in a two-dimensional space, more or less, because each seed can be identified by the two numbers that give that seed's coordinates on the surface of the glass.

Now imagine that you take the plate and tilt it diagonally upwards, so that the surface of the glass is no longer horizontal with respect to the ground. Now, if you wanted to locate one of the seeds, you have a couple of options. If you decide to ignore the glass, then each seed would appear to be floating in the three-dimensional space above the table, and so you'd need to describe each seed's location using three numbers, one for each spatial direction. But just by tilting the glass, you haven't changed the fact that the seeds still live on a two-dimensional surface. So you could describe how the surface of the glass lies in three-dimensional space, and then you could describe the locations of the seeds on the glass using your original two dimensions.

In this thought experiment, the glass surface is akin to a low-dimensional manifold that exists in a higher-dimensional space : no matter how you rotate the plate in three dimensions, the seeds still live along the surface of a two-dimensional plane.

Examples

More generally, a low-dimensional manifold embedded in a higher-dimensional space is just a set of points that, for whatever reason, are considered to be connected or part of the same set. Notably, the manifold might be contorted somehow in the higher-dimensional space (e.g., perhaps the surface of the glass is warped into a bowl shape instead of a plate shape), but the manifold is still basically low-dimensional. Especially in high-dimensional space, this manifold could take many different forms and shapes, but because we live in a three-dimensional world, it's difficult to imagine examples that have more than three dimensions. Just as a sample, though, consider these examples :

  • a piece of glass (planar, two-dimensional) in physical space (three-dimensional)
  • a single thread (one-dimensional) in a piece of fabric (two-dimensional)
  • a piece of fabric (two-dimensional) crumpled up in the washing machine (three-dimensional)

Common examples of manifolds in machine learning (or at least sets that are hypothesized to live along low-dimensional manifolds) include :

  • images of natural scenes (typically you do not see images of white noise, for instance, meaning that "natural" images do not occupy the entire space of possible pixel configurations)
  • natural sounds (similar argument)
  • human movements (the human body has hundreds of degrees of freedom, but movements appear to live in a space that can be represented effectively using ~10 dimensions)

Learning the manifold

The manifold assumption in machine learning is that, instead of assuming that data in the world could come from every part of the possible space (e.g., the space of all possible 1-megapixel images, including white noise), it makes more sense to assume that training data come from relatively low-dimensional manifolds (like the glass plate with the seeds). Then learning the structure of the manifold becomes an important task; additionally, this learning task seems to be possible without the use of labeled training data.

There are many, many different ways of learning the structure of a low-dimensional manifold. One of the most widely used approaches is PCA, which assumes that the manifold consists of a single ellipsoidal "blob" like a pancake or cigar shape, embedded in a higher-dimensional space. More complicated techniques like isomap, ICA, or sparse coding relax some of these assumptions in various ways.

Semi-supervised learning

The reason the manifold assumption is important in semi-supervised learning is two-fold. For many realistic tasks (e.g., determining whether the pixels in an image show a 4 or a 5), there is much more data available in the world without labels (e.g., images that might have digits in them) than with labels (e.g., images that are explicitly labeled "4" or "5"). In addition, there are many orders of magnitude more information available in the pixels of the images than there are in the labels of the images that have labels. But, like I described above, natural images aren't actually sampled from the uniform distribution over pixel configurations, so it seems likely that there is some manifold that captures the structure of natural images. But if we assume further that the images containing 4s all lie on their own manifold, while the images containing 5s likewise lie on a different but nearby manifold, then we can try to develop representations for each of these manifolds using just the pixel data, hoping that the different manifolds will be represented using different learned features of the data. Then, later, when we have a few bits of label data available, we can use those bits to simply apply labels to the already-identified manifolds.

Most of this explanation comes from work in the deep and feature learning literature. Yoshua Bengio and Yann LeCun -- see the Energy Based Learning Tutorial have particularly accessible arguments in this area.

  • This doesn't answer the question: you aren't explaining why manifolds are needed, you are basically explaining why higher dimensional embeddings are not needed (a subset of a higher dimensional embedding needs not be a manifold in order to fit your examples). – gented Jul 10 '17 at 13:42

First, make sure that you understand what an embedding is. It's borrowed from mathematics. Roughly speaking, it is a mapping of the data into another space (often called embedding space or feature space), preserving some structure or properties of the data. Note that its dimensionality can be bigger or smaller than the input space. In practice, the mapping is complex and highly non-linear. A few examples:

  • A real-valued "word vector" to represent a word, such as word2vec
  • The activations of a layer of a convnet, such as the FC7 layer AlexNet (FC7 is the 7th fully-conected layer)

To illustrate, I'll take an example of this paper from Josh Tenenbaum:

Fig. 1 illustrates the feature discovery problem with an example from visual perception. The set of views of a face from all possible viewpoints is an extremely high-dimensional data set when represented as image arrays in a computer or on a retina; for example, 32 x 32 pixel grey-scale images can be thought of as points in a 1,024-dimensional observation space [input space] . The perceptually meaningful structure of these images [feature space], however, is of much lower dimensionality; all of the images in Fig. 1 lie on a two-dimensional manifold parameterized by viewing angle

enter image description here

Josh Tenenbaum then discusses the difficulties of learning such a mapping from input to feature space. But let's go back to the question: we are interested in how the input and feature spaces are related.

  • The 32*32 array of grey pixel values is the input space
  • The [x1=elevation, x2=azimuth] space is the feature space (although simplistic, it can be thought as a valid embedding space).

Re-stating the manifold hypothesis (quoting from this great article):

The manifold hypothesis is that natural data forms lower-dimensional manifolds in its embedding space

With this example, it is clear that the dimensionality of the embedding space is way less that the input space: 2 vs 1024. (This distinction will hold even for choices higher dimensional, less simplistic embedding spaces).

To convince yourself that the embedding forms a manifold, I invite you to read the rest of the Tenenbaum paper paper or the Colah article.

Note: this is just an illustration of what the manifold hypothesis means, not an argument of why it happens.

Related: Explanation of word vectors, word2vec paper

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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