Exercise 4.7

Sweater Monkey · #1 10-23-2013, 12:15 PM

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

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 · #2 10-25-2013, 08:16 AM

Quote:

Originally Posted by Sweater Monkey

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 · #3 04-06-2016, 03:51 AM

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?

(I'm not good at math though...)

ntvy95 · #4 07-19-2016, 09:58 AM

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?

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode