Nonuniform learnability

摘要

The learning model of Valiant is extended to allow the number of examples required for learning to depend on the particular concept to be learned, instead of requiring a uniform bound for all concepts of a concept class. This extension, called nonuniform learning, enables learning many concept classes not learnable by the previous definitions. Nonuniformly learnable concept classes are characterized. Some examples (Boolean formulae, recursive, and r.e. sets) are shown to be nonuniformly learnable by a polynomial (in the size of the representation of the concept and in the error parameters) number of examples, but not necessarily in polynomial time. Restricting the learning protocol such that the learner has to commit himself after a finite number of examples does not affect the concept classes which can be learned. An extension of nonuniform learnability to nonuniform learnability with respect to specific distributions is presented.