Statistical learning theory

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.

If independent inputs $Z_1,\dots ,Z_n$ enter a function whose value changes by at most $L_i$ when only coordinate $i$ changes, then

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

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.

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

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

The shattering coefficient is

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.

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

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.

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.

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.