Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

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 (x,y)(\mathbf x,y) come from an unknown distribution PP, and the learner sees nn of them, the training set. A predictor hh is judged by its risk, the expected loss on a fresh pair, but the learner can only compute the empirical risk on its sample:

R(h)=E(x,y)∼P[ℓ(h(x),y)],R^(h)=1n∑i=1nℓ(h(xi),yi).R(h)=\E_{(\mathbf x,y)\sim P}\big[\ell(h(\mathbf x),y)\big],\qquad\hat R(h)=\frac1n\sum_{i=1}^n\ell\big(h(\mathbf x_i),y_i\big).

Empirical risk minimization (ERM) picks hh from a hypothesis class H\mathcal H to minimize R^\hat R. How far R^\hat R can stray from RR is the subject of Generalization & Overfitting. This lesson asks what the best possible predictor is, and how four classic methods approximate it.

DerivationProof for 0–1 loss and for unequal costs
  1. R(h)=Ex[E[ℓ(h(x),y)∣x]]R(h)=\E_{\mathbf x}\Big[\E\big[\ell(h(\mathbf x),y)\mid\mathbf x\big]\Big]

    Condition on x\mathbf x. The risk is an average over x\mathbf x of the conditional risk, and h(x)h(\mathbf x) can be chosen separately for each x\mathbf x, so it suffices to minimize the conditional risk pointwise:

  2. E[1{y≠c}∣x]=1−P(y=c∣x)⟹h∗(x)=arg max⁡cP(c∣x)\E\big[\mathbf 1\{y\ne c\}\mid\mathbf x\big]=1-P(y=c\mid\mathbf x)\quad\Longrightarrow\quad h^*(\mathbf x)=\argmax_cP(c\mid\mathbf x)

    Under 0–1 loss, the conditional risk of predicting class cc is the probability that y≠cy\ne c, which is smallest for the most probable class:

  3. cFP(1−η(x))<cFN η(x)  ⟺  η(x)>cFPcFP+cFNc_{\mathrm{FP}}\big(1-\eta(\mathbf x)\big)<c_{\mathrm{FN}}\,\eta(\mathbf x)\iff\eta(\mathbf x)>\frac{c_{\mathrm{FP}}}{c_{\mathrm{FP}}+c_{\mathrm{FN}}}

    With costs, predicting 1 risks a false positive, expected cost cFP(1−η)c_{\mathrm{FP}}(1-\eta), and predicting 0 risks a false negative, expected cost cFNηc_{\mathrm{FN}}\eta. Predict 1 when the first is smaller:

LossTypical useBayes-optimal output
Squared, (y−f)2(y-f)^2least squares, MSEE[y∣x]\E[y\mid\mathbf x]
Absolute, ∣y−f∣\abs{y-f}robust regressiona median of y∣xy\mid\mathbf x
0–1, 1{y≠h}\mathbf 1\{y\ne h\}accuracyarg max⁡yP(y∣x)\argmax_yP(y\mid\mathbf x)
Log loss, −log⁡q(y∣x)-\log q(y\mid\mathbf x)logistic regression, cross-entropythe true P(⋅∣x)P(\cdot\mid\mathbf x) itself
Hinge, max⁡(0,1−yf)\max(0,1-yf) with y=±1y=\pm1support vector machinessign⁡(2η(x)−1)\sign\big(2\eta(\mathbf x)-1\big)
The loss decides what is being estimated. Log loss is a proper scoring rule, minimized by the true conditional probabilities; the hinge loss is minimized by the Bayes classifier's labels and carries no probability at all.

Logistic regression: convex maximum likelihood

Logistic regression models the conditional probability directly: P(y=1∣x)=σ(w⊤x)P(y=1\mid\mathbf x)=\sigma(\mathbf w^\top\mathbf x), with the sigmoid σ(z)=1/(1+e−z)\sigma(z)=1/(1+e^{-z}) 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 X⊤(σ−y)X^\top(\boldsymbol\sigma-\mathbf y) is derived in The Math Toolkit of AI. The second derivative tells the rest of the story.

