research-article

On the Complexity of Teaching

Authors:

M.J. KearnsAuthors Info & Claims

Journal of Computer and System Sciences, Volume 50, Issue 1

Pages 20 - 31

https://doi.org/10.1006/jcss.1995.1003

Published: 01 February 1995 Publication History

Abstract

While most theoretical work in machine learning has focused on the complexity of learning, recently there has been increasing interest in formally studying the complexity of teaching. In this paper we study the complexity of teaching by considering a variant of the on-line learning model in which a helpful teacher selects the instances. We measure the complexity of teaching a concept from a given concept class by a combinatorial measure we call the teaching dimension, Informally, the teaching dimension of a concept class is the minimum number of instances a teacher must reveal to uniquely identify any target concept chosen from the class.

References

[1]

D. Angluin, Queries and concept learning, Mach. Learning 2, No. 4 (1988), 319-342.

Digital Library

[2]

M. Anthony, G. Brightwell, D. Cohen, and J. Shawe-Taylor, On exact specification by examples, in "Proceedings, Fifth Annual Workshop on Computational Learning Theory," pp. 311-318, ACM Press, July 1992.

[3]

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, Leamability and the Vapnik-Chervonenkis dimension, J. Assoc. Comput. Mach. 36, No. 4 (1989), 929-965.

Digital Library

[4]

J. C. Cherniavsky, M. Velauthapillai, and R. Statman, Inductive inference: An abstract approach, in "Proceedings, 1988 Workshop on Computational Learning Theory," pp. 251-266, Morgan Kaufmann, San Mateo, CA, 1988.

[5]

V. Chvatal, A greedy heuristic for the set covering problem, Math. Oper. Res. 4, No. 3 (1979), 233-235.

Digital Library

[6]

M. R. Garey and D. S. Johnson, "Computers and Intractability: A guide to the Theory of NP-Completeness," Freeman, San Francisco, 1979.

Digital Library

[7]

S. Goldman and D. Mathias, Teaching a smarter learner, in "Proceedings, Sixth Annual ACM Conference on Computational Learning Theory," pp. 67-76, ACM Press, New York, 1993.

Digital Library

[8]

S. A. Goldman, M. J. Kearns, and R. E. Schapire, Exact identification of circuits using fixed points of amplification functions, SIAM J. Comput. 22, No. 4 (1993), 705-726.

Digital Library

[9]

S. A. Goldman, R. L. Rivest, and R. E. Schapire, Learning binary relations and total orders, SIAM J. Comput. 22, No. 5 (1993), 1006-1034.

Digital Library

[10]

S. A. Goldman, "Learning Binary Relations, Total Orders, and Read-once Formulas," Ph.D. thesis, Dept. of Electrical Engineering and Computer Science, MIT, July 1990.

[11]

S. Goldwasser, S. Goldwasser, and C. Rackoff, The knowledge complexity of interactive proofs, in "26th Annual Symposium on Foundations of Computer Science, October 1985," pp. 291-304.

[12]

J. Jackson and A. Tomkins, A computational model of teaching, in "Proceedings, Fifth Annual Workshop on Computational Learning Theory," pp. 319-326, ACM Press, New York, 1992.

[13]

N. Linial, Y. Mansour, and R. L. Rivest, Results on leamability and the Vapnik-Chervonenkis dimension, Inform and Comput. 90, No. 1 (1991), 33-49.

Digital Library

[14]

W. Maass and G. Turin, On the complexity of learning from counterexamples, in "30th Annual Symposium on Foundations of Computer Science, October 1989," pp. 262-267.

[15]

B. K. Natarajan, On learning Boolean functions, in "Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing," pp. 296-304, May 1987.

[16]

R. L. Rivest, Learning decision lists, Machine Learning 2 (3) (1987), 229-246.

[17]

K. Romanik, Approximate testing and learnability, in "Proceedings of the Fifth Annual Workshop on Computational Learning Theory," pp. 327-332, ACM Press, July 1992.

[18]

