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.
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 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.
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 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.
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 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.
Week 4 covers three forms of machine learning. Supervised learning fits a hypothesis function to labeled data: classify by the k nearest neighbors, or draw a decision boundary with a set of weights (perceptron learning rule, logistic regression, support vector machines), then use loss functions, regularization and cross-validation against overfitting. Reinforcement learning uses Q-learning to update the estimated value of each state and action from rewards, with ε-greedy keeping some probability of random exploration. Unsupervised learning clusters with k-means. With time links for every section, plus the approach and ways to check your work for the Shopping and Nim projects.