LFD Book Forum - View Single Post - slide #4 lecture 6 'Recursive Bound on B(N,k)'

skwong · #5 04-23-2013, 03:39 AM

Quote:

Originally Posted by yaser

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

is an upper bound, there is no problem here.

2) In the matrix that excludes the all 0's, the set

contains only the pattern 0001, so $\alpha=1$ , while the set

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

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

Am I missing something ?