Introduction & History

Machine Learning (ML) is the field of study that gives computers the ability to learn from data without being explicitly programmed for every situation. Instead of writing rules by hand, we write programs that infer the rules from examples.

This first lesson says what "learning" means, when it is worth it, and shows it at work in a machine with no electronics at all: matchboxes and colored beads that learn a small board game from feedback alone. It then tells how the field got here, in 200 years of history, and maps the questions the rest of the course will answer. The numbers quoted about the matchbox machine come from its two simulators on this page, which are deterministic: everyone who presses the same buttons sees the same games.

How this lesson is organized

The lesson has two approaches. Each has slides, text and an activity to do in class in the simulator on this page; the quiz at the end covers the fundamental one. Start with the fundamental approach: the advanced one builds on it.

Both labs run in the matchbox simulator of section 3, in the browser: there is nothing to install, and no notebook this time.

Fundamental approach

One question drives this part: what does it mean for a machine to learn, and when is it worth it? The answer starts from a definition with three ingredients, a task, experience and a way to measure performance, and ends with a machine made of matchboxes that gets better at a game only because its mistakes are removed, one bead at a time.

This part follows one path in four stages, drawn below: 1. what learning is, Mitchell's definition; 2. why learn, when hand-written rules break down and how learning inverts the flow; 3. a machine that learns, matchboxes that learn a game from feedback alone; 4. why now, the three forces behind today's machine learning and its main eras. Each stage links to its section, and in the slides a strip at the bottom shows which stage you are in.

Fundamental approach slides

Click the slides and use the ← → arrows to navigate; F opens full screen and Esc shows every slide. Open the slides in a new tab

1. What it means to learn

Stage 1. The classic formal definition is due to Tom Mitchell:

Every project in this course can be described in that vocabulary. A spam filter, for instance:

• Task \(T\): classify e-mails as spam or not spam;
• Experience \(E\): a corpus of e-mails already labeled by humans;
• Performance \(P\): the fraction of e-mails classified correctly (or a more careful metric, as we will see in Classification Metrics).

The three ingredients are not optional. Without \(P\) there is no way to say that anything improved, and a system that only stores more and more examples, with no measure of whether it answers better, has not learned in Mitchell's sense.

2. Why learn from data?

Stage 2. Hand-written rules break down when:

1. The rules are unknown. Nobody can write down the exact rules that distinguish a malignant tumor from a benign one in a raw image.
2. The rules change. Spammers adapt; a static filter decays. A learning system can be retrained.
3. The rules are too many. Recognizing handwritten digits with if/else statements is hopeless — there are too many ways to write a "7".
4. Personalization is needed. A recommender must behave differently for every user; learning from each user's history scales, hand-tuning does not.

Machine learning inverts the traditional flow: instead of rules + data → answers, we feed data + answers to an algorithm and obtain a model — an approximation of the rules — which we then use to answer new, unseen cases.

The converse matters as much: when the rule is fixed, fully known and short, such as "a card number has exactly 16 digits", program it. Learning pays off only where one of the four reasons above holds.

3. A learning machine made of matchboxes

Stage 3. Long before GPUs, Martin Gardner's 1962 Scientific American column described a machine that learns to play a game using only matchboxes and colored beads — no electronics at all. For the mini-game Hexapawn (three pawns per side on a 3×3 board), build one matchbox per possible board position, and fill it with beads for each legal move:

1. to move, open the matchbox for the current position and draw a random bead — that's the move;
2. if the machine eventually loses the game, remove the bead that led to the losing move (punishment);
3. if it wins, the beads stay (or extra copies are added — reward).

If the box for the current position is empty, every move from there has already lost: the machine resigns, and the punishment goes to the move that led it there. After a few dozen games the bad moves have literally been removed from the boxes: the machine plays perfectly. This is reinforcement learning in its purest mechanical form (Donald Michie built the same idea for tic-tac-toe in 1961 and called it MENACE), and it makes Mitchell's definition tangible: the task \(T\) is playing Hexapawn, the experience \(E\) is games played, the performance \(P\) is the win rate — and learning is nothing more than adjusting parameters (beads) based on feedback.

The learning loop, step by step

The machine needs 19 boxes, one per position it can face when a position and its mirror image share a box, and 47 beads, one per legal move. The simulator below follows its first three training games against an opponent that plays at random, one move per step: the position, the box for that position, the bead drawn and, at the end of each game, the update. The panel on the right keeps Mitchell's tally, \(E\) games played and \(P\) the win rate.

