Classification in statistical learning

Classification predicts a discrete label from observed covariates.

The misclassification rate is the expected zero-one loss of a classification in statistical learning rule. Its empirical version is the fraction of incorrectly labeled observations. Evaluation on the fitting sample gives a training error; evaluation on an independent test set estimates prediction error. For a majority-class leaf of a classification tree, the training error count is $n_t-{\max }_k{n}_{tk}$, unlike classification-tree deviance, which also uses the fitted class probabilities.

A classification tree partitions predictor space recursively and attaches a class probability vector to each terminal region. For a categorical response, a fitted leaf commonly uses its observed class proportions and predicts their largest entry. Binary numerical splits compare one coordinate with a threshold. Growing a tree greedily by reducing classification-tree deviance gives an interpretable rule but does not globally optimize the tree. Cost-complexity tree pruning and cross-validation control complexity and assess prediction error.

Pruning balances a tree's empirical loss $R(T)$ against the number of leaves. Increasing $\alpha$ favors a nested sequence of smaller subtrees, obtained by removing splits with the smallest effective cost per removed leaf. Choose complexity using cross-validation or a validation set, and assess the selected tree on a separate test set. The loss can be deviance or misclassification loss; the chosen convention must be specified.

Maximizing a node's multinomial likelihood gives class probabilities ${\hat{p}}_{tk}=n_{tk}/n_t$. Twice the negative maximized log-likelihood relative to perfect classification is the displayed deviance, with $0\log 0=0$. It equals twice the node size times its Shannon entropy. A split is chosen by maximizing $D(t)-D(t_L)-D(t_R)$, and tree deviance is the sum over terminal nodes. The training misclassification count is instead ${\sum }_t(n_t-{\max }_k{n}_{tk})$; the two criteria are different.

Classification in statistical learning with two possible labels. Given the conditional probability $\eta (x)=\mathbb{P}(Y=1\mid X=x)$, a Bayes classifier under zero-one loss predicts one exactly when $\eta (x)\ge 1/2$, with arbitrary decisions at ties.

The false positive rate is $\mathbb{P}(\text{positive result}\mid \text{truly negative class})$. In screening, it measures erroneous positives among genuinely disease-free individuals.

A decision boundary is the subset of covariate space across which a classifier changes its predicted class.

For binary classification under zero-one loss, the Bayes decision boundary is the set on which the two conditional class probabilities are equal.

A majority-vote ensemble predicts the class selected by more constituent classifiers than any other class.

A confusion matrix cross-tabulates true classes against predicted classes. Its diagonal entries count correct predictions and its off-diagonal entries describe the kinds of classification errors.

A classification and regression tree recursively splits covariate space into axis-aligned regions and assigns a constant prediction to each terminal region.

Recursive partitioning repeatedly selects a split of one current region, then applies the same splitting rule independently to the resulting child regions.

A surrogate split uses another predictor to approximate the left-versus-right assignments made by a tree node's primary split. It can route observations whose primary predictor is missing. Surrogates are ranked by agreement with the primary split on observations where both predictors are known, accounting for trivial majority assignments. This differs from simply filling a missing predictor with its sample mean.

For class proportions $p_1,\dots ,p_K$ in a tree node, Gini impurity is $1-{\sum }_k{p}_k^2$. For two classes it is twice $p(1-p)$; omitting the constant factor does not change the selected split.

A random forest aggregates deeply grown decision trees fitted to bootstrap samples, while restricting each split to a random subset of predictor coordinates. Classification uses a majority vote over the trees.

The out-of-bag error predicts each training observation using only trees whose bootstrap samples omitted it, then averages the resulting losses.

The conditional class probability for class $k$ isA Bayes classifier selects a class maximizing this probability.

A sequence of classifiers $h_n$ is risk-consistent when its classification risk converges to the Bayes risk as the training sample size tends to infinity.

The K-nearest neighbors algorithm predicts from the labels or responses of the $K$ training observations closest to the query under a chosen distance.

With fixed neighbor positions, independent equal-variance errors and weights $w,(1-w)/2,(1-w)/2$, the displayed variance is minimized at $w=1/3$, with value ${\sigma }^2/3$. Its bias is $w{m}_1+(1-w)(m_2+m_3)/2-m(x)$. Larger nearest-point weight often reduces smoothing bias, but neither the bias nor the variance is universally monotone over $0<w<1$. If the nearest point is the target, the squared bias is $(1-w{)}^2[(m_2+m_3)/2-m(x){]}^2$.

// Target: probability-and-statistics.bigb

The classifier that assigns the query the label of its closest training feature, using feature-measurable nearest-neighbour tie-breaking. Its misclassification risk need not converge to Bayes risk, even with infinitely many independent and identically distributed random variables as training data.

