Dense representations: the core idea

21 min read

An embedding is, for now, a name. The previous lesson, on bag of words and TF-IDF (term frequency–inverse document frequency), used up what an axis reserved for each vocabulary entry can do (count, weight, compare documents) and set out the way through: instead of an axis per entry, a few coordinates, far fewer than $\lvert V \rvert$ , in which every entry has a value. What that lesson did not say is what object this is, how it is stored, what it has to do with the one-hot it replaces, and where its numbers come from.

The subword vocabulary from the lesson on tokenisation has $\lvert V \rvert = 50\,000$ entries. The other figure is how many coordinates to give each one: 300, a common value that no theory fixes (you choose it by trying, and in use they run from a few dozen to a few thousand), so nothing that follows depends on it being exactly 300. With one axis per entry, what a model learns about superb is of no use when it meets magnificent: two different axes, and that is the end of the story. The moment the two share coordinates that stops being true, and it stops being true for all 50,000 entries at once. The price is the numbers in the table, $50\,000 \cdot 300 = 15$ million, and who decides them is the question this lesson ends on.

Before the definition, a map. Each point is a word placed by its two coordinates; pick car, apple or cat from the dropdown and watch what lights up around it.

The neighbours of the chosen word join it with a line. Try words from different groups and notice that no one wrote those lists: they come from the coordinates.

Two warnings, because the map promises more than it can give. I placed its coordinates by hand for the course: they come from no trained model. And a real embedding has hundreds of dimensions; what survives being flattened down to two is the neighbourhood, which is what to look at here. The analogy button shows something stronger, that directions mean something too, and this lesson does not charge for it: that takes up the rest of the block.

A short vector for each vocabulary entry

Fix a number $d_{\text{model}}$ far smaller than $\lvert V \rvert$ and assign each vocabulary entry a vector of that dimension, with arbitrary real coordinates. That vector is the embedding of the entry $w$ , and we write it $\mathbf{e}_w$ :

r(w) = \mathbf{e}_w \in \mathbb{R}^{d_{\text{model}}}, \qquad d_{\text{model}} \ll \lvert V \rvert.

The one-hot vector was sparse: $\lvert V \rvert$ coordinates of which only one is nonzero. This one is dense: few coordinates and all of them filled. The change of name marks a change of idea. In one-hot, coordinate $j$ answered a question that made sense (is this the entry that occupies position $j$ of the vocabulary?), and so a single coordinate was enough to identify the entry. Here no coordinate answers anything we can put into words on its own: what places the entry is $\mathbf{e}_w$ as a whole, its $d_{\text{model}}$ coordinates at once.

Storing $r$ is once again storing a table, and this time the table fits in memory. With the vocabulary ordered as in the lesson on one-hot encoding, the embedding matrix is

\mathbf{E} \in \mathbb{R}^{\lvert V \rvert \times d_{\text{model}}},

one row per entry and $d_{\text{model}}$ columns, with row $i$ equal to $\mathbf{e}_{w_i}^{\top}$ , transposed because vectors are columns in this course.

Looking up an entry's vector then looks like a memory access and not a mathematical operation. The two coincide, and seeing it takes one line. Multiply the one-hot vector from the lesson on one-hot encoding by the matrix and look at coordinate $j$ of the result:

\left(\mathbf{o}_{w_i}^{\top}\mathbf{E}\right)_j = \sum_{k=1}^{\lvert V \rvert} (\mathbf{o}_{w_i})_k \, \mathbf{E}_{kj} = \mathbf{E}_{ij},

because the only summand that does not vanish is the one for $k = i$ , where the one-hot is $1$ . Coordinate by coordinate, what comes out is row $i$ :

\mathbf{e}_{w_i}^{\top} = \mathbf{o}_{w_i}^{\top}\mathbf{E}.

The one-hot does not disappear, then: it becomes the index a row is read with. In practice no one builds the 50,000 coordinates to multiply them (you write E[i]), and even so the operation being performed is a matrix product. A whole text inherits the computation: that lesson turned $T$ tokens into $\mathbf{X} \in \mathbb{R}^{T \times \lvert V \rvert}$ , one one-hot row per position, and multiplying by $\mathbf{E}$ gives

\mathbf{X}\mathbf{E} \in \mathbb{R}^{T \times d_{\text{model}}},

the same sentence written with 300 columns instead of 50,000.

The three demands from the lesson on the problem of representing language still hold. The dimension is fixed, $d_{\text{model}}$ for every entry. Determinism comes from $\mathbf{E}$ being frozen once training ends. And totality is still given by <UNK>, which has its row like any other entry, as in the lesson on vocabulary and out-of-vocabulary words.

What does change is the price of the table. It is

\lvert V \rvert \cdot d_{\text{model}} \quad \text{numbers},

against the $\lvert V \rvert^{2}$ of one-hot: 15 million against 2,500 million, about 60 MB instead of 10 GB. The comparison is real and it is not the argument: the one-hot table is the identity and is never stored. What is gained is that the vector the system receives has 300 coordinates and not 50,000, every one of them carrying information.

What letting two entries lie close buys

With dense vectors there is geometry again, and this time it is not inherited from an alphabetical order that knows nothing of meanings. The measure is the previous lesson's, cosine similarity, which there compared documents and here compares entries:

\cos(\mathbf{e}_u, \mathbf{e}_v) = \frac{\mathbf{e}_u^{\top}\mathbf{e}_v}{\lVert \mathbf{e}_u \rVert \, \lVert \mathbf{e}_v \rVert}.

One thing changes when the object changes. TF-IDF weights were never negative, so the cosine lived in $[0, 1]$ ; the coordinates of a dense vector are arbitrary reals, the dot product can come out negative and the cosine runs over the whole of $[-1, 1]$ . Zero stops being the minimum and comes to mean "no relation", with the negatives pointing in opposite directions.

The contrast with one-hot closes the argument. There, two distinct entries always gave dot product $0$ and distance $\sqrt{2}$ , a single value without exception. Here the cosine can be anything, and what it is depends on the numbers in $\mathbf{E}$ : the equidistance is broken, and breaking it was the condition for everything else.

With that, the argument that lesson could not use becomes available: high-dimensional representations are saved because they have a neighbourhood (two photographs that differ in one pixel are alike), and one-hot could not appeal to that because in it there are no neighbours. With dense vectors there are: if $\mathbf{e}_{\textit{boy}}$ and $\mathbf{e}_{\textit{girl}}$ point in almost the same direction, the window the girl plays in the square stops being unknown territory for a model that has only seen the boy plays in the square. Why a similar entry produces a similar output is the business of Block 2, on the multilayer perceptron; what is needed here is that the representation make the resemblance possible.

And here is the concession, and it is a large one. Nothing above says the coordinates of $\mathbf{E}$ mean anything: fill the matrix with random numbers and you will have dense 300-dimensional vectors, with the wrong neighbours. Density makes it possible for superb and magnificent to end up close; it does not bring them close. What brings them close is the numbers, and no one has set them yet.

The hypothesis the numbers come from

They are 15 million and there is no human way to write them: fixing the 300 coordinates of a single entry by hand is already dubious (what is the third coordinate of flour worth?), and there are 50,000 entries. An automatic procedure has to set them from text, and for one to exist there first has to be a hypothesis about where, in a corpus, the information about meaning lies.

The distributional hypothesis is that hypothesis: two entries that appear surrounded by the same entries tend to mean similar things. It is almost always cited in Firth's line: you shall know a word by the company it keeps. It can be checked with a couple of blanks. In she poured a glass of ___, a bottle of ___ on the table and the ___ was cold, wine and juice fit, and hammer and Monday do not. No one has said what wine and juice mean; what has been looked at is the company they keep.

What the hypothesis buys is a change of question. Asking what an entry means gets you nowhere by counting; asking what it appears with is answered by walking the corpus, without anyone having to note it down first: the raw text already carries the answer. Meaning stops being something you enter by hand and becomes something you measure.

Look, too, at what the hypothesis does not say, because the block's limits come from there. It does not say that two entries with the same context are synonyms: cold and hot appear in almost identical contexts and mean the opposite, and a representation built this way places them close. And it is not a theorem but an empirical bet, worth whatever its results are worth. They turn out to be worth a great deal.

Dense vectors in NumPy: the lookup, the cosine and the neighbours

The cell builds a matrix $\mathbf{E}$ of eight entries with $d_{\text{model}} = 4$ and checks what the derivation above claims against it. I put its numbers in by hand (with 50,000 entries it would be impossible, and that is the open problem), and at this scale they serve to show the mechanics. Run it and look at three things: that the product with the one-hot returns the row, what the matrix of cosines looks like against the one-hot's, and how many numbers each table takes up.

import numpy as np

V = ["<UNK>", "car", "automobile", "truck", "flour", "sugar", "cat", "dog"]
d_model = 4

# I put the numbers in E by hand. Nothing here is trained yet.
E = np.array([
  [ 0.12,  0.09,  0.11,  0.95],   # <UNK>
  [ 0.91, -0.28,  0.19,  0.06],   # car
  [ 0.86, -0.21,  0.27,  0.10],   # automobile
  [ 0.79, -0.16,  0.12,  0.24],   # truck
  [-0.22,  0.88,  0.07,  0.13],   # flour
  [-0.31,  0.86,  0.10,  0.05],   # sugar
  [ 0.06,  0.13,  0.93, -0.11],   # cat
  [ 0.03,  0.19,  0.87, -0.05],   # dog
])
print("E has shape", E.shape, " ->  one row per entry,", d_model, "columns")
print()

# The lookup IS a product with the one-hot, which is why no one builds the one-hot.
i = V.index("car")
o = np.zeros(len(V))
o[i] = 1.0
print("o_car @ E =", o @ E)
print("E[i]      =", E[i])
print("equal:", np.array_equal(o @ E, E[i]))
print()

# Cosine between all entries: normalise the rows and multiply by the transpose.
U = E / np.linalg.norm(E, axis=1, keepdims=True)
S = U @ U.T

