PAC learning with generalized samples and an application to stochastic geometry

ABSTRACT

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.

REFERENCES

• AR89: A.D. Alexandrov and Yu.G. Reshetnyak. G~r~aral Tt~aory of Irregular Curves. Kluwer Academic Publishers, 1989. Mathematics and Its Applications (Soviet Series) Vol. 29.
• BEHW86: A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
• BI88: Gyora M. Benedek , Alon Itai, Learnability by fixed distributions, Proceedings of the first annual workshop on Computational learning theory, p.80-90, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• Dud78: R.M. Dudley. Central limit theorems for empirical measures. Ann. Probability, 6:899-929, 1978.
• Hau90: David Haussler, DECISION THEORETIC GENERALIZATIONS OF THE PAC MODEL FORNEURAL NET AND OTHER LEARNING APPLICATIONS, University of California at Santa Cruz, Santa Cruz, CA, 1990
• Kar91: William Clement Karl , George C. Verghese, Reconstructing objects from projections, 1991
• Kul91: Sanjeev Ramesh Kulkarni, Problems of computational and information complexity in machine vision and learning, Massachusetts Institute of Technology, Cambridge, MA, 1992
• LKW90: A.S. Lele, S.R. Kulkarni, and A.S. Willsky. Convex set estimation from support line measurements and applications to target reconstruction from laser radar data. In SPIE Proc. Vol. 12~2, Laser Radar V, pages 58-82, 1990. To appear in J. Optical Soc. of Amer.
• Mor66: P.A.P. Moran. Measuring the length of a curve. Biometrika, 53:359-364, 1966.
• Pol84: D. Pollard. Convergence of Stochastic Processes. Sprlnger-Verlag, 1984.
• PW90: J. L. Prince , A. S. Willsky, Reconstructing Convex Sets from Support Line Measurements, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.4, p.377-389, April 1990 [doi>10.1109/34.50623]
• Ric92: T.J. Richardson. Forthcoming, 1992.
• San76: L.A. Santalo. Integral Geometry and Geometric Probability. Addison-Wesley, Reading, MA, 1976. Volume I of Encyclopedia of Mathematics and its Applications.
• Ski88: Steven Sol Skiena , Herbert Edelsbrunner, Geometric probing, 1988
• Ste54: H. Steinhaus. Length, shape, and area. Colloquium Mathematicum, 3:1-13, 1954.
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Vap82: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• VC71: V.N. Vapnik and A.Ya. Chervonenkis. On the uniform convergence of relative frequencies to their probabilities. Theory of Prob. and its Appl., 16:264-280, 1971.
• VC81: V.N. Vapnik and A.Ya. Chervonenkis. Necessary and sufficient conditions for the uniform convergence of means to their expecrations. Theory of Prob. and its Appl., 26:532-553, 1981.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.0 General

General Terms:
Theory, Verification