For binary classification, write $\eta (x)=\mathbb{P}(Y=1\mid X=x)$ and assume feature-measurable nearest-neighbour tie-breaking. If $\mathbb{E}|\eta (X_{(1)}(X))-\eta (X)|\to 0$, then the expected conditional misclassification risk of the one-nearest-neighbour classifier tends to $\mathbb{E}[2\eta (X)(1-\eta (X))]$. Couple each label and an oracle label using one uniform variable. Their disagreement has the preceding expected absolute difference. The oracle and the test label are conditionally independent Bernoulli random variables of parameter $\eta (X)$, so their disagreement probability is exactly $2\eta (X)(1-\eta (X))$. The difference of classification in statistical learning error probabilities is at most the coupling disagreement.

Under the hypotheses for the one-nearest-neighbour asymptotic risk, the limiting risk satisfies $R^{\ast }\le R_{\infty }\le 2R^{\ast }$. Put $a=\min (\eta ,1-\eta )$: then $a\le 2a(1-a)\le 2a$ since $0\le a\le 1/2$. Integrate, using the definition of Bayes risk. Constant $\eta =1/4$ gives limiting risk $3/8$ and Bayes risk $1/4$, so the lower comparison is not generally equality.

For a fixed query, order training features by their distances and break equal distances by a rule depending only on features, such as original index. If auxiliary uniforms are independent of the features, the uniform selected by the resulting index remains uniform conditional on all features: sum over the possible selected indices. Label-dependent tie-breaking can invalidate Bernoulli coupling by a shared uniform random variable and the usual one-nearest-neighbour asymptotic risk.

The L-nearest-neighbour classifier estimates each class probability by its empirical frequency among the $L$ nearest training covariates and predicts a class of greatest estimated probability.

One-nearest-neighbour classification assigns a query the label of its single nearest training observation. Under local regularity, its limiting conditional error is $1-{\sum }_k{p}_k(x{)}^2$.

For binary classification with posterior estimate ${\hat{p}}_1$, the plug-in classifier satisfies

A support vector machine chooses a separating decision function by trading a wide geometric margin against hinge-loss violations.

A kernel support vector machine trains a support vector machine using a positive-definite kernel instead of explicit feature coordinates. The kernel trick evaluates all required feature inner products through the training Gram matrix; prediction is ${\sum }_i{\alpha }_i{y}_{i}k(x_i,x)+b$. Nonzero dual coefficients identify support vectors. An unpenalized intercept supplies the dual equality ${\sum }_i{\alpha }_i{y}_i=0$. The Reproducing kernel Hilbert space construction explains why a positive-semidefinite kernel defines valid feature geometry.

For signed training labels, a linear soft-margin support vector machine minimizeswith $C>0$. Its Karush-Kuhn-Tucker conditions give $w={\sum }_i{\alpha }_i{y}_i{x}_i$, ${\sum }_i{\alpha }_i{y}_i=0$, and $0\le {\alpha }_i\le C$.

For the kernel support vector machine objective $n^{-1}{\sum }_i(1-Y_i(\mu +K_i^T\alpha ){)}_{+}+\lambda {\alpha }^{T}K\alpha$, assume $Y_i\in \{-1,1\}$, $\lambda >0$, and that the kernel matrix $K$ is invertible. The subdifferential optimality equation givesThus strict margins greater than one force zero coefficients, while misclassified observations have nonzero coefficients. Invertibility matters: a singular kernel matrix allows coefficient changes in its null space without changing the fitted function or objective.

For a fixed $C$ in the unnormalized sum-of-slacks objective and unique training optimizers, deleting an observation with ${\alpha }_i=0$ preserves the Karush-Kuhn-Tucker conditions and the fitted decision function. It is correctly classified when held out. Consequently Leave-one-out cross-validation makes at most $s$ errors, where $s$ counts positive dual coefficients. With geometric support vectors, counting all points of signed margin at most one also gives the bound, without a nondegeneracy assumption.

A dual support vector has ${\alpha }_i>0$. Every such point has signed margin at most one, but a point exactly on the margin can have ${\alpha }_i=0$ in a degenerate solution. If ${\alpha }_i=0$, complementary slackness forces ${\xi }_i=0$, so the point is correctly classified with margin at least one.

For signed observations $(x_i,y_i)$, an affine hyperplane with score $f(x)=\alpha +x^T\beta$ is separating when $y_{i}f(x_i)>0$ for every observation.

The slack variables satisfy ${\xi }_i\ge \max \{0,1-y_{i}f(x_i)\}$ and quantify margin violations.

For a linear score $f(x)=\alpha +x^T\beta$, the decision boundary is $f(x)=0$.

For a linear support vector machine, the geometric margin lies between $f(x)=-1$ and $f(x)=1$ and has width $2/\Vert \beta \Vert$.

The two margin boundaries of a linear support vector machine are the parallel hyperplanes $f(x)=1$ and $f(x)=-1$.

A support vector is a training observation on or inside the fitted margin; it has a nonzero dual coefficient and can affect the fitted boundary.

The perceptron is an online linear classifier that adds a misclassified observation's signed feature vector to its current parameter vector.