print("cosine similarity")
print(" " * 10 + "".join(w[:6].rjust(7) for w in V))
for j, w in enumerate(V):
  print(w[:9].rjust(10) + "".join(("%+.2f" % S[j, k]).rjust(7) for k in range(len(V))))
print()

def neighbours(w, k=2):
  j = V.index(w)
  order = np.argsort(-S[j])
  return [(V[m], round(float(S[j, m]), 2)) for m in order if m != j][:k]

for w in ["car", "flour", "cat"]:
  print("neighbours of", w.ljust(9), neighbours(w))
print()

# The same computation on one-hot, the previous representation.
O = np.eye(len(V))
off_diagonal = O @ O.T - np.eye(len(V))
print("one-hot: the largest cosine between two distinct entries is", off_diagonal.max())
print()

# What each table takes up. Computed, NOT allocated.
print("   |V|  d_model      E: |V|*d_model     one-hot: |V|^2")
for size, dm in [(8, 4), (50000, 300)]:
  print(str(size).rjust(6), str(dm).rjust(8), str(size * dm).rjust(18), str(size * size).rjust(20))

numpy

The first run downloads the Python interpreter (~15 MB). After that it stays in the browser cache and is reused across every lesson.

The lookup comes out exact: o @ E and E[i] are the same vector coordinate by coordinate, which is what the derivation promised. The matrix of cosines is the thing to look at. car with automobile gives $0.99$ and with truck $0.97$ ; with flour it gives $-0.48$ , a negative value that in one-hot could not exist; cat with <UNK> gives $0.02$ , which is "nothing in common" written in numbers. Below, the same computation on one-hot returns a zero in every off-diagonal cell: the "single value" of the lesson on one-hot encoding, now next to a matrix that has some relief to it.

One unvarnished detail: the second neighbour of cat is automobile, at $0.30$ . It is noise, and it is there because I made the numbers up: with four coordinates and eight entries there is no room for more. With 300 coordinates and a corpus behind it, that second neighbour would be another animal.

A thirty-second test. Copy car's row into flour's, changing a couple of decimals, and run it again: flour goes off with the vehicles, without anyone having touched the vocabulary or the shape of the table. The representation is not in the table, it is in its numbers.

Test your intuition

Four questions on what you now have: what the product with the one-hot computes, what density buys, what happens to the cosine when the object changes, and what exactly the distributional hypothesis claims.

You store the vectors in the matrix $\mathbf{E} \in \mathbb{R}^{\lvert V \rvert \times d_{\text{model}}}$ and you want the one for the entry at position $i$ . What does $\mathbf{o}_{w_i}^{\top}\mathbf{E}$ compute?

Row

i

\mathbf{E}

, which is

\mathbf{e}_{w_i}^{\top}

.Column

i

\mathbf{E}

, a vector of

\lvert V \rvert

coordinates.Another vector of

\lvert V \rvert

coordinates with a single one, the same as

\mathbf{o}_{w_i}

.A combination of all the rows of

\mathbf{E}

that matches no particular row.

You swap one-hot for dense vectors of $d_{\text{model}} = 300$ over a vocabulary of $\lvert V \rvert = 50\,000$ entries. What is gained? Tick all that apply.

Select every correct option. This is graded all-or-nothing: there is no partial credit.

Two entries can end up close, so that what is learned about one can serve the other.The table goes from

\lvert V \rvert^{2}

\lvert V \rvert \cdot d_{\text{model}}

numbers, and the vector stops being almost all zeros.The coordinates come to mean something by the mere fact of being few and all filled.There is no longer any need to fix the vocabulary in advance, because no coordinate is assigned to an entry.

Between two TF-IDF vectors the cosine similarity lived in $[0, 1]$ . Between two dense vectors it can come out negative.

TrueFalse

What exactly does the distributional hypothesis claim?

That two entries surrounded by the same entries tend to mean similar things, so that the resemblance can be measured by counting company.That two entries that appear in the same sentence mean the same thing.That two synonyms appear together, in the same document, far more often than you would expect.That each coordinate of

\mathbf{e}_w

corresponds to a feature of the meaning (gender, number, whether it is a living thing), and that is why the vectors can be read.

The object is now defined, and with it half of what the lesson on one-hot encoding left pending: 300 coordinates instead of 50,000, all carrying information, and a geometry where two entries can lie close. The other half is still open: the matrix $\mathbf{E}$ is 15 million numbers, and everything you have seen holds equally well for an $\mathbf{E}$ full of noise. The distributional hypothesis says where to look, at the company each entry keeps, but looking is not a procedure: from counting contexts to fixing 300 coordinates there is a leap no one has made yet.

Taking it is the lesson on Word2Vec. There, instead of counting contexts, Word2Vec trains a model to predict them, and uses as the embedding the numbers that let it succeed: skip-gram predicts the context from the entry, and CBOW (continuous bag of words) does the reverse. Both stumble on the same stone the moment you write them out with care, and it is a big one: sharing probability out among the possible entries forces a sum over all 50,000, once for every (entry, context) pair in the corpus. Getting that sum out of the way takes up half a lesson.