LFD Book Forum *ANSWER* q5
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
04-21-2013, 02:55 PM
 OlivierB Member Join Date: Apr 2013 Location: Paris Posts: 16

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.
#2
04-21-2013, 03:50 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478

Quote:
 Originally Posted by OlivierB 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 or else it has to be bounded above by a polynomial. The two excluded cases are faster than any polynomial, but still short of .
__________________
Where everyone thinks alike, no one thinks very much
#3
04-21-2013, 05:58 PM
 OlivierB Member Join Date: Apr 2013 Location: Paris Posts: 16

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.
#4
04-21-2013, 09:06 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478

Quote:
 Originally Posted by OlivierB 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
#5
09-07-2013, 03:59 PM
 GB449 Member Join Date: Aug 2013 Posts: 20

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.
#6
09-07-2013, 04:17 PM
 GB449 Member Join Date: Aug 2013 Posts: 20

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.
#7
09-09-2013, 05:09 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478

Quote:
 Originally Posted by GB449 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
#8
10-19-2021, 06:40 AM
 noslen Junior Member Join Date: Oct 2021 Posts: 1

I'm having a hard time proving that functions iii) and iv) are not bounded by any polynomial in N (any idea or suggestion, would be appreciated). I found a very similar solution (I would like to know if it is correct):

If there exist a finite breakpoint k, then
(a) m_H(N) = 2^N for all N<k, and m_H(N) < 2^N for all N>=k
otherwise,
(b) m_H(N) = 2^N for all N

Functions iii) and iv) do not satisfy (b), so there must exist a finite k>=1 such that (a) is satisfied. Whatever this k be, we can check that for k>1, (a) is violated for N=1. And for k = 1 we must have a constant growth function, which is also not satisfied.

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 11:00 AM.

 Contact Us - LFD Book - Top