LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)
-   -   Problem 2.14(c) (http://book.caltech.edu/bookforum/showthread.php?t=1876)

mileschen 09-30-2012 10:50 PM

Problem 2.14(c)
 
For Problem 2.14(c), to determine the min value, the way I think would be try to solve the equation in (b) and get L. Maybe L is the second part of the min. However, how to solve the equation is a really hard question. Thus, could anyone tell me how to solve the equation or give me a hint on how to get the right answer?

magdon 10-01-2012 04:46 AM

Re: Problem 2.14(c)
 
Yes, solving the equation is really hard. It is simpler to show that if \ell takes on the value in the second part of the min, the condition in (b) is satisfied.
Quote:

Originally Posted by mileschen (Post 5971)
For Problem 2.14(c), to determine the min value, the way I think would be try to solve the equation in (b) and get L. Maybe L is the second part of the min. However, how to solve the equation is a really hard question. Thus, could anyone tell me how to solve the equation or give me a hint on how to get the right answer?


BojanVujatovic 07-14-2014 05:29 PM

Re: Problem 2.14(c)
 
Quote:

Originally Posted by magdon (Post 5975)
It is simpler to show that if \ell takes on the value in the second part of the min, the condition in (b) is satisfied.

I have difficulties solving this problem. If I assume that \ell=d_{VC} \log_2 d_{VC} + (d_{VC}+1) \log_2 K, then the condition in (b) 2^\ell>K\ell^{d_{VC}+1} is not satisfied.
(e.g. when d_{VC}=2, K=2, then \ell=5 and 2^5=32 \ngtr 2 \cdot 5^3=250).

I believe the right thing to do would be to assume that \ell \geq d_{VC} \log_2 d_{VC} + (d_{VC}+1) \log_2 K because the min bound will still hold and I believe the condition in (b) is then satisfied? But how do I prove that?

I appreciate any help.

magdon 07-17-2014 08:26 AM

Re: Problem 2.14(c)
 
There is a typo in the equation, sorry.

The second term in the minimum should be

7(d_{VC}+K)\log_2(d_{VC}K).

Rather than solve the inequality in (b) to get this bound, you may rather just verify that this is a bound by showing that if \ell=7(d_{VC}+K)\log_2(d_{VC}K), then the inequality in (b) is satisfied, namely 2^\ell>2K\ell^{d_{VC}}.

Quote:

Originally Posted by mileschen (Post 5971)
For Problem 2.14(c), to determine the min value, the way I think would be try to solve the equation in (b) and get L. Maybe L is the second part of the min. However, how to solve the equation is a really hard question. Thus, could anyone tell me how to solve the equation or give me a hint on how to get the right answer?


BojanVujatovic 07-20-2014 08:48 AM

Re: Problem 2.14(c)
 
Thank you for your reply!

zhaozb15 10-01-2015 07:46 AM

Re: Problem 2.14(c)
 
Quote:

Originally Posted by magdon (Post 11695)
There is a typo in the equation, sorry.

The second term in the minimum should be

7(d_{VC}+K)\log_2(d_{VC}K).

Rather than solve the inequality in (b) to get this bound, you may rather just verify that this is a bound by showing that if \ell=7(d_{VC}+K)\log_2(d_{VC}K), then the inequality in (b) is satisfied, namely 2^\ell>2K\ell^{d_{VC}}.

If d_{VC}=K=1, then 7(d_{VC}+K)\log_2(d_{VC}K)=0. Seems not correct

ilson 10-06-2015 09:15 PM

Re: Problem 2.14(c)
 
Quote:

Originally Posted by zhaozb15 (Post 12077)
If d_{VC}=K=1, then 7(d_{VC}+K)\log_2(d_{VC}K)=0. Seems not correct

I came here to say exactly this. Also, if K=1 then d_{\text{vc}}(\mathcal{H}) = d_{\text{vc}} trivially, so can we assume that K\geq 2?

magdon 10-07-2015 06:05 AM

Re: Problem 2.14(c)
 
Quote:

Originally Posted by ilson (Post 12085)
I came here to say exactly this. Also, if K=1 then d_{\text{vc}}(\mathcal{H}) = d_{\text{vc}} trivially, so can we assume that K\geq 2?

Yes, the problem should state that K>1, otherwise the problem is trivial.

RicLouRiv 07-12-2017 10:59 AM

Re: Problem 2.14(c)
 
I'm pretty stuck on this one -- any hints?

ppaquay 05-21-2018 11:55 AM

Re: Problem 2.14(c)
 
Hi, I'm also stuck on this one. I don't know if I'm missing an algebraic argument (in verifying that 2^l > 2Kl^d) or if I'm missing something more important. Any hint would be appreciated.


All times are GMT -7. The time now is 01:16 AM.

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.