0.8 Classification error bounds

Recap: classifier design

Given a set of training data ${\{X_i,Y_i\}}_{i=1}^n$ and a finite collection of candidate functions $\mathcal{F}$ , select ${\widehat{f}}_n\in \mathcal{F}$ that (hopefully) is a good predictor for future cases. That is

where ${\widehat{R}}_n\left(f\right)$ is the empirical risk. For any particular $f\in \mathcal{F}$ , the corresponding empirical risk is defined as

Hoeffding's inequality

Hoeffding's inequality (Chernoff's bound in this case) allows us to gauge how close ${\widehat{R}}_n\left(f\right)$ is to the true risk of $f$ , $R\left(f\right)$ , in probability

Since our selection process involves deciding among all $f\in \mathcal{F}$ , we would like to gauge how close the empirical risks are to theirexpected values. We can do this by studying the probability that one or more of the empirical risks deviates significantly from itsexpected value. This is captured by the probability

Note that the event

is equivalent to union of the events

Therefore, we can use Bonferonni's bound (aka the “union of events” or “union” bound) to obtain

where $\left|\mathcal{F}\right|$ is the number of classifiers in $\mathcal{F}$ . In the proof of Hoeffding's inequality we also obtained a one-sided inequality thatimplied

and hence

We can restate the inequality above as follows, For all $f\in \mathcal{F}$ and for all $\delta >0$ with probability at least $1-\delta$

This follows by setting $\delta =\left|\mathcal{F}\right|e^{-2n{ϵ}^2}$ and solving for $ϵ$ . Thus with a high probability $(1-\delta )$ , the true risk for all $f\in \mathcal{F}$ is bounded by the empirical risk of $f$ plus a constant that depends on $\delta >0$ , the number of training samples n, and the size $\mathcal{F}$ . Most importantly the bound does not depend on the unknown distribution $P_{XY}$ . Therefore, we can call this a distribution-free bound.

Error bounds

We can use the distribution-free bound above to obtain a bound on the expected performance of the minimum empirical riskclassifier

We are interested in bounding

the expected risk of ${\widehat{f}}_n$ minus the minimum risk for all $f\in \mathcal{F}$ . Note that this difference is always non-negative since ${\widehat{f}}_n$ is at best as good as

Recall that $\forall f\in \mathcal{F}$ and $\forall \delta >0$ , with probability at least $1-\delta$

where

In particular, since this holds for all $f\in \mathcal{F}$ including ${\widehat{f}}_n$ ,

and for any other $f\in \mathcal{F}$

since ${\widehat{R}}_n\left({\widehat{f}}_n\right)\le {\widehat{R}}_n\left(f\right)$ $\forall f\in \mathcal{F}$ . In particular,

where $f^{*}=arg{min}_{f\in \mathcal{F}}R\left(f\right)$ .

Let $\Omega$ denote the set of events on which the above inequality holds. Then by definition

We can now bound $E\left[R\left({\widehat{f}}_n\right)\right]-R\left(f^{*}\right)$ as follows

since $E\left[{\widehat{R}}_n\left(f^{*}\right)\right]=R\left(f^{*}\right)$ . The quantity above is bounded as follows.

since $P\left(\Omega \right)\le 1$ , $1-P\left(\Omega \right)\le \delta$ and $R\left({\widehat{f}}_n\right)-{\widehat{R}}_n\left(f^{*}\right)\le 1$

Thus

So we have

In particular, for $\delta =\sqrt{1/n}$ , we have

Application: histogram classifier

Let $\mathcal{F}$ be the collection of all classifiers with M equal volume cells. Then $\left|\mathcal{F}\right|=2^M$ , and the histogram classification rule

satisfies

which suggests the choice $M={log}_{2}n$ (balancing $Mlog2$ with $logn$ ), resulting in