LFD Book Forum - Problem 2.14(c)

Page 1 of 2

Show 40 post(s) from this thread on one page

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 11: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 05: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)

BojanVujatovic

07-14-2014 06: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 09: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)

BojanVujatovic

07-20-2014 09:48 AM

Re: Problem 2.14(c)

Thank you for your reply!

zhaozb15

10-01-2015 08:46 AM

Re: Problem 2.14(c)

Quote:

Originally Posted by magdon (Post 11695)

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

ilson

10-06-2015 10: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

then $d_{\text{vc}}(\mathcal{H}) = d_{\text{vc}}$ trivially, so can we assume that $K\geq 2$ ?

magdon

10-07-2015 07:05 AM

Re: Problem 2.14(c)

Quote:

Originally Posted by ilson (Post 12085)

I came here to say exactly this. Also, if

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 11:59 AM

Re: Problem 2.14(c)

I'm pretty stuck on this one -- any hints?

ppaquay

05-21-2018 12:55 PM

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 03:50 PM.

Page 1 of 2

Show 40 post(s) from this thread on one page

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2021, 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.