We provide some theoretical results on sample complexity of PAC learning when the hypotheses are given by subsymbolical devices such as neural networks. In this framework we give new foundations to the notion of degrees of freedom of a statistic and relate it to the complexity of a concept class. Thus, for a given concept class and a given sample size, we discuss the efficiency of subsymbolical learning algorithms in terms of degrees of freedom of the computed statistic. In this setting we appraise the sample complexity overhead coming from relying on approximate hypotheses and display an increase in the degrees of freedom yield by embedding available formal knowledge into the algorithm. For known sample distribution, these quantities are related to the learning approximation goal and a special production prize is shown. Finally, we prove that testing the approximation capability of a neural network generally demands smaller sample size than training it.
Gaining degrees of freedom in subsymbolic learning / B. Apolloni, D. Malchiodi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 255:1-2(2001 Mar), pp. 295-321.
|Titolo:||Gaining degrees of freedom in subsymbolic learning|
APOLLONI, BRUNO (Primo)
MALCHIODI, DARIO (Ultimo)
|Parole Chiave:||Computational learning ; sentry functions ; nested concept classes ; approximate learning ; neural networks|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||mar-2001|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/S0304-3975(99)00289-3|
|Appare nelle tipologie:||01 - Articolo su periodico|