flowchart LR
A1["Voice signal"] --> B1(["N.Net"]) --> C1["Transcription"]
A2["Image"] --> B2(["N.Net"]) --> C2["Text caption"]
A3["Game state"] --> B3(["N.Net"]) --> C3["Next move"]
A4["Theorem"] --> B4(["N.Net"]) --> C4["Proof"]
Neural Networks: A History of an Idea
Deep Learning
A history of the idea behind neural networks, from Plato’s associationism and Bain’s 1873 claim that the information is in the connections, through the McCulloch-Pitts neuron, Turing’s unorganised machines, Hebb’s rule and Rosenblatt’s perceptron, to the XOR wall and the three senses in which a multi-layer perceptron is universal.
This post is the first in a series of notes following Carnegie Mellon University’s course 11-785, Introduction to Deep Learning, taught by Bhiksha Raj and Rita Singh (Raj & Singh, 2025). The plan for the series is to read like careful lecture notes: everything the lecture covers, in the order it covers it, with the derivations filled in, the diagrams redrawn, and the primary sources actually cited rather than gestured at.
Lecture one is a history lecture, and it is easy to mistake a history lecture for a warm-up. This one is not. By the end of it we will have stated, and mostly justified, three claims that the entire rest of the field is built on. The history is how those claims are earned.
What is in the box?
Start with what these systems can do, because the capability is the thing that needs explaining.
The year everything changed was 2016. In that one year, four problems that had resisted decades of effort fell over in quick succession.
Speech recognition. People had been working on automatic speech recognition since the 1950s. As late as 2015, asking your phone to transcribe a sentence was mostly a way of finding out what strange thing it would come up with instead. Then a speech recognition system reached parity with professional human transcribers on a standard conversational benchmark (Xiong et al., 2016). Not “approached”. Parity.
Machine translation. In early 2016, translating an English sentence into Spanish with an online translator and then translating it back was a party trick: what came out was usually not what went in, and often was not even related to what went in. Later that year Google switched its translation system over to a neural architecture (Wu et al., 2016), and the output became good enough that professional translators started using it as a first draft.
Go. We have long treated purely intellectual games as a proxy for intelligence, on the reasoning that they have no evolutionary purpose. There is a plausible story about why humans might be good at recognising faces or catching thrown objects. There is no such story about chess. So if a machine could beat a human at chess, surely the machine was thinking.
Chess fell first, and the machine that did it has a local history worth knowing: the first computer to beat a grandmaster was Deep Thought, built at CMU on hardware originally designed for dynamic programming, which its authors realised could be repurposed for game-tree search. The team then moved to IBM and built Deep Blue, which beat Garry Kasparov in 1997 (Hsu, 2002). By the mid-1990s chess was, in the relevant sense, done.
Go was supposed to be different. The comparison usually quoted is that chess has on the order of \(10^{120}\) possible games while Go has on the order of \(10^{160}\) or more. The precise figures depend on exactly what you count, but the gap is the point: Go is not a little harder than chess, it is enormously harder. The received wisdom was that computers would not beat top human players at Go for another decade at least. In March 2016, AlphaGo beat Lee Sedol (Silver et al., 2016). Within a few years there were systems that learned to play at that level starting from self-play alone.
Image captioning. Also in 2016, systems appeared that could look at a photograph and write a sentence about it (Vinyals et al., 2015). Shown a photograph, such a system would produce “a man in a black shirt is playing a guitar”, and it would be right. At the time this seemed close to impossible.
And that was a decade ago. Today you can hand a model a photograph of your room and get back a paragraph noting the water stains on the ceiling, the posters, the light fixture and air vent, the bed with someone lying on it, the general clutter, and a judgement that the water stains are the most concerning thing in the picture. You can hand a model a mathematical statement that appears in no textbook, phrased loosely, and more often than not get a proof.
Every one of these systems is a neural network. From the outside, each is a box: something goes in, something comes out.
So the question for this entire post, and the question the lecture opens with, is the obvious one:
What is in the box?
Here is the route we are going to take to answer it. Each node is a question, and each arrow is the answer that forces the next question.
flowchart TD
A["What is in the box?"] --> B["These are things brains do.<br/>So look at the brain"]
B --> C["Associationism:<br/>the mind links things that co-occur"]
C --> D["But where do the links live?<br/>Connectionism: in the connections"]
D --> E["Then what is a single element?<br/>The McCulloch-Pitts unit"]
E --> F["How does an element learn?<br/>Hebb, then Rosenblatt"]
F --> G["One element is too weak.<br/>XOR is impossible"]
G --> H["Network them:<br/>the multi-layer perceptron"]
H --> I["Universal<br/>Boolean machine"]
H --> J["Universal<br/>classifier"]
H --> K["Universal function<br/>approximator"]
I --> L["The box is an MLP"]
J --> L
K --> L
style A fill:#1f6feb,stroke:#58a6ff,color:#fff
style L fill:#1f6feb,stroke:#58a6ff,color:#fff
A note on how this post is built. Rather than switching examples every section, one small scenario runs through the whole thing: a storm detector with two sensors, one that sees the flash of lightning and one that hears the rumble of thunder. That example is not arbitrary. Lightning and thunder is the standard illustration of the very first theory of cognition, an idea some 2,400 years old, which means our concrete anchor and our first historical idea are the same object. We will follow it from “these two things go together” all the way to “a network can approximate any function you like”.
The magical capacity of humans
Everything in Figure 1 is something a human can do. We learn. We solve problems. We recognise patterns. We create. We can sit still with no input at all and think, and produce an idea that was not there before. That list is worth emulating, which is exactly why people have tried to build machines that do it.
But if we want to emulate it, we should probably ask how the original works. And here the field runs immediately into a difficulty that Marvin Minsky put better than anyone:
If the brain was simple enough to be understood, we would be too simple to understand it.
That has not stopped anyone from trying, and the trying goes back a long way.
Associationism
The earliest model of human cognition is associationism, and its claim is a single sentence: we perform all of our inferences through associations, and those associations are learned from experience.
Take our storm. Every time you see a flash of lightning, a few seconds later you hear thunder. It happens again, and again, and again. Before long, something in you has linked the two: see the flash, and you brace for the noise. Hear the noise with no flash, and you conclude that lightning struck somewhere out of sight.
That is the whole idea. And notice how much of what we now call machine learning is exactly this: given an input, produce the output that has historically gone with it. Associationism is not a quaint precursor to the field. It is close to a description of it.
The idea is usually traced to Plato around 400 BC, and Aristotle gave it structure about fifty years later. In On Memory and Reminiscence (Aristotle, 350 C.E.) he wrote:
Hence, too, it is that we hunt through the mental train, excogitating from the present or some other, and from similar or contrary or coadjacent. Through this process reminiscence takes place.
Which, translated, is: we remember and we reason by association. Aristotle then set out four laws governing when associations form. They are genuinely a list, so here they are as one.
| Law | What it says | Our storm |
|---|---|---|
| Contiguity | Things that occur close together in space or time get linked | The flash and the rumble arrive seconds apart |
| Frequency | The more often two things co-occur, the stronger the link | Every storm strengthens the link a little |
| Similarity | If two things are similar, the thought of one triggers the other | A camera flash makes you flinch for a moment |
| Contrast | Seeing or recalling something may trigger its opposite | Thinking of a storm calls up a clear sky |
Associationism then had a very long run. John Locke, David Hume, David Hartley, James Mill, John Stuart Mill, Alexander Bain and Ivan Pavlov all worked in this tradition, and the behaviourism of the early twentieth century is a direct descendant: behaviour is learned by repeatedly associating actions with feedback. The associationist theory of mental process is that there is essentially only one mental process, the ability to associate ideas. Table 2 lays out the whole arc we are about to walk through, so that you can see where each name sits.
| When | Who | What they contributed |
|---|---|---|
| c. 400 BC | Plato | Associationism: inference works by association |
| c. 350 BC | Aristotle | The four laws of association (Table 1) |
| 1749 | David Hartley | Associations are physical vibrations in the brain |
| mid 1800s | microscopists | The brain is a mass of interconnected cells |
| 1873 | Alexander Bain | The information is in the connections |
| 1876 | David Ferrier | Further evidence for localised brain function |
| 1930 | Lawrence Kubie | Closed loops in the nervous system could explain memory |
| 1943 | McCulloch and Pitts | A neuron as a Boolean threshold unit |
| 1948 | Alan Turing | A-type and B-type unorganised machines |
| 1949 | Donald Hebb | A learning rule: neurons that fire together wire together |
| 1958 | Frank Rosenblatt | The perceptron, with a provably convergent learning rule |
| 1969 | Minsky and Papert | What single-layer networks provably cannot do |
| 1986 | Rumelhart, McClelland et al. | Parallel Distributed Processing |
| 2016 | many | Speech, translation, Go and captioning all fall |
Associationism is a good theory of the mind. But it leaves one question wide open, and that question is where this post actually begins:
Where are the associations stored, and how?
Because they have to be somewhere. If seeing lightning is going to make you expect thunder, something physical must have changed in you between the first storm and the hundredth. What changed, and where?
Where the associations live
The first person to guess at a physical answer was David Hartley, in Observations on Man in 1749 (Hartley, 1749). His proposal was that we receive input through vibrations, that these are carried to the brain, and that memories are themselves small vibrations, which he called vibratiuncles, in the same regions. Compound ideas are formed by connecting our memories to our current senses.
It is a remarkable guess for its time, and it is also wrong in its specifics, for the good reason that nobody in 1749 knew that neurons existed. That had to wait about a century.
The brain turns out to be a network
By the middle of the 1800s, microscopy had improved enough to reveal what the brain is made of: a vast mass of interconnected cells, which we would later name neurons. Two facts stood out immediately.
- Many neurons connect in to each neuron.
- Each neuron connects out to many neurons.
In other words, the brain is a network. And once you know that, the storage question sharpens: if the associations are in there somewhere, and the thing is a network, then perhaps the associations are in the wiring.
Bain: the information is in the connections
That is precisely the leap made by Alexander Bain, a Scottish philosopher, psychologist, mathematician, logician and linguist, in his 1873 book Mind and Body: The Theories of Their Relation (Bain, 1873).
Bain’s claim is the founding claim of the field: the information is in the connections. Not in the cells, not in some separate memory store, but in which neuron is wired to which and how strongly.
If you think of artificial neural networks as a recent idea, it is worth sitting with the date. Bain published a computational model of a neural network in 1873. We have had mathematical models of neural networks for over 150 years.
He did not just assert the idea, either. He drew networks. Here is one of his examples, redrawn: three inputs, three outputs, and a wiring pattern in which different combinations of inputs produce different outputs.
Read Figure 3 as a machine. If \(a\) and \(b\) fire together, \(x\) fires. If \(a\) and \(c\) fire together, \(z\) fires. If \(b\) and \(c\) fire together, \(y\) fires. The network never changes. The inputs change, and the outputs change with them.
This seems almost too obvious to state now. In the 1870s it was considered nonsense, and Bain was mocked for it. It is worth remembering that when an idea is early enough, being right is not much protection.
Bain drew a second kind of figure too, in which the intensity and persistence of the input decide which output fires: a strong signal activates one output, a weak but sustained signal activates another. Hold on to that idea, because in about two sections we will meet a McCulloch-Pitts circuit that does exactly this, and produces a sensory illusion out of it.
Bain’s second idea: how the connections change
Bain also proposed a mechanism for learning, and the sentence is worth quoting exactly:
When two impressions concur, or closely succeed one another, the nerve-currents find some bridge or place of continuity, better or worse, according to the abundance of nerve-matter available for the transition.
Strip away the Victorian phrasing and this says: when two things happen together, the path between them gets better. Depending on how things fire, connections are made stronger or weaker.
This is Hebbian learning, three quarters of a century before Hebb wrote it down, and roughly 140 years before anyone trained a network with it at scale. Bain was very early.
Bain’s doubts, and why he was wrong to have them
He was also, in the end, defeated by arithmetic. In 1873 Bain estimated that accounting for around 200,000 “acquisitions” would need on the order of one million neurons and five billion connections. By 1883 he had realised he had not accounted for partially formed associations, nor for the neurons involved in recall and learning itself, which pushes the requirement up enormously. By the end of his life in 1903 he had recanted the whole thing: the brain, he concluded, simply could not be big enough.
There is a Bertrand Russell line the lecture pairs with this, and it lands in an unusual direction here:
The fundamental cause of the trouble is that in the modern world the stupid are cocksure while the intelligent are full of doubt.
Bain was full of doubt, and his doubt was the one part of his reasoning that was wrong. The brain is big enough, by an enormous margin. Modern counts put the human brain at roughly 86 billion neurons (Azevedo et al., 2009), with something on the order of 100 trillion connections between them. Bain thought he needed five billion connections and could not believe the brain had them. It has about twenty thousand times that many.
NoteWhat his contemporaries made of it
The Nature review of Mind and Body, published on 8 January 1874, gives a flavour of the reception (Anonymous, 1874). The reviewer is broadly sympathetic, welcoming Bain’s “application of scientific method to mental phenomena” and calling his doctrines “immeasurably nearer the truth than are the superstitions to which not only the uneducated, but also the great mass of the learned, are subject”, and then complains at length that he has given too little prominence to inheritance and that there is “something wrong about Prof. Bain’s celebrated theory of the Will”. A warm review, in other words, that misses the part of the book we now consider foundational.
The position Bain arrived at and then abandoned is called connectionism: the claim that mental computation is a property of the network of connections rather than of any individual element. The brain, on this view, is a connectionist machine, and Bain and Ferrier (Ferrier, 1876) are the usual citations for its arrival. Artificial neural networks are built to emulate exactly this structure: many simple elements, wired together, with the power of the model living in the wiring.
Connectionist machines, and what they are not
Let us make the definition explicit, because everything downstream depends on it.
A connectionist machine is a network of processing elements in which all world knowledge is stored in the connections between the elements.
Two clauses, and the second one is the load-bearing one. Not “some” knowledge. All of it.
Why this is strange
The strangeness of that definition is easiest to see by comparison with the machine you are reading this on. Your phone and your laptop are von Neumann machines (more precisely, variants of the Princeton architecture): there is a central processing unit that does the computing, and there is a separate memory holding both the program and the data. The same physical processor performs completely different tasks purely by reading different instructions out of memory. That separation is why one small device can run a browser, a music player and a compiler, often at the same time.
A neural network does not work like this at all, as Figure 4 makes plain.
%%{init: {"flowchart": {"subGraphTitleMargin": {"top": 10, "bottom": 26}}}}%%
flowchart TB
%% Two notes for anyone editing this diagram.
%% 1. subGraphTitleMargin.bottom pushes each subgraph's contents down. Without
%% it, the two-line "Von Neumann / Princeton machine" title is drawn from
%% the top of the box and its second line ends up behind "Processing unit".
%% 2. Mermaid lays disconnected subgraphs out in REVERSE declaration order, so
%% NN is declared first in order to render on the RIGHT. Do not "tidy" this
%% into narrative order: it would silently swap the two panels and make the
%% caption's left/right wrong.
subgraph NN["Connectionist machine"]
direction TB
N["Network of simple non-linear units<br/><br/>the program IS the connections<br/>the connections may also be the memory"]
end
subgraph VN["Von Neumann / Princeton machine"]
direction TB
P["Processing unit"] <--> M["Memory<br/>program + data"]
end
| Von Neumann machine | Connectionist machine | |
|---|---|---|
| Where the program lives | In memory, as data | In the connections themselves |
| Where the data lives | In memory, alongside the program | In the connections too |
| To change the task | Load different instructions | Change the wiring |
| Processing and memory | Separate | Not separated at all |
There is a practical consequence that is easy to miss. If you actually built a neural network in silicon, every connection would be hardwired. Changing the program would mean fabricating a new chip. That is why, in practice, we do not build neural networks. We emulate them on ordinary von Neumann machines, precisely because those machines can be reprogrammed by editing memory. The irony is not lost on anyone: the architecture we find most powerful is the one we run in simulation on the architecture it is supposed to replace.
TipSidebar: Turing’s unorganised machines
The lecture slides carry one slide on this that is easy to skate past, and it deserves more than that, because it means the first learnable connectionist model predates the perceptron by a decade.
In an unpublished 1948 National Physical Laboratory report titled Intelligent Machinery (Turing, 1969), Alan Turing described what he called unorganised machines. Copeland and Proudfoot (Copeland & Proudfoot, 1996) make the case that Turing was probably the first person to consider building computing machines out of simple neuron-like elements connected together largely at random.
An A-type machine is a network of two-input NAND units, wired at random, with their operation synchronised by a central clock. It has no learning mechanism of any kind: whatever it computes, it computes because of how the wires happened to fall.
A B-type machine is an A-type with one addition. Every connection between two units carries a modifier, a small two-state device spliced into the line. In one state the signal passes through unchanged. In the other, the output is pinned regardless of what arrives. Turing’s proposal was that “learning” consists of applying what he called appropriate interference, mimicking education: figuring out how to set each modifier. Notably, that setting process is itself done by an A-type machine.
Turing’s claim was that with enough units, a B-type machine can be trained to do any job a Turing machine can do. This is a connectionist learning proposal, with a training procedure, in 1948, and it went almost entirely unnoticed because the report was not published at the time.
TipSidebar: what people mean when they say “connectionist”
Two later attempts to pin down the term are worth recording, because they show what the community eventually decided the essential ingredients were.
Parallel Distributed Processing (Rumelhart et al., 1986), the two-volume work that defined the 1980s revival, lists eight requirements for a PDP system (here in the form quoted by Medler (1998)):
- A set of processing units.
- A state of activation.
- An output function for each unit.
- A pattern of connectivity among units.
- A propagation rule for propagating patterns of activity through the network of connectivities.
- An activation rule for combining the inputs impinging on a unit with the unit’s current state, to produce a new activation level.
- A learning rule whereby patterns of connectivity are modified by experience.
- An environment within which the system must operate.
Bechtel and Abrahamsen (Bechtel & Abrahamsen, 1991) compress this to four:
- The connectivity of units.
- The activation function of units.
- The nature of the learning procedure that modifies the connections between units.
- How the network is interpreted semantically.
Compare either list against a modern network and you will find that only the last item on Bechtel and Abrahamsen’s list is still genuinely open.
ImportantPoll 1: check yourself
Q1. Who is the first person to propose connectionism?
- Aristotle (b) Alexander Bain (c) David Hartley (d) Alan Turing
Q2. Roughly how many connections exist between neurons in the brain?
- 1 million (b) 5 billion (c) 80 billion (d) 100 trillion
NoteAnswers
A1: (b) Alexander Bain, in 1873. Hartley (1749) is the tempting wrong answer, and he genuinely did propose a physical substrate for memory, but he did not know about neurons and did not locate information in connections between them. Turing’s connectionist work is real but comes 75 years after Bain.
A2: (d) 100 trillion. Option (c), 80 billion, is the approximate neuron count, not the connection count. That distinction is the whole point of connectionism: the neurons are not where the capacity is.
Let us take stock. We have a hypothesis about the architecture: a network of simple elements, with everything stored in the wiring. We have not said one word about what the elements actually are. That is the next question.
The unit
To work out what a computational element should look like, we go back to the thing we are copying.
A real neuron, briefly
Signals arrive through the dendrites, the many branching fibres on the input side, and accumulate in the soma, the cell body. If the accumulated signal is large enough, the neuron fires, and the resulting pulse travels out along the axon. The axon is wrapped in a myelin sheath, a fatty insulator formed by glial cells, which is what lets the pulse travel quickly, and it terminates in structures that connect onto the dendrites of other neurons.
Three details from Figure 6 matter for the rest of this post.
- Many inputs, one output. A neuron has many dendrites but exactly one axon. Whatever it computes, it computes a single value and broadcasts it.
- Firing is thresholded. Strictly, the outgoing signal is a pulse train whose frequency depends on the accumulated input. But an equivalent and far more convenient view is that if the accumulated input exceeds a threshold, the neuron fires.
- The interesting variation is in the connections. Not in the cells.
There is a nice aside on the myelin. Someone did once take a piece of Einstein’s brain and run the tests, and the finding was that he had about as many neurons as anyone else. What he had more of was glial cells: more fat in his head. Whatever you make of a sample size of one, being a fat head appears not to be an insult.
McCulloch and Pitts, 1943
The first mathematical model of a neuron came from an unlikely pair. Warren McCulloch was a neurophysiologist at the University of Chicago. Walter Pitts was a homeless, self-taught logician who had turned up at his door. Together they wrote A Logical Calculus of the Ideas Immanent in Nervous Activity (McCulloch & Pitts, 1943), one of the foundational papers of the field. Pitts was twenty years old.
The paper is famously hard to read, and the lecture is candid about this. What it proposes, though, is clean: model the neurons of the brain, and the brain itself, as performing propositional logic, with each neuron evaluating the truth value of its input propositions. In effect, Boolean logic.
The model gives each neuron two kinds of incoming connection.
- An excitatory synapse transmits a weighted input to the neuron. These accumulate, and if the total exceeds the threshold, the neuron fires.
- An inhibitory synapse is not a negative weight. It is a veto. In the paper’s own words, the activity of any inhibitory synapse absolutely prevents excitation of the neuron at that time, regardless of every other input.
Writing the rule out, with excitatory inputs \(x_1, x_2, \dots, x_d \in \{0, 1\}\), a threshold \(\theta\), and an inhibitory input \(x_{\text{inh}} \in \{0, 1\}\):
\[ y = \begin{cases} 0 & \text{if } x_{\text{inh}} = 1,\\ 1 & \text{if } x_{\text{inh}} = 0 \text{ and } \sum_{i=1}^{d} x_i \geq \theta,\\ 0 & \text{otherwise}. \end{cases} \tag{1}\]
That absolute veto in the first line of Equation 1 is what distinguishes Equation 1 from everything that comes later. Modern units have no such thing: a strongly negative weight can always be outvoted by enough positive input. In the 1943 model it cannot.
Gates out of neurons
With Equation 1 you can build logic gates, and the paper does. In its own convention, every neuron fires exactly when it receives two excitatory endings and no inhibitory ones, and you build different gates by choosing how many endings each source lands on its target.
Read Figure 8 one panel at a time.
- Delay. Neuron 1 sends two endings to neuron 2. One source is therefore enough, and neuron 2 simply repeats neuron 1 one tick later: \(N_2(t) \iff N_1(t-1)\).
- OR. Neurons 1 and 2 each send two endings to neuron 3. Either source alone reaches the threshold of two, so \(N_3(t) \iff N_1(t-1) \vee N_2(t-1)\).
- AND. Neurons 1 and 2 each send one ending. Now it takes both of them to reach two: \(N_3(t) \iff N_1(t-1) \wedge N_2(t-1)\).
- AND-NOT. Neuron 1 sends two endings, and neuron 2 sends an inhibitory hoop. Neuron 1 alone is enough, unless neuron 2 fires, in which case nothing is: \(N_3(t) \iff N_1(t-1) \wedge \neg N_2(t-1)\).
Notice that every one of these formulas relates the output at time \(t\) to the inputs at time \(t-1\). Each unit costs one tick. That is not incidental bookkeeping; it is what makes the next construction possible.
An illusion, built from six units
Here is the part of the 1943 paper that convinces people it is not a toy.
Touch something very cold, very briefly, and your first sensation is one of heat. You have to keep your finger on it for a moment before the cold registers. This is a real and slightly disconcerting perceptual quirk, and McCulloch and Pitts showed that a small network of their units reproduces it exactly.
The circuit needs six units: a heat receptor, a cold receptor, a delay unit, a unit that the cold receptor can veto, and the two sensations. The wiring is:
- The cold receptor sends two endings to the delay unit, so the delay unit reports “cold, one tick ago”.
- The cold receptor and the delay unit each send one ending to cold sensation, so cold sensation fires only when those two are firing at the same tick, which means cold now and cold a tick ago. Cold has to persist to register as cold.
- The delay unit sends two endings to the vetoable unit, and the cold receptor sends it an inhibitory hoop. So that unit fires when there was cold, and then it stopped: it is a detector for cold that has just ended.
- The heat receptor sends two endings to heat sensation, and so does the vetoable unit. Either route fires the heat sensation.
Figure 9 steps that circuit through both cases, one tick at a time.
For a brief touch of cold, present at \(t = 1\) only: the cold receptor fires at \(t=1\), and the delay unit fires at \(t = 2\). Those two are never firing at the same tick, so cold sensation never fires at all. Meanwhile the vetoable unit sees the delay unit firing at \(t=2\) with no cold to veto it, and fires at \(t=3\), which fires the heat sensation at \(t=4\). Brief cold feels hot.
For sustained cold, on from \(t = 1\) onwards: the cold receptor fires at every tick and the delay unit fires from \(t = 2\), so from \(t=2\) they are firing together, and cold sensation fires from \(t = 3\). The vetoable unit, meanwhile, is silenced at every tick, because the cold receptor’s hoop is active every tick. Sustained cold feels cold, and the heat path never opens at all.
The only difference between the two runs is how long the finger stayed. The circuit turns a difference in duration into a difference in quality of sensation. That is not a small thing for a model published in 1943.
What else the model claimed, and what it lacked
Since any Boolean gate can be built (Figure 8), any Boolean function can be composed out of them. McCulloch and Pitts also pointed out that networks containing loops can remember: a signal that circulates in a closed cycle is a stored bit. Lawrence Kubie had suggested as early as 1930 that closed loops in the central nervous system might be the mechanism of memory (Kubie, 1930). We will come back to loops much later in the series, when we get to recurrent networks.
The paper attracted two serious criticisms, and the second is the one that matters here.
- They claimed more than they proved. They said their nets could compute a small class of functions, and that if a tape were provided they would be equivalent to Turing machines, which is to say Turing complete. This is broadly right, but they did not prove it themselves.
- They gave no learning mechanism. And this is the real gap. Equation 1 tells you exactly how a network with the right thresholds and the right wiring will behave. It says nothing whatsoever about how the right thresholds and the right wiring would ever come to exist. Every connection is assumed, by some unspecified process, to already be correct.
Which brings us to the obvious question. If all the knowledge is in the connections, how do the connections get set?
How a unit learns
The first concrete answer came from Donald Hebb, who arrived at neuroscience by an unusually indirect route. Before settling on a PhD, he had tried being a novelist, a farmer, a hobo and a schoolteacher. In 1949 he published The Organization of Behavior (Hebb, 1949), and in it a proposal that is now quoted in every textbook in the field:
When an axon of cell A is near enough to excite a cell B and repeatedly or persistently takes part in firing it, some growth process or metabolic change takes place in one or both cells such that A’s efficiency, as one of the cells firing B, is increased.
Which is usually compressed to: neurons that fire together wire together.
The physical picture
Two neurons do not touch. The axon of the first ends in a bulb, sitting a small distance from the dendrite of the second. When a signal arrives at the bulb, chemicals are released across the gap, exciting the second cell. Hebb’s proposal is about that bulb: every time an excitation of the first neuron successfully takes part in firing the second, the bulb grows slightly, and the connection strengthens.
It is worth flagging one thing that Figure 10 glosses over, and that the lecture flags too. Neuron B is not responding only to neuron A; it has an entire population of inputs. How, mechanistically, does the synapse from A “know” that it was one of the ones that helped? The honest answer is that the details are still debated. The rule is a model, and a good one, not a settled account.
The rule as mathematics
Write \(x\) for the firing of the input neuron and \(y\) for the firing of the output neuron, both in \(\{0, 1\}\), and \(w_{xy}\) for the strength of the connection between them. Hebb’s rule is
\[ w_{xy} \leftarrow w_{xy} + \eta\, x\, y, \tag{2}\]
where \(\eta > 0\) is a small learning rate. If both fire, the product \(xy\) is 1 and the weight grows a little. If either is silent, the product is 0 and nothing happens.
Algorithm 1
\begin{algorithm}
\caption{Hebbian learning}
\begin{algorithmic}
\INPUT Learning rate $\eta > 0$
\OUTPUT Connection weights $w_{xy}$
\STATE Initialize $w_{xy} \leftarrow 0$ for every connected pair $(x, y)$
\WHILE{the network is receiving input}
\STATE Observe the firing pattern of every neuron
\FOR{every connected pair $(x, y)$}
\STATE $w_{xy} \leftarrow w_{xy} + \eta\, x\, y$
\ENDFOR
\ENDWHILE
\end{algorithmic}
\end{algorithm}
Equation 2 is, without exaggeration, the great-grandparent of nearly every learning rule in machine learning. Even gradient descent, which we will spend a great deal of this series on, is recognisably a variant of it.
Why it does not work on its own
Look hard at alg. 1 and something should bother you. There is no line anywhere in it that makes a weight smaller.
Every co-firing adds. Nothing ever subtracts. And a stronger connection is more likely to succeed in firing its target, which produces more co-firing, which makes it stronger still. Weights grow without bound until they hit whatever physical ceiling exists, and then they sit there.
Figure 11 is the failure in one picture. At the start, the three weights are informative: the frequently co-firing input has the largest weight, the rare one the smallest. That ordering is exactly what we wanted the network to learn. But since nothing ever decreases, the frequent connection reaches the ceiling, then the occasional one, and eventually even the rare one. At that point all three weights are equal, and the neuron can no longer distinguish its inputs at all. The learning has erased itself.
Stated as a list, Hebbian learning is:
- Fundamentally unstable. Stronger connections reinforce themselves.
- Uncompetitive. There is no mechanism by which one connection growing costs another connection anything.
- One-directional. No reduction in weights is possible.
- Unbounded. Learning never converges to anything; it only saturates.
Later work added the missing ingredients. The best known is Sanger’s rule, also called generalized Hebbian learning (Sanger, 1989), which distributes an input’s contribution across multiple outputs and subtracts off what has already been accounted for:
\[ w_{ij} \leftarrow w_{ij} + \eta\, y_j \left( x_i - \sum_{k \leq j} w_{ik}\, y_k \right). \tag{3}\]
The bracketed term in Equation 3 is the part that Hebb was missing: a quantity that can be negative, so a weight can shrink. Variants like this fixed the stability problem, but none of them satisfied what people actually wanted, for a reason that is easier to see once you have seen the alternative.
ImportantPoll 2: check yourself
Hebbian learning is…
- fundamentally stable, since stronger connections will enforce themselves
- fundamentally unstable, since there is no reduction in weights
- fundamentally stable, since learning is unbounded
- fundamentally unstable, since weights compete for adjustment
NoteAnswer
(b). Note that (a) and (b) contain the same observation and draw opposite conclusions from it: self-reinforcement is precisely why it is unstable, not why it is stable. And (d) is wrong in its reason rather than its verdict: the problem is that weights do not compete. Competition is one of the things a repair like Equation 3 has to add.
Here is the missing ingredient, and it is almost embarrassingly simple. In Equation 2, nowhere does the rule refer to what the neuron was supposed to output. There is no target. The rule reinforces whatever happens to happen. What if the update depended not on what the neuron did, but on how wrong it was?
Rosenblatt’s perceptron
That is the contribution of Frank Rosenblatt, a psychologist and logician who in 1958 published The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Rosenblatt, 1958). He died young, in a boating accident in 1971.
The original model, and the model we kept
Rosenblatt’s actual proposal is a model of the visual system, and it is considerably richer than what we now call a perceptron. Groups of sensors on the retina (the S-units) combine onto cells in an association area \(A_1\); groups of \(A_1\) cells combine into a second association area \(A_2\); and signals from \(A_2\) combine into response cells \(R\). Connections may be excitatory or inhibitory. There is even feedback from the response cells back to the association cells, which serves to make the outputs mutually exclusive.
What survived is a simplification of that: sensory units feed association units through a set of fixed, prespecified weights, and the association units feed the response units through learnable weights. Figure 12 puts the two side by side.
The simplified unit on the right of Figure 12 is what the word “perceptron” now means: a number of inputs combined linearly and compared against a threshold. Electrical engineers know this as threshold logic, and it is powerful. With inputs \(x_1, \dots, x_N\), weights \(w_1, \dots, w_N\) and threshold \(T\):
\[ y = \begin{cases} 1 & \text{if } \displaystyle\sum_{i=1}^{N} w_i x_i - T \geq 0,\\ 0 & \text{otherwise}. \end{cases} \tag{4}\]
Compare Equation 4 against the McCulloch-Pitts rule Equation 1 and two changes stand out. The inputs now carry weights, so different inputs can matter different amounts. And there is no absolute veto: inhibition, if you want it, is just a negative weight, which enough excitation can overcome.
The gates, again
Threshold logic gives you Boolean gates immediately, and this time the weights make it easy to read off.
In the language of our storm detector, with \(X\) = “flash seen” and \(Y\) = “rumble heard”:
- AND (\(X \wedge Y\), “storm confirmed”) uses weights \(1, 1\) and threshold \(2\). Only \(1 + 1 = 2\) reaches the threshold, so it takes both sensors.
- OR (\(X \vee Y\), “something happened”) uses the same weights and threshold \(1\). Either sensor alone is enough.
- NOT (\(\overline{X}\), “no flash”) uses a single input with weight \(-1\) and threshold \(0\). When \(X = 0\) the sum is \(0 \geq 0\) and it fires; when \(X = 1\) the sum is \(-1 < 0\) and it does not.
Same unit, same rule, three different functions, obtained purely by changing numbers. The fourth panel of Figure 13 has question marks in it, and we will get to that shortly.
The learning rule
Rosenblatt did not just give a model. He gave a rule for setting the weights, and this is where the story turns. Let \(d(\vb{x})\) be the desired output for input \(\vb{x}\) and \(y(\vb{x})\) the output the perceptron actually produces. Then
\[ \vb{w} \leftarrow \vb{w} + \eta \left( d(\vb{x}) - y(\vb{x}) \right) \vb{x}. \tag{5}\]
Put Equation 5 next to Equation 2 and the difference is a single factor.
Hebb (1949):
\[ w_{xy} \leftarrow w_{xy} + \eta\, \underbrace{x\, y}_{\text{input} \times \text{output}} \]
Rosenblatt (1958):
\[ \vb{w} \leftarrow \vb{w} + \eta\, \underbrace{\left( d(\vb{x}) - y(\vb{x}) \right) \vb{x}}_{\text{input} \times \text{error}} \]
Hebb multiplies the input by the output. Rosenblatt multiplies the input by the error, the gap between what the unit should have said and what it did say. That one substitution fixes everything that was wrong with Equation 2:
- If the perceptron is right, then \(d(\vb{x}) - y(\vb{x}) = 0\), the whole update term vanishes, and nothing changes. The rule is silent when it has nothing to correct.
- If the perceptron fires when it should not, the error is \(-1\) and the weights move down along \(\vb{x}\). Weights can now decrease, which is exactly what Hebb’s rule could never do.
- If it stays silent when it should fire, the error is \(+1\) and the weights move up along \(\vb{x}\).
Because the update only ever happens on a mistake, the weights stop moving as soon as the unit is correct on everything. There is no runaway. This rule is also known as the delta rule, after the error term.
Algorithm 2
\begin{algorithm}
\caption{The perceptron learning rule}
\begin{algorithmic}
\INPUT Training pairs $\left(\vb{x}_1, d_1\right), \dots, \left(\vb{x}_n, d_n\right)$ with $d_i \in \{0, 1\}$; learning rate $\eta > 0$
\OUTPUT Weights $\vb{w}$, bias $b$
\STATE Initialize $\vb{w}$ and $b$ arbitrarily
\REPEAT
\STATE $m \leftarrow 0$
\FOR{$i = 1$ \TO $n$}
\STATE $y_i \leftarrow 1$ if $\vb{w}^{\intercal} \vb{x}_i + b \geq 0$, else $0$
\IF{$y_i \neq d_i$}
\STATE $\vb{w} \leftarrow \vb{w} + \eta \left(d_i - y_i\right) \vb{x}_i$
\STATE $b \leftarrow b + \eta \left(d_i - y_i\right)$
\STATE $m \leftarrow m + 1$
\ENDIF
\ENDFOR
\UNTIL{$m = 0$}
\end{algorithmic}
\end{algorithm}
And Rosenblatt proved something about alg. 2 that nobody had been able to prove about a learning rule before: if the two classes are linearly separable, the rule converges to a perfect classifier in a finite number of updates. Not “tends to improve”. Converges, provably, in finite time. We will watch it run in Figure 18, once we have the geometric picture that makes “linearly separable” mean something.
The hype
It is hard to overstate how this was received. The work was funded by the US Navy, and the press coverage in 1958 was extraordinary. The New York Times described the perceptron as (The New York Times, 1958):
the embryo of an electronic computer that [the Navy] expects will be able to walk, talk, see, write, reproduce itself and be conscious of its existence.
The Tulsa Oklahoma Times went with the headline “Frankenstein Monster Designed by Navy That Thinks”.
Underneath the hype was a specific technical error. It is roughly true of Rosenblatt’s full model that it can represent any Boolean circuit and perform any logic, if you do not ask awkward questions about how large the circuit would need to be. People took that claim and applied it to the simplified model, the single threshold unit of Equation 4. And that is false, in a way that is about to become very concrete.
The wall
Go back to Figure 13 and look at the fourth panel. We want a single unit that computes \(X \oplus Y\), exclusive or: fire when exactly one of the two sensors fires.
This is not a contrived function. For our storm detector it is the most useful diagnostic there is. If both sensors fire, there is a storm. If neither fires, there is no storm. But if exactly one fires, then either you saw lightning with no thunder or heard thunder with no lightning, and something is wrong with your equipment. “Exactly one” is the fault condition, and it is XOR.
We want weights \(w_1, w_2\) and a threshold \(T\) such that
\[ y = 1 \iff w_1 x_1 + w_2 x_2 \geq T \]
reproduces the XOR truth table. Write out what each row demands.
| \(x_1\) | \(x_2\) | \(x_1 \oplus x_2\) | What the unit must satisfy |
|---|---|---|---|
| 0 | 0 | 0 | \(0 < T\) |
| 1 | 0 | 1 | \(w_1 \geq T\) |
| 0 | 1 | 1 | \(w_2 \geq T\) |
| 1 | 1 | 0 | \(w_1 + w_2 < T\) |
Now just add them up. From rows two and three of Table 4, \(w_1 \geq T\) and \(w_2 \geq T\), so
\[ w_1 + w_2 \geq 2T. \]
From row one, \(T > 0\), so \(2T > T\), and therefore
\[ w_1 + w_2 \geq 2T > T. \]
But row four demands \(w_1 + w_2 < T\). The two conclusions contradict each other. No weights and no threshold exist. Not “we have not found them yet”: they do not exist, and four lines of arithmetic prove it.
This is the wall the first wave of perceptron research ran into. It is customary to credit, or blame, Marvin Minsky and Seymour Papert’s 1969 book Perceptrons (Minsky & Papert, 1969) for what happened next, and it is worth being precise about what they did and did not say.
TipSidebar: what Minsky and Papert actually argued
The popular version of this story is that Perceptrons proved neural networks could not compute XOR, everyone believed it, and the field died for fifteen years. That is not quite right on any of the three counts.
What Minsky and Papert did was give a rigorous computational-geometry analysis of what single-layer threshold networks can and cannot represent, and what those limits cost in terms of the number and size of the units required. XOR is the smallest example of the limits, not the substance of the argument. The lecture is careful to say that they alluded to the weakness of individual elements rather than explicitly declaring the enterprise dead.
Their own retrospective is the clearest source. In the epilogue added to the expanded 1988 edition, titled “The New Connectionism” (Minsky & Papert, 1988), they explain what they were actually after:
When perceptron-like machines came on the scene, we found that in order to understand their capabilities we needed some new ideas. It was not enough simply to examine the machines themselves or the procedures used to make them learn. Instead, we had to find new ways to understand the problems they would be asked to solve. This is why our book turned out to be concerned less with perceptrons per se than with concepts that could help us see the relation between patterns and the types of parallel-machine architectures that might or might not be able to recognize them.
Their complaint, in other words, was that the field had a machine and no theory of what the machine was for. The 1988 epilogue then goes on to assess Parallel Distributed Processing (Rumelhart et al., 1986) in the same spirit.
The funding collapse was real, and neural networks did spend a long stretch in the wilderness. But the cause was less a single book than the distance between what the 1958 headlines had promised and what the machines actually delivered. Rigorous criticism arriving on top of unmet expectations is what ends a funding cycle.
So: individual elements are weak computational elements, and networking them is not optional. Which is a strange conclusion to have to reach, because the brain was never one unit. It is a massive interconnection of many simple units, and we knew that from the start. Let us do what the brain does.
Networking them: universal Boolean machines
XOR is not a half-plane. But it is built out of things that are.
\[ X \oplus Y = \underbrace{\left( X \vee Y \right)}_{\text{at least one fired}} \wedge \underbrace{\left( \overline{X} \vee \overline{Y} \right)}_{\text{not both fired}}. \tag{6}\]
Read Equation 6 in storm-detector terms: exactly one sensor fired means at least one fired and they did not both fire. Both of those clauses are ordinary gates, and we already know how to build ordinary gates from single units. So build one unit for each clause, and feed both into a third unit that ANDs them.
Check Figure 14 by hand, because it takes ten seconds and it is worth the certainty.
- The top hidden unit has weights \(1, 1\) and threshold \(1\): it fires when \(X + Y \geq 1\), which is \(X \vee Y\).
- The bottom hidden unit has weights \(-1, -1\) and threshold \(-1\): it fires when \(-X - Y \geq -1\), that is when \(X + Y \leq 1\), which is true unless both fired. That is \(\overline{X} \vee \overline{Y}\).
- The output unit has weights \(1, 1\) and threshold \(2\): it fires only when both hidden units fire.
Feed in \(X = 1, Y = 1\): top fires, bottom does not, output sees \(1 < 2\) and stays silent. Correct. Feed in \(X = 1, Y = 0\): both hidden units fire, output sees \(2 \geq 2\) and fires. Correct. The wall is gone.
The general recipe
XOR was one function. The claim we want is much stronger: any Boolean function, no matter how complicated, can be computed by an MLP. And the recipe that gets us there is entirely mechanical.
Take any Boolean function of any number of inputs. Write down its truth table. Look at every row where the function outputs 1, and write a conjunction that is true on exactly that row and nowhere else: for each input, use the plain letter if that input is 1 in the row, and the barred letter if it is 0. Then OR all those conjunctions together. This is the disjunctive normal form, and every Boolean function has one, because the construction is nothing more than an enumeration of the true rows.
Let us do it on a function that genuinely requires the machinery. Add a third sensor to our detector, a barometer that fires on a sudden pressure drop, and consider the function “exactly two of the three sensors fired”. That is the ambiguous case worth flagging: not a clean storm signature, not a clean all-clear.
| \(X\) (flash) | \(Y\) (rumble) | \(Z\) (pressure) | \(f\) | Conjunction for this row |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 1 | \(\overline{X} \wedge Y \wedge Z\) |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | \(X \wedge \overline{Y} \wedge Z\) |
| 1 | 1 | 0 | 1 | \(X \wedge Y \wedge \overline{Z}\) |
| 1 | 1 | 1 | 0 |
So from Table 5,
\[ f(X, Y, Z) = \left( X \wedge Y \wedge \overline{Z} \right) \vee \left( X \wedge \overline{Y} \wedge Z \right) \vee \left( \overline{X} \wedge Y \wedge Z \right). \tag{7}\]
Before we build it, notice that this function is not something a single unit could do, and the proof runs exactly like the XOR one. Suppose weights \(w_1, w_2, w_3\) and a threshold \(T\) existed. The three firing rows demand
\[ w_1 + w_2 \geq T, \qquad w_1 + w_3 \geq T, \qquad w_2 + w_3 \geq T, \]
and adding those three gives \(2\left(w_1 + w_2 + w_3\right) \geq 3T\). But the row \((1,1,1)\) must stay silent, so \(w_1 + w_2 + w_3 < T\), and therefore \(2\left(w_1 + w_2 + w_3\right) < 2T\). Putting the two together,
\[ 3T \leq 2\left(w_1 + w_2 + w_3\right) < 2T, \]
which forces \(T < 0\). Yet the row \((0,0,0)\) must stay silent too, and that demands \(0 < T\). Contradiction. So Equation 7 needs a hidden layer, exactly as XOR did.
Turning Equation 7 into a network is now mechanical. Each conjunction becomes one unit: put weight \(+1\) on each plain letter, weight \(-1\) on each barred letter, and set the threshold to the number of plain letters. Then one final unit with all weights \(1\) and threshold \(1\) ORs them.
Verify the top unit of Figure 15: weights \(+1, +1, -1\) and threshold \(2\) means it fires when \(X + Y - Z \geq 2\), which happens only at \(X = 1, Y = 1, Z = 0\). That is exactly the conjunction \(X \wedge Y \wedge \overline{Z}\) and nothing else.
Nothing in that construction was specific to this function or to three inputs. Every Boolean function has a truth table; every truth table gives a disjunctive normal form; every disjunctive normal form is one layer of AND units under one OR unit. Therefore:
MLPs are universal Boolean machines. Give me any Boolean function, of any number of inputs, and I can build you an MLP that computes it.
Two honest caveats, both of which the lecture flags and defers.
- This says nothing about size. The construction above uses one hidden unit per true row of the truth table, and a function of \(d\) inputs has \(2^d\) rows, any number of which may be true. For \(d = 30\) that is up to a billion hidden units. The claim is that an MLP exists, not that it is practical. How the required size depends on the function, and how depth changes the answer, is the subject of the next lecture.
- This says nothing about learning. We built the weights by hand, from a truth table we already had. Nobody has said how you would find them from data.
Where we are
flowchart TD
A["What is in the box?"] --> B["Connectionism"]
B --> C["McCulloch-Pitts unit"]
C --> D["Hebb, then Rosenblatt"]
D --> E["XOR: one unit is not enough"]
E --> F["The multi-layer perceptron"]
F --> G["Universal<br/>Boolean machine"]
F --> H["Universal classifier"]
F --> I["Universal function<br/>approximator"]
style G fill:#2ecc71,stroke:#2ecc71,color:#111
style H fill:#333,stroke:#777,color:#aaa
style I fill:#333,stroke:#777,color:#aaa
One claim down, two to go. But there is a problem with everything so far, and it is a big one: our brains are not Boolean. The signal arriving from your eyes is not a truth value; it is an intensity. Nor are our inferences Boolean. We estimate distances and durations and probabilities, not just yes and no.
So we need to handle two generalisations. First, real-valued inputs with Boolean outputs. Then real-valued outputs as well. Take them in that order.
Real inputs: universal classifiers
Here is the good news: the perceptron already handles real-valued inputs, and we do not have to change a thing.
Look again at Equation 4. The rule computes \(\sum_i w_i x_i\) and compares it to \(T\). Nothing in that expression requires \(x_i \in \{0, 1\}\). Feed in the brightness of the flash and the loudness of the rumble instead of yes-or-no, and the arithmetic is identical. The unit still fires if the weighted input matches or exceeds the threshold.
Affine, not linear
Before we look at what such a unit computes geometrically, it is worth rewriting it in the form the rest of the field uses. Move the threshold across the inequality by defining a bias \(b = -T\). Then the firing condition \(\sum_i w_i x_i \geq T\) becomes
\[ z = \sum_{i=1}^{N} w_i x_i + b = \vb{w}^{\intercal} \vb{x} + b \geq 0, \tag{8}\]
and the unit’s output is \(y = f(z)\) where \(f\) is a threshold activation that returns 1 when \(z \geq 0\) and 0 otherwise.
The function \(\vb{w}^{\intercal} \vb{x} + b\) in Equation 8 is called an affine function of the inputs, and it is worth being careful about the distinction from a linear one, since the two words get used loosely.
Linear:
\[ \sum_{i=1}^{N} w_i x_i = 0 \]
is a hyperplane that always passes through the origin.
Affine:
\[ \sum_{i=1}^{N} w_i x_i + b = 0 \]
is a hyperplane that can sit anywhere.
That constant \(b\) is what buys the freedom to place the boundary anywhere, rather than pinning it to the origin, and we are about to need that freedom.
Splitting the unit into an affine part and an activation, as Figure 17 does, looks like pure bookkeeping, and for now it is. But it has a consequence worth flagging early: once the unit is “an affine function followed by an activation”, the activation becomes a component you can swap out. We will collect on that at the end of the post.
What a perceptron computes: a hyperplane
Now the geometry. The unit outputs 1 on one side of the surface where \(z = 0\), and 0 on the other. That surface, \(\vb{w}^{\intercal} \vb{x} + b = 0\), is a hyperplane: a line in two dimensions, a plane in three, an \((N-1)\)-dimensional surface in \(\mathbb{R}^N\).
So a perceptron over real inputs is a linear classifier, and the whole of its behaviour is captured by where that hyperplane sits. Its parameters are just the weights (with the bias counted among them).
Which is exactly what makes “linearly separable” concrete, and lets us finally watch alg. 2 do its work. Our two sensors now report real numbers, and each storm we have logged is a point in the plane.
Two things in Figure 18 are worth naming, because they are properties of the algorithm rather than of this particular dataset.
First, the rule does nothing when it is correct. That is Equation 5 doing exactly what it says: when \(d(\vb{x}) = y(\vb{x})\), the update term is zero.
Second, it stops at the first line that works, not the best one. The algorithm has no notion of a good separator, only of a correct one. It halts the instant a full pass produces no mistakes, so the line you end up with depends on the order the examples arrived in. Any of infinitely many lines would have satisfied it. This is a real limitation, and the search for the best separating hyperplane is a different story for a later post.
Why XOR fails, seen properly
We proved algebraically, from the constraints in Table 4, that XOR is impossible for one unit. Now we can see it.
The Boolean case is just the real case restricted to the four corners of the unit square. Put \((0,0)\), \((1,0)\), \((0,1)\) and \((1,1)\) in the plane, and each Boolean function is a demand about which corners fall on which side of a line.
AND, OR and NOT in Figure 19 are each a matter of sliding one line around. AND needs a line with only \((1,1)\) above it. OR needs one with only \((0,0)\) below it. NOT ignores one axis entirely and splits the square down the middle. Move the boundary, get a different gate.
XOR asks for something a line cannot give. Its two firing corners, \((1,0)\) and \((0,1)\), are diagonally opposite, and so are its two silent corners, \((0,0)\) and \((1,1)\). Any straight line you draw leaves one corner on the wrong side. The algebra of Table 4 and the picture of Figure 19 are the same fact in two languages.
Fencing off a region
Here is where it gets good. If one unit gives us a half-plane, what do several units give us?
Suppose we want a network that fires when the input lands inside a pentagon, and stays silent outside it. Foreshadowing the punchline so the construction is easy to follow: a convex polygon is nothing but the AND of the half-planes cut by its own sides, and we already know how to build an AND.
Take five units, one per side of the pentagon, each firing on the polygon’s side of its own line. Every point in the plane now carries a number: how many of the five units are firing there. That count is 5 in exactly one place.
The sixth unit in Figure 20 takes the five outputs \(y_1, \dots, y_5\) with weights all equal to 1, and has threshold 5. It fires precisely when
\[ \sum_{i=1}^{5} y_i \geq 5, \tag{9}\]
which, since each \(y_i \in \{0,1\}\), means all five are firing at once. That is an AND over five inputs, and Equation 9 is the whole network.
Six units total, as Figure 21 shows, for a shape that no single unit could come close to.
And now it snowballs. Two disjoint pentagons? Build the pentagon subnetwork twice and OR the two outputs with one more unit, which requires a third layer. A region with a curved boundary? A curve is not a polygon, but it can be approximated by a union of small polygons as closely as you like, and a union is an OR.
The third panel of Figure 22 is the general case. Chop the region into little polytopes, build each one as an AND of half-planes, and OR the lot. Shrink the polytopes and the approximation improves without limit. There is nothing special about the pentagon; the construction works for any region you can tile, which is to say any region at all, provided you are willing to spend enough units.
Which gives us the second claim
MLPs are universal classifiers. Give me any decision boundary, and I can build you an MLP that captures it to arbitrary precision.
This is less abstract than it sounds. Classification is the problem of finding decision boundaries in high-dimensional space. An MNIST digit is a 28-by-28 greyscale image, which is 784 numbers, so every handwritten digit is a point in \(\mathbb{R}^{784}\). Somewhere in that space is the region occupied by images that look like a 2. Building a “2 versus everything else” classifier means capturing the boundary of that region, and we have just shown that an MLP can capture any boundary at all.
As before, the claim is about what is possible. It says nothing about how many units the boundary needs, and nothing about how you would find the weights from data rather than by construction.
ImportantPoll 3: check yourself
How many threshold-activation perceptrons are needed in an MLP to model a hexagonal decision region over a two-dimensional input space?
- 6 (b) 7 (c) 12 (d) 13
NoteAnswer
(b) 7. Six units, one per side of the hexagon, each firing on the hexagon’s side of its own line. Then a seventh unit with all weights 1 and threshold 6, which fires only where all six are firing at once, exactly as Equation 9 did with 5.
The tempting wrong answer is (a) 6, from counting the sides and forgetting that something has to combine them. The half-plane units alone produce six separate outputs, not one decision.
Where we are now
flowchart TD
A["What is in the box?"] --> B["Connectionism"]
B --> C["McCulloch-Pitts unit"]
C --> D["Hebb, then Rosenblatt"]
D --> E["XOR: one unit is not enough"]
E --> F["The multi-layer perceptron"]
F --> G["Universal<br/>Boolean machine"]
F --> H["Universal classifier"]
F --> I["Universal function<br/>approximator"]
style G fill:#2ecc71,stroke:#2ecc71,color:#111
style H fill:#2ecc71,stroke:#2ecc71,color:#111
style I fill:#333,stroke:#777,color:#aaa
We can take real numbers in. But we are still only producing yes or no. Our storm detector can tell you whether a storm is coming; it cannot yet tell you that it will arrive in eleven minutes. Can a network of these units compute a continuous-valued function?
Real outputs: universal approximators
Yes, and the construction is a small delight. Let us do the scalar case, \(y = f(x)\) with both \(x\) and \(y\) real, since everything generalises from there.
A bump from three units
Take two threshold units. Give each a weight of 1 on the input \(x\), and give the first a threshold \(T_1\) and the second a threshold \(T_2\), with \(T_1 < T_2\) (which we may assume without loss of generality, since otherwise we just swap their names). Now sum the two outputs with weights \(+1\) and \(-1\).
Walk Figure 24 across the real line.
- For \(x < T_1\): neither unit fires. The sum is \(0 - 0 = 0\).
- For \(T_1 \leq x < T_2\): the first unit fires, the second does not. The sum is \(1 - 0 = 1\).
- For \(x \geq T_2\): both fire, and the \(+1\) and \(-1\) cancel. The sum is \(1 - 1 = 0\).
The result is a square pulse: height 1 between \(T_1\) and \(T_2\), and zero everywhere else. Three units. And since \(T_1\) and \(T_2\) are ours to choose, the pulse can sit anywhere on the line and be as narrow as we like.
From bumps to anything
Once you can make a bump of any width, anywhere, scaled by any height, you can make anything.
Chop the domain into small intervals. On each interval build one pulse, and scale it by a value representative of the target function there: its average over the interval, or simply its value at the midpoint. Sum them all. What comes out is a staircase that hugs the function, and the accuracy is controlled entirely by how narrow you are willing to make the pulses.
The numbers in Figure 25 are the point. Nothing about the target function was chosen to be convenient, and no amount of cleverness went into placing the pulses; the width shrank, and the error shrank with it. The relationship is not an accident: halving the width roughly halves how much the function can vary across a single pulse, which is what bounds the error.
One small accounting note. Building each pulse separately would cost two threshold units per pulse, but adjacent pulses share an edge, so \(n\) pulses need only \(n+1\) threshold units: pulse \(k\) is (the step at \(T_k\)) minus (the step at \(T_{k+1}\)), and the output unit takes a weighted sum of all the steps. That is why Figure 25 reports 33 threshold units for 32 pulses rather than 64.
So we can state the third claim.
MLPs are universal function approximators. Name any function and any error tolerance \(\epsilon > 0\), and I can build you an MLP whose output stays within \(\epsilon\) of that function everywhere on a bounded domain.
Which finally closes the loop on our running example. Feed the storm detector a barometric pressure reading and it can now answer “eleven minutes”, not just “yes”. The output stopped being a verdict and became a number.
This generalises to functions of any number of inputs. Instead of one-dimensional pulses you build multi-dimensional ones, using the polytope construction from Figure 22 to fence off a small cell of the input space, and you assign each cell a height. The bookkeeping is heavier; the argument is identical. The details are for the next lecture.
TipSidebar: capacity is not learnability
A question that comes up immediately, and it is a good one. That staircase is not differentiable at any of its edges. Does that not break everything?
No, and understanding why is worth a paragraph, because it clarifies what kind of claim we have actually been making.
Differentiability matters for learning. Gradient-based training needs to compute how the error changes as each weight changes, and that requires derivatives to exist. A staircase built from hard thresholds has a derivative of zero almost everywhere and no derivative at all at the edges, so gradient descent would have nothing to work with. This is a real problem, and it is one of the reasons the threshold activation was eventually replaced in practice.
But the claim in this post is about capacity: what functions the model is able to represent, given the right weights. That is a statement about the set of functions the architecture can express, and it does not care how you would find the weights. We built every network in this post by hand, from a truth table or a geometric picture. Not once did we train anything.
Capacity and learnability are different questions, and this lecture answers only the first. The rest of the series is largely about the second.
The activation was always a choice
We used the threshold activation throughout, for the good reason that it is the simplest thing to reason about, and everything above is possible with it. But Equation 8 separated the unit into an affine part and an activation part, and once you have done that, the activation is a free choice.
The sigmoid in Figure 26 is a smooth version of the threshold, and being smooth it has derivatives everywhere, which is exactly what the sidebar above says we will need. Softplus and the rectified linear unit are the two that came to dominate practice. We will spend proper time on all three later in the series.
For now, one demonstration that the choice of activation is not cosmetic.
ImportantPoll 4: check yourself
How many neurons with a sinusoidal activation, \(y = \sin(z)\), are required to model the scalar function \(y = \cos(2x)\) precisely (not approximately)?
- 3 (b) \(\lfloor \pi/2 \rfloor\) or \(\lceil \pi/2 \rceil\) (c) infinite (d) none of the above
NoteAnswer
(d) none of the above. The answer is one.
The intuition that says “infinite” is imported from the threshold activation: to build \(\cos(2x)\) out of square pulses you would need an unbounded number of them, since the staircase is only ever an approximation. But we are not using square pulses now. A sinusoidal unit computes \(y = \sin\left(wx + b\right)\), and
\[ \cos(2x) = \sin\left(2x + \frac{\pi}{2}\right). \]
So set \(w = 2\) and \(b = \pi/2\), and a single unit reproduces the target exactly, with zero error.
The lesson is that how many units you need is a fact about the pairing of activation and target, not about the target alone. Anything is possible with threshold activations, which is why they are the right choice for proving universality. But entire classes of activation exist that will do particular jobs for a fraction of the cost.
Closing the loop
We opened with four boxes and one question. Let us go back to them.
Along the way we passed through Plato and Aristotle on association, Hartley’s guess at a physical substrate, the discovery that the brain is a network, Bain’s claim that the information is in the connections and his sad recantation of it, Turing’s unorganised machines, McCulloch and Pitts’ threshold unit and its logic and its illusions, Hebb’s learning rule and its instability, Rosenblatt’s perceptron and its provable convergence and its unfortunate press, the XOR wall, and finally the multi-layer perceptron. And we arrived at three claims.
| Claim | What it means | Built from |
|---|---|---|
| Universal Boolean machine | Any Boolean function, of any number of inputs, is computed by some MLP | Truth table \(\to\) disjunctive normal form \(\to\) ANDs under an OR (Figure 15) |
| Universal classifier | Any decision boundary is captured by some MLP, to arbitrary precision | Half-planes ANDed into polytopes, polytopes ORed into any region (Figure 22) |
| Universal function approximator | Any function is approximated by some MLP, to any error you name | Two thresholds make a pulse, pulses tile the domain (Figure 25) |
And there is more that we have only gestured at. Allow loops in the network, so a unit’s output can feed back as an input at the next time step, and the network can remember: Kubie proposed closed loops as the mechanism of memory in the central nervous system in 1930 (Kubie, 1930), and modern recurrent networks are that idea made precise. MLPs can also represent probability distributions, over integer, real and complex-valued domains, both prior distributions and posteriors conditioned on other variables. And once you can represent a distribution you can sample from it, which is how networks generate images and text and audio from distributions that are complicated or entirely unknown. All of that is later in the series.
So, finally: what is a neural network?
A neural network is a function. Given an input, it computes layer by layer to produce an output. More generally, given one or more inputs, it predicts one or more outputs.
And that is the answer to the question we opened with, because each of the boxes in Figure 1 was a function all along, as Figure 28 relabels them.
flowchart LR
A1["Voice signal"] -->|"f: audio to text"| C1["Transcription"]
A2["Image"] -->|"f: image to caption"| C2["Text caption"]
A3["Game state"] -->|"f: state to move"| C3["Next move"]
A4["Theorem"] -->|"f: statement to proof"| C4["Proof"]
Speech recognition is a function from a waveform to a string. Captioning is a function from an image to a sentence. Playing Go is a function from a board position to a move. Table 6 says that whatever those functions are, an MLP can in principle be them. That is what is in the box.
flowchart TD
A["What is in the box?"] --> B["Connectionism"]
B --> C["McCulloch-Pitts unit"]
C --> D["Hebb, then Rosenblatt"]
D --> E["XOR: one unit is not enough"]
E --> F["The multi-layer perceptron"]
F --> G["Universal<br/>Boolean machine"]
F --> H["Universal classifier"]
F --> I["Universal function<br/>approximator"]
G --> J["The box is an MLP"]
H --> J
I --> J
style G fill:#2ecc71,stroke:#2ecc71,color:#111
style H fill:#2ecc71,stroke:#2ecc71,color:#111
style I fill:#2ecc71,stroke:#2ecc71,color:#111
style J fill:#1f6feb,stroke:#58a6ff,color:#fff
What we have not answered
It would be dishonest to end without listing what this post carefully avoided, because in each case the omission is the subject of a later one.
How big? Every universality argument here is an existence proof, and every one of them is profligate. The disjunctive normal form construction wants one hidden unit per true row of the truth table. The polytope construction wants enough polytopes to approximate a curve. The pulse construction wants enough pulses to hit your error target. None of these tells you how the required size actually scales with the difficulty of the function, and that turns out to be where the question of depth lives: why deep networks are so much more efficient than wide shallow ones, and by how much. That is the next lecture.
How do we find the weights? Every network in this post was built by hand. The only learning rule we have that provably works is alg. 2, which applies to a single unit and only when the classes are linearly separable. How to train a network of many units, with a hidden layer whose targets nobody knows, is the central problem of the field, and it needs the differentiability we set aside in the sidebar above.
Which activation? We proved everything with the threshold, and then Poll 4 showed that the threshold can be spectacularly wasteful. Which activation to use, and why the field converged on the ones it did, is a topic of its own.
Next up: neural networks as universal approximators in more depth, and the question of depth in networks.
References
Anonymous. (1874). The Relation of Mind and Body. Nature, 9, 178–179.
Aristotle. (350 C.E.). On Memory and Reminiscence (J. I. Beare, Trans.).
Azevedo, F. A. C., Carvalho, L. R. B., Grinberg, L. T., Farfel, J. M., Ferretti, R. E. L., Leite, R. E. P., Jacob Filho, W., Lent, R., & Herculano-Houzel, S. (2009). Equal Numbers of Neuronal and Nonneuronal Cells Make the Human Brain an Isometrically Scaled-Up Primate Brain. The Journal of Comparative Neurology, 513(5), 532–541. https://doi.org/10.1002/cne.21974
Bain, A. (1873). Mind and Body: The Theories of Their Relation (Vol. 4). HS King & Company 1873 Farnborough Eng. Gregg International.
Bechtel, W., & Abrahamsen, A. (1991). Connectionism and the Mind: An Introduction to Parallel Processing in Networks. Basil Blackwell.
Copeland, B. J., & Proudfoot, D. (1996). On Alan Turing’s Anticipation of Connectionism. Synthese, 108(3), 361–377. https://doi.org/10.1007/BF00413694
Ferrier, D. (1876). The Functions of the Brain. Smith, Elder; Co.
Hartley, D. (1749). Observations on Man, His Frame, His Duty, and His Expectations. S. Richardson.
Hebb, D. O. (1949). The Organization of Behavior: A Neuropsychological Theory. Wiley.
Hsu, F. (2002). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. Princeton University Press.
Kubie, L. S. (1930). A Theoretical Application to Some Neurological Problems of the Properties of Excitation Waves which Move in Closed Circuits. Brain, 53(2), 166–177. https://doi.org/10.1093/brain/53.2.166
McCulloch, W. S., & Pitts, W. (1943). A Logical Calculus of the Ideas Immanent in Nervous Activity. The Bulletin of Mathematical Biophysics, 5, 115–133. https://doi.org/10.1007/BF02478259
Medler, D. A. (1998). A Brief History of Connectionism. Neural Computing Surveys, 1, 18–72.
Minsky, M., & Papert, S. (1969). An Introduction to Computational Geometry. Cambridge Tiass., HIT, 479(480), 104. https://leon.bottou.org/publications/pdf/perceptrons-2017.pdf
Minsky, M., & Papert, S. (1988). Perceptrons: An Introduction to Computational Geometry (Expanded). MIT Press.
Raj, B., & Singh, R. (2025). 11-785 Introduction to Deep Learning, Fall 2025 (Lecture Videos). YouTube playlist, Carnegie Mellon University Deep Learning. https://youtube.com/playlist?list=PLp-0K3kfddPxpDVLFdFwXzAS2TH-f-QX8
Rosenblatt, F. (1958). The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review, 65(6), 386. https://psycnet.apa.org/record/1959-09865-001
Rumelhart, D. E., McClelland, J. L., & the PDP Research Group. (1986). Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Volume 1: Foundations. MIT Press.
Sanger, T. D. (1989). Optimal Unsupervised Learning in a Single-Layer Linear Feedforward Neural Network. Neural Networks, 2(6), 459–473. https://doi.org/10.1016/0893-6080(89)90044-0
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Driessche, G. van den, Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., & Hassabis, D. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529(7587), 484–489. https://doi.org/10.1038/nature16961
The New York Times. (1958). New Navy Device Learns By Doing. The New York Times.
Turing, A. M. (1969). Intelligent Machinery. In B. Meltzer & D. Michie (Eds.), Machine intelligence 5 (pp. 3–23). Edinburgh University Press.
Vinyals, O., Toshev, A., Bengio, S., & Erhan, D. (2015). Show and Tell: A Neural Image Caption Generator. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 3156–3164. https://doi.org/10.1109/CVPR.2015.7298935
Wu, Y., Schuster, M., Chen, Z., Le, Q. V., Norouzi, M., et al. (2016). Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation. https://arxiv.org/abs/1609.08144
Xiong, W., Droppo, J., Huang, X., Seide, F., Seltzer, M., Stolcke, A., Yu, D., & Zweig, G. (2016). Achieving Human Parity in Conversational Speech Recognition. https://arxiv.org/abs/1610.05256