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 12: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 06:29 AM

Re: Exercise 2.2 (b)

 chemistry21 01-27-2018 10:08 AM

Re: Exercise 2.2 (b)

I thinke your undrestanding is correct.
------------------------------
my weblog: سئو وب سایت

 subbupd 02-13-2018 09:02 PM

Re: Exercise 2.2 (b)

m_H(N) = 2^k - This is perfect

 All times are GMT -7. The time now is 12:28 AM.