DerivationConvexity and Newton’s method
  1. ∇2ℓ(w)=∑i=1nσi(1−σi) xixi⊤=X⊤SX,S=diag⁡(σi(1−σi))\nabla^2\ell(\mathbf w)=\sum_{i=1}^n\sigma_i(1-\sigma_i)\,\mathbf x_i\mathbf x_i^\top=X^\top SX,\qquad S=\diag\big(\sigma_i(1-\sigma_i)\big)

    Since σ′(z)=σ(z)(1−σ(z))\sigma'(z)=\sigma(z)(1-\sigma(z)), differentiating the gradient ∑i(σi−yi)xi\sum_i(\sigma_i-y_i)\mathbf x_i once more gives the Hessian, where σi=σ(w⊤xi)\sigma_i=\sigma(\mathbf w^\top\mathbf x_i):

  2. v⊤X⊤SX v=∑iσi(1−σi) (xi⊤v)2 ≥ 0\mathbf v^\top X^\top SX\,\mathbf v=\sum_i\sigma_i(1-\sigma_i)\,(\mathbf x_i^\top\mathbf v)^2\ \ge\ 0

    It is positive semidefinite, so the negative log-likelihood is convex and every local minimum is global. If XX has full column rank, the Hessian is positive definite and a minimizer, when it exists, is unique:

  3. w←w−(X⊤SX)−1X⊤(σ−y)=(X⊤SX)−1X⊤S z,z=Xw−S−1(σ−y)\mathbf w\leftarrow\mathbf w-(X^\top SX)^{-1}X^\top(\boldsymbol\sigma-\mathbf y)=(X^\top SX)^{-1}X^\top S\,\mathbf z,\qquad\mathbf z=X\mathbf w-S^{-1}(\boldsymbol\sigma-\mathbf y)

    Newton's method uses this curvature. Each step solves a weighted least-squares problem with weights SS and working responses z\mathbf z, hence the name iteratively reweighted least squares (IRLS):

  4. w←w−η (σ(w⊤xi)−yi) xi\mathbf w\leftarrow\mathbf w-\eta\,\big(\sigma(\mathbf w^\top\mathbf x_i)-y_i\big)\,\mathbf x_i

    Near the optimum Newton converges quadratically, usually within a handful of iterations, at O(nd2+d3)\order{nd^2+d^3} per step for dd features. For large nn, stochastic gradient descent instead takes cheap O(d)\order{d} steps, one example at a time:

With KK classes the same construction gives softmax regression, P(y=k∣x)∝ewk⊤xP(y=k\mid\mathbf x)\propto e^{\mathbf w_k^\top\mathbf x}, again a convex problem because log-sum-exp is convex. Logistic regression is the simplest discriminative model: it never says how x\mathbf x itself is distributed, only how yy depends on it.

Check your understanding

Logistic regression with features x1,x2x_1,x_2 and an intercept is trained on two classes arranged as a disk inside a ring. What is the best it can do?

  1. Near-perfect accuracy, since its loss is convex and the optimizer finds the global minimum
  2. Not much better than chance: its boundary w⊤x=0\mathbf w^\top\mathbf x=0 is a straight line, and no line separates a disk from the ring around it
  3. Perfect training accuracy but poor test accuracy
  4. Nothing: training fails because the Hessian is singular
Show the answer

B. Not much better than chance: its boundary w⊤x=0\mathbf w^\top\mathbf x=0 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 σ(w⊤x)=12\sigma(\mathbf w^\top\mathbf x)=\tfrac12 is the line w⊤x=0\mathbf w^\top\mathbf x=0, 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 x12+x22x_1^2+x_2^2 would make the classes linearly separable.

Generative classifiers: naive Bayes

A generative classifier models how each class produces its features, P(x∣y)P(\mathbf x\mid y), together with the class frequencies P(y)P(y), and classifies with Bayes' rule. For dd binary features, a full table of P(x∣y)P(\mathbf x\mid y) needs 2d−12^d-1 numbers per class. Naive Bayes assumes that the features are conditionally independent given the class, which needs only dd:

