Name
Abstract | ||
|---|---|---|
In this paper we prove various results about PAC learning in the presence of malicious and random classification noise. Our main theme is the use of randomized hypotheses for learning with small sample sizes and high malicious noise rates. We show an algorithm that PAC learns any target class of VC-dimension d using randomized hypotheses and order of d/ε training examples (up to logarithmic factors) while tolerating malicious noise rates even slightly larger than the information-theoretic bound ε/(1+ε) for deterministic hypotheses. Combined with previous results, this implies that a lower bound d/Δ+ε/Δ2 on the sample size, where η=ε/(l+ε)−Δ is the malicious noise rate, applies only when using deterministic hypotheses. We then show that the information-theoretic upper bound on the noise rate for deterministic hypotheses can be replaced by 2ε/(l+2ε) if randomized hypotheses are used. Investigating further the use of randomized hypotheses, we show a strategy for learning the powerset of d elements using an optimal sample size of order dε/Δ2 (up to logarithmic factors) and tolerating a noise rate η=2ε/(l+2ε)−Δ. We complement this result by proving that this sample size is also necessary for any class |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/3-540-62685-9_11 | EuroCOLT |
Keywords | Field | DocType |
minimum disagreement hypotheses,randomized hypotheses,vc dimension,upper bound,lower bound,sample size,pac learning | Discrete mathematics,Combinatorics,Upper and lower bounds,Artificial intelligence,Logarithm,Sample size determination,Machine learning,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-62685-9 | 1 | 0.41 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolò Cesa-Bianchi | 1 | 4609 | 590.83 |
| Paul Fischer | 2 | 1694 | 118.39 |
| Eli Shamir | 3 | 835 | 157.77 |
| Hans-Ulrich Simon | 4 | 567 | 104.52 |