Teaching Memoryless Randomized Learners Without Feedback | SpringerLink
Skip to main content
Springer Nature Link
Log in

Teaching Memoryless Randomized Learners Without Feedback

  • Conference paper
Algorithmic Learning Theory (ALT 2006)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 4264))

Included in the following conference series:

Abstract

The present paper mainly studies the expected teaching time of memoryless randomized learners without feedback.

First, a characterization of optimal randomized learners is provided and, based on it, optimal teaching teaching times for certain classes are established. Second, the problem of determining the optimal teaching time is shown to be \({{\mathcal N\!P}}\)-hard. Third, an algorithm for approximating the optimal teaching time is given. Finally, two heuristics for teaching are studied, i.e., cyclic teachers and greedy teachers.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Angluin, D., Kriķis, M.: Teachers, learners and black boxes. In: Proc. 10th Ann. Conf. on Comput. Learning Theory, pp. 285–297. ACM Press, New York (1997)

    Chapter  Google Scholar 

  2. Angluin, D., Kriķis, M.: Learning from different teachers. Machine Learning 51(2), 137–163 (2003)

    Article  MATH  Google Scholar 

  3. Anthony, M., Brightwell, G., Cohen, D., Shawe-Taylor, J.: On exact specification by examples. In: Proc. 5th Ann. ACM Works. on Comput. Learning Theory, pp. 311–318. ACM Press, New York (1992)

    Chapter  Google Scholar 

  4. Balbach, F.J.: Teaching Classes with High Teaching Dimension Using Few Examples. In: Auer, P., Meir, R. (eds.) COLT 2005. LNCS (LNAI), vol. 3559, pp. 668–683. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  5. Balbach, F.J., Zeugmann, T.: Teaching randomized learners. In: Lugosi, G., Simon, H.U. (eds.) COLT 2006. LNCS (LNAI), vol. 4005, pp. 229–243. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  6. Bertsekas, D.P.: Dynamic Programming and Optimal Control. Athena Sci. (2005)

    Google Scholar 

  7. Blondel, V.D., Canterini, V.: Undecidable problems for probabilistic automata of fixed dimension. Theory of Computing Systems 36(3), 231–245 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. Freivalds, R., Kinber, E.B., Wiehagen, R.: On the power of inductive inference from good examples. Theoret. Comput. Sci. 110(1), 131–144 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  9. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  10. Goldman, S.A., Kearns, M.J.: On the complexity of teaching. J. of Comput. Syst. Sci. 50(1), 20–31 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  11. Goldman, S.A., Mathias, H.D.: Teaching a smarter learner. J. of Comput. Syst. Sci. 52(2), 255–267 (1996)

    Article  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  13. Jackson, J., Tomkins, A.: A computational model of teaching. In: Proc. 5th Ann. ACM Works. on Comput. Learning Theory, pp. 319–326. ACM Press, New York (1992)

    Chapter  Google Scholar 

  14. Jain, S., Lange, S., Nessel, J.: On the learnability of recursively enumerable languages from good examples. Theoret. Comput. Sci. 261(1), 3–29 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  15. Kuhlmann, C.: On Teaching and Learning Intersection-Closed Concept Classes. In: Fischer, P., Simon, H.U. (eds.) EuroCOLT 1999. LNCS (LNAI), vol. 1572, pp. 168–182. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  16. Lee, H.K., Servedio, R.A., Wan, A.: DNF Are Teachable in the Average Case. In: Lugosi, G., Simon, H.U. (eds.) COLT 2006. LNCS (LNAI), vol. 4005, pp. 214–228. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  17. Madani, O., Hanks, S., Condon, A.: On the undecidability of probabilistic planning and infinite-horizon partially observable markov decision problems. In: Proc. 16th Nat. Conf. on Artificial Intelligence & 11th Conf. on Innovative Applications of Artificial Intelligence, pp. 541–548. AAAI Press/MIT Press (1999)

    Google Scholar 

  18. Mathias, H.D.: A model of interactive teaching. J. of Comput. Syst. Sci. 54(3), 487–501 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  19. Patek, S.D.: On partially observed stochastic shortest path problems. In: Proc. of the 40-th IEEE Conf. on Decision and Control, pp. 5050–5055 (2001)

    Google Scholar 

  20. Shinohara, A., Miyano, S.: Teachability in computational learning. New Generation Computing 8(4), 337–348 (1991)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Theoretische Informatik, Universität zu Lübeck, Ratzeburger Allee 160, 23538, Lübeck, Germany

    Frank J. Balbach

  2. Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo, 060-0814, Japan

    Thomas Zeugmann

Authors
  1. Frank J. Balbach
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Zeugmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departament de Llenguatges i Sistemes Informàtics Laboratori d’Algorísmica Relacional, Complexitat i Aprenentatge, Universitat Politècnica de Catalunya, Barcelona,  

    José L. Balcázar

  2. Google, 1600 Amphitheatre Parkway, 94043, Mountain View, CA, USA

    Philip M. Long

  3. Department of Computer Science and Department of Mathematics, National University of Singapore, 117543, Singapore, Republic of Singapore

    Frank Stephan

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Balbach, F.J., Zeugmann, T. (2006). Teaching Memoryless Randomized Learners Without Feedback. In: Balcázar, J.L., Long, P.M., Stephan, F. (eds) Algorithmic Learning Theory. ALT 2006. Lecture Notes in Computer Science(), vol 4264. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11894841_11

Download citation

  • DOI: https://doi.org/10.1007/11894841_11

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-46649-9

  • Online ISBN: 978-3-540-46650-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics