0.11 Decision trees

Minimum complexity penalized function

Recall the basic results of the last lectures: let $\mathcal{X}$ and $\mathcal{Y}$ denote the input and output spaces respectively. Let $X\in \mathcal{X}$ and $Y\in \mathcal{X}$ be random variables with unknown joint probability distribution $P_{XY}$ . We would like to use $X$ to “predict” $Y$ . Consider a loss function $0\le \ell (y_1,y_2)\le 1,\forall y_1,y_2\in \mathcal{Y}$ . This function is used to measure the accuracy of our prediction. Let $\mathcal{F}$ be a collection of candidate functions (models), $f:\mathcal{X}\to \mathcal{Y}$ . The expected risk we incur is given by $R\left(f\right)\equiv E_{XY}\left[\ell (f\left(X\right),Y)\right]$ . We have access only to a number of i.i.d. samples, ${\{X_i,Y_i\}}_{i=1}^n$ . These allow us to compute the empirical risk ${\widehat{R}}_n\left(f\right)\equiv \frac{1}{n}{\sum }_{i=1}^n\ell (f\left(X_i\right),Y_i)$ .

Assume in the following that $\mathcal{F}$ is countable. Assign a positive number $c\left(f\right)$ to each $f\in \mathcal{F}$ such that ${\sum }_{f\in \mathcal{F}}{2}^{-c\left(f\right)}\le 1$ . If we use a prefix code to describe each element of $\mathcal{F}$ and define $c\left(f\right)$ to be the codeword length (in bits) for each $f\in \mathcal{F}$ , the last inequality is automatically satisfied.

We define the minimum complexity penalized estimator as

As we showed previously we have the bound

The performance (risk) of ${\widehat{f}}_n$ is on average better than

where

If it happens that the optimal function, that is

is close to an $f\in \mathcal{F}$ with a small $c\left(f\right)$ , then ${\widehat{f}}_n$ will perform almost as well as the optimal function.

Classification

Consider the particularization of the above to a classification scenario. Let $\mathcal{X}={[0,1]}^d$ , $\mathcal{Y}=\{0,1\}$ and $\ell (\widehat{y},y)\equiv {\mathbf{1}}_{\{\widehat{y}\ne y\}}$ . Then $R\left(f\right)=E_{XY}\left[{\mathbf{1}}_{\left\{f\right(X)\ne Y\}}\right]=P(f\left(X\right)\ne Y)$ . The Bayes risk is given by

As it was observed before, the Bayes classifier ( i.e., a classifier that achieves the Bayes risk) is given by

This classifier can be expressed in a different way. Consider the set $G^{*}=\{x:P(Y=1|X=x)\ge 1/2\}$ . The Bayes classifier can written as $f^{*}\left(x\right)={\mathbf{1}}_{\{x\in G^{*}\}}$ . Therefore the classifier is characterized entirely by the set $G^{*}$ , if $X\in G^{*}$ then the “best” guess is that $Y$ is one, and vice-versa. The boundary of this set corresponds to the points where the decision is harder.The boundary of $G^{*}$ is called the Bayes Decision Boundary . In [link] (a) this concept is illustrated. If $\eta \left(x\right)=P(Y=1|X=x)$ is a continuous function then the Bayes decision boundary is simply given by $\{x:P(Y=1|X=x)=1/2\}$ . Clearly the structure of the decision boundary provides importantinformation on the difficulty of the problem.