Vectors: Arrows, Lists and Data

How this course works

In Mathematics for Machine Learning you learned to read the symbols: a bold $\mathbf{x}$ for a vector, $\mathbb{R}^n$, $\sum$, the transpose $\top$. This course is about what those objects do. Linear algebra is the mathematics of vectors and matrices, and nearly every model in machine learning is built from it. An image is a vector, a layer of a neural network is a matrix, and training a model means moving one very long vector of parameters around.

You don't need any linear algebra to start. Each idea arrives geometry first (a picture you can drag), then as algebra (rules you can compute with), then with a derivation or a proof (why the rules are true), and always with a link back to machine learning.

Every chamber runs the research loop you met in the first course:

Each chamber has an interactive lab with a challenge, proofs to assemble and to write, three coding problems in the style of Project Euler, and at least one decoder for an equation from a real paper. The checkpoint at the end clears the chamber. Nine chambers from now, Talos, the bronze giant who guarded Crete, is waiting.

Discover: arithmetic with words

In 2013, three researchers at Microsoft Research looked closely at the numbers a language model had learned. The model had turned every word in its vocabulary into a list of numbers (up to 1,600 of them) only to help it predict the next word in a sentence. But when the researchers did arithmetic with those lists, the arithmetic made sense.

To answer the analogy “$a$ is to $b$ as $c$ is to what?”, the paper takes the lists for the three words, computes $y = x_b - x_a + x_c$, and looks for the word whose list is closest to $y$. With $a$ = man, $b$ = king and $c$ = woman, the abstract reports that king − man + woman gives a vector very close to queen.

How do you subtract a word? You can't. But you can subtract one list of numbers from another, entry by entry. That is the first idea of this chamber: a vector is a list of numbers that you can add, subtract and scale, and it is also an arrow you can draw. (The paper writes its vectors in plain italics, $x_b$. This course writes them in bold, $\mathbf{x}_b$, as the first course did.)

Try the arithmetic on vectors small enough to do by hand.

Learn: two views of one object

A vector has two faces, and much of the power of linear algebra comes from switching between them.

The arrow. A physicist's vector is an arrow: it has a length and a direction, and nothing else. Slide it anywhere and it's the same vector. In linear algebra we usually start every arrow at the origin, the point where the axes cross, so the arrow is pinned down by where its tip lands.

The list. A programmer's vector is an ordered list of numbers, like [3, 1]. Order matters: $(3, 1)$ and $(1, 3)$ are different vectors.

The bridge between the two is coordinates. The list $(3, 1)$ says: from the origin, walk 3 units along the first axis and 1 unit along the second. The arrow ends there. We write vectors as columns,

read “v is the column vector three, one, in R two”. In running text we save space and write $\mathbf{v} = (3, 1)$. The numbers $v_1 = 3$ and $v_2 = 1$ are the vector's components, or entries.

$\mathbb{R}^2$ is the plane: every list of two real numbers. $\mathbb{R}^3$ is ordinary three-dimensional space, and $\mathbb{R}^n$ is every list of $n$ real numbers. You can't draw an arrow in $\mathbb{R}^{784}$, but you don't need to. Every rule in this chamber works one entry at a time, so it works in 784 dimensions exactly as it does in 2. Draw in 2D, then trust the algebra in any number of dimensions.

An arrow doesn't have to start at the origin. The arrow from point $P$ to point $Q$ is written $\overrightarrow{PQ}$, and its components are “destination minus start”. From $P = (1, 2)$ to $Q = (4, 0)$, it's $\overrightarrow{PQ} = (4 - 1, 0 - 2) = (3, -2)$: three right and two down.

Learn: adding, scaling and subtracting

Adding two vectors means one thing in each view, and the two agree.

• As lists: add entry by entry, so $(3, 1) + (1, 2) = (4, 3)$.
• As arrows: put the tail of the second arrow at the tip of the first, tip to tail. The sum runs from the start of the first to the tip of the second.

Why do they agree? Walking along $(3, 1)$ takes you 3 right and 1 up. Walking along $(1, 2)$ from there takes you 1 more right and 2 more up. In total you've gone $3 + 1$ right and $1 + 2$ up. Walking the two arrows in the other order traces the other two sides of a parallelogram and ends at the same corner, which is why $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$.

Scaling a vector by a number $c$ multiplies every entry by $c$: $c\,\mathbf{v} = (c v_1, c v_2)$. Geometrically it stretches the arrow by a factor $|c|$ and turns it round if $c$ is negative. So $2\mathbf{v}$ is twice as long, $\tfrac{1}{2}\mathbf{v}$ is half as long, and $-\mathbf{v}$ has the same length but points the opposite way. Ordinary numbers like $c$ are called scalars, because they scale.

Two more pieces complete the kit. The zero vector $\mathbf{0} = (0, 0)$ is the arrow that goes nowhere, and adding it changes nothing. Subtraction is adding a negative: $\mathbf{u} - \mathbf{v} = \mathbf{u} + (-\mathbf{v})$.

