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 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.
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.
CS189 Spring 2026 Lec 11–12 splits classification into two routes. Generative models fit p(x|y) for each class (GDA: shared covariance gives LDA and a linear boundary, per-class covariance gives QDA and a quadratic one). Discriminative models fit p(y|x) directly (logistic regression: sigmoid, softmax, cross-entropy MLE, no closed form, so gradient descent). The bridge: the LDA posterior can always be written in logistic form, but not the other way around. For evaluation, accuracy misleads under class imbalance; ROC/AUC sweeps every threshold and ignores calibration; PR curves care about class balance.
Lecture 9 stops learning p(y|x) directly. Instead it learns the class prior p(y) and the class-conditional p(x|y), then inverts them with Bayes rule. The price is stronger assumptions; the payoff is the ability to generate new data and more stability with little data. Naive Bayes uses conditional independence to make the parameters estimable, GDA uses multivariate Gaussians for continuous features, and whether the covariances match decides a linear or a curved boundary.
CS181 Spring 2026 HW2 (due Feb 27) has four problems worth 90 points: train 10 logistic models on planet observations to see bias and variance, derive the MLE of a generative classifier, implement five classifiers on 27 loan applicants, and watch ridge reshape the loss surface under SGD, momentum, and Adam. The core skill is separating what one model's probability says from how much 10 models disagree.
Lecture 9 models P(y=1|x) with a sigmoid instead of directly predicting 0 or 1, learns parameters with cross-entropy and convex optimization, and extends naturally to softmax regression.