The puzzle (The Math Behind AI)

Try it first

Pause here. Really. It’s more fun if you fail at it yourself.

Each square has an address (x, y): first how far across, then how far up. So (0, 1) is 0 across and 1 up, the top-left square. The cats sit at (0, 0) and (1, 1). The dogs sit at (0, 1) and (1, 0).

Your job: draw one straight line with both cats on one side and both dogs on the other. No wobbly lines like the one in the picture above: the rule says straight.

Draw one straight lineHands-on

Drag the yellow dots to move the line, or tap the board to move the nearest dot there. The blue side is where the cats should be, the amber side is where the dogs should be, and a red ring marks an animal on the wrong side.

Puzzle

Cats at (0, 0) and (1, 1). Dogs at (0, 1) and (1, 0).

2 on the wrong side. Keep moving the line.

Three lines to try

Engineers call this puzzle XOR, short for “exclusive or”: x or y is 1, but not both. That’s exactly where the dogs sit.

Every line you try fails

Flat, upright, slanted: some animal always lands on the wrong side. Each line is named by its rule. $y=\tfrac12$ is every point halfway up, $x=\tfrac12$ is every point halfway across, and $x+y=1.5$ is every point whose two numbers add up to 1.5. The three line buttons in the lab above draw all three for you.

The best any straight line can do is three animals out of four. But “I tried a lot of lines” isn’t a proof. Here’s one.

Why it can’t be done: a short proof

A proof you can check with a pencil.

Every straight line can be written as $w_1x+w_2y+b=0$ , where $w_1x$ means $w_1$ times $x$ . Think of $\li{w_1}$ , $\li{w_2}$ and $\li{b}$ as three dials; the little 1 and 2 just number them. For example, $w_1=0$ , $w_2=1$ , $b=-0.5$ gives $y-0.5=0$ . That’s $y=\tfrac12$ again, the flat line halfway up.

Now drop the “= 0” and just work out the left side, $y-0.5$ , at any point. On the line it’s exactly 0. At (0, 0), below the line, it’s $-0.5$ , a negative number. At (0, 1), above it, it’s $+0.5$ , a positive one. Every line splits the grid like that: positive on one side, negative on the other.

Flip all three signs and you get the very same line, with its positive and negative sides swapped: $w_1=0$ , $w_2=-1$ , $b=0.5$ is the flat line too. The labs on this page show whichever version puts more animals on their correct side (dogs positive, cats negative; on a tie, the one with a negative b), so don’t be surprised when their signs flip.

Now pretend some line does work, with the dogs on the positive side and the cats on the negative side. I’ll show that this leads to a clash. Plug in each animal’s address ( $\lt 0$ means “is negative”; $\gt 0$ means “is positive”):

\begin{aligned} \cy{\text{cat }(0,0)}&:\quad w_1\times0+w_2\times0+b=b \lt 0\\ \cy{\text{cat }(1,1)}&:\quad w_1\times1+w_2\times1+b=w_1+w_2+b \lt 0\\ \am{\text{dog }(0,1)}&:\quad w_1\times0+w_2\times1+b=w_2+b \gt 0\\ \am{\text{dog }(1,0)}&:\quad w_1\times1+w_2\times0+b=w_1+b \gt 0 \end{aligned}

Two positive numbers always add up to a positive number, and two negative numbers add up to a negative one. So add the two dog rows: $(w_2+b)+(w_1+b)=w_1+w_2+2b\gt 0$ . Add the two cat rows: $b+(w_1+w_2+b)=w_1+w_2+2b\lt 0$ . That’s the exact same number both times, and it can’t be both above and below zero. So no such line exists. (If you want the dogs on the negative side instead, every sign flips and the same clash appears.)

Worked by hand: the slanted line

Move the 1.5 to the left side and $x+y=1.5$ becomes $x+y-1.5=0$ . So $w_1=1$ , $w_2=1$ , $b=-1.5$ . Plug in all four squares:

