Syllabus Module 4 · From symbols to statistics (1943–2012)
NSW 3011 / 32
Software Engineering with Language Models

Module 4 · From symbols to statistics (1943–2012)

Class time
60 minutes
Slides
32, each with teacher’s notes
Goes with
Discussion questions 1 to 3
Module 42 / 32

Where this module sits

  • Part I fixed the vocabulary: model, harness and labels.
  • Part II explains where the technology came from and how it works.
  • This class covers 1936 to 2012, from rule-based symbols to learned statistics.
  • The aim is that you can derive later design choices instead of memorising them.
  • This class prepares you for Module 5, "The Transformer and the scaling era (2013–2026)".
Module 43 / 32

Objectives

  • Place any current technique on a seventy-year timeline.
  • Explain why each earlier approach stalled.
  • State the three ingredients whose arrival in the same decade made deep learning work.
  • Define a language model as a factorised probability distribution.
  • State the bitter lesson and turn it into a falsifiable prediction.
Module 44 / 32

Agenda

  • 4 min: frame and objectives.
  • 12 min: 4.1 two founding ideas and Shannon's thread.
  • 14 min: 4.2 why the first two waves stalled.
  • 10 min: 4.3 backpropagation and the long wait.
  • 9 min: 4.4 statistical language processing.
  • 11 min: 4.5 the year 2012, the timeline, mistakes, recap.
Module 45 / 32

4.1 Thinking as symbol manipulation

  • The first idea is that thinking is the manipulation of symbols by rules.
  • 1936: Turing's machine shows that a small set of mechanical operations can compute anything computable.
  • 1950: Turing turns the question of machine thought into a behavioural test conducted in text.
  • 1956: the Dartmouth workshop gives the programme its name.
  • The Logic Theorist, the General Problem Solver and later LISP-based systems follow.
  • Those systems pursue intelligence as search through a space of symbolic expressions.
Module 46 / 32

Thinking as adjusted connections

  • The second idea is that thinking is what networks of simple units do when experience adjusts their connection strengths.
  • 1943: McCulloch and Pitts model the neuron as a threshold logic gate.
  • 1958: Rosenblatt's perceptron adds a learning rule.
  • The rule says to adjust every weight in proportion to the error after each example.
  • The rule provably converges when the problem is linearly separable.
Module 47 / 32

Drawing of a threshold unit

 x1 --w1--\
           sum --> 1 if sum >= t
 x2 --w2--/        0 otherwise

 sum = w1*x1 + w2*x2

 After each example:
 nudge each weight in proportion
 to the error.
Module 48 / 32

Shannon's third thread

  • 1948: Shannon defines the information content of a message from the probability of its symbols.
  • 1951: Shannon measures the entropy of printed English.
  • His method is to have people guess the next letter of a text.
  • A language model in the modern sense is that guessing game played by a machine.
  • A language model is a function that assigns a probability to the next symbol, given the symbols so far.
Module 49 / 32

Definition of a language model

P(x1 ... xn)
  = P(x1)
  x P(x2 | x1)
  x P(x3 | x1 x2)
  ...
  x P(xn | x1 ... xn-1)

Each factor:
P(next token | tokens so far)
Module 410 / 32

Worked example: factorising a sentence

  1. The sentence is "the cat sat". The probabilities are made up.
  2. P(the) = 0.10.
  3. P(cat | the) = 0.02.
  4. P(sat | the cat) = 0.30.
  5. P(the cat sat) = 0.10 x 0.02 x 0.30 = 0.0006.
  6. To generate, the model runs the same factors forward: evaluate, choose a token, append, repeat.
Module 411 / 32

Ask the room: discussion question 2

  • Shannon's human guessers put the entropy of English at roughly one bit per letter.
  • State what a model's per-token loss measures in the same terms.
  • Explain why lower loss is evidence of something that looks like understanding.
  • Work for two minutes in pairs, then two pairs report.
Module 412 / 32

