Supervised Learning: Classification

Where linear regression predicts an unbounded real number, classification tasks such as spam detection require an output that behaves like a probability, a value between 0 and 1. Logistic regression achieves this by passing the same linear combination θᵀx used in linear regression through the sigmoid function, so that its hypothesis becomes hθ(x) = g(θᵀx) = 1 / (1 + e^(−θᵀx)), as defined in Stanford CS229's lecture notes. The sigmoid function g squashes any real-valued input into the open interval (0, 1), asymptoting to 0 for very negative inputs and to 1 for very positive ones, which lets hθ(x) be interpreted directly as the model's estimate of P(y = 1 | x). CS229's notes also derive a convenient calculus property of the sigmoid, g′(z) = g(z)(1 − g(z)), meaning the function's own derivative can be written entirely in terms of its own output rather than requiring z itself; this identity considerably simplifies the algebra involved in fitting the model. Because the sigmoid crosses exactly 0.5 when its argument θᵀx is exactly 0, the classifier's decision boundary, the set of points where it is equally likely to predict either class, is precisely the hyperplane θᵀx = 0; every point on one side of this hyperplane is classified as the positive class and every point on the other side as the negative class, which is why logistic regression, despite modeling a probability, is fundamentally a linear classifier.

Fitting logistic regression means choosing θ to make the model assign high probability to the correct label for every training example, which CS229's notes formalize by deriving the log-likelihood of θ under the assumption that each training label is drawn from a Bernoulli distribution with parameter hθ(x). Maximizing this log-likelihood via gradient ascent yields an update rule, θⱼ := θⱼ + α(y⁽ⁱ⁾ − hθ(x⁽ⁱ⁾))xⱼ⁽ⁱ⁾, that looks algebraically identical to the LMS update used for linear regression, even though hθ is now the nonlinear sigmoid rather than a raw linear combination; the two algorithms converge to different hypotheses precisely because hθ itself means something different in each case. What makes logistic regression a discriminative classifier is what it chooses not to model: it estimates P(y | x) directly, drawing a decision boundary that separates the classes, without ever trying to model how the inputs x themselves were generated for each class. A discriminative model can ignore everything about the input distribution that is irrelevant to distinguishing the classes and spend its entire representational capacity on the boundary itself, which is often exactly the quantity a practitioner cares about, but it also means logistic regression has nothing useful to say about how likely a given x is to occur in the first place, only about which class it more likely belongs to given that it did occur.

Logistic regression fits a fixed set of parameters θ once and then discards the training data, using only θ to classify every future point. The k-nearest neighbors classifier, as presented in Stanford's CS231n course notes, takes the opposite strategy: it stores the entire training set and defers all of the real work to prediction time. To classify a new point, the algorithm measures the distance from that point to every training example, finds the k training examples with the smallest distance, the k nearest neighbors, and lets those k neighbors vote on the label, assigning the new point whichever class receives the most votes among them; when k = 1, this reduces to simple nearest-neighbor classification, in which a point is given the label of the single closest training example. CS231n's notes work through this using two concrete distance metrics on image data: L1 distance, the sum of absolute pixel-wise differences, and L2 distance, ordinary Euclidean distance, noting that L2 is "much more unforgiving than the L1 distance when it comes to differences between two vectors," since squaring amplifies large individual disagreements more than it amplifies several small ones. The choice of k itself functions as a hyperparameter that must be tuned like any other: CS231n's notes observe that "higher values of k have a smoothing effect that makes the classifier more resistant to outliers," trading away some sensitivity to fine local structure in exchange for a decision boundary that is less easily thrown off by any single mislabeled or unusual training point.

This design gives k-NN a distinctive cost profile compared to logistic regression. Because there is no parameter-fitting step at all, CS231n's notes point out that k-NN requires no training time beyond simply storing the data, which makes building the classifier essentially instantaneous. The cost is deferred rather than eliminated, however: every single prediction now requires comparing the query point against the entire stored training set, so k-NN's test-time computation grows directly with the size of the training data, the opposite of logistic regression, where prediction is a single cheap dot product regardless of how large the original training set was. CS231n's notes also flag a deeper limitation specific to high-dimensional data such as raw images: pixel-wise distances between images correlate more with background color and overall brightness than with the semantic content that actually determines an image's category, so two images of the same object can end up numerically far apart while two unrelated images with similar backgrounds end up numerically close, a manifestation of the broader curse of dimensionality that makes naive distance metrics increasingly unreliable as the number of input features grows.

Naive Bayes takes a third approach entirely, one that models how each class generates its data rather than drawing a boundary between classes directly. As Stanford CS229's notes on generative learning algorithms describe, the method starts from an assumption that dramatically simplifies the problem: given the class label y, the individual input features are assumed to be conditionally independent of one another, a simplification CS229's notes call "the Naive Bayes (NB) assumption," which lets the joint probability of all the features given the class factor into a simple product, ∏ⱼ p(xⱼ | y), of individual per-feature probabilities. This assumption is almost never exactly true, since real features are typically correlated, but it makes every parameter of the model trivial to estimate directly from counts in the training data, such as the fraction of spam emails containing a given word, without needing to solve any joint optimization problem at all. Because a word that never once appeared in the training examples for a class would otherwise be assigned a probability of exactly zero, and a single zero in the product would forcibly zero out the entire prediction regardless of how strongly every other word pointed the other way, CS229's notes recommend Laplace smoothing, which adds 1 to every count and adjusts the denominator accordingly so that no feature-class combination is ever treated as strictly impossible. At prediction time, these per-feature probabilities are combined with Bayes' rule, computing p(y = 1 | x) as proportional to the product of the individual p(xⱼ | y = 1) terms times the class prior p(y = 1), and comparing that to the analogous quantity for the other class.

Naive Bayes belongs to a broader family that CS229's notes call generative learning algorithms, which also includes Gaussian Discriminant Analysis, or GDA, a method that models each class's inputs as coming from a multivariate Gaussian distribution, p(x | y = 0) ~ N(μ₀, Σ) and p(x | y = 1) ~ N(μ₁, Σ), sharing a single covariance matrix Σ between the two classes. What unites Naive Bayes and GDA, and separates both from logistic regression, is which quantity each algorithm actually models: generative algorithms like these model p(x | y), the distribution of the input features within each class, together with p(y), the overall prevalence of each class, and only combine the two via Bayes' rule at prediction time to obtain p(y | x); logistic regression instead models p(y | x) directly and has no representation of p(x) at all. This distinction has a striking mathematical consequence that CS229's notes make explicit: "if p(x|y) is multivariate gaussian (with shared Σ), then p(y|x) necessarily follows a logistic function," meaning that GDA's generative assumptions, when they hold, imply the exact same sigmoid-shaped decision rule that logistic regression fits directly and discriminatively. CS229's notes describe generative methods as requiring less data when their distributional assumptions are approximately correct, since they exploit that extra structure, while logistic regression makes fewer assumptions and is generally more robust when those assumptions do not hold, which is why it remains the more commonly deployed default of the two.