K. Romanik and C. Smith, Testing geometric objects, Technical Report UMIACS-TR-90-69, University of Maryland, College Park, Department of Computer Science, 1990.

Digital Library

[19]

S. Salzberg, A. Delcher, D. Heath, and S. Kasif, Learning with a helpful teacher, in "12th International Joint Conference on Artificial Intelligence, August 1991," pp. 705-711.

[20]

A. Shinohara and S. Miyano, Teachability in computational learning, New Generation Comput. 8 (1991), 337-347.

Digital Library

[21]

L. Valiant, A theory of learnable, Comm. ACM 27, No. 11 (1984), 1134-1142.

Digital Library

[22]

V. N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. 16, No. 2 (1971), 264-280.

Cited By

Weiss GGoldberg YYahav E(2024)Extracting automata from recurrent neural networks using queries and counterexamples (extended version)Machine Language10.1007/s10994-022-06163-2113:5(2877-2919)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10994-022-06163-2
Zhang CCao XLiu WTsang IKwok JKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Nonparametric iterative machine teachingProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620120(40851-40870)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620120
Çelikok MMurena PKaski SWilliams BChen YNeville J(2023)Teaching to learnProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25735(5939-5947)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25735
Show More Cited By

Index Terms

On the Complexity of Teaching
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Learning by teaching SimStudent: an initial classroom baseline study comparing with cognitive tutor
AIED'11: Proceedings of the 15th international conference on Artificial intelligence in education

This paper describes an application of a machine-learning agent, SimStudent, as a teachable peer learner that allows a student to learn by teaching. SimStudent has been integrated into APLUS (Artificial Peer Learning environment Using SimStudent), an on-...
Teaching Phonics to Chinese L1 EFL Pupils: Pathway to the Future

Despite that converging evidence has led to the mandate of phonics instruction in primary education in the UK, U.S. and EFL English as a Foreign Language China and Taiwan, teachers across the board native or EFL, experienced or novice alike have been ...
Application of a Network Teaching Platform in English Classroom Teaching

The online teaching platform based on the online teaching system on the internet has been widely used in the English education industry. Language education researchers, English teachers, and educational technology professionals are interested in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 1995

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Weiss GGoldberg YYahav E(2024)Extracting automata from recurrent neural networks using queries and counterexamples (extended version)Machine Language10.1007/s10994-022-06163-2113:5(2877-2919)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10994-022-06163-2
Zhang CCao XLiu WTsang IKwok JKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Nonparametric iterative machine teachingProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620120(40851-40870)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620120
Çelikok MMurena PKaski SWilliams BChen YNeville J(2023)Teaching to learnProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25735(5939-5947)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25735
Caro M(2023)From undecidability of non-triviality and finiteness to undecidability of learnabilityInternational Journal of Approximate Reasoning10.1016/j.ijar.2023.109057163:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.ijar.2023.109057
Mansouri FSimon HSingla AZilles SKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)On batch teaching with sample complexity bounded by VCDProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601414(15732-15742)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601414
Losey DBajcsy AO’Malley MDragan A(2022)Physical interaction as communicationInternational Journal of Robotics Research10.1177/0278364921105095841:1(20-44)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1177/02783649211050958
Chhibber NGoh JLaw E(2022)Teachable Conversational Agents for Crowdwork: Effects on Performance and TrustProceedings of the ACM on Human-Computer Interaction10.1145/35552236:CSCW2(1-21)Online publication date: 11-Nov-2022
https://dl.acm.org/doi/10.1145/3555223
Kumar AChen YSingla ARanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Teaching via best-case counterexamples in the learning-with-equivalence-queries paradigmProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3542321(26897-26910)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3542321
Yengera GDevidze RKamalaruban PSingla ARanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Curriculum design for teaching via demonstrationsProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541064(10496-10509)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541064
Ai LMuggleton SHocquette CGromowski MSchmid U(2021)Beneficial and harmful explanatory machine learningMachine Language10.1007/s10994-020-05941-0110:4(695-721)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s10994-020-05941-0
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents