Fat-shattering and the learnability of real-valued functions

ABSTRACT

We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide characterizations of the learnability of a real-valued function class in terms of a generalization of the Vapnik-Chervonenkis dimension, the fat shattering function, introduced by Kearns and Schapire. We show that, given some restrictions on the noise, a function class is learnable in our model if and only if its fat-shattering function is finite. With different (also quite mild) restrictions, satisfied for example by gaussian noise, we show that a function class is learnable from polynomially many examples if and only if its fat-shattering function grows polynomially. We prove analogous results in an agnostic setting, where there is no assumption of an underlying function class.

REFERENCES

• 1: N. ALON, S. BEN-DAVID, N. CESA-BIANCHI AND D. HAUS- SLER, Scale-sensitive dimensions, uniform convergence, and learnability, Symposium on Foundations of Computer Science, 1993.
• 2: D. ANGLUIN AND L. G. VALIANT, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Journal of Computer and System Sciences, 18 (1979), pp. 155-193.
• 3: Martin Anthony , John Shawe-Taylor, Valid generalisation of functions from close approximations on a sample, Proceedings of the first European conference on Computational learning theory, p.95-108, October 1994, Royal Holloway, Univ. of London, United Kingdom
• 4: Peter Auer , Philip M. Long , Wolfgang Maass , Gerhard J. Woeginger, On the complexity of function learning, Proceedings of the sixth annual conference on Computational learning theory, p.392-401, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168384]
• 5: Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195152]
• 6: Peter L. Bartlett, Learning with a slowly changing distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.243-252, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130412]
• 7: Shai Ben-David , Nicolò Cesa-Bianchi , Philip M. Long, Characterizations of learnability for classes of {O, …, n}-valued functions, Proceedings of the fifth annual workshop on Computational learning theory, p.333-340, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130423]
• 8: Gyora M. Benedek , Alon Itai, Learnability with respect to fixed distributions, Theoretical Computer Science, v.86 n.2, p.377-389, Sept. 2, 1991 [doi>10.1016/0304-3975(91)90026-X]
• 9: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 10: S. VAN DE GEER, Regression Analysis and Empirical Processes, Centrnm voor Wiskunde en Informatica, Amsterdam, 1988.
• 11: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• 12: M.J. KEARNS AND R. E. SCHAPIRE, Efficient distrbutionfree learning of probabilistic concepts (extended abstracO, Proceedings of the 31 st Annual Symposium on the Foundations of Computer Science, 1990.
• 13: Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
• 14: N. MERHAVANDM. FEDER, Universal schemes for sequential decision from individual data sequences, IEEE Transaction on Information Theory, 39 (1993), pp. 1280-1292.
• 15: B. K. Natarajan, On Learning Sets and Functions, Machine Learning, v.4 n.1, p.67-97, October 1989 [doi>10.1023/A:1022605311895]
• 16: B. K. Natarajan, Occam's razor for functions, Proceedings of the sixth annual conference on Computational learning theory, p.370-376, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168380]
• 17: J.K. PATEL AND C. B. READ, The BigBook of Facts About the Normal Distribution, Marcel Dekker, New York, 1982.
• 18: D. POLLARD, Convergence of Stochastic Processes, Springer, New York, 1984.
• 19: H.L. ROYDEN, Real Analysis, Macmillan, New York, 1988.
• 20: John Shawe-Taylor , Martin Anthony , N. L. Biggs, Bounding sample size with the Vapnik-Chervonenkis dimension, Discrete Applied Mathematics, v.42 n.1, p.65-73, Feb. 26, 1993 [doi>10.1016/0166-218X(93)90179-R]
• 21: H.U. S~ON, Bounds on the number of examples needed for learning functions, FB Informatik, LS II, Universitat Dortmund, Forschungsbericht Nr. 501, 1993.
• 22: 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]
• 23: V.N. VAPNIK AND A. Y. CHERVONENKIS, On the uniform convergence of relative frequencies of events to theirprobabilities, Theory of Probability and its Applications, XVI (1971), pp. 264-280.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

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

General Terms:
Theory, Verification