Game 1 is lost and its last bead goes (47 → 46); game 2 is won and nothing changes, since this machine only punishes; game 3 is lost again (46 → 45), and the bead removed was the only one in its box, so that box is now empty. After three games \(P = 1/3\): learning has barely started, but every loss already makes one bad move impossible.

Play against the machine

Play against the machine below (you are blue and move first), then press train N games and watch the beads disappear from the boxes as the machine's win rate climbs. Keep an eye on the line under the simulator: at some point the machine can no longer be beaten.

Nothing in the boxes "understands" Hexapawn: the machine got better only because feedback removed the moves that lost.

4. Why now?

Stage 4. None of the core ideas are new — least squares is from 1805 — but three forces converged in the last two decades to make ML ubiquitous:

• Data: the web, sensors, and digitization produced datasets large enough to learn subtle patterns;
• Compute: GPUs and cloud computing made it cheap to fit large models;
• Algorithms & software: open-source libraries (scikit-learn, XGBoost, PyTorch) turned decades of research into a few lines of code.

The main eras

The history of ML is a 200-year conversation between statistics and computer science. In five eras (the advanced approach tells it milestone by milestone):

The last era is where the three forces meet: deep networks are an idea of the 1980s that needed the data and the compute of the 2010s.

5. Summary: learning in five lines

1. ML is programs that infer the rules from examples, instead of rules written by hand.
2. Learning, after Mitchell: performance \(P\) on a task \(T\) improves with experience \(E\). No \(P\), no learning.
3. It inverts the flow: data + answers → model, used on new, unseen cases. It pays off when the rules are unknown, change, are too many or must be personalized; a short, fixed rule should be programmed.
4. The matchbox machine: learning is adjusting parameters (beads) from feedback (losses), with no understanding at all.
5. Why now: the ideas are old; data, compute and open-source software made them practical.

Fundamental lab — teach the matchbox machine

The problem. A fresh matchbox machine plays Hexapawn at random. You will play against it, train it and try to beat it after training, watching \(E\) grow, \(P\) climb and the beads go. The question behind the three steps: when can you say that a machine has learned, and how sure can you be that it has learned everything?

Step 1 — play a fresh machine

Predict. A fresh machine draws its moves at random from full boxes. Will you beat it easily? And when you win, what changes inside its boxes?

Before playing, step through the learning loop once (about 20 clicks). Then play three games against the machine: click one of your blue pawns, then its destination square. After each game, look at the boxes: the box the machine used last has an orange border, and the bead of its last move is ringed.

A fresh machine is easy to beat, and every win of yours removes one bead, marked ✕ in its box: that move will never be played again. When the machine wins, its beads stay where they are. The line under the board counts the beads left, out of 47.

Step 2 — train it for 50 games

Predict. Press reset machine (opponent: random, N = 50) and then train N games. Will the win rate climb smoothly? Will the machine stop losing within these 50 games?

The readout under the simulator says:

50 games played: the machine won 36 and lost 14; each loss removed one bead. Beads left: 33/47.
Can it still be beaten? yes: some line of play still leads to a bead that loses.

The 14 losses removed 14 beads (47 → 33). They are not spread evenly: the red marks on the curve crowd at the left, and all 14 losses happen in the first 38 games (games 1, 3, 5, 6, 7, 8, 9, 11, 19, 20, 21, 27, 30 and 38). The win rate over the last 10 games does not climb smoothly, because the machine still draws at random among the beads it has left. In Mitchell's terms: \(E\) grew from 0 to 50 games and \(P\) rose from losing 8 of the first 11 games to winning the last 12 in a row.

Step 3 — the champion that can still be beaten

Predict. Train 50 more games (same N). If the machine wins all 50, can you conclude that it can no longer be beaten?

50 games played: the machine won 50 and lost 0; each loss removed one bead. Beads left: 33/47. It won every game, yet it can still be beaten: it only learned the lines this opponent plays.
Can it still be beaten? yes: some line of play still leads to a bead that loses.

Fifty wins in a row, and still beatable. A random opponent rarely plays the one line that still works, so no game in this batch reached the losing bead, and a bead that is never reached is never punished. A perfect record on the games it has seen says nothing about the games it has not.

Simulation: beat the champion. Without training any further, play against the machine yourself and find a line of play that still beats it. Hint: open with your center pawn, and think about which pawn of yours can reach the last row once the machine captures.