y^(x)=arg max⁡y [log⁡P(y)+∑j=1dlog⁡P(xj∣y)]\hat y(\mathbf x)=\argmax_y\ \Big[\log P(y)+\sum_{j=1}^d\log P(x_j\mid y)\Big]
Training is counting: each P(xj∣y)P(x_j\mid y) is a class-specific frequency. Laplace smoothing adds a pseudo-count to each value, P^(xj=1∣y)=(Njy+1)/(Ny+2)\hat P(x_j=1\mid y)=(N_{jy}+1)/(N_y+2), so that a word never seen in one class's training examples cannot veto that class with a zero.
DerivationWhat boundary does naive Bayes draw?
  1. log⁡P(y=1∣x)P(y=0∣x)=log⁡P(y=1)P(y=0)+∑j[xjlog⁡θj1θj0+(1−xj)log⁡1−θj11−θj0]\log\frac{P(y=1\mid\mathbf x)}{P(y=0\mid\mathbf x)}=\log\frac{P(y=1)}{P(y=0)}+\sum_j\Big[x_j\log\frac{\theta_{j1}}{\theta_{j0}}+(1-x_j)\log\frac{1-\theta_{j1}}{1-\theta_{j0}}\Big]

    For binary features with θjy=P(xj=1∣y)\theta_{jy}=P(x_j=1\mid y), the log-odds of class 1 against class 0 is a sum of per-feature terms:

  2. =b+∑jwjxj,wj=log⁡θj1(1−θj0)θj0(1−θj1)=b+\sum_jw_jx_j,\qquad w_j=\log\frac{\theta_{j1}(1-\theta_{j0})}{\theta_{j0}(1-\theta_{j1})}

    Collect the terms: the log-odds is linear in x\mathbf x, 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:

  3. log⁡P(y=1∣x)P(y=0∣x)=c+∑j[(xj−μj0)22σj02−(xj−μj1)22σj12]\log\frac{P(y=1\mid\mathbf x)}{P(y=0\mid\mathbf x)}=c+\sum_j\Big[\frac{(x_j-\mu_{j0})^2}{2\sigma_{j0}^2}-\frac{(x_j-\mu_{j1})^2}{2\sigma_{j1}^2}\Big]

    With Gaussian features, xj∣y∼N(μjy,σjy2)x_j\mid y\sim\mathcal N(\mu_{jy},\sigma_{jy}^2), each term is quadratic in xjx_j. 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 dd, while logistic regression needs a number linear in dd, 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 kk closest training points, usually in Euclidean distance after standardizing each feature. A brute-force query costs O(nd)\order{nd}; 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?

