<< Chapter < Page Chapter >> Page >

Error bound

Suppose that we have a pool of candidate functions F , and we want to select a function f from F using the training data. Our usual approach is to show that the distribution of R n ^ ( f ) concentrates about its mean as n grows. First, we assign a complexity c ( f ) > 0 to each f F so that 2 - c ( f ) 1 . Then, apply the union bound to get a uniform concentration inequality holding for all models in 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 F so that the excess risk is small.

0 R ( f ) - R ( f * ) = 1 n E [ log p f * ( Y ) - log p f ( Y ) ] = 1 n E log p f * ( Y ) p f ( Y ) 1 n K ( p f , p f * )

where

K ( p f , p f * ) = i = 1 n log p f * ( x i ) ( y i ) p f ( x i ) ( y i ) · p f * ( x i ) ( y i ) d y i K ( p f ( x i ) , p f * ( x i ) )

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

1 n E H 2 ( p f ( Y ) , p f * ( Y ) ) = 1 n i = 1 n p f ( x i ) ( y i ) - p f * ( x i ) ( y i ) 2 d y i .

Maximum complexity-regularized likelihood estimation

Theorem

Li-barron 2000, kolaczyk-nowak 2002

Let { x i , Y i } i = 1 n be a random sample of training data with { Y i } independent,

Y i p f * ( x i ) ( y i ) , i = 1 , ... , n

for some unknown function f * .

Suppose we have a collection of candidate functions F , and complexities c ( f ) > 0 , f F , satisfying

f F 2 - c ( f ) 1 .

Define the complexity-regularized estimator

f n ^ arg min f F - 1 n i = 1 n log p f ( Y i ) + 2 c ( f ) log 2 n .

Then,

1 n E H 2 ( p f ( Y ) , p f * ( Y ) ) - 2 n E log A ( p f ( Y ) , p f * ( Y ) ) min f F 1 n K ( p f , p f * ) + 2 c ( f ) log 2 n .

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

Gaussian noise

Suppose Y i = f ( x i ) + W i , W i i . i . d . N ( 0 , σ 2 ) .

p f ( x i ) ( y i ) = 1 2 π σ 2 e - ( y i - f ( x i ) ) 2 2 σ 2 .

Using results from example 1 , we have

- 2 log A p f n ^ ( Y ) , p f * ( Y ) = i = 1 n - 2 log A p f n ^ ( x i ) ( Y i ) , p f * ( x i ) ( Y i ) = i = 1 n - 2 log p f n ^ ( x i ) ( y i ) · p f * ( x i ) ( y i ) d y i = 1 4 σ 2 i = 1 n f n ^ ( x i ) - f * ( x i ) 2 .

Then,

- 2 n E log A ( p f n ^ , p f * ) = 1 4 σ 2 n i = 1 n E f n ^ ( x i ) - f * ( x i ) 2 .

We also have,

1 n K ( p f , p f * ) = 1 n i = 1 n f ( x i ) - f * ( x i ) 2 2 σ 2 - log p f ( Y ) = i = 1 n ( Y i - f ( X i ) ) 2 2 σ 2 .

Combine everything together to get

f n ^ = arg min f F 1 n i = 1 n ( Y i - f ( X i ) ) 2 2 σ 2 + 2 c ( f ) log 2 n .

The theorem tells us that

1 4 n i = 1 n E f n ^ ( x i ) - f * ( x i ) 2 σ 2 min f F 1 n i = 1 n f ( x i ) - f * ( x i ) 2 2 σ 2 + 2 c ( f ) log 2 n

or

1 n i = 1 n E f n ^ ( x i ) - f * ( x i ) 2 min f F 2 n i = 1 n f ( x i ) - f * ( x i ) 2 + 8 σ 2 c ( f ) log 2 n .

Now let's come back to the proof.

Proof
H 2 p f n ^ , p f * = p f n ^ ( y ) - p f * ( y ) 2 d y - 2 log p f n ^ ( y ) · p f * ( y ) d y a f f i n i t y
E H 2 p f n ^ , p f * 2 E log 1 p f n ^ ( y ) · p f * ( y ) d y .

Now, define the theoretical analog of f n ^ :

f n = arg min f F 1 n K p f , p f * + 2 c ( f ) log 2 n .