4.2 The first stall in 1969

  • 1969: Minsky and Papert publish "Perceptrons".
  • They prove that a single-layer perceptron cannot represent functions that are not linearly separable.
  • The standard example is XOR.
  • Multi-layer networks can represent such functions.
  • Nobody then had a practical way to train the hidden layers.
  • Funding moved to symbolic systems.
Module 413 / 32

Worked example: XOR and a single threshold unit

x1x2XORRequired of the unit
000t is above 0
011w2 is at least t
101w1 is at least t
110w1 + w2 is below t
Module 414 / 32

Expert systems

  • Symbolic AI then produced expert systems.
  • An expert system is a hand-written rule base.
  • MYCIN diagnosed infections.
  • XCON configured VAX orders.
  • Expert systems worked inside narrow domains.
  • Expert systems failed outside those domains.
Module 415 / 32

The failure of expert systems

  • Reason 1 is the knowledge-acquisition bottleneck: knowledge was extracted from experts one rule at a time.
  • Reason 2 is that rules interacted in ways their authors could not predict.
  • Reason 3 is that nothing degraded gracefully when an input fell outside the rules.
  • The result was the second "AI winter" in the late 1980s.
Module 416 / 32

Ask the room: discussion question 1

  • Expert systems failed on the knowledge-acquisition bottleneck.
  • A present-day agent depends on hand-written tool descriptions and instruction files.
  • Identify the equivalent bottleneck in that agent.
  • Argue whether the agent's bottleneck is the same failure or a different failure.
  • Work for three minutes in pairs, then two pairs report.
Module 417 / 32

The bitter lesson

  • A system whose competence is bounded by hand-written knowledge stops improving when its builders run out of time.
  • A system whose competence is bounded by data and compute keeps improving as data and compute grow.
  • Sutton later named this pattern the bitter lesson.
  • The evidence for the lesson is seventy years of results.
  • General methods that scale with computation overtook methods that encode human insight about the domain.
Module 418 / 32

In-class exercise: discussion question 3

  • Turn the bitter lesson into a falsifiable prediction about a tool you use now.
  • Step 1: name one part of the tool that encodes human insight by hand.
  • Step 2: predict what a more general, compute-scaled method does to that part.
  • Step 3: state the measurement that would show the prediction wrong.
  • Work for three minutes alone, then read one prediction aloud.
Module 419 / 32

4.3 Backpropagation

  • 1986: Rumelhart, Hinton and Williams popularise backpropagation.
  • Step 1: compute the error at the output.
  • Step 2: apply the chain rule backwards through the layers.
  • The result is the gradient of the error with respect to every weight.
  • Backpropagation solved the hidden-layer training problem in principle.
Module 420 / 32

Drawing of backpropagation

forward:
 input -> L1 -> L2 -> output
                        |
                  error at output
                        |
backward (chain rule):
 error -> L2 grads -> L1 grads

Every weight gets a gradient.
Module 421 / 32

Working networks and the long wait

  • 1989 to 1998: LeCun's convolutional networks read handwritten digits on bank cheques.
  • Recurrent networks handled sequences by feeding their own hidden state back in.
  • 1997: Hochreiter and Schmidhuber's Long Short-Term Memory adds gated cells.
  • Gated cells let gradients survive across long spans.
  • 1990s and 2000s: support vector machines, boosted trees and graphical models mostly outperformed neural networks.
  • Those methods had better theory and lower compute demands.
Module 422 / 32

The three missing ingredients

IngredientWhat was missingWhat supplied it
DataLabelled sets at the scale of millionsThe web; ImageNet (2009), 14 million labelled images
ComputeCheap dense linear algebraGraphics processors programmed for general use (CUDA, 2007)
TechniqueStable training of deep stacksReLU activations, better initialisation, dropout; later batch and layer normalisation, residual connections
Module 423 / 32

4.4 The noisy channel

  • Language technology took the statistical turn earlier than vision.
  • From the late 1980s IBM's speech and translation groups frame both problems as noisy-channel decoding.
  • The rule is to choose the output sentence that maximises P(output) x P(input | output).
  • The first factor, P(output), is a language model.
Module 424 / 32

N-gram models and smoothing

  • In practice the language model was an n-gram model.
  • An n-gram model estimates the probability of a word from counts of the previous two to four words.
  • The problem is that some word sequences never occur in the training text.
  • The remedy is smoothing, which handles sequences never seen in training.
  • The module names two smoothing methods, Katz back-off and Kneser-Ney.
Module 425 / 32

Worked example: a bigram model by hand

Corpus (made-up):
the cat sat . the cat ran .
the dog sat .

P(cat|the) = n(the cat)/n(the) = 2/3
P(dog|the) = n(the dog)/n(the) = 1/3
P(sat|cat) = n(cat sat)/n(cat) = 1/2
P(ran|dog) = n(dog ran)/n(dog) = 0/1
Module 426 / 32

Two limits of n-grams and the 2003 neural language model

  • Limit 1: an n-gram model cannot use context beyond a few words.
  • Limit 2: an n-gram model treats every word as an unrelated symbol, so "cat" teaches it nothing about "kitten".
  • 2003: Bengio and colleagues publish a neural probabilistic language model.
  • The model maps each word to a learned vector.
  • The model predicts the next word from the vectors of the previous few words.
  • Words used in similar contexts end up with similar vectors.
Module 427 / 32

4.5 The three ingredients together in 2012

  • AlexNet is a convolutional network by Krizhevsky, Sutskever and Hinton.
  • AlexNet was trained on two consumer graphics cards.
  • It cut the ImageNet top-5 error from about 26% to about 15%.
  • Nothing in AlexNet was conceptually new.
  • The result was the first large public demonstration that depth, data and GPU compute beat hand-engineered features.
  • Within three years deep networks held the best results in speech recognition, vision and translation.
Module 428 / 32

The timeline from 1936 to 2012

1936 Turing machine
1943 threshold neuron
1948 Shannon: information
1956 Dartmouth workshop
1958 perceptron
1969 "Perceptrons": XOR limit
1986 backpropagation
1997 LSTM
2003 neural language model
2012 AlexNet
Module 429 / 32

In-class exercise: present-day techniques on the timeline

  • Next-token prediction as the definition of a language model.
  • Embeddings and semantic search.
  • Training a multi-layer network by gradients.
  • Training on graphics processors.
  • A hand-written rule file that tells an agent what to do.
  • For each item, give the year it starts and what had blocked it.
Module 430 / 32

Common mistakes

  • Learning names and dates only. Fix: state what stalled and what removed the block.
  • Believing 2012 introduced a new idea. Fix: nothing in AlexNet was conceptually new.
  • Believing neural networks are recent. Fix: 1943, 1958 and 1986 are the dates.
  • Believing XOR defeated neural networks. Fix: XOR defeated single layers.
  • Treating next-token prediction as a recent trick. Fix: next-token prediction is Shannon's 1951 guessing game.
  • Merging the two n-gram limits. Fix: short context is one limit; unrelated symbols is the other limit.
Module 431 / 32

Recap

  • Two ideas compete: rules over symbols, and networks whose weights are adjusted by experience.
  • A language model is a probability distribution over token sequences, factorised left to right.
  • Single-layer perceptrons stalled on XOR in 1969; expert systems stalled on the knowledge-acquisition bottleneck.
  • The bitter lesson says that methods that scale with computation overtake hand-encoded domain insight.
  • Deep learning needed data, compute and technique together; the three met in 2012.
  • Embeddings descend from the 2003 neural language model.
Module 432 / 32

Before next class

  • Read Module 5, "The Transformer and the scaling era (2013–2026)".
  • Write a paragraph answering discussion question 2 in your own words.
  • Keep your falsifiable prediction from discussion question 3.
  • Count the bigram example again by hand without looking at the slide.
  • Module 5's problem set and the pyramid in Assignment 2 start from a bigram model.