LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 3

Reply
 
Thread Tools Display Modes
  #1  
Old 04-21-2013, 02:55 PM
OlivierB OlivierB is offline
Member
 
Join Date: Apr 2013
Location: Paris
Posts: 16
Default *ANSWER* q5

I see why i, ii, v are possible formulae for growth functions: We have seen examples in class.

But I don't see why iii and iv are not possible formulae for growth functions too, since both this quantities are smaller than the maximum i.e. 2^N (obviously in the case of iv for all N; and in the case of iii for N large - ok, I have not checked for all N).

Of course I would have a hard time coming up with a H that has exactly one of these growth functions, but why would that be impossible ? How can we be sure that no H can have that sort of growth function ?
I must have missed something..

Even if this type of consideration has little practical consequences, I would be interested to know.
Reply With Quote
  #2  
Old 04-21-2013, 03:50 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: *answer* q5

Quote:
Originally Posted by OlivierB View Post
I would have a hard time coming up with a H that has exactly one of these growth functions, but why would that be impossible ? How can we be sure that no H can have that sort of growth function ?
Hi,

The reason is that we proved that the growth function is either identically 2^N or else it has to be bounded above by a polynomial. The two excluded cases are faster than any polynomial, but still short of 2^N.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 04-21-2013, 05:58 PM
OlivierB OlivierB is offline
Member
 
Join Date: Apr 2013
Location: Paris
Posts: 16
Default Re: *ANSWER* q5

Argh !!
And you spent the whole of lecture 6 showing it !
And I followed..

Thank you for repeating !
It helps me learn..

By the way, I received the book and so far it is very good.
Reply With Quote
  #4  
Old 04-21-2013, 09:06 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: *ANSWER* q5

Quote:
Originally Posted by OlivierB View Post
Argh !!
And you spent the whole of lecture 6 showing it !
And I followed..

Thank you for repeating !
It helps me learn..

By the way, I received the book and so far it is very good.
Enjoy!
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #5  
Old 09-07-2013, 03:59 PM
GB449 GB449 is offline
Member
 
Join Date: Aug 2013
Posts: 20
Default Re: *ANSWER* q5

Is the following solution also correct?

(iii) cannot be a growth function. For N=1, the formula gives the growth function = 1. This means that the max number of dichotomies for a single point x, is 1 which implies for a given point x, the number of dichotomies is 1 which means h(x) is the same for all h. Now take any two points, x & y, (h(x), h(y)) will be the same for all h (because h(x) is the same for all h and h(y) is the same for all h). The number of dichotomies for a given x & y is therefore 1 so the max number of dichotomies as we vary x & y over X is also 1. But substituting N=2 in the formula gives 2.

If the above is true, the same logic can be applied to prove (iv) also cannot be a growth function.
Reply With Quote
  #6  
Old 09-07-2013, 04:17 PM
GB449 GB449 is offline
Member
 
Join Date: Aug 2013
Posts: 20
Default Re: *ANSWER* q5

Is the following solution also correct?

(iv) cannot be a growth function because for N=1, growth function according to the formula is 1. This means the number max number of dichotomies for all x is 1. Which implies for a given x the number of dichotomies is 1. Which implies for a given x, h(x) is the same for all h. Therefore for a given x & y, (h(x), h(y)) is the same for all h i.e. the cardinality of the dichotomy for any pair of values is 1 and hence the max. cardinality as we vary x & y is also 1. But substituting N = 2 in the formula gives the growth function = 2.

If the above is correct, then the same logic can be applied to determine (iii) also cannot be a growth function because, based on the formula, growth function for N=1 is 1 and for N=2, it is 2.
Reply With Quote
  #7  
Old 09-09-2013, 05:09 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: *ANSWER* q5

Quote:
Originally Posted by GB449 View Post
Is the following solution also correct?

(iii) cannot be a growth function. For N=1, the formula gives the growth function = 1. This means that the max number of dichotomies for a single point x, is 1 which implies for a given point x, the number of dichotomies is 1 which means h(x) is the same for all h. Now take any two points, x & y, (h(x), h(y)) will be the same for all h (because h(x) is the same for all h and h(y) is the same for all h). The number of dichotomies for a given x & y is therefore 1 so the max number of dichotomies as we vary x & y over X is also 1. But substituting N=2 in the formula gives 2.

If the above is true, the same logic can be applied to prove (iv) also cannot be a growth function.
Hi,

I am traveling and I only have primitive Internet access so I don't have the homework with me, but your argument sounds correct!
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -7. The time now is 10:48 AM.


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