LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 4 - Overfitting (http://book.caltech.edu/bookforum/forumdisplay.php?f=111)
-   -   Exercise 4.7 (http://book.caltech.edu/bookforum/showthread.php?t=4452)

Sweater Monkey 10-23-2013 11:15 AM

Exercise 4.7
 
I feel like I'm overthinking Exercise 4.7 (b) and I am hoping for a little bit of insight.

My gut instinct says that Var[E_{\text{val}}(g^-)] = \frac{1}{K} (P[g^-(x),y])^2

I arrived at this idea by considering that the probability is similar to the standard deviation which is the square root of the variance so since:
Var[E_{\text{val}}(g^-)] = \frac{1}{K}Var_{x}[e(g^-(x),y)] and P[{g^-(x)}\neq{y}] = P[e(g^-(x),y)] does Var_{x}[e(g^-(x),y)] = P[{g^-(x)}\neq{y}]^2 ???

Then for part (c) on the exercise, assuming that the above is true, I used the notion that P[{g^-(x)}\neq{y}] \le 0.5 because if the probability of error were greater than 0.5 then the learned g would just flip its classification. Therefore this shows that for any g^- in a classification problem,
Var[E_{\text{val}}(g^-)] \le \frac{1}{K}0.5^2 and therefore:
Var[E_{\text{val}}(g^-)] \le \frac{1}{4K}

Any indication as to whether I'm working along the correct lines would be appreciated!

magdon 10-25-2013 07:16 AM

Re: Exercise 4.7
 
Quote:

Originally Posted by Sweater Monkey (Post 11588)
I feel like I'm overthinking Exercise 4.7 (b) and I am hoping for a little bit of insight.

My gut instinct says that Var[E_{\text{val}}(g^-)] = \frac{1}{K} (P[g^-(x),y])^2

Var[E_{\text{val}}(g^-)] can be obtained from part (a) by computing \sigma^2(g^-), which is the variance (over x) of the error that the hypothesis makes. For the specific error measure, the error is bounded between [0,1], so you can bound this variance.

ntvy95 04-06-2016 02:51 AM

Re: Exercise 4.7
 
Hello, I'm currently stuck at (d). I have derived to this point:

Var_{x}[(g^{-}(x) - y)^{2}] = E[((g^{-}(x) - y)^{2} - E[(g^{-}(x) - y)^{2}])^{2}]
E[((g^{-}(x) - y)^{2} - E[(g^{-}(x) - y)^{2}])^{2}] = E[(g^{-}(x) - y)^{4}] - (E[(g^{-}(x) - y)^{2}])^{2}

and I'm currently stuck. The hint says that the squared error is unbounded hence I guess that there should be no bound for expected value of squared error? :clueless: (I'm not good at math though...)

ntvy95 07-19-2016 08:58 AM

Re: Exercise 4.7
 
I'm not sure if I can re-interpret the Figure 4.8 like this: If you train your data with one horrible hypothesis you will get a very bad generalization bound despite the number of data points is large? :confused:


All times are GMT -7. The time now is 10:49 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.