Supervised Learning: Regression

Where classification predicts a label drawn from a small set of discrete categories, regression is the branch of supervised learning devoted to predicting a continuous numeric quantity, such as the price of a house or the temperature tomorrow. The most fundamental regression model is linear regression, which represents its prediction as a hypothesis hθ(x) = θᵀx, a weighted sum of the input features x with a learned parameter vector θ. To find good values for θ, Stanford's CS229 lecture notes define a cost function J(θ) equal to one-half the sum of squared differences between each prediction hθ(x⁽ⁱ⁾) and the true target y⁽ⁱ⁾ across all training examples, so that θ is chosen to make the model's predictions as close as possible to the observed data in a squared-error sense. One way to minimize J(θ) is an iterative procedure called the least-mean-squares, or LMS, update rule, which repeatedly nudges each parameter θⱼ in the direction that reduces the error on a given training example, scaled by a learning rate α; when the entire training set is processed this way at every step it is called batch gradient descent. Because linear regression's cost function is convex, CS229's notes also derive a closed-form solution called the normal equations, θ = (XᵀX)⁻¹Xᵀy, where X is the matrix whose rows are the training inputs and y is the vector of targets; this expression directly computes the θ that minimizes J(θ) in one step, without any iteration, whenever XᵀX is invertible.

Linear regression's hypothesis is linear in the parameters θ, but nothing requires the input features themselves to be linear in the original measurements. Polynomial regression exploits this by replacing a single input x with an expanded feature vector, such as [1, x, x², x³, ..., xᵈ], and then fitting an ordinary linear regression on top of these new features; because the model is still a linear combination of its inputs, the same cost function, gradient descent update, and normal equations from ordinary linear regression apply unchanged, and what changes is only which numbers are fed into them. This lets a straight-line method trace curves, letting the fitted function bend to follow a relationship that is not itself a straight line, such as the way a projectile's height changes with time. The tradeoff is that as the polynomial degree d grows, the model gains enough flexibility to pass through, or very close to, every single training point, which drives the training error toward zero while often making predictions on new data far worse: a fitted curve that wiggles wildly between the training points to hit each one exactly is a textbook case of a model whose variance has grown too large relative to how much it has actually learned about the underlying trend.

When a regression model has enough flexibility to fit its training data almost perfectly, it risks memorizing the noise in that data rather than the true underlying pattern, exactly the overfitting failure mode. Regularization addresses this directly by adding a penalty term to the least-squares cost function that discourages the coefficient vector w from growing too large. Stanford CS229's supplementary notes on regularized regression define ridge regression as the model that minimizes RSS(w) + λ‖w‖₂², where RSS(w) is the ordinary residual sum of squares and the added penalty ‖w‖₂² is the sum of the squared coefficients, w₀² + ... + w_D²; larger values of the regularization strength λ push every coefficient continuously closer to zero without generally forcing any individual coefficient to reach zero exactly. Lasso regression instead minimizes RSS(w) + λ‖w‖₁, replacing the squared-coefficient penalty with the sum of absolute values of the coefficients, ‖w‖₁ = |w₀| + ... + |w_D|. CS229's notes highlight that this single change in the shape of the penalty has a qualitatively different effect: lasso "leads to sparse solutions," meaning that as λ increases, individual coefficients can be shrunk exactly to zero rather than merely toward it, which effectively removes the corresponding feature from the model entirely and performs a form of automatic feature selection that ridge regression does not.

Both penalties are controlled by the same kind of hyperparameter, λ, and choosing it well is itself an exercise in the training, validation, and test methodology used throughout supervised learning: λ is tuned by comparing performance across a range of values on a held-out validation set, never on the final test set, for exactly the reason that repeatedly checking against the test set would let the model configuration become shaped to fit that particular set. The choice of λ also has a direct bias-variance interpretation. Setting λ to zero recovers ordinary least squares, which has the lowest possible bias among linear models but the highest variance, since it is free to chase every fluctuation in the training sample; increasing λ constrains the coefficients, which raises bias, because the model can no longer fit the training data as closely, but lowers variance, because the fitted coefficients become less sensitive to which particular training sample was drawn. Practitioners therefore treat λ as a dial that trades bias for variance rather than a value with one universally correct setting, selecting whichever value minimizes error on validation data. Ridge regression is generally preferred when most features are believed to contribute at least a little to the outcome, while lasso is preferred when the true relationship is believed to depend on only a small subset of the available features and the practitioner wants the model itself to identify which ones.

Every regression method considered so far fits one fixed set of parameters θ once, using the entire training set, and then reuses that same θ for every future prediction. Locally weighted regression, described in Stanford CS229's lecture notes, takes a fundamentally different, non-parametric approach: rather than fitting a single global θ, it refits a new local regression every time it needs to make a prediction at a query point x, weighting nearby training examples more heavily than distant ones. Concretely, to predict at a point x, the algorithm chooses θ to minimize a weighted sum Σᵢw⁽ⁱ⁾(y⁽ⁱ⁾ − θᵀx⁽ⁱ⁾)², where the weight assigned to training example i is w⁽ⁱ⁾ = exp(−(x⁽ⁱ⁾ − x)²/(2τ²)); this weight is close to 1 for training points near the query point x and decays smoothly toward 0 for points far away, so distant examples contribute almost nothing to the local fit. The parameter τ, called the bandwidth, controls how quickly this influence decays with distance: a small τ produces a highly local, wiggly fit that only trusts training points very close to each query, while a large τ approaches an ordinary global linear fit. Because locally weighted regression must retain the entire training set and solve a small weighted least-squares problem for every new prediction, CS229's notes describe it as a non-parametric algorithm, in contrast to the fixed, finite parameter vector θ used by ordinary linear regression.

Least squares regression can also be justified from a probabilistic rather than purely geometric standpoint, and CS229's notes work through this derivation explicitly. Suppose the relationship between inputs and outputs is y⁽ⁱ⁾ = θᵀx⁽ⁱ⁾ + ε⁽ⁱ⁾, where ε⁽ⁱ⁾ is an unobserved noise term assumed to be independently and identically distributed according to a Gaussian, ε⁽ⁱ⁾ ~ N(0, σ²). Under this assumption, the probability of observing a particular y⁽ⁱ⁾ given x⁽ⁱ⁾ and θ follows a Gaussian density centered at θᵀx⁽ⁱ⁾, and multiplying this density across all n independent training examples gives the likelihood of θ. CS229's notes show that maximizing the log of this likelihood with respect to θ is mathematically equivalent to minimizing the very same sum of squared errors, Σ(y⁽ⁱ⁾ − θᵀx⁽ⁱ⁾)², that defines the ordinary least-squares cost function J(θ), so that "least-squares regression corresponds to finding the maximum likelihood estimate" of θ under this Gaussian noise assumption. This result is significant because it reframes an apparently ad hoc choice, minimizing squared error rather than some other measure of fit, as the mathematically optimal choice under a specific, explicit, and checkable assumption about how the data was generated; it also opens the door to probabilistic regression more broadly, where instead of predicting a single number, a model outputs an entire predictive distribution over y, with this Gaussian view of least squares being the simplest example of that idea.