Dot Products, Lengths and Angles

Discover: a million-dollar multiplication

In 2006, Netflix offered a million dollars to anyone who could predict its customers' film ratings 10% more accurately than its own system. The prize was won in 2009, and three members of the winning team explained one of its key ideas in a magazine article. The idea fits on one line:

Read it as “r hat u i equals q i transpose p u”. $\hat{r}_{ui}$ is the predicted rating of user $u$ for item $i$ (the hat marks an estimate, as in the first course). Each item gets a vector $q_i$ and each user a vector $p_u$, with the same number of entries, $f$. The paper suggests 20 to 100. Each entry measures a “factor”: how much of some quality a film has, and how much the user likes that quality. The factors are learned from the ratings. Some may be recognisable, such as comedy versus drama or the amount of action, and others have no obvious meaning at all. The article's own sketch uses two, placing films from serious to escapist on one axis, and predicts that a user called Gus will love Dumb and Dumber.

And $q_i^T p_u$? You met the transpose notation in Chamber 6 of the first course. It says: multiply matching entries of the two vectors and add them up. Try it.

That operation is the dot product. It looks like bookkeeping, but it turns out to measure three things at once: how long vectors are, the angle between them, and how much they agree. This chamber shows how, and why the same multiplication sits inside recommenders, search engines and transformers.

Learn: the dot product

The dot product of two vectors in $\mathbb{R}^n$ multiplies matching entries and adds:

Read it “u dot v”. The result is a single number, a scalar, which is why it's also called the scalar product. For example,

The same number goes by several names in papers. Machine learning prefers $\mathbf{u}^\top \mathbf{v}$, “u transpose v”: a row times a column, which is exactly the sum above. Mathematicians often write $\langle \mathbf{u}, \mathbf{v} \rangle$, the inner product. Koren's $q_i^T p_u$ is the same thing again, with a plain $T$ for the transpose.

The dot product obeys a few rules. Each one follows from ordinary arithmetic, one entry at a time.

• Symmetry: $\mathbf{u} \cdot \mathbf{v} = \mathbf{v} \cdot \mathbf{u}$, since $u_i v_i = v_i u_i$.
• It distributes over addition: $\mathbf{u} \cdot (\mathbf{v} + \mathbf{w}) = \mathbf{u} \cdot \mathbf{v} + \mathbf{u} \cdot \mathbf{w}$.
• Scalars come out: $(c\,\mathbf{u}) \cdot \mathbf{v} = c\,(\mathbf{u} \cdot \mathbf{v})$.
• A vector dotted with itself is never negative: $\mathbf{v} \cdot \mathbf{v} = \sum_i v_i^2 \ge 0$, and it is zero only when every $v_i$ is zero, that is, when $\mathbf{v} = \mathbf{0}$.

The last rule is the doorway to length.

Learn: length, distance and three norms

In the plane, the arrow $\mathbf{v} = (v_1, v_2)$ is the long side of a right-angled triangle whose other sides are $v_1$ and $v_2$. Pythagoras gives its length as $\sqrt{v_1^2 + v_2^2}$. In three dimensions, apply Pythagoras twice: the diagonal across the floor has length $\sqrt{v_1^2 + v_2^2}$, and it forms a right angle with the vertical side $v_3$, so the full length is $\sqrt{v_1^2 + v_2^2 + v_3^2}$. The pattern continues, and in $\mathbb{R}^n$ we take it as the definition of the length, or norm:

So $\lVert (3, 4) \rVert = \sqrt{9 + 16} = 5$. The double bars are read “the norm of v”. Two consequences get used constantly:

• Scaling scales the length: $\lVert c\,\mathbf{v} \rVert = |c|\,\lVert \mathbf{v} \rVert$. So dividing a non-zero vector by its own length gives a unit vector, of length 1, pointing the same way: $\hat{\mathbf{v}} = \mathbf{v} / \lVert \mathbf{v} \rVert$. This is called normalising. For $(3, 4)$, $\hat{\mathbf{v}} = (0.6, 0.8)$.
• Distance is the length of a difference. The distance between the tips of $\mathbf{u}$ and $\mathbf{v}$ is $\lVert \mathbf{u} - \mathbf{v} \rVert$, the length of the arrow between them (Chamber 1). Between $(1, 2)$ and $(4, 6)$ it's $\lVert (3, 4) \rVert = 5$.

