THE STANDARD DEFINITION (Mitchell, 1997), and it is worth quoting precisely because it names the three things any learning problem must specify: "A computer program is said to LEARN from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E." THE THREE COMPONENTS, and a learning problem is not properly stated until all three are: T THE TASK what the program must do P THE PERFORMANCE how success is measured MEASURE E THE EXPERIENCE what it learns from WORKED SPECIFICATIONS: SPAM FILTERING T: classify an email as spam or not P: the fraction of emails correctly classified E: a corpus of emails labelled by users PLAYING CHECKERS (Samuel, 1959) T: play checkers P: the fraction of games won against opponents E: games played against itself RECOMMENDING A REVISION TOPIC T: choose the next topic for a student P: expected exam mark E: the tick history and outcomes of many students NOTE THAT P IS THE SAME OBJECT AS THE AGENT'S PERFORMANCE MEASURE FROM ACtE0901, and it carries the same danger: A LEARNING SYSTEM OPTIMISES EXACTLY WHAT YOU MEASURE. Every warning from the agents topic applies here with more force, because the system will search harder for the loophole than a hand-written program ever could. WHY LEARN AT ALL — four reasons, each with a case where nothing else works: 1. THE KNOWLEDGE IS UNAVAILABLE. Nobody can articulate the rule for recognising a handwritten digit, so it cannot be programmed — only learned. 2. THE ENVIRONMENT CHANGES. Spam adapts, so a fixed rule set decays, as the agent-types topic established. 3. THE PROBLEM IS TOO LARGE TO ENUMERATE. There is no table of every possible email. 4. IT IS CHEAPER. Collecting labelled examples costs less than interviewing experts, which is the bottleneck argument. THE FUNDAMENTAL ASSUMPTION, and everything depends on it: THE FUTURE RESEMBLES THE PAST. Formally, training and test data are drawn from the SAME DISTRIBUTION. When that fails — DISTRIBUTION SHIFT — the model degrades and usually does not announce it. This is the third question of the AI applications checklist, and it is why deployed models need monitoring rather than delivery.

EVERY SUPERVISED LEARNING PROBLEM has the same anatomy: INSTANCE (example, sample) one thing to be classified or predicted FEATURES (attributes) the measurable properties of an instance, written as a vector x LABEL (target) the correct answer y, for supervised learning TRAINING SET the examples used to fit the model HYPOTHESIS h the function the learner produces, mapping features to a prediction HYPOTHESIS SPACE H the set of all functions the learner can possibly produce LOSS FUNCTION how wrong a prediction is TEST SET held-back examples used to estimate performance on unseen data THE LEARNING TASK, stated formally: find the hypothesis h in H that minimises the expected loss on data drawn from the true distribution — while only being able to measure the loss on the training set. THAT GAP IS THE ENTIRE DIFFICULTY OF MACHINE LEARNING. THE HYPOTHESIS SPACE DETERMINES WHAT CAN BE LEARNED, and this is the most under-appreciated point in the topic: · if H is too SMALL, the true function may not be in it, and no amount of data helps. A linear model cannot learn XOR however many examples it sees — the result that stalled neural networks for seventeen years. · if H is too LARGE, the learner can fit the training data exactly, including its noise, and generalise badly. CHOOSING H IS THEREFORE THE CENTRAL DESIGN DECISION, and it is called the INDUCTIVE BIAS: the set of assumptions the learner brings about what the answer looks like. NO INDUCTIVE BIAS MEANS NO LEARNING. This is worth stating carefully because it is counter-intuitive: a learner with no assumptions cannot generalise at all, because any function consistent with the training data is equally acceptable, and most of them behave arbitrarily on new inputs. WORKED: given three points (1,1), (2,4), (3,9), what is f(4)? "16" requires assuming a simple polynomial. Without that assumption, a function returning 16 and one returning −7 000 are equally consistent with the data. THE NO FREE LUNCH THEOREM makes this precise: averaged over ALL possible problems, every learning algorithm performs identically. Algorithms differ only in which assumptions they make, and an algorithm is good only because its assumptions happen to fit the problems we care about. THE TYPES OF TASK: CLASSIFICATION predict a discrete label — spam/not, which disease, which digit REGRESSION predict a continuous value — price, temperature, days to failure CLUSTERING group similar instances, with no labels DIMENSIONALITY find a lower-dimensional representation REDUCTION ASSOCIATION find co-occurrence rules — "customers who RULE MINING buy X also buy Y" RANKING order items by relevance SEQUENCE predict the next element, or label a LABELLING sequence