DerivationProof sketch (two classes)
  1. xn′ ⟶ x\mathbf x'_n\ \longrightarrow\ \mathbf x

    As n→∞n\to\infty, the nearest training point xn′\mathbf x'_n of a query x\mathbf x converges to x\mathbf x, almost surely for x\mathbf x in the support of the data.

  2. Pr⁡(error∣x,x′)=η(x)(1−η(x′))+(1−η(x))η(x′) ⟶ 2η(x)(1−η(x))\Pr(\text{error}\mid\mathbf x,\mathbf x')=\eta(\mathbf x)\big(1-\eta(\mathbf x')\big)+\big(1-\eta(\mathbf x)\big)\eta(\mathbf x')\ \longrightarrow\ 2\eta(\mathbf x)\big(1-\eta(\mathbf x)\big)

    Given the two locations, the query's label and its neighbor's label are independent draws. An error happens when they differ, and if η\eta is continuous at x\mathbf x its probability tends to

  3. R1NN=E[2r(1−r)]=2R∗−2 E[r2] ≤ 2R∗(1−R∗),2r(1−r)≥rR_{1\mathrm{NN}}=\E\big[2r(1-r)\big]=2R^*-2\,\E[r^2]\ \le\ 2R^*(1-R^*),\qquad2r(1-r)\ge r

    Write r(x)=min⁡(η,1−η)r(\mathbf x)=\min(\eta,1-\eta), the Bayes classifier's conditional error, so R∗=E[r]R^*=\E[r] and 2η(1−η)=2r(1−r)2\eta(1-\eta)=2r(1-r). Jensen's inequality E[r2]≥(Er)2\E[r^2]\ge(\E r)^2 gives the upper bound, and r≤12r\le\frac12 the lower one:

Predict before you look

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 %

2R∗(1−R∗)=2×0.1×0.9=0.182R^*(1-R^*)=2\times0.1\times0.9=0.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 [0,1]d[0,1]^d, a cubical neighborhood needs side 0.011/d0.01^{1/d}: 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 kk by cross-validation, and when dd 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 xj≤tx_j\le t, 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.

text
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 II; CART uses Gini. With each feature sorted once, a level of the tree costs O(dnlog⁡n)\order{dn\log n}. Deep trees are then pruned back, for instance by CART's cost-complexity pruning.

H(p)=−∑kpklog⁡2pk,G(p)=1−∑kpk2,IG=H(D)−∑v∣Dv∣∣D∣ H(Dv)H(p)=-\sum_kp_k\log_2p_k,\qquad G(p)=1-\sum_kp_k^2,\qquad\mathrm{IG}=H(D)-\sum_v\frac{|D_v|}{|D|}\,H(D_v)
The entropy HH and the Gini impurity GG of the class proportions pp, and the information gain of a split into parts DvD_v, which is the mutual information between the split and the label.
Predict before you look

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 H=1H=1 bit. Each child has proportions (0.8,0.2)(0.8,0.2), so H=−0.8log⁡20.8−0.2log⁡20.2≈0.722H=-0.8\log_20.8-0.2\log_20.2\approx0.722 bits, and so does their weighted average. The gain is 1−0.722≈0.281-0.722\approx0.28 bits. In Gini terms the impurity falls from 0.5 to 1−0.82−0.22=0.321-0.8^2-0.2^2=0.32.

Choosing a model, and going deeper

ModelDecision boundaryTrainingPredictionStrengths and weaknesses
Logistic regressiona hyperplane in feature spaceconvex; Newton (IRLS) or SGDO(d)\order{d}calibrated probabilities when the model is right; curved boundaries need engineered features
Naive Bayeslinear (discrete features) or an axis-aligned conic (Gaussian)one counting pass, O(nd)\order{nd}O(dK)\order{dK}works with tiny data and many features; overconfident probabilities
k-NNarbitrary, piecewise linear (Voronoi cells for k=1k=1)none: store the dataO(nd)\order{nd} per query, brute forceconsistent as k→∞k\to\infty, k/n→0k/n\to0; needs a meaningful metric; suffers in high dimension
Decision treeaxis-aligned boxesgreedy, O(dnlog⁡n)\order{dn\log n} per levelO(depth)\order{\text{depth}}interpretable, invariant to monotone rescaling of features, handles mixed types; high variance
No method wins everywhere, a point the no-free-lunch theorems make formally. In practice, linear models suit high-dimensional sparse data such as text, boosted trees suit tabular data, and neural networks suit images, audio and language.

Key takeaways

  • Risk is expected loss, and the loss fixes the target: the conditional mean for squared loss, the median for absolute loss, and arg max⁡yP(y∣x)\argmax_yP(y\mid\mathbf x) for 0–1 loss, with threshold cFP/(cFP+cFN)c_{\mathrm{FP}}/(c_{\mathrm{FP}}+c_{\mathrm{FN}}) when errors have unequal costs.
  • Logistic regression's negative log-likelihood has Hessian X⊤SX⪰0X^\top SX\succeq0, 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 R∗R^* and 2R∗(1−R∗)2R^*(1-R^*) (Cover & Hart), and kk-NN is universally consistent as k→∞k\to\infty with k/n→0k/n\to0, 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.

Question 1

Missing a positive case costs 9 times as much as a false alarm. Above what value of P(y=1∣x)P(y=1\mid\mathbf x) should a Bayes-optimal classifier predict positive?

  1. 0.5
  2. 0.9
  3. 0.1
  4. 1/9≈0.111/9\approx0.11
Show the answer

C. 0.1

Predict positive when the expected cost of a false alarm, 1⋅(1−η)1\cdot(1-\eta), is below that of a miss, 9η9\eta: that is, when η>1/(1+9)=0.1\eta>1/(1+9)=0.1. Unequal costs move the threshold, not the model, so a well-calibrated probability estimate lets you choose the threshold after training.

Question 2

What exactly does naive Bayes assume?

  1. The features are independent of each other
  2. The features are conditionally independent given the class
  3. The classes are equally likely
  4. Every feature is Gaussian
Show the answer

B. The features are conditionally independent given the class

P(x∣y)=∏jP(xj∣y)P(\mathbf x\mid y)=\prod_jP(x_j\mid y): 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.

Question 3

k-NN is run on two features, annual income in dollars and age in years, without standardizing them. What goes wrong?

  1. Nothing: k-NN is scale-invariant
  2. Ages dominate the distances
  3. The algorithm stops converging
  4. 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.

Question 4

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?

  1. A, because its children are balanced
  2. Neither: equal error rates mean equal impurity
  3. B, because a strictly concave impurity rewards creating a pure child even when the error rate does not change
  4. 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 1−0.752−0.252=0.3751-0.75^2-0.25^2=0.375, so the weighted impurity is 0.375. After B: 34(1−(13)2−(23)2)+14⋅0=34⋅49≈0.333\frac34\big(1-(\frac13)^2-(\frac23)^2\big)+\frac14\cdot0=\frac34\cdot\frac49\approx0.333, 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.)

Question 5

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?

  1. It tends to 0
  2. It stays bounded away from 0, because 1-NN always overfits
  3. It tends to 50%
  4. It depends on the learning rate
Show the answer

A. It tends to 0

Cover and Hart's bound gives R1NN≤2R∗(1−R∗)=0R_{1\mathrm{NN}}\le2R^*(1-R^*)=0. 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

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).