Statistical learning theory

Statistical learning theory studies mathematical guarantees and limitations for learning from data, including how a hypothesis class, loss function, and sample size affect generalization. It distinguishes a particular fitted rule's prediction error from the expected performance of the learning procedure across possible training data.

A concept class $C$ is weakly PAC learnable using a hypothesis class $H$ when a learning procedure has a fixed edge $\gamma >0$ such that, for every target in $C$, every input probability distribution, and every confidence parameter $\delta$, sufficiently many independent target-labelled examples let it return an $h\in H$ satisfying the displayed bound with probability at least $1-\delta$. The example bound must be polynomial in $1/\delta$ under this definition. Computational efficiency is an additional requirement when explicitly imposed. This distribution-wide guarantee should be distinguished from merely obtaining an advantage on one finite training sample.

A finite VC dimension gives simultaneous control of empirical misclassification risk for every member of a hypothesis class. Sufficient independent sample size is $A{\eta }^{-2}(v\log (2/\eta )+\log (2/\delta ))$. The displayed event implies an empirical risk minimization rule has misclassification risk at most ${\inf }_{h}R(h)+2\eta$, including for unrealizable labels.^[ref]

The observations used to construct a classifier or other fitted rule. For a random fitted classifier, its conditional misclassification risk conditions on these observations and evaluates an independent test pair. Auxiliary randomization used in fitting belongs to the conditioning information as well.

An image dataset organized around labelled object categories, widely used for training and testing visual recognition models. Its category labels and image statistics supply a particular learning environment, not a literal reconstruction of a developing primate’s experience.

A binary hypothesis class is a family of functions from an input space to a two-element label set, commonly $\{-1,1\}$.

A classifier is a function that assigns an input to one of a discrete set of labels. A binary classifier has two possible labels.

An affine linear classifier assigns binary labels according to the sign of an affine function. Its boundary is an affine hyperplane, and its positive region is a closed half-space under the displayed convention. On ${\mathbb{R}}^d$ the full class has VC dimension $d+1$: arbitrary signs interpolate on $d+1$ affinely independent points, while the intersecting convex hull partition theorem prevents shattering any $d+2$ points. Requiring $b=0$ gives the homogeneous case and a different VC dimension.

The sign function records whether a real number is positive or negative, with a convention chosen separately at zero.

Empirical risk minimization chooses a hypothesis that minimizes the average loss on the observed data.

The empirical risk of a hypothesis $h$ on observations $z_1,\dots ,z_n$ is the sample-average loss

A loss function assigns a numerical penalty to a prediction and its observed outcome. Its expected value is the population risk optimized by a statistical learning procedure.

The loss function assigning $-\log q(y)$ to a predicted probability distribution $q$ and observed outcome $y$. It is the negative logarithmic scoring rule; its expected value under the true probability distribution is cross-entropy. Predicting zero probability for an observed outcome gives infinite loss.

The population risk of a prediction rule is its expected loss on a fresh observation from the target probability distribution.

Given a hypothesis class $\mathcal{H}$ and a loss function $\ell$, its loss class is the function classIt lets properties of a learning problem be studied through the random fluctuations of the losses themselves.

For a classifier $h$ and a labelled example $z=(x,y)$, the misclassification loss isIt is also called zero-one loss because it is zero for a correct prediction and one for an incorrect prediction.

The misclassification risk of a classifier is its expected misclassification loss,

For a random classifier $C$ determined by training information $\mathcal{T}$, and an independent test pair $(X,Y)$, its conditional misclassification risk is $L(C)=\mathbb{P}(C(X)\ne Y\mid \mathcal{T})$. It is itself a training-dependent random variable. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$.

On labelled examples $Z_1,\dots ,Z_n$, the empirical misclassification risk isAn empirical risk minimizer chooses a classifier attaining the smallest value over its hypothesis class.

If $h^{\ast }$ minimizes the population risk over a hypothesis class, the excess risk of $h$ is the nonnegative difference $R(h)-R(h^{\ast })$.

