PAC LEARNING WITH GENERALIZED SAMPLES AND AN APPLICATION TO STOCHASTIC GEOMETRY

In this paper, we introduce an extension of the standard probably appr oximately correct (PAC) learning model, which allows the use of genera lized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by th e functional operating on the unknown concept. It appears that this mo del can be applied to a number of problems in signal processing and ge ometric reconstruction to provide sample size bounds under a PAC crite rion. We consider a specific application of the generalized model to a problem of curve reconstruction and discuss some connections with a r esult from stochastic geometry.