slide #4 lecture 6 'Recursive Bound on B(N,k)'
I have difficulty in understanding this. I tried to think about it by using
numerical example, say with the Perception, k = 4; and using N = 4 (0 = 1, 1 = +1). Say, for alpha, I ignore x4 (don't care terms), then I can list all 8 combination of x1 to x3; when x4 is 0, then only 3 case works; and the opposite is same. Therefore, I can come up with following: x1 x2 x3  x4 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 #1 0 1 0 (that should be left out) 1 1 0 0 1 1 1 1 1 0 0 1 #0 1 0 1 (that should be left out) 0 0 1 1 Then, I found that I misunderstood. Because: 1) The total is 14 (which matches with what was found in previous lecture), but does not match with the B(N, k) calculation result of 15. 2) According to the numerical table in slide 8/18, the beta is 7, alpha should be 1. I try to list them out like the above, but cannot know which 7 combination to pick for beta rows, because I think I need to kick out the 1010 and 0101 pattern. But then the 2 sections of beta in the table will not be same for the x1 to x3. Therefore, I actually do not understand it. Can you please enlighten me ? Thanks in advance. SK 
Re: slide #4 lecture 6 'Recursive Bound on B(N,k)'

Re: slide #4 lecture 6 'Recursive Bound on B(N,k)'
I should perhaps explain the thinking behind my last post on the general bounds on the variation of growth functions (so someone can check it :) ). The minimum number of dichotomies on a set of points where is given by the fact that we know some set of points is shattered, and we can extend such a shattering in a minimal way to the whole set of points in a way that excludes all other points. This makes the growth function constant for all .
I believe all the possible values of the growth function between this minimum and the bound B(N, k) can occur for some carefully chosen hypothesis set, but haven't actually proved it. Is this so? 
Re: slide #4 lecture 6 'Recursive Bound on B(N,k)'
Quote:
15 is upper bound and do no harm. That confirmed my thought. For the original subject, I did not understand. After repeatedly watching the video and thinking, I eventually understood the motive and reasoning behind. But then my question is, would it be possible to think it the other way: First group the rows with k2 column, for the N = 4, k = 4 case (and now name this as half of with rows: 0 1 1 0 1 0 1 0 1 1 0 0 Then, make the complementary 1 0 0 1 0 1 0 1 0 0 1 1 And let the remaining as : 0 0 0 x 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 x And the calculation will be Then, obviously, when k = N, the B(N, k) will not be evaluated to Am I missing something ? 
Re: slide #4 lecture 6 'Recursive Bound on B(N,k)'
Quote:

All times are GMT 7. The time now is 05:05 PM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2020, 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.