Euclidean length isn't the only useful way to measure a vector. Machine learning uses three regularly, each written with a subscript:

With no subscript, $\lVert \mathbf{v} \rVert$ almost always means $\ell_2$. Each norm has its own “unit circle”, the set of vectors of length 1. For $\ell_2$ it's the ordinary circle; for $\ell_1$ it's a diamond with corners on the axes; for $\ell_\infty$ it's a square.

What makes something a norm? Three properties, true of all three:

1. $\lVert \mathbf{v} \rVert \ge 0$, and $\lVert \mathbf{v} \rVert = 0$ only for $\mathbf{v} = \mathbf{0}$.
2. $\lVert c\,\mathbf{v} \rVert = |c|\,\lVert \mathbf{v} \rVert$.
3. The triangle inequality: $\lVert \mathbf{u} + \mathbf{v} \rVert \le \lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert$. Going straight is never longer than going round. You'll prove it for $\ell_2$ at the end of this chamber.

Learn: the angle between two vectors

Here is the surprise. The dot product, defined by multiplying entries, also knows the angle between two arrows. Let's derive the connection.

Draw $\mathbf{u}$ and $\mathbf{v}$ from the origin, with angle $\theta$ (theta) between them. The arrow from the tip of $\mathbf{v}$ to the tip of $\mathbf{u}$ is $\mathbf{u} - \mathbf{v}$, so the three arrows form a triangle with sides of length $\lVert \mathbf{u} \rVert$, $\lVert \mathbf{v} \rVert$ and $\lVert \mathbf{u} - \mathbf{v} \rVert$.

1. 1

   The law of cosines

   For any triangle with sides $a$ and $b$ meeting at angle $\theta$, the third side $c$ satisfies $c^2 = a^2 + b^2 - 2ab\cos\theta$. (When $\theta = 90°$, $\cos\theta = 0$ and this is Pythagoras.) For our triangle:

   $$\lVert \mathbf{u} - \mathbf{v} \rVert^2 = \lVert \mathbf{u} \rVert^2 + \lVert \mathbf{v} \rVert^2 - 2\,\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert \cos\theta .$$
2. 2

   Expand the left side with the dot product

   Squared length is a dot product with itself. Distribute, and use symmetry to merge the two middle terms:

   $$\lVert \mathbf{u} - \mathbf{v} \rVert^2 = (\mathbf{u} - \mathbf{v}) \cdot (\mathbf{u} - \mathbf{v}) = \mathbf{u} \cdot \mathbf{u} - 2\,\mathbf{u} \cdot \mathbf{v} + \mathbf{v} \cdot \mathbf{v} = \lVert \mathbf{u} \rVert^2 - 2\,\mathbf{u} \cdot \mathbf{v} + \lVert \mathbf{v} \rVert^2 .$$
3. 3

   Compare

   The two right-hand sides are equal. Cancel $\lVert \mathbf{u} \rVert^2$ and $\lVert \mathbf{v} \rVert^2$ from both, then divide by $-2$:

   $$\mathbf{u} \cdot \mathbf{v} = \lVert \mathbf{u} \rVert \, \lVert \mathbf{v} \rVert \cos\theta .$$

So for non-zero vectors,

Lengths are positive, so the sign of the dot product is the sign of $\cos\theta$, and it tells you the kind of angle at a glance:

Orthogonality is the most useful case, because testing it needs no square roots and no cosines: two vectors are at right angles exactly when their dot product is zero. For example, $(2, 1) \cdot (-1, 2) = -2 + 2 = 0$. (By convention, $\mathbf{0}$ counts as orthogonal to everything.)

The lab shows all of it live. The panel computes $\mathbf{u} \cdot \mathbf{v}$ term by term; the marker at the origin is a blue arc when the angle is acute, a green square at a right angle and a red arc when it's obtuse.

