jmlr jmlr2011 jmlr2011-65 jmlr2011-65-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sandra Zilles, Steffen Lange, Robert Holte, Martin Zinkevich
Abstract: While most supervised machine learning models assume that training examples are sampled at random or adversarially, this article is concerned with models of learning from a cooperative teacher that selects “helpful” training examples. The number of training examples a learner needs for identifying a concept in a given class C of possible target concepts (sample complexity of C) is lower in models assuming such teachers, that is, “helpful” examples can speed up the learning process. The problem of how a teacher and a learner can cooperate in order to reduce the sample complexity, yet without using “coding tricks”, has been widely addressed. Nevertheless, the resulting teaching and learning protocols do not seem to make the teacher select intuitively “helpful” examples. The two models introduced in this paper are built on what we call subset teaching sets and recursive teaching sets. They extend previous models of teaching by letting both the teacher and the learner exploit knowing that the partner is cooperative. For this purpose, we introduce a new notion of “coding trick”/“collusion”. We show how both resulting sample complexity measures (the subset teaching dimension and the recursive teaching dimension) can be arbitrarily lower than the classic teaching dimension and known variants thereof, without using coding tricks. For instance, monomials can be taught with only two examples independent of the number of variables. The subset teaching dimension turns out to be nonmonotonic with respect to subclasses of concept classes. We discuss why this nonmonotonicity might be inherent in many interesting cooperative teaching and learning scenarios. Keywords: teaching dimension, learning Boolean functions, interactive learning, collusion c 2011 Sandra Zilles, Steffen Lange, Robert Holte and Martin Zinkevich. Z ILLES , L ANGE , H OLTE AND Z INKEVICH
D. Angluin and M. Krikis. Teachers, learners and black boxes. In Proc. of the 10th Annual Confer¸ ence on Computational Learning Theory (COLT’97), pages 285–297. ACM, New York, 1997. D. Angluin and M. Krikis. Learning from different teachers. Mach. Learn., 51:137–163, 2003. ¸ M. Anthony, G. Brightwell, D.A. Cohen, and J. Shawe-Taylor. On exact specification by examples. In Proc. of 5th Annual Workshop on Computational Learning Theory (COLT’92), pages 311–318. 382 M ODELS OF C OOPERATIVE T EACHING AND L EARNING ACM, New York, 1992. F. Balbach. Measuring teachability using variants of the teaching dimension. Theoret. Comput. Sci., 397(1-3):94–113, 2008. F. Balbach and T. Zeugmann. Recent developments in algorithmic teaching. In Proc. 3rd Intl. Conf. on Language and Automata Theory and Applications, pages 1–18, 2009. S. Ben-David and N. Eiron. Self-directed learning and its relation to the VC-dimension and to teacher-directed learning. Machine Learning, 33(1):87–104, 1998. T. Doliwa, H.U. Simon, and S. Zilles. Recursive teaching dimension, learning complexity, and maximum classes. In Proc. of the 21st International Conference on Algorithmic Learning Theory (ALT’10), volume 6331 of Lecture Notes in Artificial Intelligence, pages 209–223. Springer, 2010. R. Freivalds, E.B. Kinber, and R. Wiehagen. On the power of inductive inference from good examples. Theoret. Comput. Sci., 110(1):131–144, 1993. S. Goldman and M. Kearns. On the complexity of teaching. In Proc. of the 4th Annual Workshop on Computational Learning Theory, COLT’91, pages 303–314. Morgan Kaufmann, 1991. S.A. Goldman and M.J. Kearns. On the complexity of teaching. J. Comput. Syst. Sci., 50(1):20–31, 1995. S.A. Goldman and H.D. Mathias. Teaching a smarter learner. J. Comput. Syst. Sci., 52(2):255–267, 1996. S. Hanneke. Teaching dimension and the complexity of active learning. In Proc. of the 20th Annual Conference on Learning Theory (COLT 2007), pages 66–81. LNCS 4539, Springer, Berlin, 2007. T. Heged˝ s. Generalized teaching dimensions and the query complexity of learning. In Proc. of the u 8th Annual Conference on Computational Learning Theory (COLT’95), pages 108–117. ACM, New York, 1995. J. Jackson and A. Tomkins. A computational model of teaching. In Proc. of 5th Annual Workshop on Computational Learning Theory (COLT’92), pages 319–326. ACM, New York, 1992. H. Kobayashi and A. Shinohara. Complexity of teaching by a restricted number of examples. In Proc. of the 22nd Annual Conference on Learning Theory, COLT’09, pages 293–302, 2009. S. Lange, J. Nessel, and R. Wiehagen. Learning recursive languages from good examples. Ann. Math. Artif. Intell., 23(1-2):27–52, 1998. H.D. Mathias. A model of interactive teaching. J. Comput. Syst. Sci., 54(3):487–501, 1997. M. Ott and F. Stephan. Avoiding coding tricks by hyperrobust learning. Theoret. Comput. Sci., 284 (1):161–180, 2002. R.L. Rivest and Y.L. Yin. Being taught can be faster than asking questions. In Proc. of the 8th Annual Conference on Computational Learning Theory (COLT’95), pages 144–151. ACM, New York, 1995. 383 Z ILLES , L ANGE , H OLTE AND Z INKEVICH R.A. Servedio. On the limits of efficient teachability. Inf. Process. Lett., 79(6):267–272, 2001. A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Comput., 8 (4):337–348, 1991. L.G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, 1984. S. Zilles, S. Lange, R. Holte, and M. Zinkevich. Teaching dimensions based on cooperative learning. In Proc. of the 21st Annual Conference on Learning Theory (COLT’08), pages 135–146. Omnipress, 2008. 384