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.8 (http://book.caltech.edu/bookforum/showthread.php?t=2053)

axelrv 10-10-2012 08:46 AM
Problem 2.8
 
I thought that growth functions could take on any polynomial function of N, so why is 1 + N + N(N-1)(N-2) / 6 not a possible growth function?

magdon 10-10-2012 08:52 AM
Re: Problem 2.8
 
The growth function cannot be any polynomial function of N. A valid growth function must satisfy the following theorem:

Theorem: If m(k)<2^k for some (any) k, then for all N, m(N)\le N^{k-1}+1.

In your example growth function below, try k=2 to show that the precondition of the theorem is satisfied with k=2 and hence deduce a linear bound on m(N). This contradicts the growth function being cubic. More generally, a cubic growth function cannot have a break point less than 4.

Quote:
Originally Posted by axelrv (Post 6247)
I thought that growth functions could take on any polynomial function of N, so why is 1 + N + N(N-1)(N-2) / 6 not a possible growth function?

axelrv 10-10-2012 01:44 PM
Re: Problem 2.8
 
thanks!

k_sze 03-21-2018 10:15 AM
Re: Problem 2.8
 
Quote:
Originally Posted by magdon (Post 6249)
The growth function cannot be any polynomial function of N. A valid growth function must satisfy the following theorem:

Theorem: If m(k)<2^k for some (any) k, then for all N, m(N)\le N^{k-1}+1.

In your example growth function below, try k=2 to show that the precondition of the theorem is satisfied with k=2 and hence deduce a linear bound on m(N). This contradicts the growth function being cubic. More generally, a cubic growth function cannot have a break point less than 4.
To show that a growth function is invalid, is it sufficient to do this?
  1. Determine the smallest k where m_\mathcal{H}(k+1) < 2^{k+1}, such that k would be our d_{\text{vc}} if the growth function were valid;
  2. Find any concrete value of N where one of the inequalities vs m_\mathcal{H}(N) is violated.

htlin 03-22-2018 03:08 AM
Re: Problem 2.8
 
Quote:
Originally Posted by k_sze (Post 12971)
To show that a growth function is invalid, is it sufficient to do this?
  1. Determine the smallest k where m_\mathcal{H}(k+1) < 2^{k+1}, such that k would be our d_{\text{vc}} if the growth function were valid;
  2. Find any concrete value of N where one of the inequalities vs m_\mathcal{H}(N) is violated.
Sounds reasonable to me.


All times are GMT -7. The time now is 01:14 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.