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)
-   -   Exercise 2.2 (b) (http://book.caltech.edu/bookforum/showthread.php?t=4783)

mauriciogruppi 09-25-2017 01:37 PM

Exercise 2.2 (b)
The question is asking if there is a hypothesis set for which m_H(N) = N + 2^floor(N/2).

Theorem 2.4 states that m_H(N) <= sum{0 to k-1} (N choose i) if k is a breakpoint.

My understanding is that m_H(N) = 2^k or it is bounded by a polynomial.

However, the given growth function m_H(N) = N + 2^floor(N/2) seems exponential because of 2^(N/2). Therefore my answer is NO, it does not make sense to look for such hypothesis set.

Can someone clarify if this is correct?

Edit: Indeed, it is possible to show that m_H(N) is not bounded by a polynomial.

htlin 09-27-2017 07:29 AM

Re: Exercise 2.2 (b)
Your understanding seems very reasonable!

subbupd 02-13-2018 10:02 PM

Re: Exercise 2.2 (b)
m_H(N) = 2^k - This is perfect

All times are GMT -7. The time now is 05:17 AM.

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