We narrow the width of the confidence interval introduced by Vapnik and Chervonenkis for the risk function in PAC learning boolean functions through non-consistent hypotheses. To obtain this improvement for a large class of learning algorithms we introduce both a theoretical framework for statistical inference of functions and a concept class complexity index, the detail, that is dual to the Vapnik-Chervonenkis dimension. Detail of a class and maximum number of mislabelled points add up linearly to constitute the learning prob- lem complexity. The sample complexity dependency on this index is almost similar to the one on VC dimension. We formally prove that the former leads to confidence intervals for the risk function that are definitely narrower than in the latter.

Narrowing confidence interval width of PAC learning risk function by algorithmic inference / B. Apolloni, D. Malchiodi. ((Intervento presentato al 7. convegno International symposium on Artificial Intelligence and Mathematics tenutosi a Fort Lauderdale nel 2002.

Narrowing confidence interval width of PAC learning risk function by algorithmic inference

B. Apolloni
Primo
;
D. Malchiodi
Ultimo
2002

Abstract

We narrow the width of the confidence interval introduced by Vapnik and Chervonenkis for the risk function in PAC learning boolean functions through non-consistent hypotheses. To obtain this improvement for a large class of learning algorithms we introduce both a theoretical framework for statistical inference of functions and a concept class complexity index, the detail, that is dual to the Vapnik-Chervonenkis dimension. Detail of a class and maximum number of mislabelled points add up linearly to constitute the learning prob- lem complexity. The sample complexity dependency on this index is almost similar to the one on VC dimension. We formally prove that the former leads to confidence intervals for the risk function that are definitely narrower than in the latter.
Settore INF/01 - Informatica
http://rutcor.rutgers.edu/~amai/aimath02/PAPERS/18.ps
Narrowing confidence interval width of PAC learning risk function by algorithmic inference / B. Apolloni, D. Malchiodi. ((Intervento presentato al 7. convegno International symposium on Artificial Intelligence and Mathematics tenutosi a Fort Lauderdale nel 2002.
Conference Object
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/160340
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact