Once a hypothesis set has a break point k, the largest number of dichotomies it can produce on N points, B(N, k), satisfies B(N, k) ≤ B(N−1, k) + B(N−1, k−1). That gives B(N, k) ≤ C(N, 0) + … + C(N, k−1), whose highest term is N to the power k−1. Three more steps put the growth function into Hoeffding and yield the VC bound: the probability of the bad event is at most 4·m_H(2N)·exp(−ε²N/8). The break point of 2D perceptrons is 4, so they can learn.
This lecture replaces the fixed target function with a target distribution P(y|x): as long as each (x, y) is drawn independently from the same joint distribution, the VC bound holds with noise just as before. The error measure err and P(y|x) together decide the ideal prediction on each x; the 0/1 error picks the most probable y and the squared error picks the weighted mean. CIA fingerprint verification penalizes a false accept 1000 times more, and this kind of weighted classification is the same as copying the −1 examples 1000 times and then doing ordinary classification.
When no straight line separates the data, you do not need to redesign the algorithm: use a feature transform Φ to turn x into z, run a linear model in Z-space as usual, and the line in Z-space is a quadratic or higher-order curve in X-space. The Q-th order polynomial transform raises the dimension to d̃ = C(Q+d, d) − 1, and computation, storage, and the VC dimension (at most d̃+1) all grow with it, so the lecture concludes that you should try the linear model first and move to higher orders only when it is not enough.
Stepping back from a 10th-order polynomial to a 2nd-order one is the same as adding a constraint to the 10th-order problem. Once the constraint is softened to ‖w‖² ≤ C, the negative gradient of E_in at the optimal solution must be parallel to w, which gives w_REG = (ZᵀZ + λI)⁻¹Zᵀy and is the same as minimizing E_aug = E_in + (λ/N)wᵀw. That is weight decay. A larger λ means a smaller equivalent C and a smaller effective VC dimension d_EFF; switching to L1 gives sparse solutions instead.
The last Foundations lecture teaches no new algorithm. It covers three situations in which the guarantees of the first fifteen lectures stop holding. A simple model rarely separates randomly labeled data by accident: with 10 points and random labels, a decision stump separates them with probability only 20/1024, so a successful separation means something. The VC guarantee fails when training and testing do not share one distribution, and once data has affected any step of the learning process it can no longer assess the outcome. The lecture closes with Power of Three, which folds the whole course into five groups of three.
Foundations spends 16 lectures on four questions: when machines can learn, why they can (Hoeffding, growth functions, VC dimension), how (linear and logistic regression, nonlinear transforms), and how to learn better (regularization, validation). Techniques spends 16 more on three ways of handling features: kernels embed features in high dimensions (SVMs), aggregation combines hypotheses (AdaBoost, random forests, GBDT), and extraction learns hidden features (neural networks, matrix factorization). All 130 YouTube videos are free; practice with the Fall 2024 HW0–HW7.
This lecture first shows that the data D alone cannot determine the answer outside D (No Free Lunch), then adds one assumption: the data and the future inputs are drawn independently from the same distribution. Hoeffding's inequality then guarantees that, for a hypothesis h fixed in advance, the probability that E_in and E_out differ by more than ε is at most 2exp(−2ε²N). An algorithm has to choose among M hypotheses, so the bound is multiplied by M and becomes 2M exp(−2ε²N); with finitely many hypotheses, enough data, and a small E_in, learning is feasible.
Fall 2024 had six Foundations assignments. HW0 is 20 multiple-choice math prerequisite questions. HW1–HW5 each have 12 problems plus a bonus: Q1–4 are auto-graded, Q5–12 are graded by TAs, the programming problems use rcv1, cpusmall, and mnist from the LIBSVM datasets site, and HW5 uses LIBLINEAR. HW1 and HW2 each include a problem where you argue with a ChatGPT-style answer. Fall 2026 has released hw0 and hw1: hw1 is now 16 multiple-choice problems with 4 secretly chosen for TA grading, and the data is the course's own hw1_train.dat. The new policy allows AI tools and vibe coding, but AI-generated code needs block-by-block comments in your own words. Neither semester publishes official solutions.
Overfitting is the process in which switching to a more powerful model lowers E_in but raises E_out. This lecture runs experiments with two learners, one who only knows polynomials up to order 2 and one who knows them up to order 10, and arrives at four causes: too little data, too much stochastic noise, too much deterministic noise (a target that is too complex), and excessive model power. It also explains why data with no noise at all can still be overfit. For remedies it covers data cleaning, pruning, and virtual examples first; regularization and validation are left to the next two lectures.
The guarantee from the previous lecture contains the number of hypotheses M, and the perceptron has infinitely many lines, so M is infinite. This lecture instead counts how many ○× patterns (dichotomies) those lines can produce on N data points, and takes the maximum over all placements to get the growth function m_H(N): N+1 for positive rays, ½N²+½N+1 for positive intervals, 2ᴺ for convex sets, and at most 14 for 2D perceptrons on 4 points. The first number of points at which the growth function falls short of 2ᴺ is called a break point; the handout conjectures that it forces the growth function down to a polynomial, and leaves the proof to the next lecture.
This lecture names the largest non-break point the VC dimension d_VC, proves in two parts (an invertible matrix, then linear dependence) that d-dimensional perceptrons have d_VC = d + 1, and rewrites the VC bound as E_out ≤ E_in + Ω: the larger d_VC is, the easier it is to push E_in down, but the larger the complexity penalty Ω becomes. By the bound, ε = δ = 0.1 and d_VC = 3 need 29,300 examples, roughly 10,000 times d_VC; in practice 10 times is often enough.
HW6 combines generalization, MLE/MAP, probabilistic learning, fairness metrics, and social impact in one written assignment about assumptions and tradeoffs.