Subtraction has a picture worth memorising. Draw $\mathbf{u}$ and $\mathbf{v}$ from the origin. Then $\mathbf{u} - \mathbf{v}$ is the arrow from the tip of $\mathbf{v}$ to the tip of $\mathbf{u}$, because $\mathbf{v} + (\mathbf{u} - \mathbf{v}) = \mathbf{u}$. It's the “destination minus start” rule again. A difference of two vectors tells you how to get from one to the other, and that's what the word-vector paper measures: $\mathbf{x}_{\text{king}} - \mathbf{x}_{\text{man}}$ is the step from “man” to “king”.

A worked example, with $\mathbf{u} = (2, -1)$ and $\mathbf{v} = (1, 3)$:

Learn: linear combinations

Put scaling and adding together and you get the central construction of linear algebra. A linear combination of $\mathbf{u}$ and $\mathbf{v}$ is any vector of the form

where the scalars $a$ and $b$ are called coefficients. With more vectors the idea is the same, written with the sum notation from Chamber 5 of the first course:

It's called linear because you only scale and add: no squaring, and no multiplying vectors together. Think of the vectors as ingredients and the coefficients as how much of each goes in.

Here's the question the lab asks. Given $\mathbf{u}$, $\mathbf{v}$ and a target point, which coefficients land on it exactly? Steer with the sliders first, then read on for the algebra.

Things to try:

1. Reach all three targets. One of them needs a coefficient that isn't a whole number.
2. Drag $\mathbf{v}$ until it lies along the same line as $\mathbf{u}$, for example $\mathbf{v} = (-3, -1)$. How much of the grid can you reach now?
3. Make $\mathbf{u}$ the zero vector. What's left?

Learn: finding the coefficients

Guessing is fine in a lab, but not in a space with 784 dimensions. So let's derive the coefficients once and for all in $\mathbb{R}^2$. We want numbers $a$ and $b$ with

1. 1

   One equation per component

   Two vectors are equal when every component is equal, so the vector equation is two ordinary equations:

   $$a u_1 + b v_1 = t_1, \qquad a u_2 + b v_2 = t_2 .$$
2. 2

   Eliminate b

   Multiply the first equation by $v_2$ and the second by $v_1$:

   $$a u_1 v_2 + b v_1 v_2 = t_1 v_2, \qquad a u_2 v_1 + b v_1 v_2 = t_2 v_1 .$$

   Subtract the second from the first. The $b$ terms cancel, leaving

   $$a\,(u_1 v_2 - u_2 v_1) = t_1 v_2 - t_2 v_1 .$$
3. 3

   Eliminate a

   Now multiply the first equation by $u_2$ and the second by $u_1$, and subtract the first from the second. This time the $a$ terms cancel:

   $$b\,(u_1 v_2 - u_2 v_1) = u_1 t_2 - u_2 t_1 .$$
4. 4

   Divide, if you can

   Both results contain the same number, $D = u_1 v_2 - u_2 v_1$. If $D \neq 0$, divide by it:

   $$a = \frac{t_1 v_2 - t_2 v_1}{D}, \qquad b = \frac{u_1 t_2 - u_2 t_1}{D}.$$

Check it on $\mathbf{u} = (2, 1)$, $\mathbf{v} = (1, 3)$ and the target $(4, 7)$. Here $D = 2 \cdot 3 - 1 \cdot 1 = 5$, so $a = (4 \cdot 3 - 7 \cdot 1)/5 = 1$ and $b = (2 \cdot 7 - 1 \cdot 4)/5 = 2$. Indeed, $\mathbf{u} + 2\mathbf{v} = (2 + 2, 1 + 6) = (4, 7)$.

And when is $D = 0$? You can check that it happens exactly when one vector is a multiple of the other, so that both lie on one line through the origin. Then every combination stays on that line, and targets off it can't be reached: the lab showed you this. Hold on to the number $D$. It returns in Chamber 5 as the determinant, where it measures the area of the parallelogram that $\mathbf{u}$ and $\mathbf{v}$ span.

Learn: the standard basis

Two vectors in $\mathbb{R}^2$ deserve names of their own:

They are one step along each axis. Every vector is a combination of them, and the coefficients are simply its components:

$\mathbb{R}^n$ has $n$ of them: $\mathbf{e}_i$ has a 1 in position $i$ and 0 everywhere else. Together they're called the standard basis (Chamber 3 explains what a basis is in general), and they reveal what the list view of a vector really is:

The components of $\mathbf{x}$ are its coefficients in the standard basis. That deserves a proof, because it's really two promises.

Claim. Every vector $\mathbf{x} \in \mathbb{R}^n$ can be written as a linear combination of $\mathbf{e}_1, \ldots, \mathbf{e}_n$, and in exactly one way.

We need one fact about the basis vectors. The $j$-th entry of $\mathbf{e}_i$ is the Kronecker delta $\delta_{ij}$ from Chamber 4 of the first course: 1 if $i = j$, and 0 otherwise.

Proof. Existence. Use the components of $\mathbf{x}$ as the coefficients. The $j$-th entry of $\sum_i x_i\,\mathbf{e}_i$ is $\sum_i x_i\,\delta_{ij}$. Every term of that sum is zero except the one with $i = j$, so the $j$-th entry is $x_j$. That holds for every $j$, so $\sum_i x_i\,\mathbf{e}_i = \mathbf{x}$.

