PAC learning with generalized samples and an applicaiton to stochastic geometry
Sanjeev R. Kulkarni, Sanjoy K. Mitter, John N. Tsitsiklis, Ofer Zeitouni · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1993
An extension of the standard probably approximately correct (PAC) learning model that allows the use of generalized samples is introduced. A generalized sample is viewed as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. A specific application of the generalized model to a problem of curve reconstruction is considered, and some connections with a result from stochastic geometry are discussed.>