Chapter 29

The Geometry of a Decision

Think back to the handwritten threes we tried in the first chapter. The reader recognized some immediately, hesitated over another, and confidently called one a five. To us, these were different ways of writing the same digit. What was the reader seeing that made it answer so differently?

We took the machine apart to find out. First, it measured the ink in $64$ blocks, turning a picture into a point in $ℝ 64$ . Then it gave that same list of measurements to ten scoring rules, one for each possible digit. Each rule multiplied the measurements by its own stored weights and added the results, together with a bias. Finally, the ten scores became probabilities, and the largest score supplied the answer.

We could follow every multiplication in that process. But there is still something surprising about it. Where, in all that arithmetic, is the shape of a three? How can multiplying ink measurements by a list of numbers help distinguish a three from a five?

Our first clue is the dot product. We have met it before as a way to measure angles and projections. Here it appeared as a way to calculate a score. These are two descriptions of the same operation! If we can connect them, we may be able to understand the reader's decisions geometrically.

Let's begin with an experiment. Keep the reader's stored numbers fixed, take one image, and add a little ink in a single block. What happens to its score for three?

29.1What Does One Weight Do?

Recall how that score is assembled:

𝑠 3 (𝑥) = 𝑤 3, 1 𝑥 1 + \dots + 𝑤 3, 𝑖 𝑥 𝑖 + \dots + 𝑤 3, 64 𝑥 64 + 𝑏 3 .

Here $𝑥 𝑖$ is the ink measurement in block $𝑖$ , $𝑤 3, 𝑖$ is the weight that the three's rule assigns to that block, and $𝑏 3$ is its bias. Increasing $𝑥 𝑖$ by $ℎ$ changes just one term in the sum:

𝑤 3, 𝑖 (𝑥 𝑖 + ℎ) - 𝑤 3, 𝑖 𝑥 𝑖 = ℎ 𝑤 3, 𝑖 .

Everything else cancels. So a positive weight means that adding ink in this block raises the score for three. A negative weight means that adding ink lowers it. A zero weight means that this score ignores the block altogether.

Notice that the other digits have their own weights for this same block. The same addition of ink might raise the score for three and lower the score for five. The image has changed once, but each scoring rule responds according to its own list of numbers.

Figure 29.1 Change one coordinate in a copy of the image. The resulting score change is exactly the coordinate change multiplied by its weight. Select another cell or another digit's score to inspect a different coefficient.

Now change several blocks at once. Collect their changes into a vector $⃗ 𝑣 = ⟨ 𝑣 1, \dots, 𝑣 64 ⟩$ . Since the image is a point in image space, this change of picture is a displacement from $𝑥$ to $𝑥 + ⃗ 𝑣$ . For any digit $𝑘$ , adding the changes in its individual terms gives

𝑠 𝑘 (𝑥 + ⃗ 𝑣) - 𝑠 𝑘 (𝑥) = 𝑤 𝑘, 1 𝑣 1 + \dots + 𝑤 𝑘, 64 𝑣 64 = ⃗ 𝑤 𝑘 \cdot ⃗ 𝑣 .

Here is where the geometry enters. For nonzero vectors, the dot product is also the product of their lengths and the cosine of their angle:

⃗ 𝑤 𝑘 \cdot ⃗ 𝑣 = ‖ ⃗ 𝑤 𝑘 ‖ ‖ ⃗ 𝑣 ‖ c o s 𝜃 .

If the displacement is perpendicular to $⃗ 𝑤 𝑘$ , the cosine is zero and the score does not change. If we move along $⃗ 𝑤 𝑘$ , the cosine is one and the score increases. Moving in the opposite direction decreases it. The stored list has picked out a direction in image space: a direction in which pictures receive larger scores for this digit.

We cannot draw all $64$ coordinate directions at once. But we can draw the same calculation with two coordinates, and see what kind of decision it makes.

29.2A Simpler Decision

Before returning to ten competing scores, let's try a simpler proposal: call an image a three when its score for three is positive, and call it something else when that score is negative. This is a possible binary rule, “three or not three.” It is only a temporary proposal; our actual reader uses the largest of ten scores.