Since

f n ^ = arg min f F - 1 n log p f ( Y ) + 2 c ( f ) log 2 n = arg max f F 1 n log p f ( Y ) - 2 c ( f ) log 2 = arg max f F 1 2 log p f ( Y ) - 2 c ( f ) log 2 = arg max f F log p f ( Y ) · e - c ( f ) log 2 = arg max f F p f ( Y ) · e - c ( f ) log 2

we can see that

p f n ^ ( Y ) e - c ( f n ^ ) log 2 p f n ( Y ) e - c ( f n ) log 2 1 .

Then can write

E H 2 p f n ^ , p f * 2 E log 1 p f n ^ ( y ) · p f * ( y ) d y 2 E log p f n ^ ( Y ) e - c ( f n ^ ) log 2 p f n ( Y ) e - c ( f n ) log 2 · 1 p f n ^ · p f * d y .

Now, simply multiply the argument inside the log by p f * ( Y ) p f * ( Y ) to get

E H 2 p f n ^ , p f * 2 E log p f * ( Y ) p f n ( Y ) p f n ^ ( Y ) p f * ( Y ) e - c ( f n ^ ) log 2 e - c ( f n ) log 2 · 1 p f n ^ ( y ) · p f * ( y ) d y = E log p f * ( Y ) p f n ( Y ) + 2 c ( f n ) log 2 + 2 E log p f n ^ ( Y ) p f * ( Y ) · e - c ( f n ^ ) log 2 p f n ^ ( y ) · p f * ( y ) d y = K p f n , p f * + 2 c ( f n ) log 2 + 2 E log p f n ^ ( Y ) p f * ( Y ) · e - c ( f n ^ ) log 2 p f n ^ ( y ) · p f * ( y ) d y .

The terms K p f n , p f * + 2 c ( f n ) log 2 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

2 E log p f n ^ ( Y ) p f * ( Y ) · e - c ( f n ^ ) log 2 p f n ^ ( y ) · p f * ( y ) d y 2 log E e - c ( f n ^ ) log 2 · p f n ^ ( Y ) p f * ( Y ) p f n ^ ( y ) · p f * ( y ) d y .

Both Y and 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 f n ^ :

2 E log p f n ^ ( Y ) p f * ( Y ) · e - c ( f n ^ ) log 2 p f n ^ ( y ) · p f * ( y ) d y 2 log E f F e - c ( f ) log 2 · p f ( Y ) p f * ( Y ) p f ( y ) · p f * ( y ) d y = 2 log f F 2 - c ( f ) E p f ( Y ) p f * ( Y ) p f ( y ) · p f * ( y ) d y = 2 log f F 2 - c ( f ) 0 .

where the last two lines come from

E p f ( Y ) p f * ( Y ) = p f ( y ) p f * ( y ) · p f * ( y ) d y = p f ( y ) · p f * ( y ) d y

and

f F 2 - c ( f ) 1 .

Questions & Answers

what are components of cells
ofosola Reply
twugzfisfjxxkvdsifgfuy7 it
Sami
58214993
Sami
what is a salt
John
the difference between male and female reproduction
John
what is computed
IBRAHIM Reply
what is biology
IBRAHIM
what is the full meaning of biology
IBRAHIM
what is biology
Jeneba
what is cell
Kuot
425844168
Sami
what is cytoplasm
Emmanuel Reply
structure of an animal cell
Arrey Reply
what happens when the eustachian tube is blocked
Puseletso Reply
what's atoms
Achol Reply
discuss how the following factors such as predation risk, competition and habitat structure influence animal's foraging behavior in essay form
Burnet Reply
cell?
Kuot
location of cervical vertebra
KENNEDY Reply
What are acid
Sheriff Reply
define biology infour way
Happiness Reply
What are types of cell
Nansoh Reply
how can I get this book
Gatyin Reply
what is lump
Chineye Reply
what is cell
Maluak Reply
what is biology
Maluak
what is vertibrate
Jeneba
what's cornea?
Majak Reply
what are cell
Achol
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Statistical learning theory. OpenStax CNX. Apr 10, 2009 Download for free at http://cnx.org/content/col10532/1.3
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Statistical learning theory' conversation and receive update notifications?

Ask