Unsupervised Learning Algorithms

Representations without labels

Supervised learning has a teacher who labels every example. Unsupervised learning sees only the inputs, here , and must find structure without answers. The book notes that the line between the two is not rigid, because nothing objective decides whether a value is a feature or a target. Informally, unsupervised learning covers density estimation, drawing samples, removing noise, finding the surface the data lies near, and clustering.

A classic task is to find a good representation: a new description of each example that keeps as much information about as possible, under a constraint that makes it simpler.

• Low-dimensional representations use fewer numbers than the input.
• Sparse representations have mostly zero entries for most inputs. They usually need more entries than the input, so that the zeros do not discard too much.
• Independent representations have entries that are statistically independent, so each one carries its own part of the story.

The three overlap. Removing redundancy shrinks a description, and it also weakens the dependencies between its entries. This module builds two examples. PCA gives a low-dimensional code whose entries are uncorrelated. k-means gives an extremely sparse code with a single 1.

The low-dimensional code keeps one coordinate along the long direction. The sparse code names the clump with a one-hot vector . The decorrelated code turns the axes so that the two coordinates have no linear relationship, and it keeps everything. No algorithm was told which of these is right. Each answers the same question: what is a simpler description of this point?

PCA as a learned representation

Section 2.12 used principal components analysis to compress data. The book reads the same algorithm as representation learning. PCA learns a representation whose entries have no linear correlation with each other, a first step toward independence.

PCA is an orthogonal, linear map. It sends an input to the representation

where has orthonormal columns, so that . Each column of is a direction in input space, and each entry of says how far the input reaches along one of them.

The design matrix and its covariance

Stack the examples into the design matrix , with rows and columns. The book assumes the data have mean zero, . If they do not, subtract the mean first. The unbiased sample covariance is

The entry in row and column is the covariance of feature with feature , and the diagonal holds the variances. A nonzero off-diagonal entry means the cloud is tilted. PCA looks for the map that makes diagonal, so that the new coordinates are uncorrelated.

The book’s Figure 5.8 shows data with most of its variance along a tilted direction. Drag across the left picture to turn the two axes, or use the slider. The right picture shows the same points in the new coordinates.

As you turn, variance moves between the two coordinates while their sum stays fixed. The covariance is zero at two angles 90 degrees apart. At one of them the first coordinate has the largest variance.

Checkpoint on the representation

Why the covariance becomes diagonal

The rotation in the last demo was found by eye. The book computes it exactly. Section 2.12 gave the principal components as the eigenvectors of . In the columns are the eigenvectors, and in the eigenvalues:

The book then uses the singular value decomposition. Every matrix can be written as times times transposed, where and have orthonormal columns and is diagonal with non-negative singular values:

The book states that the principal components are the right singular vectors of , which are the columns of here. Substituting the decomposition into the eigenvector equation gives

This is the eigenvector equation again, with the same as the eigenvector basis, and with eigenvalues . The singular values are the square roots of the eigenvalues.

Equations 5.88 to 5.91 show that the covariance is diagonal:

Each step uses , which holds because the of the decomposition is orthogonal. Now take , so that for the whole design matrix . Equations 5.92 to 5.95 then follow:

The step to 5.94 uses . The result is diagonal, so the entries of are mutually uncorrelated, and their variances are the squared singular values divided by .

Step through the derivation with numbers. The demo uses a sample of eight points, so every matrix fits on the screen. Stretch the cloud with the sliders and check that each equation holds.

The last step prints the covariance of the new coordinates. Its off-diagonal entries are zero up to rounding, about 1e-16 here, and its diagonal equals the squared singular values over . The same holds for any sample. The book calls this a simple example of a representation that disentangles the factors of variation: the rotation aligns the principal axes with the basis of the new space.

Checkpoint on the derivation

Compression and the limit of decorrelation

The variances come out sorted from largest to smallest. Keeping only the first columns of gives a -dimensional representation. Rebuilding the examples from it loses the variance of the dropped components. The mean squared error of that rebuild is given by the formula below, which is added here and is not printed in the book:

