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)
-   -   Positive intervals (http://book.caltech.edu/bookforum/showthread.php?t=928)

jianpan 07-29-2012 10:17 AM

Positive intervals
 
On book page 44, the growth function of positive intervals is defined as 2C(N+1). This is the fomular of selection without replacement, which implies we can't pick the same interval twice. But the book says " if the both end values fall in the same region, ....", which means we do allow to pick the same interval twice. If that's case, we should use selection with replacement N^2 in this case. This doesn't change the order of polynomial, but seems more rigorous.

htlin 07-29-2012 03:09 PM

Re: Positive intervals
 
Quote:

Originally Posted by jianpan (Post 3732)
On book page 44, the growth function of positive intervals is defined as 2C(N+1). This is the fomular of selection without replacement, which implies we can't pick the same interval twice. But the book says " if the both end values fall in the same region, ....", which means we do allow to pick the same interval twice. If that's case, we should use selection with replacement N^2 in this case. This doesn't change the order of polynomial, but seems more rigorous.

The "if ..." part contributes to a single (constant) dichotomy, while the "selection without replacement" part contributes to C(N+1, 2) different dichotomies. If we directly use "selection with replacement" for counting the number of dichotomies, it would be an over-estimate of the growth function. Hope this helps.


All times are GMT -7. The time now is 06:10 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, 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.