Teaching dimension

In computational learning theory, the teaching dimension[1] of a concept class C is defined to be , where is the minimum size of a witness set for c in C.

The teaching dimension of a finite concept class can be used to give a lower and an upper bound on the membership query cost of the concept class.

In Stasys Jukna's book "Extremal Combinatorics", a lower bound is given for the teaching dimension in general:

Let C be a concept class over a finite domain X. If the size of C is greater than

then the teaching dimension of C is greater than k.

However, there are more specific teaching models that make assumptions about teacher or learner, and can get lower values for the teaching dimension. For instance, several models are the classical teaching (CT) model,[2] the optimal teacher (OT) model,[3] recursive teaching (RT),[4] preference-based teaching (PBT),[5] and non-clashing teaching (NCT).[6]

References
  1. Sally Goldman and Ronald Rivest and Robert Schapire (1989). "Learning Binary Relations and Total Orders" (PDF). SIAM J. Comput. 22: 46–51. doi:10.1109/SFCS.1989.63454. ISBN 0-8186-1982-1. S2CID 9339374. Archived from the original (PDF) on 2018-01-04.
  2. Sally A Goldman and Michael J Kearns (1995). "On the complexity of teaching". Journal of Computer and System Sciences. 50: 20–31. doi:10.1006/jcss.1995.1003. S2CID 7869310.
  3. Frank J Balbach (2008). "Measuring teachability using variants of the teaching dimension". Theoretical Computer Science. 397 (1–3): 94–113. doi:10.1016/j.tcs.2008.02.025.
  4. Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich (2011). "Models of cooperative teaching and learning". Journal of Machine Learning Research. 12: 349–384.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  5. Ziyuan Gao, Christoph Ries, Hans Ulrich Simon, and Sandra Zilles (2017). "Preference-based teaching". Journal of Machine Learning Research. 18. arXiv:1702.02047.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  6. Kirkpatrick, Hans U Simon, and Sandra Zilles (2019). "Optimal collusion-free teaching". Algorithmic Learning Theory: 506–528. arXiv:1903.04012.{{cite journal}}: CS1 maint: multiple names: authors list (link)


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.