LFD Book Forum Page 47 / Lecture 6 (10 min) Partitioning the table
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
04-20-2013, 07:44 PM
 markact Junior Member Join Date: Apr 2013 Posts: 3
Page 47 / Lecture 6 (10 min) Partitioning the table

I am struggling with one of more simpler bits of chapter 2.

On page 47 (Lecture 6 - 9 ~ 12 mins), I do not understanding how the table is constructed.

"Some dichotomies on these N-1 points appear only once" Okay, so to me, this implies we have 2^(n-1) rows for the first set (S1).

"The remaining dichotomies on the first n-1 appear twice, once with +1 and once with -1" How can this be true...?

To me, "the remaining dichotomies on the first n-1" would mean (2^n) less (2^n-1) = 2^n-1. But these appear twice! So we have 2*(2^n-1) = 2^n for set S2.

This seems as though we are counting twice.

S1 = 2^n-1
S2 = 2^n

The total of S1 + S2 is greater than 2^n.

Surely, I must be missing something really simple here. But what...? Please help.

Thanks,

Mark
#2
04-20-2013, 09:06 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: Page 47 / Lecture 6 (10 min) Partitioning the table

Quote:
 Originally Posted by markact "Some dichotomies on these N-1 points appear only once" Okay, so to me, this implies we have 2^(n-1) rows for the first set (S1).
At most since it's not necessary that all of them are there. The fact that there may be that many does not play a role in the argument.

Quote:
 "The remaining dichotomies on the first n-1 appear twice, once with +1 and once with -1" How can this be true...?
The and are the entries in the last () column. The dichotomies on the first columns appear twice as they appear once with and once with in the last column.
__________________
Where everyone thinks alike, no one thinks very much
#3
04-20-2013, 10:56 PM
 markact Junior Member Join Date: Apr 2013 Posts: 3
Re: Page 47 / Lecture 6 (10 min) Partitioning the table

Thank you very much for replying.

I read the answers and think that I understand the points being made in regards to the maximum being 2^(n-1).

But on reflection, perhaps my misunderstanding could have been expressed more clearly. So, I am sorry about the following tables, but perhaps these help to demonstrate what I am missing in regards to partitioning the original set into 3 disjoint sets.

The following assumes a space of 4 points - a maximum of 16 dichotomies. I have labelled each row with its base 10 equivalence.

Here is alpha (N-1 appears once, with XN either 1 or 0)

X1 X2 X3 XN ID
0 0 0 0 0
0 0 1 1 3
0 1 0 0 4
0 1 1 1 7
1 0 0 0 8
1 0 1 1 11
1 1 0 0 12
1 1 1 1 15

We are left with 8 rows remaining If these have XN being either 1 or -1, then these 8 rows are split into the following two partitions (S2+ and S2-).

[S2+]
X1 X2 X3 XN ID
0 0 0 1 1
0 1 0 1 5
1 0 0 1 9
1 1 0 1 13

[S2-]
X1 X2 X3 XN ID
0 0 1 0 2
0 1 1 0 6
1 0 1 0 10
1 1 1 0 14

So, given the partitions above, I seem to get that X1, X2 appears twice but this is not N-1 appearing twice (i.e. X1, X2, X3).

I understand we are attempting to describe situations were there is a break point and all the combinations listed above will not exist.

But given the instructions in the book and using a nice-and-neat 2n construction, I do not understand how the exhaustive and exclusive 3 sets are derived.

Mark
#4
04-20-2013, 11:36 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: Page 47 / Lecture 6 (10 min) Partitioning the table

Quote:
 Originally Posted by markact these help to demonstrate what I am missing in regards to partitioning the original set into 3 disjoint sets. The following assumes a space of 4 points - a maximum of 16 dichotomies. I have labelled each row with its base 10 equivalence. Here is alpha (N-1 appears once, with XN either 1 or 0) X1 X2 X3 XN ID 0 0 0 0 0 0 0 1 1 3 0 1 0 0 4 0 1 1 1 7 1 0 0 0 8 1 0 1 1 11 1 1 0 0 12 1 1 1 1 15 We are left with 8 rows remaining If these have XN being either 1 or -1, then these 8 rows are split into the following two partitions (S2+ and S2-). [S2+] X1 X2 X3 XN ID 0 0 0 1 1 0 1 0 1 5 1 0 0 1 9 1 1 0 1 13 [S2-] X1 X2 X3 XN ID 0 0 1 0 2 0 1 1 0 6 1 0 1 0 10 1 1 1 0 14
Thank you for the detailed example. I can now see where the misunderstanding is. The set contains all the patterns that appear once, and none of the patterns that appear twice, of the original matrix. Therefore, if all the above patterns are indeed in that matrix, then the decimal pattern 0 should not be in since the decimal pattern 1 makes that pattern appear twice (on the first 3 columns). Similarly, the set contains all patterns that appear twice, and none that appear once.
__________________
Where everyone thinks alike, no one thinks very much
#5
04-21-2013, 02:00 AM
 markact Junior Member Join Date: Apr 2013 Posts: 3
Re: Page 47 / Lecture 6 (10 min) Partitioning the table

Got it!!

Thank you very much for your patience.

 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 09:23 PM.

 Contact Us - LFD Book - Top