0.5 Plug-in classifier and histogram classifier  (Page 2/2)

Consistency of histogram classifiers

If $M\to \infty$ and $\frac{n}{M}\to \infty$ as $n\to \infty$ , then the histogram classifier risk converges to the Bayes risk for every distribution $P_{XY}$ with marginal density $p_X\left(x\right)\ge c$ , for some constant $c>0$ . Actually, the result holds for every distribution $P_{XY}$ . For the more general theorem, refer to Theorem $6.1$ in A probabilistic Theory of Pattern Recognition by Luc Devroye, László Györfi and Gábor Lugosi. .

What the theorem tells us is that we need the number of partition cells to tend to infinity (to insure that the bias tends to zero), but they can'tgrow faster than the number of samples ( i.e., we want the number of samples per box tending to infinity to drive the variance to zero).

Let $P_j\equiv \frac{{\int }_{Q_j}\eta \left(x\right)p_X\left(x\right)dx}{{\int }_{Q_j}{p}_X\left(x\right)dx}$ (the theoretical analog of ${\widehat{P}}_j$ ) and define

The function $\overline{\eta }$ is the theoretical analog of $\widehat{\eta }$ (i.e., the function obtained by averaging $\eta$ over the partition cells). By the triangle inequality,

Let's first bound the estimation error. For any $x\in {[0,1]}^d$ , let $Q\left(x\right)$ denote the histogram bin in which $x$ falls in. Define the random variable

If $Q\left(x\right)=Q_j$ , then this random variable is simply $n{\widehat{P}}_j$ . Note that

where $B\left(x\right)=={\sum }_{i=1}^n{\mathbf{1}}_{\{X_i\in Q\left(x\right),Y_i=1\}}={\sum }_{i:X_i\in Q\left(x\right)}{Y}_i$ . $B\left(x\right)$ is simply the number of samples in cell $Q\left(x\right)$ labelled 1. Now ${\widehat{\eta }}_n\left(x\right)$ is a fairly complicated random variable, but the conditional distribution of $B\left(x\right)$ given $N\left(x\right)$ is relatively simple. Note that

since $\overline{\eta }\left(x\right)$ is the probability of a sample in $Q\left(x\right)$ having the label 1 and we are conditioning on the event of observing $k$ samples in $Q\left(x\right)$ .

Now consider the conditional expectation

Next note that

by the Jensen's inequality, $E\left[\right|Z\left|\right]\le {\left(E\right[\left|Z\right|}^2{\left]\right)}^{\frac{1}{2}}$ .

Therefore,

and

or in other words,

Now taking expectation with respect to $N\left(x\right)$

Now a key fact is that for any $k>0$ , $P(N\le k)\to 0\text{as}n\to \infty$ . This follows from the assumption that the marginal density $p_X\left(x\right)\ge c$ , for some constant $c>0$ , and $\frac{n}{M}\to \infty$ as $n\to \infty$ . This result is easily verified by contradiction. If $P(N\le k)\to q>0\text{as}n\to \infty$ , then $P_X\left(x\right)>0$ is contradicted. Thus, for any $ϵ>0$ there exists a $k>0$ such that $\frac{1}{2\sqrt{k}}<ϵ$ and $P(N\le k)<ϵ$ for $n$ sufficiently large. Therefore, for $n$ sufficiently large and every $x\in {[0,1]}^d$ ,

where the expectation is with respect to the distribution of the sample ${\{X_i,Y_i\}}_{i=1}^n$ . Thus,

where the expectation is now with respect to the distribution of the sampleand the marginal distribution of $X$ .

Next consider the approximation error $E\left[|,{\overline{\eta }}_n,\left(X\right)-\eta \left(X\right)|\right]$ , where the expectation is over $X$ alone. The function $\eta$ may not itself be continuous, but there is another function ${\eta }_{ϵ}$ that is uniformly continuous and such that $E\left[|,{\eta }_{ϵ},\left(X\right)-\eta \left(X\right)|\right]<ϵ$ . Recall that uniformly continuous functions can be well approximated by piecewiseconstant functions.

By the triangle inequality,

where ${\overline{\eta }}_{ϵ}\left(x\right)={\sum }_{j=1}^m\left[{\int }_{Q_j},{\eta }_{ϵ},\left(x^{\text{'}}\right),p_X,\left(x^{\text{'}}\right),d,x^{\text{'}}\right]{\mathbf{1}}_{\{x\in Q_j\}}$ .

and since ${\eta }_{ϵ}$ is uniformly continuous,

By taking $M$ sufficiently large, $\delta$ can be made arbitrarily small. So for large $M$ , $\delta \le ϵ$ .

Thus, we have shown

for sufficiently large $M$ . Since $ϵ>0$ was arbitrary, we have shown that taking

satisfies

if