Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 65:
=== Sample-complexity bounds ===
<div id='bounds'/>
Suppose <math>\mathcal H</math> is a class of binary functions. Then, <math>\mathcal H</math> is <math>(\epsilon,\delta)</math>-PAC-learnable with a sample of size:
<ref>{{Cite journal|title=The optimal sample complexity OF PAC learning
Line 75 ⟶ 76:
N = \Omega\bigg(\frac{VC(\mathcal H) + \ln{1\over \delta}}{\epsilon}\bigg)
</math>
Thus, the sample-complexity is a linear function of the [[VC dimension]] of the hypothesis space.
==Other Settings==
| |||