*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. 
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. 
Re: *ANSWER* q5
Quote:

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. 
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. 
Re: *ANSWER* q5
Quote:
I am traveling and I only have primitive Internet access so I don't have the homework with me, but your argument sounds correct! 
Re: *ANSWER* q5
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. 
All times are GMT 7. The time now is 12:38 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. AbuMostafa, Malik MagdonIsmail, and HsuanTien Lin, and participants in the Learning From Data MOOC by Yaser S. AbuMostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.