To draw what the proposal does, reduce the input to two coordinates $(𝑢, 𝑣)$ and invent the scoring rule

𝑠 3 (𝑢, 𝑣) = 2 𝑢 + 𝑣 - 1 .

At $(0, 0)$ the score is $- 1$ , while at $(1, 1)$ it is $2$ . Where does the answer change? Exactly where the score is zero:

2 𝑢 + 𝑣 - 1 = 0 .

That is a line. On one side the score is positive, and on the other it is negative. A long-looking sum of pixel contributions has become a familiar geometric operation: checking which side of a boundary contains a point.

Figure 29.2 The proposed positive-score rule divides the plane into two half-planes. Move the input, rotate the normal, or change the bias. The initial rule is

2 𝑢 + 𝑣 - 1 = 0

; the coefficients are invented for this small example.

The coefficients form the normal vector $⃗ 𝑤 = ⟨ 2, 1 ⟩$ . For example, $⟨ 1, - 2 ⟩$ points along the line, since $⟨ 2, 1 ⟩ \cdot ⟨ 1, - 2 ⟩ = 0$ . Starting at any boundary point and moving in that direction keeps the score zero. Moving in the normal direction crosses the boundary.

The bias determines where the line sits. In $⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏 = 0$ , changing $𝑏$ leaves the normal fixed and translates the line. Changing the direction of $⃗ 𝑤$ rotates it. These are two different jobs performed by the stored numbers.

29.3From a Line to a Hyperplane

Nothing in this argument required exactly two coordinates. In three dimensions,

𝑤 1 𝑥 1 + 𝑤 2 𝑥 2 + 𝑤 3 𝑥 3 + 𝑏 = 0

is a plane with normal $⃗ 𝑤 = ⟨ 𝑤 1, 𝑤 2, 𝑤 3 ⟩$ , provided $⃗ 𝑤 \neq ⃗ 0$ . More generally, in $ℝ 𝑛$ we call

𝐻 = {𝑥 : ⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏 = 0}

a hyperplane. It has one fewer dimension than the surrounding space. The two inequalities $⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏 > 0$ and $⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏 < 0$ describe its two sides.

If $𝑞$ is any point on $𝐻$ , then $⃗ 𝑤 \cdot ⃗ 𝑞 = - 𝑏$ , so its equation can also be written

⃗ 𝑤 \cdot (⃗ 𝑥 - ⃗ 𝑞) = 0 .

This is the point-normal equation from the main notes, with more coordinates. The displacement from $𝑞$ to another boundary point is perpendicular to the normal. There may be $64$ coordinates in the displacement, but perpendicularity still means exactly the same thing: its dot product with $⃗ 𝑤$ is zero.

29.4How Far Are We from the Boundary?

Knowing the side of a boundary is useful. Knowing the distance to it tells us more. How far would we have to move the input before reaching the boundary?

Let's recover the formula rather than try to remember it. Take a point $𝑞$ on the hyperplane and form the displacement

⃗ 𝑣 = ⃗ 𝑥 - ⃗ 𝑞 .

The projection chapter taught us to split a vector into a component parallel to a chosen direction and a perpendicular remainder. Projecting onto the normal $⃗ 𝑤$ gives

⃗ 𝑣 ∥ = ⃗ 𝑣 \cdot ⃗ 𝑤 ‖ ⃗ 𝑤 ‖ 2 ⃗ 𝑤, ⃗ 𝑣 ⟂ = ⃗ 𝑣 - ⃗ 𝑣 ∥ .

Be careful about what the words refer to here. The parallel component is parallel to the normal, so it points across the hyperplane. The perpendicular remainder is perpendicular to the normal, so it points along the hyperplane.

Start at $𝑞$ and follow only the remainder. We arrive at a point $𝑥 𝐻$ on the hyperplane, directly underneath $𝑥$ in the normal direction. Equivalently, start at $𝑥$ and remove its normal component:

⃗ 𝑥 𝐻 = ⃗ 𝑥 - ⃗ 𝑣 ∥ .

