Distributed Representation

Many features, many concepts

Picture a row of light switches on a wall. Each switch is up or down, and you can set one without touching the others. The pattern of all the switches is a code. A code built from many parts that can be set separately is a distributed representation.

The power of the idea is in the count. Suppose there are features and each one can take values. Together they name different concepts. Three switches with two positions each name 2 × 2 × 2 = 8 patterns. Ten switches name 1,024.

Compare a symbolic representation, which gives each concept its own entry and turns on only one entry at a time. This is also called a one-hot representation: a vector with exactly one entry equal to 1 and all the others equal to 0. With entries it names only concepts.

Predict first. How many different concepts can ten binary features name?

Choose one answer.

Now build codes yourself. The left bars count the concepts a one-hot code and a distributed code can name. The bars use a logarithmic scale, so each gridline up is a factor of ten.

The bars show the book's sentence in numbers: features with values describe concepts. The count grows exponentially in , while a one-hot code grows in a straight line.

Symbols and nearest neighbours

The book lists several learners that use non-distributed representations. Each one splits the input into regions, and each region has its own parameters:

• k-means assigns each input to exactly one cluster.
• k-nearest neighbours associates one or a few stored templates with each input.
• Decision trees activate one leaf and the nodes on the path to it.
• Gaussian mixtures and mixtures of experts give each template a degree of activation, but the degrees cannot be set separately from each other.
• Kernel machines with a Gaussian kernel have the same issue.
• n-gram models give each context a leaf in a tree of word suffixes, with separate parameters per leaf.

The book notes that for some of these models the output interpolates between neighbouring regions, but the number of regions still grows in line with the number of parameters or examples.

The simplest case is nearest neighbours, shown in Figure 15.8 of the book. Three stored prototypes split the input space into three regions, and each region is the set of points nearest to one prototype. The picture below rebuilds the idea. Drag a prototype to move it, or click empty space to drop a query point. The query takes the output stored for its nearest prototype.

Each region gets its own output, so the learner can fit any training set without a hard optimization. The cost is that it generalizes only locally. The only link between neighbouring regions is the smoothness assumption: a nearby input should get a nearby output. A function with many peaks and troughs then needs about as many examples as it has regions.

Shared attributes make similar things close

As pure symbols, cat and dog are as far apart as any two symbols. Now give each animal a distributed code with entries such as has fur, four legs or barks. Whatever is true of cats then generalizes to dogs, and the reverse. The book calls this generalization through shared attributes.

Distributed codes therefore induce a rich similarity space, in which semantically close concepts are close in distance. The book cites neural language models, which generalize much better on distributed word representations than on one-hot word codes (section 12.4).

Predict first. With one-hot codes, is cat closer to dog than to car?

Choose one answer.

Each animal below has five yes or no attributes. Click a cell to change it. The squared distance between two animals counts the attributes on which they disagree:

A one-hot code gives every pair of different concepts the squared distance 2. This is because the two codes differ in exactly two entries, each by 1:

Attributes break that symmetry. Here cat and dog share three of five attributes, so they are closer than either is to the car. A learned embedding can go further and place similar words close together, which a one-hot table cannot do.

Counting regions with hyperplanes

Now the geometry. Let each binary feature answer yes or no by thresholding a linear function of the input. A hyperplane is the set of points where that linear function equals zero: a line in the plane, or a flat sheet in three dimensions. It cuts the space into two half-spaces, one for each answer. Feature is 1 on one side of its hyperplane and 0 on the other.

Figure 15.7 of the book takes three such features in the plane. A region is a set of points that share one code, where the code is the list of answers, one for each feature. The figure shows seven of the eight possible codes. The code [0, 0, 0] never occurs, which is why the book says that not every code is feasible.

Predict first. Three lines in general position cut the plane into how many regions?

Choose one answer.

The book counts the regions with a general result on arrangements of hyperplanes (Zaslavsky, 1975; Pascanu et al., 2014b). For binary features in input dimensions the count is Equation 15.4:

Each term is a binomial coefficient, the number of ways to choose of the features. For = 3 and = 2 the sum is 1 + 3 + 3 = 7, which matches the figure. The sum counts regions when the hyperplanes are in general position: no two are parallel and no three pass through one point. The book does not spell out that condition in this section. It is added here, and the demo checks it for lines.

For fixed the sum grows like , which is polynomial in the number of features. For fixed the bound grows exponentially in . That reading holds only while is below : the exact sum never exceeds , so once reaches every code is possible and extra input dimensions add nothing. The table gives the first values.

Few parameters, many regions

The book gives a geometric argument for generalization. With linear-threshold features in there are parameters, and they distinguish regions. A learner that gave each region its own symbol would need separate parameters for every region, and so examples to fill them. Fewer parameters means fewer things to fit, so the distributed model needs far fewer examples.

The argument extends to nonlinear feature extractors. If a parametric transformation with parameters can learn about regions, with , it can generalize much better than a non-distributed setting that needs examples. A footnote gives a concrete case: a function that must differ across regions of a -dimensional input, with two distinguishable values per dimension, needs training examples.

Capacity also stays limited. A network of linear-threshold units has a VC dimension of only , where is the number of weights (Sontag, 1998). The VC dimension is the largest set of points that a model can label in every possible way. A linear classifier on top of the code also expresses a belief: the classes are linearly separable as a function of the underlying factors. The book says we typically do not want categories that need XOR logic, such as red cars with green trucks against green cars with red trucks.

This count of parameters is added here and is not printed in the book. It counts one weight per input dimension and one bias for each feature.

Predict first. With 20 features in a 10-dimensional input, how many regions can the code carve?

Choose one answer.

The chart uses a logarithmic scale. Parameters grow in a straight line with the number of features, while regions grow much faster once the number of features passes the input dimension.

Directions that mean something

The book's last example is a generative model of face images, trained by Radford et al. (2015). Its distributed representation has separate directions for different factors of variation. One direction tracks whether the face is male or female, and another tracks whether the person wears glasses. These directions were found automatically from the data. No labels were given to the hidden units. The book notes that gradient descent learns semantically meaningful features when the task requires them.

Figure 15.9 of the book shows the arithmetic. Start from the code of a man with glasses, subtract the code of a man without glasses, and add the code of a woman without glasses. The result decodes to a woman with glasses. The book's photographs are not reproduced here. The demo below uses an invented toy with the same arithmetic.

Zhou et al. (2015) found that hidden units in deep convolutional networks often correspond to labels that people would name, though not always. The book describes this as statistical separability: a learner can learn about one factor without seeing every combination of the others, and so it can generalize to combinations it has never seen.

Predict first. Start with the card man with glasses, subtract man without glasses, and add woman without glasses. Which card does the result reach?

Choose one answer.

The step from a man to a woman is (1, 0), and the glasses step is (0, 1). In this toy the glasses step is the same for both genders, which is the separate direction the book describes. Many different choices of cards A, B and C land on the same result, because the toy has only four cards.

• A distributed code with features and values names concepts. A one-hot code names only .
• Non-distributed learners such as nearest neighbours give one region per stored example, and they generalize only locally.
• Shared attributes place similar concepts close together. One-hot codes make every pair of different concepts equally far apart.
• Lines in general position cut the plane into regions, which is Equation 15.4 with .
• For fixed the number of regions grows like , while the parameters grow in line with . This is the geometric argument the book gives for why distributed codes generalize.
• Directions in a learned code can carry separate factors, such as gender and glasses, which is the idea behind the arithmetic in Figure 15.9.

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 15.4 (pages 546–552), 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.