Can it still be beaten? no: whatever blue plays, every bead left leads to a win. Learning = beads removed by feedback.

Simulation: let the random opponent find it. Press reset machine, train 50 games twice (as in steps 2 and 3), then set N = 200 and train twice more. In which batch does the 15th loss come, and what does the readout say after it?

200 games played: the machine won 200 and lost 0; each loss removed one bead. Beads left: 33/47. It won every game, yet it can still be beaten: it only learned the lines this opponent plays.
200 games played: the machine won 199 and lost 1; each loss removed one bead. Beads left: 32/47.
Can it still be beaten? no: whatever blue plays, every bead left leads to a win. Learning = beads removed by feedback.

To close the fundamental part. In one sentence each: (1) what are \(T\), \(E\) and \(P\) for the matchbox machine? (2) What, exactly, changed inside the machine when it got better? (3) Why did 50 wins in a row not prove that it could no longer be beaten?

Your turn (fundamental)

At home:

1. Mitchell's vocabulary. Describe three systems you use every day (a recommender, a voice assistant, a map that predicts traffic, for instance) by their \(T\), \(E\) and \(P\). Which one is hardest to give a \(P\)?
2. Learn or program? For each of the four reasons hand-written rules break down, find an example from your own experience; then find one task you would simply program.
3. On paper. Read Gardner's original article and play Hexapawn with a friend, one of you being the machine with boxes and beads. How many games does your machine need before it stops losing?

Advanced approach

The fundamental part defined learning and watched a machine do it. This part steps back to see how the field got here and where this course is going: the 200-year timeline, what the matchbox machine has in common with the perceptron (and what it lacks), the two AI winters and the revivals that followed, three lessons that shape the design of this course, and the questions the next lessons will answer.

This part follows one path in four stages, drawn below: 1. 200 years of milestones; 2. the perceptron and the winters; 3. reading the arc; 4. the course ahead. Each stage links to its section, and in the slides a strip at the bottom shows which stage you are in.

Advanced approach slides

Click the slides and use the ← → arrows to navigate; F opens full screen and Esc shows every slide. Open the slides in a new tab

6. A brief history of machine learning

Stage 1. The history of ML is a 200-year conversation between statistics and computer science. The timeline below marks the milestones this course will visit — from the historical basis to the current edge.

[timeline left alternate(./docs/2026.2/classes/introduction/timeline.json)]

7. From matchboxes to the perceptron, and two winters

Stage 2. The matchbox machine and Rosenblatt's perceptron (1958) learn the same way: from feedback on their mistakes. The perceptron is a linear classifier with one weight per feature; when it gets an example wrong, it nudges its weights toward the right answer, and when it gets it right, it changes nothing — the neural networks lesson runs it by hand. The difference is in what is stored. The matchbox machine keeps one box per position, a lookup table: what it learns in one box says nothing about any other, and a position it never met would find no box at all. The perceptron keeps a few weights shared by every input, so each update changes its answer on examples it has never seen: it generalizes. Hexapawn is small enough to give each of its positions a box; almost no real problem is, which is why every model in this course is a function with parameters, not a table of answers.

That generalization has limits, and the first one stopped the field. In 1969 Minsky and Papert proved that a single perceptron cannot learn problems that are not linearly separable, such as XOR; the Lighthill Report (1973) concluded that AI had failed to deliver, and funding collapsed across the US and the UK: the first AI winter (roughly 1974–1980). Learning revived in the 1980s on two fronts: backpropagation (1986) made multi-layer networks trainable — and they do solve XOR — while CART (1984) and ID3 (1986) made decision trees practical. A second winter (roughly 1987–1993) followed the collapse of the expert-systems boom, programs built from hand-written rules — exactly the approach that section 2 says breaks down. Both winters have the same shape: promises outran results.

Two revivals followed, each answering a weakness. Statistical learning (1995–2001: support vector machines, AdaBoost, random forests, gradient boosting) brought theory — margins, generalization bounds — and the habit of honest validation. Deep learning (2012 onward) brought neural networks back at scale, once the three forces of section 4 were in place: large labeled datasets, GPUs and open software.

8. Reading the arc

Stage 3. Three lessons from this history shape the design of this course:

