<< Chapter < Page | Chapter >> Page > |
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,\phantom{\rule{4pt}{0ex}}\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.
Suppose ${f}^{*}\in \mathcal{F}$ , then
Furthermore if $c\left({f}^{*}\right)=O(logn)$ then
that is, only within a small $O\left(\sqrt{\frac{logn}{n}}\right)$ offset of the optimal risk.
In general, we can also bound the excess risk $E\left[R\left({\widehat{f}}_{n}\right)\right]-{R}^{*}$ , where ${R}^{*}$ is the Bayes risk,
By subtracting ${R}^{*}$ (a constant) from both sides of the inequality
we obtain
Note that two terms in this upper bound: $R\left(f\right)-{R}^{*}$ is a bound on the approximation error of a model $f$ , and remainder is a bound on the estimation error associated with $f$ . Thus, we see that complexity regularization automatically optimizes a balance between approximation and estimationerrors. In other words, complexity regularization is adaptive to the unknown tradeoff between approximation and estimation.
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:\phantom{\rule{4pt}{0ex}}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:\phantom{\rule{4pt}{0ex}}P(Y=1|X=x)=1/2\}$ . Clearly the structure of the decision boundary provides importantinformation on the difficulty of the problem.
Notification Switch
Would you like to follow the 'Statistical learning theory' conversation and receive update notifications?