Uniqueness. Now suppose some numbers $c_1, \ldots, c_n$ also work: $\mathbf{x} = \sum_i c_i\,\mathbf{e}_i$. By the same calculation, the $j$-th entry of the right-hand side is $c_j$. Two vectors are equal only when all their entries are equal, so $c_j = x_j$ for every $j$. Any combination that works uses exactly the coefficients we already had. $\blacksquare$

Notice the shape of the argument. “There is one” and “there is only one” are separate claims, and each needs its own proof. Uniqueness proofs nearly always go like the second half: suppose there's another answer, then show it's forced to equal the first.

Learn: the rules of the game

Everything you've done with vectors rests on a short list of rules. For all vectors $\mathbf{u}$, $\mathbf{v}$, $\mathbf{w}$ and scalars $a$, $b$:

For lists of numbers, each rule follows from the matching rule for ordinary numbers, applied one entry at a time. For example, the $i$-th entry of $a(\mathbf{u} + \mathbf{v})$ is $a(u_i + v_i) = a u_i + a v_i$, which is the $i$-th entry of $a\mathbf{u} + a\mathbf{v}$.

Now the mathematician's move. Any collection of objects that can be added and scaled while obeying these eight rules is called a vector space, and every theorem proved from the rules alone holds in all of them at once. Polynomials qualify: you can add two polynomials and scale one, and the rules hold. So do sound recordings and images, added sample by sample or pixel by pixel. That's why one body of theory serves so many kinds of data. You'll use the rules, lightly, in this chamber's proofs.

Learn: data as vectors

Machine learning's first move, almost always, is to turn data into vectors, so that everything above applies.

• Images. A greyscale MNIST digit is 28 by 28 pixels, each a brightness value. Read the pixels row by row into one list and the image becomes a vector in $\mathbb{R}^{784}$. Brightening an image scales it, blending two images is a linear combination, and the “average digit” is the combination with every coefficient equal to $\tfrac{1}{n}$.
• Ratings. If a streaming service has 10,000 films, a user can be a vector in $\mathbb{R}^{10000}$: their rating of each film. Chamber 2 shows how a recommender system learns a much shorter vector for every user and every film, and predicts ratings from them.
• Features. A house can be $(\text{floor area}, \text{bedrooms}, \text{age}) \in \mathbb{R}^3$. A table of data is a stack of such feature vectors, one per row.
• Words. A word has no natural numbers attached, so we learn some. An embedding gives each word a vector, and training adjusts the vectors until words used in similar ways end up with similar vectors. The pre-trained vectors released with Google's word2vec tool give each of 3 million words and phrases a vector of 300 numbers.

Now the analogy from the start of the chamber makes sense. Suppose the step from “man” to “woman” is roughly the same wherever you take it, so that

Add $\mathbf{x}_{\text{king}}$ to both sides and you get $\mathbf{x}_{\text{queen}} \approx \mathbf{x}_{\text{king}} - \mathbf{x}_{\text{man}} + \mathbf{x}_{\text{woman}}$, which is exactly $y = x_b - x_a + x_c$. The four words sit at the corners of a rough parallelogram. The paper's first example is grammatical rather than royal: $x_{\text{apple}} - x_{\text{apples}} \approx x_{\text{car}} - x_{\text{cars}}$, one offset for “singular to plural”.

Read beyond the course

Each of these takes the ideas of this chamber a little further, and each is free.

Papers and lectures

The paper from the start of this chamber is short (six pages) and more readable than most. Read the abstract, then the paragraph of Section 1 that begins “In this work”, with the apples and cars. Then read Section 5, “The Vector Offset Method”, which is half a column long, and look at Figure 2, which draws the offsets as arrows. Skip Section 3, which describes the recurrent neural network that produced the vectors, and glance at Table 2 only to see that the network's longer vectors answered more analogies correctly. Section 5 contains one formula you can't read yet, a cosine similarity. You'll meet it in Chamber 2.

Later that year, Mikolov and colleagues at Google published a faster way to train word vectors, the word2vec method. Its Equation 2 shows where the vectors come from. Read Section 1 and the first page of Section 2, up to and including Equation 2. The rest of Section 2 (hierarchical softmax and negative sampling) is engineering you can come back to.

Watch

Grant Sanderson's Essence of linear algebra is the classic visual introduction to the subject, and this first episode covers this chamber in ten minutes. Watch for his three perspectives on what a vector is (the physics student's, the computer science student's and the mathematician's), and for how he pictures addition and scaling as movements.

Your turn

If you haven't cleared the lab's challenge yet, it's waiting in the Learn section. Here, match arrows to lists and maths to code, assemble a proof and write one, then solve three problems in code.

Proofs

The first proof shows that combining combinations never gets you anything new, an idea Chamber 3 builds on. The second is a classic of geometry that vectors make short.

Code it up

Each problem has exactly one answer. Write a few lines of Python, on your own machine or in the runner under each problem, and submit the number. The second applies the vector offset method from the paper; the third rewards the uniqueness proof from this chamber.