THE CENTRAL PROBLEM: a model must perform well on data it has never seen. Fitting the training data is easy and insufficient. OVERFITTING: the model captures noise and idiosyncrasy in the training set rather than the underlying pattern. Training error falls, test error rises. UNDERFITTING: the model is too simple to capture the pattern. Both errors stay high. THE CHARACTERISTIC CURVES: error │ │╲ ╱ test error │ ╲ ╱ │ ╲ ╱ │ ╲__________________╱ │ ╲ │ ╲________ training error └────────────────────────────────── simple ──── model complexity ──── complex ↑ the sweet spot: minimum TEST error TRAINING ERROR ALWAYS FALLS WITH COMPLEXITY. Test error falls and then rises. THE GAP BETWEEN THEM IS THE OVERFITTING, and it is the only thing worth watching. THE BIAS-VARIANCE DECOMPOSITION explains why: BIAS error from wrong assumptions — the model cannot represent the truth. High for simple models. VARIANCE error from sensitivity to the particular training sample — a different sample gives a very different model. High for complex models. IRREDUCIBLE NOISE error nothing can remove total expected error = bias² + variance + noise THE TRADE-OFF: reducing bias by adding complexity increases variance. THE ART IS BALANCING THEM, and more data shifts the balance — it reduces variance without affecting bias, which is why complex models become viable at scale. HOW TO MEASURE GENERALISATION HONESTLY: TRAIN/TEST SPLIT hold back, say, 20–30% and never look at it until the end VALIDATION SET a third split, used for choosing hyperparameters — because tuning against the test set contaminates it K-FOLD CROSS- split into k parts, train on k−1 and VALIDATION test on the remaining one, k times, and average. Uses all the data for both purposes. WORKED: 5-fold cross-validation on 1,000 examples trains five models, each on 800 examples and tested on a different 200, then averages the five scores. More reliable than one split, at five times the compute. THE CARDINAL RULE: NEVER EVALUATE ON DATA USED FOR TRAINING OR FOR TUNING. Every honest performance number comes from data the model has not influenced in any way — which is the held-out discipline the AI history topic credited with ending the second AI winter. EVALUATION METRICS FOR CLASSIFICATION, and the arithmetic that matters: the CONFUSION MATRIX predicted + predicted − actual + true positive false negative actual − false positive true negative ACCURACY = (TP + TN) / total PRECISION = TP / (TP + FP) of those flagged, how many were right? RECALL = TP / (TP + FN) of the real cases, how many were caught? F1 = 2 · precision · recall / (precision + recall) the harmonic mean, which punishes imbalance between the two AND THE WARNING THE APPLICATIONS TOPIC ALREADY GAVE: ACCURACY IS USELESS ON IMBALANCED DATA. With 1% fraud, predicting "not fraud" always gives 99% accuracy and catches nothing. PRECISION AND RECALL TRADE OFF, and which matters depends on the relative cost of the two error types — the fraud calculation in that topic showed the same recall flipping a deployment decision from clearly worthwhile to clearly negative as precision changed. REGULARISATION is the standard defence against overfitting: add a penalty for model complexity to the training objective, so the learner prefers a simpler hypothesis unless the data strongly justifies a complex one. It is Occam's razor, implemented as arithmetic.