Things to try:

1. Find two vectors at right angles with every component non-zero. (The challenge.) Is there a quick recipe that turns any $(a, b)$ into a vector orthogonal to it?
2. Set $\mathbf{u} = (2, 1)$, note the dot product and the angle, then double $\mathbf{u}$ to $(4, 2)$. The dot product doubles. What happens to the angle?
3. Make the angle obtuse and watch the violet projection flip to point away from $\mathbf{v}$.

One question should be nagging you. The derivation used a triangle, and triangles are drawn in the plane. What does “the angle between two vectors in $\mathbb{R}^{300}$” mean? In higher dimensions we turn the result around and define the angle by $\cos\theta = \frac{\mathbf{u} \cdot \mathbf{v}}{\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert}$. But that only makes sense if the fraction is always between $-1$ and $1$, because no angle has a cosine of 1.3. Is it? That's the most important inequality in this course.

Learn: the Cauchy–Schwarz inequality

Theorem (Cauchy–Schwarz). For all $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$,

$|\mathbf{u} \cdot \mathbf{v}| \le \lVert \mathbf{u} \rVert \, \lVert \mathbf{v} \rVert ,$

with equality exactly when one of the vectors is a multiple of the other.

Dividing both sides by $\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$ gives $-1 \le \cos\theta \le 1$, which is exactly what we need. The proof uses one idea you already know, that a squared length can't be negative, and one clever choice.

Proof. If $\mathbf{v} = \mathbf{0}$, both sides are 0 and there's nothing to prove. So suppose $\mathbf{v} \ne \mathbf{0}$. For every real number $t$, the vector $\mathbf{u} - t\,\mathbf{v}$ has a length, and its square is not negative. Expanding with the rules of the dot product:

This holds for every $t$, so we may pick the most useful one: $t = \dfrac{\mathbf{u} \cdot \mathbf{v}}{\lVert \mathbf{v} \rVert^2}$. Substituting,

Multiply both sides by the positive number $\lVert \mathbf{v} \rVert^2$ and rearrange: $(\mathbf{u} \cdot \mathbf{v})^2 \le \lVert \mathbf{u} \rVert^2 \lVert \mathbf{v} \rVert^2$. Both sides are non-negative, so taking square roots keeps the inequality: $|\mathbf{u} \cdot \mathbf{v}| \le \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$.

For the equality case: if $|\mathbf{u} \cdot \mathbf{v}| = \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$, every step above is an equality, so $\lVert \mathbf{u} - t\,\mathbf{v} \rVert^2 = 0$ for our chosen $t$. Only the zero vector has length 0, so $\mathbf{u} = t\,\mathbf{v}$. Conversely, if $\mathbf{u} = c\,\mathbf{v}$ then both sides equal $|c|\,\lVert \mathbf{v} \rVert^2$. (If $\mathbf{v} = \mathbf{0}$, then $\mathbf{v} = 0\,\mathbf{u}$ is a multiple of $\mathbf{u}$.) $\blacksquare$

Where did that value of $t$ come from? The expression $\lVert \mathbf{u} \rVert^2 - 2t\,(\mathbf{u} \cdot \mathbf{v}) + t^2 \lVert \mathbf{v} \rVert^2$ is a parabola in $t$, and school algebra puts its lowest point at $t = \frac{\mathbf{u} \cdot \mathbf{v}}{\lVert \mathbf{v} \rVert^2}$. We chose the $t$ that makes $\mathbf{u} - t\,\mathbf{v}$ as short as possible, so the inequality “squared length $\ge 0$” is as sharp as it can be. Remember that $t$: it comes straight back in the next section.

Learn: projection, a preview

Shine a light straight down onto the line through $\mathbf{v}$, and $\mathbf{u}$ casts a shadow on it. That shadow is the projection of $\mathbf{u}$ onto $\mathbf{v}$:

The coefficient is exactly the $t$ from the proof: the multiple of $\mathbf{v}$ that comes closest to $\mathbf{u}$. And the leftover part, $\mathbf{u} - t\,\mathbf{v}$, is at right angles to $\mathbf{v}$, because

