LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)
-   -   *ANSWER* q5 (http://book.caltech.edu/bookforum/showthread.php?t=4230)

OlivierB 04-21-2013 02:55 PM

*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.

yaser 04-21-2013 03:50 PM

Re: *answer* q5
 
Quote:

Originally Posted by OlivierB (Post 10539)
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.

OlivierB 04-21-2013 05:58 PM

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.

yaser 04-21-2013 09:06 PM

Re: *ANSWER* q5
 
Quote:

Originally Posted by OlivierB (Post 10542)
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!

GB449 09-07-2013 03:59 PM

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.

GB449 09-07-2013 04:17 PM

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.

yaser 09-09-2013 05:09 PM

Re: *ANSWER* q5
 
Quote:

Originally Posted by GB449 (Post 11470)
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!


All times are GMT -7. The time now is 12:36 PM.

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.