LFD Book Forum  

Go Back   LFD Book Forum > Book Feedback - Learning From Data > Chapter 2 - Training versus Testing

Thread Tools Display Modes
Old 01-03-2013, 12:10 PM
udaykamath udaykamath is offline
Junior Member
Join Date: Jan 2013
Posts: 9
Question Growth Function division into S1 and S2

I had one question on the book related to theory of generalization, where the dichotomies are "shuffled" in growth function. You mentioned that for (x1,x2....xn-1, xn) we take one of them in the S1 or alpha. How come then "two" of the patterns stay in S2, it should be either of the "unused" pattern that stay either of the Betas right?

For example (x1 x2 x3 x4) and lets take the pattern
1 1 1 1 (stays in alpha) we have only one remaining (1 1 1 -1) which will go to one of the betas, with -1 if we choose 1 (ending one) to go to alpha.

I understand the reformulation but the example given in lecture uses the same pattern (1 -1....1 1) and (1 -1....1 -1) to be in both betas, only 1 of them can be in any betas and the other one should be in the alpha, right?

Can you elaborate on this or clarify with example i have?
Thanks a ton!
Reply With Quote
Old 01-03-2013, 03:02 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Growth Function division into S1 and S2

A full dichotomy on all N points can have a "twin" dichotomy (also on all N points) that is identical to it except for the last bit, where it differs so one dichotomy ends with +1 and the other ends with -1. It is those "twin" dichotomies that end up in the set S_2 (both of them); the one ending with +1 goes to S_2^+ and the one ending with -1 goes to S_2^-. Each of S_2^+ and S_2^- has \beta elements, hence S_2 which is their union has 2\beta elements.

The dichotomies that do not have a "twin" are the ones that end up in S_1 and there are \alpha of them. Each dichotomy goes to one, and only one, of the sets S_1, S_2^+, S_2^-. I hope this clarifies the matter. Please feel free to ask further questions.
Where everyone thinks alike, no one thinks very much
Reply With Quote
Old 01-04-2013, 02:03 AM
udaykamath udaykamath is offline
Junior Member
Join Date: Jan 2013
Posts: 9
Default Re: Growth Function division into S1 and S2

Thanks Dr Yaser that makes it more clear!
Reply With Quote

Thread Tools
Display Modes

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 Jump

All times are GMT -7. The time now is 02:14 PM.

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. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.