0.5 Plug-in classifier and histogram classifier

We return to the topic of classification, and we assume an input (feature) space $\mathcal{X}$ and a binary output (label) space $\mathcal{Y}=\{0,1\}$ . Recall that the Bayes classifier (which minimizes the probability of misclassification) is defined by

Throughout this section, we will denote the conditional probability function by

Plug-in classifiers

One way to construct a classifier using the training data ${\{X_i,Y_i\}}_{i=1}^n$ is to estimate $\eta \left(x\right)$ and then plug-it into the form of the Bayes classifier. That is obtain an estimate,

and then form the “plug-in" classification rule

Therefore, in this sense plug-in methods are solving a more complicated problem than necessary. However, plug-in methods can perform well,as demonstrated by the next result.

Plug-in classifier

Let $\tilde{\eta }$ be an approximation to $\eta$ , and consider the plug-in rule

Then,

where

Consider any $x\in {\mathbf{R}}^d$ . In proving the optimality of the Bayes classifier $f^{*}$ in Lecture 2 , we showed that

which is equivalent to

since $f^{*}\left(x\right)=1$ whenever $2\eta \left(x\right)-1>0$ . Thus,

where the first inequality follows from the fact

and the second inequality is simply a result of the fact that ${\mathbf{1}}_{\{f^{*}\left(x\right)\ne f\left(x\right)\}}$ is either 0 or 1.

The theorem shows us that a good estimate of $\eta$ can produce a good plug-in classification rule. By “good" estimate, we mean an estimator $\tilde{\eta }$ that is close to $\eta$ in expected $L_1\text{-norm}$ .

The histogram classifier

Let's assume that the (input) features are randomly distributed over theunit hypercube $\mathcal{X}={[0,1]}^d$ (note that by scaling and shifting any set of bounded features we can satisfy this assumption),and assume that the (output) labels are binary, i.e., $\mathcal{Y}=\{0,1\}$ . A histogram classifier is based on a partition the hypercube ${[0,1]}^d$ into $M$ smaller cubes of equal size.

Partition of hypercube in 2 dimensions

Consider the unit square ${[0,1]}^2$ and partition it into $M$ subsquares of equal area (assuming $M$ is a squared integer). Let the subsquares be denoted by $\left\{Q_i\right\},i=1,...,M$ .

Define the following piecewise-constant estimator of $\eta \left(x\right)$ :

$${\widehat{\eta }}_n\left(x\right)=\sum _{j=1}^M{\widehat{P}}_j{\mathbf{1}}_{\{x\in Q_j\}}$$

where

$${\widehat{P}}_j=\frac{{\sum }_{i=1}^n{\mathbf{1}}_{\{X_i\in Q_j,Y_i=1\}}}{{\sum }_{i=1}^n{\mathbf{1}}_{\{X_i\in Q_j\}}}.$$

Like our previous denoising examples, we expect that the bias of ${\widehat{\eta }}_n$ will decrease as $M$ increases, but the variance will increase as $M$ increases.