Foundations Lecture 1 defines machine learning as "use data to compute a hypothesis g that approximates the target f" and gives three conditions for deciding whether to use it: there is a pattern to learn, there is no programmable definition, and there is data. The skeleton of the whole lecture is one flow chart: an unknown f generates the data D, and an algorithm A picks g from a hypothesis set H. A plus H is called the learning model, and the next 15 lectures keep swapping parts on this chart.
This lecture puts the first concrete content into the flowchart from Lecture 1: the hypothesis set H is all lines (perceptrons), and the algorithm A is PLA, which adds yₙxₙ to w whenever it sees a misclassified point. When the data is linearly separable, PLA started from w₀ = 0 halts after at most R²/ρ² corrections; when the data cannot be separated, switch to pocket, which keeps the line with the fewest mistakes seen so far in its pocket.
This lecture takes the learning flow diagram from Lecture 1 and swaps one part at a time along four directions: the output space Y (binary classification, multiclass classification, regression, structured learning), the labels yₙ (supervised, unsupervised, semi-supervised, reinforcement learning), the way data reaches the algorithm (batch, online, active), and the input space X (concrete, raw, abstract features). Each direction has one core option, and together they mark the home ground for the rest of Foundations: batch, supervised binary classification and regression on concrete features.
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.
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.
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 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.
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.
Linear regression writes the squared error as (1/N)‖Xw − y‖², sets the gradient to zero, and gets w_LIN = X†y with no iteration. The hat matrix H = XX† projects y onto the space spanned by the columns of X, and trace(I − H) = N − (d+1), which gives average E_in = σ²(1 − (d+1)/N) and average E_out = σ²(1 + (d+1)/N). Squared error is also an upper bound on the 0/1 error, so w_LIN can be used for binary classification too.
Logistic regression uses θ(wᵀx) to estimate P(+1|x), yet the data contains only circles and crosses. This lecture derives the cross-entropy error ln(1 + exp(−y wᵀx)) from maximum likelihood and uses the chain rule to show that the gradient is a θ-weighted average of −yₙxₙ. Setting the gradient to zero gives a non-linear equation of w with no closed-form solution, so the lecture switches to fixed learning rate gradient descent, w ← w − η∇E_in(w), and walks to the bottom of the valley one step at a time.
PLA, linear regression, and logistic regression all start by computing the score s = wᵀx, and all three errors can be written as functions of ys. The squared error and the cross-entropy rescaled to log₂ both sit above the 0/1 error, so making the regression E_in small also gives a guarantee on the classification E_out. Next, replacing the average over N examples in the gradient with one randomly drawn example gives SGD at O(1) per step. Finally, OVA (K classifiers, take the highest score) and OVO (K(K−1)/2 classifiers, vote) assemble binary classifiers into a multiclass classifier.
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.
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.
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.
Selecting a model by E_in always favors the most complex one, and selecting by E_test needs test data you cannot get. This lecture holds out K of the N examples on hand as a validation set and obtains E_out(g_m*) ≤ E_out(g⁻_m*) ≤ E_val(g⁻_m*) + O(√(log M / K)), which explains why you retrain on all the data after selecting and why K is taken as N/5. It then pushes K down to 1 to get the almost unbiased leave-one-out estimate, and finally brings the computation back to something feasible with 5-fold or 10-fold cross validation.
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.
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.
Many lines classify all the data correctly; this lecture picks the one farthest from its nearest data point, the fattest one. After scaling (b, w) so that min yₙ(wᵀxₙ+b)=1, the largest margin is the same as minimizing ½wᵀw subject to yₙ(wᵀxₙ+b)≥1 for every point, which can go straight to a quadratic programming solver. Fatness helps for two reasons: it is weight decay within E_in=0, and it reduces the dichotomies that can be produced.
The primal hard-margin SVM has d̃+1 variables, so it stops being solvable once the feature dimension gets large. This lecture uses Lagrange duality to trade it for a quadratic program with only N variables and N+1 constraints, then uses the KKT conditions to recover w and b from α; only the support vectors, the points with α greater than 0, affect the answer. The dual's matrix still contains d̃-dimensional inner products, so the feature dimension is not really gone until the next lecture.
The dual SVM's variable count no longer depends on the feature dimension d̃, but every entry of the Q matrix is still one d̃-dimensional inner product. This lecture merges "transform + inner product" into a single kernel function K(x, x′); for the second-order transform the inner product takes only O(d). Once training, computing b, and prediction all use K, the SVM never touches the Z space. Pushed to the limit, the same move gives the Gaussian kernel, which corresponds to an infinite-dimensional transform, at the price that too large a γ still overfits.
Hard-margin SVM insists on separating the data perfectly, so it fits noise. This lecture gives every point a violation ξₙ and uses the parameter C to trade margin width against total violation, which yields soft-margin SVM; its dual differs from the hard-margin dual only in that αₙ gains the upper bound C. The value of αₙ sorts the data into non-support vectors, free SVs, and bounded SVs, and b is computed from a free SV; C and γ are chosen by cross-validation, and the fraction of support vectors #SV/N is an upper bound on the leave-one-out error.
The ξₙ of the soft-margin SVM can be written directly as max(1 − yₙ(wᵀzₙ + b), 0), which turns the whole problem into ½wᵀw plus C times the sum of hinge errors: an L2-regularized model in which C corresponds to 1/(2λ). The hinge error and logistic regression's cross-entropy are both convex upper bounds of the 0/1 error, so the SVM approximates L2-regularized logistic regression. There are two routes to probability outputs: Platt's two-level learning learns only two extra numbers, A and B; the representer theorem guarantees that the optimal w is a linear combination of the zₙ, so kernel logistic regression can be done directly in the Z space, at the price that the N coefficients βₙ are usually all nonzero.
The representer theorem turns ridge regression into a problem in β, which gives kernel ridge regression the analytic solution β = (λI + K)⁻¹y, but almost none of the N values βₙ are 0. Replace the squared error with the ε-insensitive tube error, write the problem as a QP along the soft-margin SVM route, take the dual, and you get support vector regression (SVR): the dual has 2N variables, and every point strictly inside the tube has βₙ equal to 0.
With T hypotheses gₜ in hand, you can do more than pick one by validation: give each one vote (uniform blending), learn a set of ballot counts (linear blending), or learn another model that combines them (the form the handout calls any blending, also named stacking). This lecture proves in six lines of algebra that, under squared error, the averaged G is never worse than the average performance of the gₜ, and the gap is exactly how spread out the gₜ are, which is the variance. Finally, bootstrapping re-samples T data sets from the one data set you have, trains one gₜ on each, and lets them vote; that is bagging.
This lecture re-reads bagging's bootstrap as putting a weight on every example, then deliberately tunes the weights so that the previous round's gₜ has a weighted error rate of exactly 1/2, which forces the next round to learn a different hypothesis. The recipe multiplies incorrect examples by ◆ₜ = √((1−εₜ)/εₜ), divides correct ones by it, and uses αₜ = ln ◆ₜ as the vote weight in a linear vote. That is AdaBoost. As long as the base algorithm is a little better than random guessing in every round, E_in drops to 0 within O(log N) rounds; with decision stumps, three hand-computed rounds on six examples are enough to see it.
A decision tree is a model that learns conditional aggregation as it goes: every path from the root to a leaf is a condition, and the leaf is a constant. C&RT splits the data in two with one decision stump at a time, picks the split with the smallest weighted impurity, and keeps going until nothing can be split. A tree grown this way almost always has E_in equal to 0, so it is pruned with "E_in plus λ times the number of leaves", with λ chosen by validation. The same recursion also handles multiclass problems, categorical features, and missing values.
A random forest is bagging applied to fully-grown C&RT trees, with each branch looking only at a few randomly projected features. When bootstrap draws N times, each example has about a 1/e ≈ 36.8% chance of not being used by a given tree. These out-of-bag examples give E_oob directly, a validation that needs no held-out data and no re-training; add the permutation test and you get an importance for every feature. The price is that the result wobbles with the random seed, so you keep adding trees until G is stable.
The sum of AdaBoost's weights in each round is exactly the sum of the exponential error exp(−ys). From that, this lecture derives that the gₜ found by the base algorithm is an approximate functional gradient direction, and the vote αₜ is the best step size along that direction. Swap the exponential error for squared error and the same derivation becomes 'in each round, run regression on the residuals yₙ − sₙ, then set the step size with one-variable linear regression'; with a weakened C&RT as the base model, that is GBDT.
A linear aggregation of perceptrons can implement AND and OR but not XOR; one more layer can, and that is the multi-layer perceptron. This lecture replaces the sign in the middle with tanh, puts linear regression at the output layer, and derives backpropagation from the chain rule: compute every layer's output x forward, then compute δ backwards from the output layer, and the gradient of each weight is the previous layer's x times this layer's δ. It ends with two troubles in training: E_in is non-convex, so the initial weights should be small and random; d_VC is roughly O(VD), so weight elimination and early stopping are needed against overfitting.
Once a network is stacked deep, each layer only has to do a little, but structure, model complexity, optimization, and computation all get harder. This lecture picks two of those, initialization and regularization: pre-train the weights layer by layer with a d—d̃—d autoencoder so that each layer first learns an information-preserving encoding; train on inputs with artificial noise added, as a form of regularization; and finally make the autoencoder linear and derive that the optimal W is the d̃ top eigenvectors of XᵀX, which becomes PCA once the mean is subtracted from the data.
The result of the Gaussian SVM can be read as a linear vote over Gaussians centered at the support vectors; let both the centers and the votes be learned and you have the RBF network. When all N examples serve as centers, the optimal votes for regression are β = Z⁻¹y and the training error is exactly 0, so you regularize with ridge or by cutting the centers down to M ≪ N prototypes. The prototypes are found with k-means, which alternates two steps, assigning every example to its closest center and moving every center to the average of its cluster, until the clusters stop changing.
The only input a recommender system gets is a user ID. Apply binary vector encoding to the ID and feed it to an N-d̃-M linear network with the tanh removed, and the hypothesis is h(x) = WᵀVx, which is the same as writing the rating matrix as R ≈ VᵀW. There are two ways to learn V and W: alternating least squares solves M+N linear regressions per round, and SGD uses one rating at a time to update the vectors of one user and one movie. The lecture closes by putting boosting, neural networks, RBF networks, matrix factorization, and k nearest neighbor on one map of extraction models.
Techniques Lecture 16 has no new model. It re-sorts the models of the first 15 lectures by three questions: where the features are hidden (kernel, aggregation, extraction, low-dimensional projection), how the error is brought down (gradients, equivalent problems, multiple steps), and how to hit the brakes when the model is too powerful (regularization, validation). This article works PCA plus AdaBoost-Stump on eight points from start to finish and checks the answer against each of the three questions; it closes by keeping the ReLU, Xavier/He initialization, momentum, RMSProp, and Adam material that the Fall 2024 on-campus course added.
The Techniques half of Fall 2024 has two homework sets and a final project, and all three PDFs are public. HW6 covers kernels, soft-margin SVM, and aggregation; its programming part uses LIBSVM on the 3-vs-7 subproblem of mnist.scale to count support vectors, compute margins, and run 128 validation rounds. HW7 covers bootstrap, impurity, AdaBoost, gradient boosting, and neural networks; its programming part is a 500-round AdaBoost-Stump on madelon. The final project is a fictional baseball league, HTMLB: predict home-team wins across two Kaggle stages and write an English report of at most seven pages that compares at least four methods. There are no official solutions. On 2026-09-30 both Kaggle pages returned 404 without login, so outside readers probably cannot get the HTMLB data and should reproduce the same splits on a public dataset instead.