Since $⃗ 𝑤 \cdot ⃗ 𝑞 = - 𝑏$ , we have $⃗ 𝑣 \cdot ⃗ 𝑤 = ⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏$ . Substitution gives

⃗ 𝑥 𝐻 = ⃗ 𝑥 - ⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏 ‖ ⃗ 𝑤 ‖ 2 ⃗ 𝑤 .

There is a quick check on our work: dot this expression with $⃗ 𝑤$ and add $𝑏$ . The result is zero, so $𝑥 𝐻$ really lies on the boundary.

Example 29.1 (Project onto a line). For $2 𝑢 + 𝑣 - 1 = 0$ and $𝑥 = (1, 1)$ , use $⃗ 𝑤 = ⟨ 2, 1 ⟩$ and $𝑏 = - 1$ . The score is $2$ , and $‖ ⃗ 𝑤 ‖ 2 = 5$ . Therefore

⃗ 𝑥 𝐻 = (1, 1) - 25 (2, 1) = (15, 35) .

Indeed, $2 (1 / 5) + 3 / 5 - 1 = 0$ . The perpendicular displacement is $⟨ 4 / 5, 2 / 5 ⟩$ , whose length is $2 / \sqrt 5$ .

Figure 29.3 Remove the component parallel to the normal to reach

𝑥 𝐻

. Compare this perpendicular route with a route to another boundary point. The second view performs the same construction for the plane

2 𝑢 + 𝑣 + 2 𝑧 = 1

Why is the perpendicular route the shortest one? If $𝑟$ is any other boundary point, the vector from $𝑥 𝐻$ to $𝑟$ lies along the hyperplane, while the vector from $𝑥 𝐻$ to $𝑥$ is normal to it. These vectors are perpendicular. Pythagoras therefore gives

‖ ⃗ 𝑥 - ⃗ 𝑟 ‖ 2 = ‖ ⃗ 𝑥 - ⃗ 𝑥 𝐻 ‖ 2 + ‖ ⃗ 𝑥 𝐻 - ⃗ 𝑟 ‖ 2 \geq ‖ ⃗ 𝑥 - ⃗ 𝑥 𝐻 ‖ 2 .

The second term vanishes only at $𝑟 = 𝑥 𝐻$ . This proves the shortest-distance claim in every dimension.

The scalar projection onto the unit normal records the signed distance:

𝑑 s i g n e d (𝑥, 𝐻) = ⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏 ‖ ⃗ 𝑤 ‖ .

Its sign identifies the side of the boundary. Its absolute value is the ordinary distance:

d i s t (𝑥, 𝐻) = | ⃗ 𝑤 \cdot ⃗ 𝑥 + 𝑏 | ‖ ⃗ 𝑤 ‖ .

Example 29.2 (Add one more coordinate). For the plane $2 𝑢 + 𝑣 + 2 𝑧 - 1 = 0$ , the normal is $⟨ 2, 1, 2 ⟩$ . At $𝑥 = (1, 1, 1)$ the score is $4$ and the squared normal length is $9$ , giving

𝑥 𝐻 = (1, 1, 1) - 49 (2, 1, 2) = (19, 59, 19) .

The distance is $4 / 3$ . Substituting the projected coordinates into the plane's equation gives $2 / 9 + 5 / 9 + 2 / 9 - 1 = 0$ , just as it should.

These formulas use the $𝑛$ -coordinate normal. Although appending a $1$ to an input is convenient for putting the bias inside a dot product, that extra coordinate is fixed. It is not another direction in which an image can move. For image-space distances, keep the bias as the offset $𝑏$ .

29.5Let the Scores Compete

Our temporary “three or not three” rule has made the geometry easy to see. Could we use ten such rules, one for each digit?

There is a problem: several rules might say yes, or every rule might say no. To see both problems without drawing ten regions, add two scores to our small example:

𝑠 3 = 2 𝑢 + 𝑣 - 1, 𝑠 5 = - 𝑢 + 2 𝑣 - 1, 𝑠 9 = 14 - 𝑢 - 𝑣 .

At $(1 / 5, 1 / 5)$ all three are negative. At $(2 / 5, 9 / 10)$ the scores for three and five are both positive. The tests do not give a single answer.