\begin{aligned}\cy{\text{cat }(0,0)}&:\quad 0+0-1.5=-1.5\\\cy{\text{cat }(1,1)}&:\quad 1+1-1.5=+0.5\\\am{\text{dog }(0,1)}&:\quad 0+1-1.5=-0.5\\\am{\text{dog }(1,0)}&:\quad 1+0-1.5=-0.5\end{aligned}

Here both dogs come out negative, so for this line the negative side is the dogs’ side. (Flip all three signs and they’d come out positive, as in the proof.) Cat (1, 1) sits alone on the positive side, which is fine. But cat (0, 0) shares the negative side with both dogs. That cat is the one animal on the wrong side when you press “x + y = 1.5” in the lab.

Now add the rows the way the proof does. The two dogs give $-1.0$ , and the two cats give $-1.0$ . The same number, so the dogs and the cats can’t end up on opposite sides. Every line hits that same clash.

Check it yourself. This copy of the lab shows the four numbers you get by plugging each address into your line.

Check the proof yourselfHands-on

Puzzle

Cats at (0, 0) and (1, 1). Dogs at (0, 1) and (1, 0).

2 on the wrong side. Keep moving the line.

Your line’s three dials (they change as you drag)

w₁ = 0.00, w₂ = 1.00, b = −0.50

Animal	w₁x + w₂y + b	Side
cat (0, 0)	−0.50	negative
cat (1, 1)	0.50	positive
dog (0, 1)	0.50	positive
dog (1, 0)	−0.50	negative

Dogs should come out positive and cats negative. Red rows are on the wrong side.

Three lines to try

A famous little puzzle

1969: a book, a limit, and a long time out of fashion.

In 1969, Marvin Minsky and Seymour Papert of MIT published a book called Perceptrons. A perceptron is a single layer of artificial neurons, the kind that can only draw straight lines. The book proved hard limits on what such a layer can recognize.

Think of x and y as two switches, 0 for off and 1 for on. Count how many are on. A dog sits wherever that count is odd (exactly one), and a cat wherever it’s even (none, or both). Telling odd counts from even ones is called parity. XOR is parity with just two switches, and it’s the smallest case of one of the book’s limits.

Minsky and Papert also guessed that adding layers would lead nowhere (“sterile”, in their word), though they called settling it an important research problem. Perceptron-style learning fell out of fashion and stayed there until the mid-1980s.

“These virtues”, in the quote below, means a single layer’s good points. The book lists them as “its linearity; its intriguing learning theorem; its clear paradigmatic simplicity”: it draws straight lines, it comes with a proof that its learning method works whenever a straight line can do the job, and it’s simple.

For the experts (skip it on a first read)

Minsky and Papert analyzed perceptrons whose units each look at only part of the input, and their headline examples were parity and connectedness. XOR alone is the classic textbook illustration (Rumelhart, Hinton and Williams in the 1986 PDP volumes; Goodfellow, Bengio and Courville, Deep Learning, section 6.1).

Sources: Quote Investigator’s transcription of the book; Léon Bottou’s foreword to the 2017 reissue; Minsky and Papert, Perceptrons, expanded edition, 1988 (its prologue); Mikel Olazaran, “A Sociological Study of the Official History of the Perceptrons Controversy”, Social Studies of Science, 1996 (abstract).

So what changed?

Two things. First, more than one layer: neurons feeding neurons. Put two neurons between the input and the answer, and they can draw two lines that fence off both dog corners. Engineers call them a hidden layer, because nobody sees their output directly.

Second, a way to train those hidden neurons: to set their dials automatically, a little at a time, from examples. That’s the hard part, because nobody can tell a hidden neuron what its right answer should be. That second piece is ideas 4 and 5 of this course (surprise in bits, and the chain rule, in lessons 7 and 8).

And here’s the twist that makes this puzzle worth a whole lesson. The AI you talk to today is still built mostly from two plain parts: dot products (lesson 3) and simple curves like the sigmoid in lesson 4. What changed most is how we stack them and train them.

Keep this grid in your head. I come back to it with a real trained network in lesson 4.

One straight line

In this lesson