Learning with prior information

In this paper, a new notion of learnability is introduced, referred to as l earnability with prior information (w.p.i.). This notion is weaker than the standard notion of probably approximately correct (PAC) learnability which has been much studied during recent years. A property called "dispersabili ty" is introduced, and it is shown that dispersability plays a key role in the study of learnability w.p.i. Specifically, dispersability of a function class is always a sufficient condition for the function class to be learna ble; moreover, in the case of concept classes, dispersability is also a nec essary condition for learnability w.p.i. Thus in the case of learnability w .p.i., the dispersability property plays a role similar to the finite metri c entropy condition in the case of PAC learnability with a fixed distributi on. Next, the notion of learnability w.p.i. is extended to the distribution -free (d.f.) situation, and it is shown that a property called d.f. dispers ability (introduced here) is always a sufficient condition for d.f. learnab ility w.p.i., and is also a necessary condition for d.f. learnability in th e case of concept classes. The approach to learning introduced in the prese nt paper is believed to be significant in all problems where a nonlinear sy stem has to be designed based on data. This includes direct inverse control and system identification.