Supervised Learning
Regression, classification, losses and gradient descent.
Four classifiers, four philosophies: model the probability of the label directly, model how each class generates its features, copy the labels of the nearest examples, or ask a sequence of yes-or-no questions. This lesson derives each one, proves what can be proved about it, from the convexity of logistic regression to Cover and Hart's "twice the Bayes rate", and pits them against each other on data that breaks their assumptions.
What you’ll learn
- Define risk and empirical risk, and derive the Bayes-optimal predictor for squared, absolute and 0–1 loss, including unequal error costs.
- Prove that logistic regression's negative log-likelihood is convex, and fit it with Newton's method (IRLS).
- Derive naive Bayes as a generative classifier, and explain when its decision boundary is linear and when it is quadratic.
- State and sketch Cover and Hart's bound on the nearest-neighbor error rate, and explain the curse of dimensionality.
- Grow a decision tree greedily by information gain or Gini impurity, and compare the four models' assumptions and costs.
Risk, losses and the Bayes-optimal predictor
In supervised learning, pairs come from an unknown distribution , and the learner sees of them, the training set. A predictor is judged by its risk, the expected loss on a fresh pair, but the learner can only compute the empirical risk on its sample:
Empirical risk minimization (ERM) picks from a hypothesis class to minimize . How far can stray from is the subject of Generalization & Overfitting. This lesson asks what the best possible predictor is, and how four classic methods approximate it.
Condition on . The risk is an average over of the conditional risk, and can be chosen separately for each , so it suffices to minimize the conditional risk pointwise:
Under 0–1 loss, the conditional risk of predicting class is the probability that , which is smallest for the most probable class:
With costs, predicting 1 risks a false positive, expected cost , and predicting 0 risks a false negative, expected cost . Predict 1 when the first is smaller:
| Loss | Typical use | Bayes-optimal output |
|---|---|---|
| Squared, | least squares, MSE | |
| Absolute, | robust regression | a median of |
| 0–1, | accuracy | |
| Log loss, | logistic regression, cross-entropy | the true itself |
| Hinge, with | support vector machines |
Logistic regression: convex maximum likelihood
Logistic regression models the conditional probability directly: , with the sigmoid and a constant feature for the intercept. Its maximum-likelihood fit minimizes the negative log-likelihood, the log loss summed over the data, whose gradient is derived in The Math Toolkit of AI. The second derivative tells the rest of the story.
Since , differentiating the gradient once more gives the Hessian, where :
It is positive semidefinite, so the negative log-likelihood is convex and every local minimum is global. If has full column rank, the Hessian is positive definite and a minimizer, when it exists, is unique:
Newton's method uses this curvature. Each step solves a weighted least-squares problem with weights and working responses , hence the name iteratively reweighted least squares (IRLS):
Near the optimum Newton converges quadratically, usually within a handful of iterations, at per step for features. For large , stochastic gradient descent instead takes cheap steps, one example at a time:
With classes the same construction gives softmax regression, , again a convex problem because log-sum-exp is convex. Logistic regression is the simplest discriminative model: it never says how itself is distributed, only how depends on it.
Logistic regression with features and an intercept is trained on two classes arranged as a disk inside a ring. What is the best it can do?
- Near-perfect accuracy, since its loss is convex and the optimizer finds the global minimum
- Not much better than chance: its boundary is a straight line, and no line separates a disk from the ring around it
- Perfect training accuracy but poor test accuracy
- Nothing: training fails because the Hessian is singular
Show the answer
B. Not much better than chance: its boundary is a straight line, and no line separates a disk from the ring around it
Convexity guarantees that the optimizer finds the best line, not that a line is any good. The boundary is the line , and every line leaves much of the ring on the disk's side; in the widget at the end of this lesson it scores 60% on test points. Adding the feature would make the classes linearly separable.
Generative classifiers: naive Bayes
A generative classifier models how each class produces its features, , together with the class frequencies , and classifies with Bayes' rule. For binary features, a full table of needs numbers per class. Naive Bayes assumes that the features are conditionally independent given the class, which needs only :
For binary features with , the log-odds of class 1 against class 0 is a sum of per-feature terms:
Collect the terms: the log-odds is linear in , the same form as logistic regression. Only the weights differ: they come from counting each feature separately, not from maximizing the conditional likelihood of the labels:
With Gaussian features, , each term is quadratic in . If the variances are shared between the classes the squares cancel and the boundary is linear again; if not, it is an axis-aligned conic, such as an ellipse, in two dimensions:
Why does such a wrong assumption work so well, in spam filters for instance? Classification only needs the argmax to be right, and errors in the probabilities often cancel there (Domingos & Pazzani, 1997). The probabilities themselves tend to be overconfident, because correlated evidence is counted twice. Ng and Jordan (2002) made the trade-off precise: naive Bayes approaches its asymptotic error after a number of examples logarithmic in , while logistic regression needs a number linear in , but logistic regression's asymptotic error is lower whenever the independence assumption is wrong. Generative models win with little data, discriminative ones with a lot.
Nearest neighbors and the Cover–Hart bound
k-nearest neighbors needs no training at all: store the data, and label a query by a majority vote among its closest training points, usually in Euclidean distance after standardizing each feature. A brute-force query costs ; k-d trees and ball trees help in low dimensions, and approximate nearest-neighbor indexes in high ones. The rule assumes nothing about the shape of the boundary, so it is nonparametric: its flexibility grows with the data. How good can such a lazy rule be?
As , the nearest training point of a query converges to , almost surely for in the support of the data.
Given the two locations, the query's label and its neighbor's label are independent draws. An error happens when they differ, and if is continuous at its probability tends to
Write , the Bayes classifier's conditional error, so and . Jensen's inequality gives the upper bound, and the lower one:
A classification problem has a Bayes error of 10%. With unlimited data, what is the largest error rate the 1-nearest-neighbor rule can have?
Show the answer
18 %
. In Cover and Hart's words, half the classification information in an infinite sample is contained in the nearest neighbor. The catch is the word unlimited: how quickly the limit is approached depends on the dimension.
That catch is the curse of dimensionality. To capture 1% of data spread uniformly in the unit cube , a cubical neighborhood needs side : 0.1 in two dimensions but 0.63 in ten. "Nearest" neighbors stop being near, distances between random points concentrate, and rates of convergence degrade. In practice, standardize the features (otherwise the feature with the largest scale decides every distance), choose by cross-validation, and when is large prefer methods that learn which directions matter.
Decision trees: greedy recursive splitting
A decision tree partitions feature space into axis-aligned boxes by a sequence of tests , and predicts the majority label (or the mean, for regression) in each leaf. Finding the smallest tree consistent with the data is NP-complete (Hyafil & Rivest, 1976), so ID3 (Quinlan, 1986), C4.5 and CART (Breiman, Friedman, Olshen & Stone, 1984) grow trees greedily, one split at a time.
function GROW-TREE(examples D, depth):
if D is pure, or depth = max_depth, or |D| < min_size:
return LEAF(majority label of D)
for each feature j, and each threshold t between consecutive sorted values of x_j:
gain(j, t) ← I(D) − (|D_≤| / |D|) · I(D_≤) − (|D_>| / |D|) · I(D_>) # I: impurity
(j*, t*) ← the split with the largest gain
if gain(j*, t*) ≤ 0: return LEAF(majority label of D)
return NODE(x_j* ≤ t*, GROW-TREE(D_≤, depth + 1), GROW-TREE(D_>, depth + 1))ID3 and C4.5 use entropy as the impurity ; CART uses Gini. With each feature sorted once, a level of the tree costs . Deep trees are then pruned back, for instance by CART's cost-complexity pruning.
A node holds 5 positive and 5 negative examples. A split sends 4 positives and 1 negative to the left, and 1 positive and 4 negatives to the right. What is its information gain, in bits?
Show the answer
0.28
The parent has bit. Each child has proportions , so bits, and so does their weighted average. The gain is bits. In Gini terms the impurity falls from 0.5 to .
Choosing a model, and going deeper
| Model | Decision boundary | Training | Prediction | Strengths and weaknesses |
|---|---|---|---|---|
| Logistic regression | a hyperplane in feature space | convex; Newton (IRLS) or SGD | calibrated probabilities when the model is right; curved boundaries need engineered features | |
| Naive Bayes | linear (discrete features) or an axis-aligned conic (Gaussian) | one counting pass, | works with tiny data and many features; overconfident probabilities | |
| k-NN | arbitrary, piecewise linear (Voronoi cells for ) | none: store the data | per query, brute force | consistent as , ; needs a meaningful metric; suffers in high dimension |
| Decision tree | axis-aligned boxes | greedy, per level | interpretable, invariant to monotone rescaling of features, handles mixed types; high variance |
Key takeaways
- Risk is expected loss, and the loss fixes the target: the conditional mean for squared loss, the median for absolute loss, and for 0–1 loss, with threshold when errors have unequal costs.
- Logistic regression's negative log-likelihood has Hessian , so it is convex and Newton's method (IRLS) solves it fast, except on separable data, where no minimizer exists without regularization.
- Naive Bayes assumes conditional independence given the class; training is counting, and the boundary is linear for discrete features and conic for Gaussian features with class-specific variances.
- The 1-NN asymptotic error lies between and (Cover & Hart), and -NN is universally consistent as with , but convergence slows badly with dimension.
- Trees are grown greedily by information gain or Gini because optimal trees are NP-hard to find; they are interpretable and flexible, but myopic and unstable.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Missing a positive case costs 9 times as much as a false alarm. Above what value of should a Bayes-optimal classifier predict positive?
- 0.5
- 0.9
- 0.1
Show the answer
C. 0.1
Predict positive when the expected cost of a false alarm, , is below that of a miss, : that is, when . Unequal costs move the threshold, not the model, so a well-calibrated probability estimate lets you choose the threshold after training.
What exactly does naive Bayes assume?
- The features are independent of each other
- The features are conditionally independent given the class
- The classes are equally likely
- Every feature is Gaussian
Show the answer
B. The features are conditionally independent given the class
: within each class the features are independent. Unconditionally they can be strongly dependent. In spam, "free" and "winner" co-occur largely because both are typical of spam, and given the class much of that dependence disappears.
k-NN is run on two features, annual income in dollars and age in years, without standardizing them. What goes wrong?
- Nothing: k-NN is scale-invariant
- Ages dominate the distances
- The algorithm stops converging
- Incomes dominate the distances, so age is effectively ignored
Show the answer
D. Incomes dominate the distances, so age is effectively ignored
Income differences of thousands dwarf age differences of tens, so Euclidean distance is essentially income distance. Standardize the features, or choose a metric that reflects which differences matter. Decision trees, by contrast, are invariant to monotone rescaling of each feature.
A node holds 400 positive and 400 negative examples. Split A gives children (300, 100) and (100, 300); split B gives (200, 400) and (200, 0). Both misclassify 200 examples. Which does Gini impurity prefer, and why grow trees with it rather than with the error rate?
- A, because its children are balanced
- Neither: equal error rates mean equal impurity
- B, because a strictly concave impurity rewards creating a pure child even when the error rate does not change
- B, because its right child has fewer examples
Show the answer
C. B, because a strictly concave impurity rewards creating a pure child even when the error rate does not change
Gini after A: each child has , so the weighted impurity is 0.375. After B: , which is lower. The error rate is only piecewise linear in the class proportions and can miss splits that make later progress easy; strictly concave impurities such as Gini and entropy reward them. (This example is from Hastie, Tibshirani and Friedman.)
Two classes never overlap, so the Bayes error is 0. As the training set grows without bound, what happens to the error of the 1-nearest-neighbor rule?
- It tends to 0
- It stays bounded away from 0, because 1-NN always overfits
- It tends to 50%
- It depends on the learning rate
Show the answer
A. It tends to 0
Cover and Hart's bound gives . Overfitting means fitting noise, and noise-free labels leave none to fit: with enough data, each query's nearest neighbor lies in its own class region, except in a shrinking band near the boundary.
Go deeper
- Linear Models & Their Geometry · Least squares, logistic regression and projections.
- Kernels & Support Vector Machines · Maximum margins and the kernel trick.
- Decision Trees & Ensembles · Splits, bagging, random forests and boosting.
Further reading
- T. Hastie, R. Tibshirani & J. Friedman, The Elements of Statistical Learning, 2nd ed. (Springer, 2009), chapters 2, 4, 9 and 13.
- T. M. Cover & P. E. Hart, "Nearest neighbor pattern classification," IEEE Transactions on Information Theory 13(1), 21–27 (1967).
- L. Breiman, J. H. Friedman, R. A. Olshen & C. J. Stone, Classification and Regression Trees (Wadsworth, 1984).
- A. Y. Ng & M. I. Jordan, "On discriminative vs. generative classifiers: a comparison of logistic regression and naive Bayes," Advances in Neural Information Processing Systems 14 (2002).