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 07: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 07: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 for some (any) , then for all N, .

In your example growth function below, try to show that the precondition of the theorem is satisfied with 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 12:44 PM

Re: Problem 2.8

thanks!

 k_sze 03-21-2018 09: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 for some (any) , then for all N, . In your example growth function below, try to show that the precondition of the theorem is satisfied with 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 where , such that would be our if the growth function were valid;
2. Find any concrete value of where one of the inequalities vs is violated.

 htlin 03-22-2018 02: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?Determine the smallest where , such that would be our if the growth function were valid; Find any concrete value of where one of the inequalities vs is violated.
Sounds reasonable to me.

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