Dominating distributions and learnability

ABSTRACT

We consider PAC-learning where the distribution is known to the student. The problem addressed here is characterizing when learnability with respect to distribution D1 implies learnability with respect to distribution D2. The answer to the above question depends on the learnability model. If the number of examples need not be bounded by a polynomial, it is sufficient to require that all sets which have zero probability with respect to D2 have zero probability with respect to d1. If the number of examples is required to be polynomial, then the probability with respect to D2 must be bounded by a multiplicative constant from that of D1. More stringent conditions must hold if we insist that every hypothesis consistent with the examples be close to the target. Finally, we address the learnability properties of classes of distributions.

REFERENCES

• 1: Peter L. Bartlett , Robert C. Williamson, Investigating the distribution assumptions in the Pac learning model, Proceedings of the fourth annual workshop on Computational learning theory, p.24-32, August 05-07, 1991, Santa Cruz, California, United States
• 2: 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]
• 3: Gyora M. Benedek , Alon Itai, Nonuniform Learnability, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.82-92, July 11-15, 1988
• 4: Shai Ben-David , Gyora M. Benedek , Yishay Mansour, A parameterization scheme for classifying models of PAC learnability, Information and Computation, v.120 n.1, p.11-21, July 1995 [doi>10.1006/inco.1995.1094]
• 5: 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]
• 6: A. Ehrenfeucht , David Haussler , Michael Kearns , Leslie Valiant, A general lower bound on the number of examples needed for learning, Proceedings of the first annual workshop on Computational learning theory, p.139-154, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 7: Halmos, P. R., Measure Theory, Van Nostrand, (1950).
• 8: Ming Li , Paul M. B. Vitányi, Learning simple concepts under simple distributions, SIAM Journal on Computing, v.20 n.5, p.911-935, Oct. 1991 [doi>10.1137/0220056]
• 9: Vapnik V.N. and Chervonenkis A.Ya., On the uniform convergence of relative frequencies of events to their probabilities, Th. Prob. and its Appl., 16(2), 264-80, (1971).
• 10: 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]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing

General Terms:
Theory, Verification