LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)
-   -   Growth Function division into S1 and S2 (http://book.caltech.edu/bookforum/showthread.php?t=3807)

udaykamath 01-03-2013 01:10 PM

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!

yaser 01-03-2013 04:02 PM

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.

udaykamath 01-04-2013 03:03 AM

Re: Growth Function division into S1 and S2
Thanks Dr Yaser that makes it more clear!

All times are GMT -7. The time now is 07:33 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.