Bounds on the number of examples needed for learning functions.
We prove general lower bounds on the number of examples needed for learning function classes within different natural learning models which are related to pac-learning (and coincide with the pac-learning model of Valiant in the case of {0,1}-valued functions. The lower bounds are obtained by showing...
| Pubblicato in: | SIAM journal on computing. 26, 3 (1997). |
|---|---|
| Autore principale: | |
| Natura: | Articolo |
| Lingua: | English |
| Soggetti: |