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(a + c) (http://book.caltech.edu/bookforum/showthread.php?t=4697)

zyteka 10-03-2016 04:15 PM

Problem 2.14(a + c)
I am having some difficulties working through problem 2.14

For a, I understand that the number of dichotomies that H can implement at most K times the number of hypothesis that H_1 can implement, which can implement N^(dvc + 1). I'm not sure how to relate this to the dvc(H).

For c, I can prove the first half of the min function using part a. For the second part of the min function, ( 7(dvc + K) log2 (dvcK) ), I plugged the function into the inequality in b, and simplified to get:
(dk)^(7(dvc+K)) > 2K(7(dvc + K) log(dvc K))^d

I am not sure how to proceed from here, and no simplifications I can do from here seem get closer to solving the inequality.

leezard87 10-03-2016 08:24 PM

Re: Problem 2.14(a + c)
For (a), if you set the break point to k*=dvc+1 for each hypothesis, it's obvious that dvc<k*. Then the upper bound of dvc for the union hypothesis set H is Kk*, meaning dvc < Kk*=K(dvc+1). This is my solution. I'm not 100% sure though.

For (c), I have the same confusion as you. I tried to simplify that inequality for a couple of hours and got nothing closer to the result. Hope someone could shed some light...

All times are GMT -7. The time now is 11:06 AM.

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.