On the Learnability of Rich Function Classes
作者:
Highlights:
•
摘要
The probably approximately correct (PAC) model of learning and its extension to real-valued function classes sets a rigorous framework based upon which the complexity of learning a target from a function class using a finite sample can be computed. There is one main restriction, however, that the function class have a finite VC-dimension or scale-sensitive pseudo-dimension. In this paper we present an extension of the PAC framework with which rich function classes with possibly infinite pseudo-dimension may be learned with a finite number of examples and a finite amount of partial information. As an example we consider learning a family of infinite dimensional Sobolev classes.
论文关键词:PAC learning,computational learning theory,information-based complexity,VC-theory,approximation theory,partial information
论文评审过程:Available online 25 May 2002.
论文官网地址:https://doi.org/10.1006/jcss.1998.1604