For data $(X_i,Y_i)$ and predictions $h_{\beta }(X)={\beta }^{T}X$, it is convenient to writeIts gradient is

The shattering coefficient is

// The existing Shattering coefficient article supplies the definition.

For binary hypothesis classes,because the label vectors realized by the union form the union of the two sets of realized label vectors.

The VC dimension is the largest number of points on which a binary hypothesis class realizes every possible labeling.

The positive-radius closed Euclidean balls in ${\mathbb{R}}^d$ have VC dimension $d+1$ for $d\ge 1$. Vertices of a regular simplex are shattered: interpolate any desired signs by an affine function $a\cdot x+b$, then perturb a sphere through the vertices to the score $1+\eta b+\eta a\cdot x-\Vert x{\Vert }^2$. For the upper bound, take an affine dependence $\lambda$ among $d+2$ points and orient it so that $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2\ge 0$. Labelling the positive coefficients inside and the negative coefficients outside would force ${\sum }_i{\lambda }_i(r^2-\Vert x_i-c{\Vert }^2)>0$, while the affine dependence makes this sum equal $-Q\le 0$. The weaker $d+2$ upper bound from unrestricted lifted affine linear classifiers loses their fixed quadratic coefficient.

If $VC(H)=D<\infty$, then $s(H,n)\le {\sum }_{j=0}^D\left(\genfrac{}{}{0ex}{}{n}{j}\right)$.

If no $k$-set were shattered, the Sauer-Shelah lemma would bound the number of traces by ${\sum }_{i<k}\left(\genfrac{}{}{0ex}{}{2k}{i}\right)=(2^{2k}-(\genfrac{}{}{0ex}{}{2k}{k}))/2<2^{2k-1}$. This strict middle-layer gap contradicts the displayed lower bound. Therefore a family with such traces at every even size has unbounded finite VC dimension.

The elementary estimate ${\sum }_{j=0}^D\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le (n+1{)}^D$ converts finite VC dimension into a polynomial bound on the number of sample labelings.

The class of lower orthants ${\prod }_{j=1}^p(-\infty ,a_j]$ in ${\mathbb{R}}^p$ has VC dimension at most $p$. Among any $p+1$ points, choose a coordinate maximizer for each of the $p$ coordinates. A remaining point cannot be excluded while all those maximizers are included.

Indicators of real intervals have VC dimension two: two ordered points can be labeled arbitrarily, while an interval containing the two outer points of a triple must contain the middle point.

For a target positive set consisting of two disjoint intervals of total probability $p$, choosing its heavier component has misclassification risk at most $p/2$. Choosing the spanning interval has misclassification risk at most $1-p$. The smaller bound is at most $1/3$. The constant is sharp: on three ordered atoms with equal masses and labels $1,0,1$, every single interval makes a mistake on at least one atom. Together with the VC uniform convergence theorem, this gives weak PAC learning using an interval hypothesis class.

Intervals together with their label complements shatter three ordered points, but cannot realize an alternating labeling on four, so their VC dimension is three.

The sign class of a $d$-dimensional real vector space of functions has VC dimension at most $d$. If $n>d$ points were shattered, the evaluation map from the function space to ${\mathbb{R}}^n$ would have a nonzero vector orthogonal to its image. Choosing labels according to the signs of that vector contradicts orthogonality.

The indicators of closed Euclidean balls in ${\mathbb{R}}^d$ have VC dimension at most $d+2$. Indeed,wherebelongs to the span of $\Vert x{\Vert }_2^2,x_1,\dots ,x_d,1$.

The map $x\mapsto (x_i{x}_j{)}_{i\le j}$ embeds homogeneous quadratic forms in a linear function space of dimension $d(d+1)/2$.

The signs of homogeneous linear forms $x\mapsto x^T\beta$ on ${\mathbb{R}}^p$ have VC dimension at most $p$. The Sauer-Shelah growth bound therefore gives

For $f={\sum }_{j=1}^m{\alpha }_j{g}_j$ with $g_j$ drawn from a binary class $\mathcal{G}$, fixing $(g_1,\dots ,g_m)$ leaves an $m$-dimensional linear sign class. Consequentlywhen $\mathcal{G}$ is finite, and in general

A bias-free network with $p$ inputs, $m$ sign-activated hidden nodes, and a thresholded linear output satisfiesThe hidden units contribute $s(\mathcal{G},n{)}^m\le (n+1{)}^{pm}$ sample patterns, and the output weights contribute $(n+1{)}^m$.

AdaBoost constructs an additive classifier by repeatedly fitting a base classifier to exponentially reweighted observations. Misclassified observations receive greater weight at the next iteration, and the final score is a nonnegative weighted sum of the base classifiers.

At score $F$, the exponential classification risk weights observation $i$ proportionally to $e^{-y_{i}F(x_i)}$. A stage $\alpha G$ multiplies this weight by $e^{-\alpha y_{i}G(x_i)}$. For weighted error $ϵ$, the loss multiplier is $(1-ϵ)e^{-\alpha }+ϵe^{\alpha }$, minimized at the displayed value. Its minimum is $2\sqrt{ϵ(1-ϵ)}$. Thus errors gain weight relative to correct observations in the next stage.

// Target: foundations-of-mathematics.bigb

For AdaBoost with initial uniform weights, labels and base predictions in $\{-1,1\}$, and edges ${\gamma }_m=1/2-{ϵ}_m>0$, the training exponential classification risk equals the product of stage normalizers. A wrongly classified point has exponential loss at least one, so empirical classification error is bounded by this product. The final inequality uses $\sqrt{1-4{\gamma }_m^2}\le e^{-2{\gamma }_m^2}$. The result concerns training error, not a guarantee against overfitting or mislabeled observations.

// Target: probability-and-statistics.bigb

For weighted binary data, a weak learner supplies a classifier whose weighted error is below one half. A uniform edge $\gamma >0$ for every weighting permits a quantitative AdaBoost training error bound. This training-weight condition is a separate assumption from merely having error below one half on the initial unweighted sample.

// Target: foundations-of-mathematics.bigb

For labels $Y\in \{-1,1\}$ and a real-valued score $f$, the exponential loss is $\varphi (Yf(X))=e^{-Yf(X)}$. Its population and empirical risks are

For independent and identically distributed random variables $Z_1,\dots ,Z_n$ and independent Rademacher signs ${\epsilon }_1,\dots ,{\epsilon }_n$, the Rademacher complexity of a function class $\mathcal{F}$ isIt measures how strongly the class can correlate with independent random signs on a random sample.

For a fixed sample $z_{1:n}$, the empirical Rademacher complexity isTaking its expected value over the sample gives ${\mathcal{R}}_n(\mathcal{F})$.

For an i.i.d. sample and an integrable function class $\mathcal{F}$,Introduce an independent ghost sample, replace each expectation by its ghost-sample average using Jensen inequality, and then multiply each paired difference by an independent Rademacher sign. Splitting the resulting supremum into its two sample contributions gives the factor two.

For a zero-one-valued loss class $\mathcal{F}$, the excess misclassification risk of an empirical risk minimizer $\hat{h}$ over a population minimizer $h^{\ast }$ satisfieswith probability at least $1-\delta$. The proof combines Rademacher symmetrization with the Bounded differences inequality for the supremum of the empirical excess-loss process.

The observable version isIt follows by another application of the Bounded differences inequality to the Empirical Rademacher complexity.

For a finite $A\subseteq {\mathbb{R}}^n$ with ${\max }_{a\in A}\Vert a{\Vert }_2\le R$, its empirical Rademacher complexity is at most $R\sqrt{2\log |A|}/n$.

For $|D_i|\le M$ and a binary class $H$ of VC dimension at most $p$, the vectors $(D_{i}h(X_i){)}_{i=1}^n$ have norm at most $M\sqrt{n}$ and at most $(n+1{)}^p$ distinct values. The Massart finite-class lemma gives

A linear functional has the same supremum over a class and its convex hull. Thus taking convex combinations does not increase empirical Rademacher complexity.

Composition with an $L$-Lipschitz scalar map increases Rademacher complexity by at most the factor $L$ after centering at zero.

Independent signs cancel cross terms in $\mathbb{E}\Vert {\sum }_i{\sigma }_i{A}_i{\Vert }_F^2$, leaving ${\sum }_i\Vert A_i{\Vert }_F^2$.

For $h_M(x)=x^{T}Mx$, $M⪰0$, $\mathrm{tr}M\le s$, and $\Vert x\Vert \le C$, the complexity is at most $C^{2}s/\sqrt{n}$.

With the $1/n$ Rademacher convention, an empirical risk minimizer has expected excess risk at most twice the Rademacher complexity of its loss class.

The hinge loss is $\max (0,1-yh(x))$ and is one-Lipschitz in the signed margin.

For a sample term $\max \{0,1-a_{i}x\}$, the active hinge set contains indices with $1-a_{i}x>0$. At strict negative margins the hinge is inactive, while zero margins allow fractional hinge-loss optimality weights. Away from zero margins, the active set stays fixed on a sufficiently small candidate solution neighborhood.

With fixed positive quadratic regularization, if all reference hinge margins are nonzero, the one-dimensional minimizer has local formula $x(a)=(\alpha n{)}^{-1}{\sum }_{i\in I}{a}_i$. The active hinge set is verified using continuity of this explicit candidate, then strong convexity identifies it as the optimizer. Its exact Euclidean Lipschitz modulus is $\sqrt{|I|}/(\alpha n)$.

The subgradient of $\max \{0,1-a_{i}x\}$ is $-{\lambda }_i{a}_i$, with ${\lambda }_i=1$ below the margin, ${\lambda }_i=0$ beyond it and ${\lambda }_i\in [0,1]$ at equality. For quadratic regularization the one-dimensional optimality condition is $\alpha nx={\sum }_i{\lambda }_i{a}_i$. The optimizer can be unique even if the weights at equality are not.

In statistical learning theory, Stability measures how much a learned predictor or its loss changes when the training sample is perturbed. Uniform stability of a learning algorithm imposes a bound valid at every test example.

This is a uniform version of Stability for learning algorithms. A learning algorithm has uniform stability $\beta$ for a loss when replacing one training example changes the loss at every test example by at most $\beta$.

Decision tree learning fits predictors by recursively partitioning input space. Leaves predict labels for classification or numerical values for regression; a regression tree is the numerical-response case.

A regression tree is the numerical-response case of decision tree learning. A regression tree recursively partitions predictor space by axis-aligned splits. At each leaf, candidate coordinates and thresholds are compared by the residual sum of squares after replacing that leaf by its two children; the selected split minimizes the total criterion. The fitted value in each terminal region is the sample mean there.

A decision stump is a decision tree with one split. A regression stump predicts a constant, usually the sample mean, in each of its two terminal regions.

For stumps $h(x)=\mathrm{sign}(x_i-b)$ of fixed polarity, sort observations along each coordinate and sweep the threshold across whole groups of equal values. Passing a group adds its positive-label weight and subtracts its negative-label weight from the weighted misclassification risk. Include thresholds below and above all observed values. Every distinct sample prediction pattern is considered, giving exact minimization in $O(nm\log m)$ time complexity for $m$ observations in ${\mathbb{R}}^n$. Coordinate sort orders can be reused across AdaBoost rounds, reducing subsequent weighted scans to $O(nm)$.

For a deterministic partition $R_1,\dots ,R_J$ andconditional independence givesIf the conditional response variance is at most ${\sigma }^2$, the prediction variance at an independent test point is at most ${\sigma }^{2}J/n$.