But the scores contain more information than their signs. We can compare their sizes and choose the largest, just as our actual reader does.

Figure 29.4 Independent positive-score tests leave gaps and overlaps. Choosing the largest score assigns a winning region to each class, apart from ties on the boundaries. The dashed line is the tie between three and five; some of it lies inside nine's winning region.

Compare two digits $𝑗$ and $𝑘$ . Digit $𝑗$ beats digit $𝑘$ exactly when

𝑠 𝑗 (𝑥) - 𝑠 𝑘 (𝑥) > 0 .

Subtract their formulas:

𝑠 𝑗 (𝑥) - 𝑠 𝑘 (𝑥) = (⃗ 𝑤 𝑗 - ⃗ 𝑤 𝑘) \cdot ⃗ 𝑥 + (𝑏 𝑗 - 𝑏 𝑘) .

Another hyperplane! Its normal is the difference of the two weight vectors, and its bias is the difference of the two biases. To win overall, digit $𝑗$ must beat every other digit. Its winning region is therefore an intersection of nine half-spaces.

A pairwise tie is only a candidate winning boundary. In our small example, three and five tie along $𝑣 = 3 𝑢$ . At the origin their scores are both $- 1$ , but nine scores $1 / 4$ . Crossing the 3/5 tie there changes which of those two losers comes second; it does not change the winning answer.

Figure 29.5 Compare the actual weight vectors for two digits and their difference. The resulting dot product, with the bias difference added, is exactly the difference between their scores on the selected image.

We can now say what the reader is doing geometrically. Its ten lists of numbers arrange hyperplanes through image space. Each input falls into a region where one score is largest. The reader assigns the digit labeling that region. For carefully chosen weights, many handwritten threes fall into the region for three, many fives fall into the region for five, and so on. A mistaken three is a point that has landed in another digit's region.

29.6A Perpendicular Move in Image Space

The projection formula works just as well on the actual $64$ coordinates. Choose two digits and set

⃗ 𝑤 = ⃗ 𝑤 𝑗 - ⃗ 𝑤 𝑘, 𝑏 = 𝑏 𝑗 - 𝑏 𝑘 .

Project an image onto their tie hyperplane. The calculation returns a list of $64$ coordinate changes. We can put those changes back on the pixel grid and see what the perpendicular move does to the picture.

Figure 29.6 Move from the original image toward a selected pairwise tie. The figure uses all

64

coordinates, reports the true distance, and follows all ten scores. At

𝑡 = 1

the selected pair ties; another digit may have overtaken them. The coordinate table retains out-of-range values even when the image preview clips them for display.

There are two distinctions to keep in view. First, projecting onto one selected tie need not give the nearest point where the winning label changes. We must also inspect the other scores. Second, ordinary Euclidean projection is free to leave the cube $[0, 1] 64$ . A negative ink amount is not a valid pixel measurement, even though the score formula can still evaluate it. Clipping that coordinate back to zero changes the projected point and generally destroys the exact tie.

The distance is also a distance between measurement lists. A small Euclidean change need not look small to a person, and a nearby list need not resemble handwriting. Geometry describes precisely what this model does; its usefulness still depends on which examples occupy its regions.

That brings us to the next problem. We know how stored weights arrange the regions, but where should we put them? We need a way to compare whole readers and decide which choices are better. This time, the object we will turn into a point is the reader itself.

Exercise 29.3 (Check both parts). Project $(2, 0)$ onto $2 𝑢 + 𝑣 - 1 = 0$ . Verify that the projected point is on the line and that the displacement to it is parallel to $⟨ 2, 1 ⟩$ .

Exercise 29.4 (Same boundary, different scores). Multiply both $⃗ 𝑤$ and $𝑏$ by a positive constant. Explain why the binary boundary, its two sides, and the distance formula do not change. What changes if the constant is negative?

Exercise 29.5 (A boundary that cannot be a line). Place one class at $(0, 0)$ and $(1, 1)$ , and another at $(1, 0)$ and $(0, 1)$ . Show that no affine score is strictly positive on the first class and strictly negative on the second. Add the two inequalities for each class and compare.