Timeline for The VC dimension when the samples are fixed
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 31, 2016 at 16:08 | vote | accept | Erel Segal-Halevi | ||
| Jul 31, 2016 at 1:47 | history | tweeted | twitter.com/StackCompSci/status/759566127072706560 | ||
| Jul 30, 2016 at 22:52 | answer | added | Ariel | timeline score: 2 | |
| Jul 30, 2016 at 21:38 | comment | added | Erel Segal-Halevi | @Ariel I did not understand the last inequality in your comment. Can you please expand? (maybe as an answer) | |
| Jul 20, 2016 at 20:13 | comment | added | Ariel | Suppose you're in the realizable model, i.e. you want to learn some $f^*\in \mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$. Let $T$ be your training set obtained in the halving procedure, then you wish to bound $\Pr\left(h(x)\neq f^*(x) | x\notin T\right)$, where $h$ is the hypothesis which minimizes the empirical error. But $\Pr\left(h(x)\neq f^*(x) | x\notin T\right) = 2\Pr_{x\sim \mathcal{D}}\left(h(x)\neq f^*(x)\right)=2err(h)$, so you can still use the usual bound (with the extra $2$ factor). | |
| Jul 20, 2016 at 13:34 | comment | added | Erel Segal-Halevi | @Ariel in the original setting, the training samples and the test samples are independent. In the halving procedure, the two halves are dependent. As an example, suppose there is a total of 1000 samples, one of the samples is X and the other 999 samples are Y. If you treat it as a finite support distribution, there is a chance of 0.001 that X will be in the train set and an independent chance of 0.001 that X will be in the test set, so there is positive chance to see X in both sets. In the halving procedure, there is 0 chance to see X twice. | |
| Jul 19, 2016 at 20:30 | comment | added | Ariel | maybe i don't understand your setting, but we have (for finite VC dimension), a bound on the error in terms of the number of samples, which holds for any distribution $\mathcal{D}$. Isn't your case simply taking a distribution with finite support $S\subseteq \mathcal{X}$ (sample space), and asking what is the error when the number of samples is greater than $|S|/2$? | |
| Jul 19, 2016 at 19:37 | history | asked | Erel Segal-Halevi | CC BY-SA 3.0 |