5,321
edits
Machine Learning: Difference between revisions
→Sauer's Lemma
| Line 205: | Line 205: | ||
* If <math>m \leq VCdim(H)</math>, then <math>\tau_H(m) = 2^m</math> | * If <math>m \leq VCdim(H)</math>, then <math>\tau_H(m) = 2^m</math> | ||
====Sauer's Lemma==== | ====Sauer's Lemma==== | ||
[https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf Reference]<br> | |||
After the VCdim, the growth function grows as a polynomial | |||
* If <math>VCdim(H)\leq d \leq \infty</math> then <math>\tau_H(m) \leq \sum_{i=0}^{d} \binom{n}{i}</math> | |||
* Also if <math>m > d+1</math> then <math>\tau_H(m) \leq (\frac{em}{d})^d</math>. | |||
===Bias-Variance Tradeoff=== | ===Bias-Variance Tradeoff=== | ||