0.14 Maximum likelihood and complexity regularization  (Page 2/2)

Error bound

Suppose that we have a pool of candidate functions $\mathcal{F}$ , and we want to select a function $f$ from $\mathcal{F}$ using the training data. Our usual approach is to show that the distribution of $\widehat{R_n}\left(f\right)$ concentrates about its mean as $n$ grows. First, we assign a complexity $c\left(f\right)>0$ to each $f\in \mathcal{F}$ so that $\sum 2^{-c\left(f\right)}\le 1$ . Then, apply the union bound to get a uniform concentration inequality holding for all models in $\mathcal{F}$ . Finally, we use this concentration inequality to bound the expected risk of our selected model.

We will essentially accomplish the same result here, but avoid the need for explicit concentration inequalities and instead make use of the information-theoretic bounds.

We would like to select an $f\in \mathcal{F}$ so that the excess risk is small.

where

is again the KL divergence.

Unfortunately, as mentioned before, $K(p_f,p_{f^{*}})$ is not a true distance. So instead we will focus on the expected squared Hellinger distance as our measure of performance. We will get a bound on

Maximum complexity-regularized likelihood estimation

Li-barron 2000, kolaczyk-nowak 2002

Let ${\{x_i,Y_i\}}_{i=1}^n$ be a random sample of training data with $\left\{Y_i\right\}$ independent,

for some unknown function $f^{*}$ .

Suppose we have a collection of candidate functions $\mathcal{F}$ , and complexities $c\left(f\right)>0,f\in \mathcal{F}$ , satisfying

Define the complexity-regularized estimator

Then,

Before proving the theorem, let's look at a special case.

Now let's come back to the proof.

Now, define the theoretical analog of $\widehat{f_n}$ :

Since

we can see that

Then can write

Now, simply multiply the argument inside the $log$ by $\sqrt{\frac{p_{f^{*}}\left(Y\right)}{p_{f^{*}}\left(Y\right)}}$ to get

The terms $K\left(p_{f_n},,,p_{f^{*}}\right)+2c\left(f_n\right)log2$ are precisely what we wanted for the upper bound of the theorem. So, to finish theproof we only need to show that the last term is non-positive. Applying Jensen's inequality, we get

Both $Y$ and $\widehat{f_n}$ are random, which makes the expectation difficult to compute. However, we can simplify the problem using the union bound,which eliminates the dependence on $\widehat{f_n}$ :

where the last two lines come from

and