A computational model of teaching

ABSTRACT

Goldman and Kearns [GK91] recently introduced a notion of the teaching dimension of a concept class. The teaching dimension is intended to capture the combinatorial difficulty of teaching a concept class. We present a computational analog which allows us to make statements about bounded-complexity teachers and learners, and we extend the model by incorporating trusted information. Under this extended model, we modify algorithms for learning several expressive classes in the exact identification model of Angluin [Ang88]. We study the relationships between variants of these models, and also touch on a relationship with distribution-free learning.

REFERENCES

• AHK89: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning Read-Once Formulas with Queries, University of California at Berkeley, Berkeley, CA, 1989
• Ang87: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• Ang88: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• Ang90: Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
• Blu90: Avrim Blum. Separating distribution-free and mistake-bound learning models over the Boolean domain. In 31st Annual Symposium on Foundations of Computer Science, pages 211-218, 1990.
• CVS88: John C. Cherniavsky , Mahendran Velauthapillai , Richard Statman, Inductive inference: an abstract approach, Proceedings of the first annual workshop on Computational learning theory, p.251-266, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• GK91: Sally A. Goldman , Michael J. Kearns, On the complexity of teaching, Proceedings of the fourth annual workshop on Computational learning theory, p.303-314, August 05-07, 1991, Santa Cruz, California, United States
• GMR85: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• GRS89: Sally A. Goldman, Ronald L. Rivest, and Robert E. Schapire. Learning binary relations and total orders. In Proceedings of the Twenty-Ninth Annual Symposium on Foundations of Computer Science, pages 46-51, 1989.
• Han90: Thomas R. Hancock, Identifying μ-formula decision trees with queries, Proceedings of the third annual workshop on Computational learning theory, p.23-37, August 06-08, 1990, Rochester, New York, United States
• HH91: Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
• HK91: Lisa Hellerstein and Marek Karpinski. Computational complexity of learning read-once formulas over different bases. Technical Report TR- 91-014, International Computer Science Institute, 1991.
• Nat87: B. K. Natarajan, On learning Boolean functions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.296-304, January 1987, New York, New York, United States [doi>10.1145/28395.28427]
• 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

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

General Terms:
Theory, Verification