1. The classics never left. Least squares (1805) is still the first model you should try on a regression problem. Logistic regression (1958) remains a production workhorse. Understanding them deeply is not archaeology — it is engineering.
2. Hype cycles are real. The field went through two "AI winters" (roughly 1974–1980 and 1987–1993) when promises outran results. Honest evaluation — the subject of the cross-validation lesson — is the antidote.
3. Modern methods are compositions of classical ideas. BERTopic (2022), which we will study in its own lesson, is literally a pipeline of embeddings + dimensionality reduction + clustering + TF-IDF — every ingredient is a classical technique. Gradient boosting is functional gradient descent on decision trees. Knowing the parts lets you understand — and debug — the whole.

9. Where this course fits

Stage 4. This course covers classical machine learning end to end and finishes at the frontier: neural networks, explainability, AutoML, MLOps, and foundation models. Deep learning gets one bridging lecture here; its full treatment lives in the companion course Artificial Neural Networks and Deep Learning.

The questions the course will answer

Every lesson ahead answers one question that a real project raises sooner or later:

Advanced lab — what the machine learned, and the map of the course

The fundamental lab trained the machine against a random opponent until it could not be beaten. This part asks what the machine really learned — the game, or the opponent it trained against — and then turns from the matchboxes to the map: where each milestone of the timeline lives in this course, and which classical pieces a modern method is made of.

Step 4 — a different teacher

Predict. The greedy opponent wins at once when it can, otherwise captures, otherwise plays at random: a stronger player than the random one. Will a machine trained against it be stronger against everyone?

Press reset machine, click the opponent button until it reads opponent: greedy, set N = 200 and train twice:

200 games played: the machine won 193 and lost 7; each loss removed one bead. Beads left: 40/47.
Can it still be beaten? yes: some line of play still leads to a bead that loses.
200 games played: the machine won 200 and lost 0; each loss removed one bead. Beads left: 40/47. It won every game, yet it can still be beaten: it only learned the lines this opponent plays.
Can it still be beaten? yes: some line of play still leads to a bead that loses.

The greedy opponent teaches fast — 7 losses, all within the first 27 games — but it teaches less. It never passes up a win or a capture, so the lines in which blue declines a capture never happen, and the beads on those lines are never punished: after 400 games the machine keeps 40 beads, against the 32 of the machine that became unbeatable against the random opponent, and it can still be beaten. The machine learned to beat this opponent, not the game. A model learns the distribution of its experience \(E\); if the cases it will face later come from a different distribution, its performance \(P\) on the training games says little about them. This is the central problem of the ML landscape lesson, generalization.

Simulation: change the teacher. Without resetting, switch the opponent back to random and train 200 more games. Does the machine lose again? Does it become unbeatable?

200 games played: the machine won 197 and lost 3; each loss removed one bead. Beads left: 37/47.
Can it still be beaten? no: whatever blue plays, every bead left leads to a win. Learning = beads removed by feedback.

Step 5 — the timeline as a map of the course

Predict. Which milestones of the timeline do you expect to meet again in this course, and which are history only?

For each milestone of the timeline, name the lesson of this course that teaches the method it introduced, using the table of questions and the course menu.

Step 6 — take a modern method apart

Predict. Gradient boosting and random forests dominate tabular data today. Are they new ideas, or old ones put together?

Write each method below as a sum of pieces from the timeline, and name the lesson where each piece is taught: (a) random forest; (b) gradient boosting; (c) BERTopic.

To close the lesson. In one sentence each: (1) why does a model that generalizes beat a table of boxes, one per case? (2) What do the two AI winters have in common, and what is their antidote? (3) Why did the machine trained against the greedy opponent remain beatable?

Your turn (advanced)

At home, with more time:

1. Reward, not only punishment. Gardner's rule also allows a reward: when the machine wins, add an extra copy of each bead it used. Predict what would change: would the machine stop losing sooner, later, or after the same number of losses? And would it still be beatable after a long winning streak against the random opponent?
2. A bigger board. MENACE learned tic-tac-toe with the same idea. Why does tic-tac-toe need many more boxes than Hexapawn, and what would happen to a matchbox machine for chess? Relate your answer to the difference between a lookup table and a model that generalizes (section 7).
3. A hype check. Pick a recent news story about an AI system. Describe it by its \(T\), \(E\) and \(P\), and write down the one piece of honest evaluation you would ask for before believing the claim.

References

• Turing, A. M. "Computing Machinery and Intelligence." Mind 59 (1950). DOI
• Samuel, A. L. "Some Studies in Machine Learning Using the Game of Checkers." IBM J. Res. Dev. 3 (1959). DOI
• Bishop, C. M. Pattern Recognition and Machine Learning. Springer, 2006.

Quiz

The quiz covers the fundamental approach.