In the demo, five features come from two hidden factors plus noise, so most variance sits in two directions. Choose how many components to keep.

Uncorrelated is not independent

The book says that full independence needs more than a linear map. A simple test, added here and not printed in the book, shows why. If two variables were independent, any function of one would be uncorrelated with any function of the other, so the squares of the two would be uncorrelated too. Predict what PCA does to a parabola.

Pick a data set, or click the plane under “Your points” to draw your own. Each click adds a point. After you have placed ten or more along a symmetric curve, the squares of the new coordinates will show the dependence.

For the Gaussian cloud, uncorrelated does mean independent, because a Gaussian is fully described by its covariance (a standard fact, not printed in the book). The parabola is not: its squares still move together.

Checkpoint on compression

k-means clustering

The second representation learner is k-means clustering. It divides the training set into clusters of nearby examples. The book reads this as a code: each input gets a -dimensional one-hot code vector , with a 1 at the index of its cluster and 0 elsewhere.

The book states this in words, and the formula above is added here. A one-hot code is sparse, since most entries are zero. Examples in one cluster share one code, and the whole code can be stored as a single integer, the cluster index.

The algorithm

Start with centroids , placed at different values. Then alternate two steps until nothing changes. In the assign step each example joins its nearest centroid. In the update step each centroid moves to the mean of its members. The formulas below are added here, as the book describes the steps in words.

Run the algorithm yourself. Press the buttons one step at a time, or run it to the end. The colored regions show the nearest centroid for each place in the plane, and the chart records the cost after each step.

Two things stand out. The cost never rises (the proof is added below), and the algorithm stops, but only at a local optimum.

An ill-posed problem

The book points out that clustering is ill-posed. No single criterion measures how well a clustering matches the real world. The cost measures how well the assignments rebuild the data, not whether the groups are meaningful. Many clusterings can each match some property of the world.

Checkpoint on clustering

One-hot versus distributed representations

The book gives an example with four kinds of vehicle: red cars, red trucks, gray cars and gray trucks. Ask a clustering algorithm for two clusters, and one answer is cars against trucks while another is red against gray. A third algorithm that chooses the number of clusters may return four. That captures both attributes, but the one-hot code now says only that each group differs from the others. Red cars are as different from gray cars as from gray trucks.

A distributed representation uses several attributes, here color and vehicle type. Two binary attributes name four groups, and ten name 1024. Similarity becomes a count of matching attributes, which is finer than asking whether one attribute matches. The book adds that it is unclear which attributes are the right ones, since the algorithm cannot know whether color and type matter more than maker and age.

The demo rebuilds the example with points: the horizontal axis is color and the vertical axis is vehicle type, with 30 examples per group. The key control is the stretch of the color axis. Stretching a coordinate is a change of units, and k-means measures Euclidean distance, so the units decide which structure it finds.

With a strongly stretched color axis, the distance between red and gray dominates, and two-cluster k-means returns red against gray. With a compressed color axis it returns cars against trucks. Near equal stretch, either answer can appear, depending on the starting centroids. With four clusters the groups are usually recovered for a stretch between about 0.6 and 2. At 0.3 or at 3 the groups are not recovered, and the readout says so.

The table compares the codes. In the one-hot code every pair of different groups is the same distance apart. With two attributes, a gray car is closer to a red car, because they share the vehicle type, than a gray truck is.

The distributed code carries more information in fewer entries. Each binary attribute doubles the number of groups it can name, while the one-hot code doubles its length.

What to take away

• Unsupervised learning sees only features. A common goal is a representation that keeps information about while being simpler.
• PCA learns an orthogonal linear map with diagonal covariance .
• Decorrelation removes linear correlation only, so uncorrelated does not mean independent.
• k-means alternates assign and update steps, giving a sparse one-hot code and only a local optimum.
• Clustering is ill-posed. A one-hot code loses the similarity between clusters, so prefer a distributed representation.

Checkpoint on codes

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 5.8 (pages 146–151), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.