PAC learning with generalized samples and an application to stochastic geometry
Sanjeev R. Kulkarni, John N. Tsitsiklis, Sanjoy K. Mitter, Ofer Zeitouni · 1992
In this paper, we introduce an extension of the standard PAC learning model which allows the use of generalized samples. We view a generalized sample 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. We consider a specific application of the model to a problem of curve reconstruction, and discuss some connections with a result from stochastic geometry.