Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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 :
Common examples of manifolds in machine learning (or at least sets that are hypothesized to live along low-dimensional manifolds) include :
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.
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.
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:
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
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.
32*32 array of grey pixel values is the input space[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
