Simple Algorithm
Artificial Intelligence · Hidden Layer · 20 min

A Short History of AI

From Dartmouth 1956 through two winters to the deep learning era.

AI's history is usually told as booms and winters. Underneath runs a story about algorithms: which ideas worked, why they hit walls, and what it took to get past them. This lesson retells the history through the machinery itself, with the proofs and the numbers that explain each turn.

What you’ll learn

  • Prove that networks of McCulloch–Pitts threshold units can compute any Boolean function, and that a single threshold unit cannot compute XOR.
  • Quantify the combinatorial explosion (branching factor, Shannon's chess estimate) and connect it to NP-completeness and the first AI winter.
  • Describe the match–resolve–act cycle of a rule-based expert system, and explain the knowledge acquisition bottleneck.
  • Explain why reverse-mode differentiation (backpropagation) made multilayer networks trainable, with a cost comparison against finite differences.
  • Quantify the growth of training compute in the deep learning era, and place its landmark systems correctly in time.

1943–1956: neurons, logic and a name

In 1943 Warren McCulloch and Walter Pitts modeled a neuron as a threshold unit: it outputs 1 when a weighted sum of binary inputs reaches a threshold, y=[∑iwixi≥θ]y=\big[\sum_iw_ix_i\ge\theta\big]. They argued that networks of such units could implement logic, and the artificial neuron was born more than a decade before the field had a name.

The name came at Dartmouth in the summer of 1956. There Allen Newell and Herbert Simon (with Cliff Shaw) presented the Logic Theorist, which went on to prove 38 of the first 52 theorems in chapter 2 of Whitehead and Russell's Principia Mathematica. By then Shannon (1950) had already described how a computer could play chess with minimax search and an evaluation function.

DerivationProof: one neuron per true row
  1. AND=[∑ixi≥n],OR=[∑ixi≥1],NOT=[−x≥0]\mathrm{AND}=\Big[\sum_ix_i\ge n\Big],\qquad\mathrm{OR}=\Big[\sum_ix_i\ge1\Big],\qquad\mathrm{NOT}=\big[-x\ge0\big]

    Single units give the basic gates: AND of nn inputs, OR, and NOT (a negative weight).

  2. ha(x)=[∑i: ai=1xi−∑i: ai=0xi ≥ ∣a∣]h_a(x)=\Big[\sum_{i:\,a_i=1}x_i-\sum_{i:\,a_i=0}x_i\ \ge\ \abs a\Big]

    For each input row aa with f(a)=1f(a)=1, build a hidden unit that fires on aa and nowhere else; ∣a∣\abs a is the number of ones in aa. On x=ax=a the sum is exactly ∣a∣\abs a, and every bit in which xx differs from aa lowers it by 1.

  3. f(x)=[∑a: f(a)=1ha(x) ≥ 1]f(x)=\Big[\sum_{a:\,f(a)=1}h_a(x)\ \ge\ 1\Big]

    The output unit ORs the hidden units. This is the disjunctive normal form of ff, wired as a network.

  4. # hidden units ≤ ∣f−1(1)∣ ≤ 2n\#\,\text{hidden units}\ \le\ \abs{f^{-1}(1)}\ \le\ 2^n

    The catch is size: up to 2n2^n hidden units, and Shannon (1949) showed that most Boolean functions need exponentially large circuits of any kind. Representing functions was never the obstacle. Learning the weights was.

1956–1974: search, optimism and the combinatorial explosion

The first decades framed intelligence as heuristic search through a space of possibilities. Newell, Shaw and Simon's General Problem Solver (1959) used means–ends analysis. Arthur Samuel's checkers program learned its own evaluation function, and his 1959 paper put the phrase "machine learning" into its title. SRI's robot Shakey (1966–1972) gave rise to the A* algorithm (1968) and the STRIPS planner (1971).

Optimism ran high. In 1958 Simon and Newell predicted that within ten years a computer would be the world chess champion.

text
function MEANS-ENDS(state, goal, depth) returns a plan or failure
  if state satisfies goal then return []
  if depth = 0 then return failure
  d ← the most important difference between state and goal
  for each operator op relevant to reducing d:
      pre ← MEANS-ENDS(state, preconditions(op), depth − 1)   // make op applicable
      if pre = failure then continue
      s ← the state reached by executing pre, then op
      rest ← MEANS-ENDS(s, goal, depth − 1)
      if rest ≠ failure then return pre + [op] + rest
  return failure

A simplified rendering of GPS's means–ends analysis: reduce the most important difference, recursively setting up subgoals that make the chosen operator applicable. Every choice point multiplies the work.

DerivationThe combinatorial explosion
  1. 1+b+b2+⋯+bd=bd+1−1b−1=Θ(bd) nodes1+b+b^2+\cdots+b^d=\frac{b^{d+1}-1}{b-1}=\Theta\big(b^d\big)\ \text{nodes}

    A search tree with branching factor bb and depth dd has

  2. 3580=1080log⁡1035≈10123.535^{80}=10^{80\log_{10}35}\approx10^{123.5}

    Chess has about b≈35b\approx35 legal moves per position and games of roughly 80 plies, so its full game tree has around 1012310^{123} nodes. Shannon's 1950 estimate of about 1012010^{120} possible games is the famous "Shannon number".

  3. 3512≈3.4×1018 positions ⇒ 3.4×109 s≈107 years35^{12}\approx3.4\times10^{18}\ \text{positions}\ \Rightarrow\ 3.4\times10^{9}\ \text{s}\approx107\ \text{years}

    Even a search only 12 plies deep, at a billion positions per second, would take about a century:

  4. toy problems: bd≈103real problems: bd≥1020\text{toy problems: } b^d\approx10^3\qquad\text{real problems: } b^d\ge10^{20}

    Theory explained the wall. Cook (1971) and Karp (1972) showed that satisfiability and dozens of combinatorial problems are NP-complete: unless P = NP, no algorithm escapes exponential time in the worst case. Methods that shone on toy problems did not scale to real ones.

Check your understanding

An exhaustive chess search (branching factor about 35) moves to a computer twice as fast. How much deeper can it search in the same time?

  1. Twice as deep
  2. One full ply deeper
  3. About a fifth of a ply deeper
  4. No deeper at all
Show the answer

C. About a fifth of a ply deeper

Depth grows like the logarithm of compute: Δd=log⁡352=ln⁡2ln⁡35≈0.19\Delta d=\log_{35}2=\frac{\ln2}{\ln35}\approx0.19 ply. Hardware alone cannot beat exponential growth. Alpha–beta pruning with good move ordering cuts the effective branching factor to about 35≈6\sqrt{35}\approx6, which roughly doubles the depth reachable with the same work; that, plus custom hardware, is how chess programs eventually reached master depth.

1958–1987: perceptrons fall, knowledge rises

Frank Rosenblatt's perceptron (1958) learned the weights of a single threshold unit from examples: after each mistake, w←w+η (y−y^) x\mathbf w\leftarrow\mathbf w+\eta\,(y-\hat y)\,\mathbf x. Novikoff (1962) proved that this rule converges whenever the two classes are linearly separable. Minsky and Papert's Perceptrons (1969) mapped what single-layer perceptrons cannot compute, and the smallest casualty is XOR.

DerivationNo single threshold unit computes XOR
  1. b≤0,w1+b>0,w2+b>0,w1+w2+b≤0b\le0,\qquad w_1+b>0,\qquad w_2+b>0,\qquad w_1+w_2+b\le0

    Suppose [w1x1+w2x2+b>0]=XOR(x1,x2)\big[w_1x_1+w_2x_2+b>0\big]=\mathrm{XOR}(x_1,x_2). The four rows of the truth table require

  2. w1+w2+2b>0 ⟹ w1+w2+b>−b≥0w_1+w_2+2b>0\ \Longrightarrow\ w_1+w_2+b>-b\ge0

    Add the two middle inequalities and use b≤0b\le0:

  3. h1=[x1+x2≥1],h2=[x1+x2≥2],y=[h1−h2≥1]h_1=[x_1+x_2\ge1],\qquad h_2=[x_1+x_2\ge2],\qquad y=[h_1-h_2\ge1]

    That contradicts the last inequality. One hidden layer fixes it: OR minus AND.

Multilayer threshold networks were known to be universal, so the real lesson was that nobody knew how to train hidden layers. Neural network research lost momentum, and the field turned to knowledge.

Expert systems encoded a specialist's know-how as if–then rules. DENDRAL inferred molecular structures from mass spectra (from 1965); MYCIN diagnosed blood infections with several hundred rules (mid-1970s); and R1, later called XCON, configured computer orders at Digital Equipment Corporation, which credited it with savings in the tens of millions of dollars a year by the mid-1980s.

text
function PRODUCTION-SYSTEM(facts, rules) returns facts
  loop:
    conflict_set ← { (r, θ) : the IF part of rule r holds in facts under bindings θ,
                     and (r, θ) has not fired before }             // MATCH
    if conflict_set is empty then return facts
    (r, θ) ← SELECT(conflict_set)       // RESOLVE: specificity, recency, priority
    facts ← facts ∪ SUBST(θ, THEN part of r)                       // ACT

The match–resolve–act cycle of a forward-chaining rule engine, as in the OPS production-system languages used to build R1. A MYCIN-style rule: IF the organism is gram-negative AND rod-shaped AND anaerobic, THEN there is suggestive evidence (0.6) that it is Bacteroides.

1986–2011: learning and probability take over

In 1986 Rumelhart, Hinton and Williams showed that multilayer networks can be trained by gradient descent if the gradient is computed by backpropagation, a reverse-mode application of the chain rule. The method had precursors (Linnainmaa's reverse-mode differentiation in 1970, Werbos's 1974 thesis), but the 1986 paper showed hidden units learning useful internal representations, and it relaunched connectionism. Why was an efficient gradient such a big deal?

DerivationThe cost of a gradient
  1. ∂L∂wj≈L(w+h ej)−L(w)h⟹P+1 passes=Θ(P2)\frac{\partial L}{\partial w_j}\approx\frac{L(\mathbf w+h\,\mathbf e_j)-L(\mathbf w)}{h}\quad\Longrightarrow\quad P+1\ \text{passes}=\Theta\big(P^2\big)

    Let a network have PP weights, so one forward pass costs Θ(P)\Theta(P) operations. Finite differences estimate one partial derivative per extra forward pass:

  2. δ(l)=(W(l+1)⊤δ(l+1))⊙σ′(z(l)),∂L∂W(l)=δ(l) a(l−1)⊤\boldsymbol\delta^{(l)}=\big(\mathbf W^{(l+1)\top}\boldsymbol\delta^{(l+1)}\big)\odot\sigma'\big(\mathbf z^{(l)}\big),\qquad\frac{\partial L}{\partial\mathbf W^{(l)}}=\boldsymbol\delta^{(l)}\,\mathbf a^{(l-1)\top}

    Reverse mode stores the activations a(l)\mathbf a^{(l)} during one forward pass, then sweeps backward once, propagating error signals δ(l)=∂L/∂z(l)\boldsymbol\delta^{(l)}=\partial L/\partial\mathbf z^{(l)} with the chain rule:

  3. cost(∇L)=Θ(P)\text{cost}(\nabla L)=\Theta(P)

    Each weight is touched a constant number of times, so the whole gradient costs a small constant multiple of one forward pass (the "cheap gradient principle").

  4. Θ(P2)Θ(P)=Θ(P)≈106\frac{\Theta(P^2)}{\Theta(P)}=\Theta(P)\approx10^6

    For a million weights, that is the difference between one backward pass and a million forward passes per training step.

Yet neural networks did not take over in the 1990s. Datasets were small, computers slow, and deep or recurrent networks suffered from vanishing gradients. Methods with convex training and strong theory often won instead: support vector machines (Cortes and Vapnik, 1995), boosting, hidden Markov models for speech, and Bayesian networks (Pearl, 1988). AI became statistical: learn from data, reason with probability.

In games, IBM's Deep Blue beat world champion Garry Kasparov in 1997 with alpha–beta search on custom chess chips, examining on the order of 10810^8 positions per second and scoring them with a carefully engineered evaluation function.

2012–today: the deep learning era

Three ingredients converged. Data: ImageNet (Deng et al., 2009) supplied over a million labeled training images in 1,000 classes for its annual challenge. Compute: graphics processors made dense linear algebra cheap. Refinements: ReLU activations, dropout and better initialization made deep networks trainable. In 2012 AlexNet, a convolutional network trained on two GPUs by Krizhevsky, Sutskever and Hinton, cut the top-5 error to 15.3%, against 26.2% for the next-best entry.

YearMilestone
2013–2015word2vec embeddings; deep Q-networks learn Atari games from pixels; GANs; sequence-to-sequence models with attention; ResNet trains networks more than 100 layers deep
2016AlphaGo defeats Lee Sedol 4–1 at Go, combining tree search with deep networks
2017The transformer ("Attention Is All You Need"); AlphaZero masters chess, shogi and Go by self-play alone
2018–2020BERT and GPT pretraining; GPT-3 (175 billion parameters) shows in-context learning; AlphaFold 2 transforms protein-structure prediction
2022ChatGPT, a large language model fine-tuned with human feedback, brings conversational AI to a mass audience
2024Nobel Prizes: Physics to John Hopfield and Geoffrey Hinton, for foundations of machine learning with artificial neural networks; Chemistry to David Baker, Demis Hassabis and John Jumper, for protein design and structure prediction
DerivationHow fast did compute grow?
  1. g(τ)=212/τg(\tau)=2^{12/\tau}

    If training compute doubles every τ\tau months, it grows by this factor each year:

  2. g(20)=20.6≈1.5 per year,g(6)=22=4 per yearg(20)=2^{0.6}\approx1.5\ \text{per year},\qquad g(6)=2^{2}=4\ \text{per year}

    Sevilla et al. (2022) estimated a doubling time of about 20 months for milestone systems before 2010, in line with Moore's law, and about 6 months from 2010 to 2022:

  3. 410=220≈106versus(20.6)10=26=644^{10}=2^{20}\approx10^{6}\qquad\text{versus}\qquad\big(2^{0.6}\big)^{10}=2^{6}=64

    Over a decade, that is six orders of magnitude versus less than two. Chips did not get a million times faster; most of the growth came from spending: more chips, running for longer.

Predict before you look

Suppose training compute doubled every 4 months. By how many orders of magnitude (powers of ten) would it grow in five years?

Show the answer

4.5

Five years is 60 months, or 15 doublings: 215≈3.3×1042^{15}\approx3.3\times10^4, about 4.5 orders of magnitude, since 15log⁡102≈4.515\log_{10}2\approx4.5.

Key takeaways

  • Threshold networks with one hidden layer compute every Boolean function (the DNF construction), but a single unit cannot compute XOR. The obstacle was learning hidden layers, not representing functions.
  • Search hit the combinatorial explosion: Θ(bd)\Theta(b^d) nodes, around 1012310^{123} for chess. NP-completeness explained the wall, and overpromising plus the ALPAC and Lighthill reports brought the first winter.
  • Expert systems (match–resolve–act over if–then rules) succeeded in narrow domains, but the knowledge acquisition bottleneck, rule interactions and brittleness brought the second winter.
  • Backpropagation made a gradient cost Θ(P)\Theta(P) rather than Θ(P2)\Theta(P^2); through the 1990s and 2000s AI turned statistical, with SVMs, HMMs and Bayesian networks.
  • Since 2012, data, GPUs and a few refinements have made deep learning dominant, with training compute growing about fourfold per year (a six-month doubling time) from 2010 to 2022.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Minsky and Papert's 1969 limitations applied most directly to which networks?

  1. All neural networks, including multilayer ones
  2. Single-layer perceptrons: one layer of trainable weights on fixed features
  3. Networks trained by backpropagation
  4. Networks without bias terms
Show the answer

B. Single-layer perceptrons: one layer of trainable weights on fixed features

Their theorems concern what one layer of adjustable weights over fixed feature detectors can compute. Multilayer threshold networks were known to be universal (McCulloch and Pitts); what was missing was a way to train their hidden layers.

Question 2

An exhaustive search with branching factor bb is extended by one more ply. Roughly how much more work does it do?

  1. Twice as much
  2. dd times as much
  3. bb times as much
  4. bdb^d times as much
Show the answer

C. bb times as much

The tree has Θ(bd)\Theta(b^d) nodes, so going from depth dd to d+1d+1 multiplies the work by about bb. That is why depth grows only logarithmically with computing power.

Question 3

Why did backpropagation make it practical to train networks with millions of weights?

  1. It finds the global minimum of the loss
  2. It avoids computing derivatives altogether
  3. It needs no training data
  4. It computes all partial derivatives for a small constant multiple of the cost of one pass through the network, instead of one pass per weight
Show the answer

D. It computes all partial derivatives for a small constant multiple of the cost of one pass through the network, instead of one pass per weight

Reverse-mode differentiation reuses intermediate results, so the full gradient costs a small constant times a forward pass. Finite differences would need one pass per weight: a millionfold slowdown at a million weights.

Question 4

What was the "knowledge acquisition bottleneck" of expert systems?

  1. Turning experts' know-how into rules was slow, costly and incomplete, and the rule bases became hard to maintain
  2. Computers of the 1980s lacked the memory to store rules
  3. Rules could not express uncertainty at all
  4. Experts refused to share their knowledge
Show the answer

A. Turning experts' know-how into rules was slow, costly and incomplete, and the rule bases became hard to maintain

Much expertise is tacit, so knowledge engineers had to coax rules out of experts one at a time, and every new rule could interact with all the others. The bottleneck was human, not hardware.

Question 5

Which combination best explains the 2012 breakthrough in image recognition?

  1. A new learning principle that replaced backpropagation
  2. Better hand-designed features fed to a linear classifier
  3. A large labeled dataset, GPU computing and refinements such as ReLU and dropout, applied to a convolutional network trained with backpropagation
  4. Symbolic rules combined with a small neural network
Show the answer

C. A large labeled dataset, GPU computing and refinements such as ReLU and dropout, applied to a convolutional network trained with backpropagation

AlexNet used ideas going back to the 1980s (convolution, backpropagation), made to work at scale by ImageNet's data, GPUs and a few refinements.

Go deeper

Further reading

  • N. J. Nilsson, The Quest for Artificial Intelligence: A History of Ideas and Achievements (Cambridge University Press, 2010).
  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), section 1.3.
  • W. S. McCulloch & W. Pitts, "A logical calculus of the ideas immanent in nervous activity," Bulletin of Mathematical Biophysics 5, 115–133 (1943).
  • D. E. Rumelhart, G. E. Hinton & R. J. Williams, "Learning representations by back-propagating errors," Nature 323, 533–536 (1986).