For example, with $\mathbf{u} = (3, 4)$ and $\mathbf{v} = (2, 1)$: $t = \frac{6 + 4}{4 + 1} = 2$, so the projection is $(4, 2)$, and the leftover $(3, 4) - (4, 2) = (-1, 2)$ satisfies $(-1, 2) \cdot (2, 1) = 0$. The lab draws the projection as the violet arrow and the leftover as the dashed line: drag $\mathbf{u}$ and watch the dashed line stay perpendicular.

This also gives the dot product a second picture. Since $t\,\lVert \mathbf{v} \rVert = \lVert \mathbf{u} \rVert \cos\theta$, the dot product $\mathbf{u} \cdot \mathbf{v}$ is the (signed) length of the shadow of $\mathbf{u}$ times the length of $\mathbf{v}$. Chamber 7 extends projection from lines to whole subspaces, and turns it into least squares and linear regression.

Learn: cosine similarity, from search to attention

Divide a dot product by both lengths and you get cosine similarity:

Thanks to Cauchy–Schwarz it always lies between $-1$ and $1$: 1 for vectors pointing the same way, 0 for orthogonal ones, $-1$ for opposite ones. It ignores length entirely, which is often exactly right. In a vector of word counts, a long document has bigger numbers than a short one on the same topic. Normalising removes that, and leaves only the direction: what the document is about.

That's why Chamber 1's paper used it. Its analogy search, which you couldn't read then, is a cosine similarity:

“Find the word $w$ whose vector $x_w$ has the greatest cosine similarity with $y = x_b - x_a + x_c$.” Notice that the paper writes the dot product as $x_w y$, with no transpose at all. Papers are often relaxed about this, and now you can tell from context.

The same measure powers modern semantic search. Sentence-BERT (Reimers and Gurevych, 2019) trains a network to turn whole sentences into vectors that can be compared with cosine similarity, so that finding similar sentences becomes a matter of dot products between unit vectors.

Not every system normalises. Koren's recommender uses the raw dot product $q_i^T p_u$, so a longer vector counts for more, and transformer attention scores every query against every key with a raw dot product, $\mathbf{q}^\top \mathbf{k}$. In the attention formula you met in the first course, $QK^\top$ is simply a table of these dot products, and the division by $\sqrt{d_k}$ keeps them from growing with the dimension. Whether to normalise is a design choice, and now you know what each choice keeps.

Read beyond the course

The same ideas from four angles. Each one is free.

Papers and lectures

Koren, Bell and Volinsky wrote for a general computing magazine, so the article is eight pages with very little heavy mathematics. Read the section “A basic matrix factorization model”, which contains Equations 1 and 2, and look at Figure 2, the two-factor sketch. Then skim “Learning algorithms”: the stochastic gradient descent updates there use nothing but dot products, vector addition and scaling. Skip the later sections on biases, implicit feedback and time for now.

Sentence-BERT is a full research paper, but the parts you can read now are short. Read the abstract, then Section 3 up to and including “Regression Objective Function”, and look at Figure 2, where two sentence embeddings $u$ and $v$ meet in a box labelled cosine-sim(u, v). The triplet objective just after it compares Euclidean distances $\lVert s_a - s_p \rVert$: norms from this chamber. Skip the experiments.

Watch

The first part of this episode shows the dot product as projection: the length of one vector's shadow on the other, times the other's length, and why the order doesn't matter. Watch that part now and compare it with the projection section above. The second part, on duality, reads vectors as transformations: come back to it after Chamber 4.

Your turn

The lab's challenge is in the Learn section if you haven't cleared it. Here: measure two vectors every way this chamber knows, translate the formulas into NumPy, prove Pythagoras and the triangle inequality, and solve three problems, two of them straight from the papers.

Proofs

The puzzle proves Pythagoras' theorem for vectors in any number of dimensions. Then use Cauchy–Schwarz to prove the third property every norm must have.

Code it up

The second problem computes Koren's Equation 2 exactly as the paper writes it, and the third is a small version of the search that Sentence-BERT made fast.