View Single Post
  #5  
Old 04-23-2013, 03:39 AM
skwong skwong is offline
Member
 
Join Date: Apr 2013
Location: Hong Kong
Posts: 13
Default Re: slide #4 lecture 6 'Recursive Bound on B(N,k)'

Quote:
Originally Posted by yaser View Post
1) The total is indeed 14 for the matrix you constructed, and for the perceprton case. The maximum possible is 15, though (take all posible patterns of 4 bits except the all 0's, and you have a break point of 4). Since B(N,k) is an upper bound, there is no problem here.

2) In the matrix that excludes the all 0's, the set S_1 contains only the pattern 0001, so \alpha=1, while the set S_2 contains the remaining 14 patterns (excluding all 0's) so \beta=7.
Thanks for the reply. For the 1), I suspected that 14 is for perceptron and
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 k-2 column, for the N = 4, k = 4 case (and now
name this as half of S_2 with \beta=3 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 \alpha=8:

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
\sum\limits_{i=0}^{k-1} {N - 1 \choose i} + \sum\limits_{i=0}^{k-2} {N - 2 \choose i}

Then, obviously, when k = N, the B(N, k) will not be evaluated to
2^k - 1

Am I missing something ?
Reply With Quote