Prescribed Learning of Indexed Families

• Autorzy: Jain S. , Stephan F. , Nan Y.
• Języki publikacji: EN

Abstrakty

EN

This work extends studies of Angluin, Lange and Zeugmann on how learnability of a language class depends on the hypothesis space used by the learner. While previous studies mainly focused on the case where the learner chooses a particular hypothesis space, the goal of this work is to investigate the case where the learner has to cope with all possible hypothesis spaces. In that sense, the present work combines the approach of Angluin, Lange and Zeugmann with the question of how a learner can be synthesized. The investigation for the case of uniformly r.e. classes has been done by Jain, Stephan and Ye [6]. This paper investigates the case for indexed families and gives a special attention to the notions of conservative and non U-shaped learning.

Słowa kluczowe

EN

inductive inference; prescribed learning; uniform learning; indexed families; conservative learning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 159--175
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Jain S.

autor

Stephan F.

autor

Nan Y.

• Department of mathematics, National University of Singapore,, Singapore 117543, Republic of Singapore,

Bibliografia

• [1] Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117- 135, 1980.
• [2] Lenore Blum and Manuel Blum. Towards a mathematical theory of inductive inference. Information and Control, 28:125-155,1975.
• [3] Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan and Rolf Wiehagen. When unlearning helps. Information and Computation, to appear.
• [4] E. Mark Gold. Language identification in the limit. Information and Control, 10:447-474,1967.
• [5] Klaus-Peter Jantke. Monotonie and Non-monotonic Inductive Inference. New Generation Computing, 8:349-360,1991.
• [6] Sanjay Jain, Frank Stephan and Nan Ye. Prescribed Learning of R.E. Classes. In M. Hutter, R. Servedio and E. Takimoto, editors, Algorithmic Learning Theory, 18th International Conference, ALT 2007, Springer Lecture Notes in Artificial Intelligence 4754:64-78,2007.
• [7] Steffen Lange. Algorithmic Learning of Recursive Languages. Habilitationsschrift, Fakultat ftir Mathematik und Informatik der Universitat Leipzig, Mensch und Buch Verlag, Berlin, 2000.
• [8] Steffen Lange and Thomas Zeugmann. Language learning in dependence on the space of hypotheses. Proceedings of the Sixth Annual Conference on Computational Learning Theory, Santa Cruz, California, United States, pages 127-136,1993.
• [9] Steffen Lange, Thomas Zeugmann and Shyam Kapur. Monotonie and dual monotonie language learning. Theoretical Computer Science, 155:365-410,1996.
• [10] Daniel Osherson, Michael Stob and Scott Weinstein. Systems That Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists. Bradford - The MIT Press, Cambridge, Massachusetts, 1986.
• [11] Emil Post. Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, 50:284-316,1944.
• [12] Ludwig Staiger. On the power of reading the whole infinite input tape. Grammars, 3:247-257,1999.
• [13] Thomas Zeugmann. Algorithmisches Lernen von Funktionen und Sprachen. Habilitationsschrift, Technische Hochschule Darmstadt, 1993.
• [14] Thomas Zeugmann and Steffen Lange. A guided tour across the boundaries of learning recursive languages. Algorithmic Learning for Knowledge-Based Systems, final report on research project Gosler, edited by Klaus P. Jantke and Steffen Lange, Springer Lecture Notes in Artificial Intelligence 961:193-262, 1995.
• [15] Thomas Zeugmann, Steffen Lange and Shyam Kapur. Characterizations of monotonie and dual monotonie language learning, Information and Computation, 120:155-173, 1995.
• [16] Hartley Rogers. Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. Reprinted by MIT Press in 1987.
• [17] Sandra Zilles. Separation of uniform learning classes. Theoretical Computer Science, 313:229-265,2004.
• [18] Sandra Zilles. Increasing the power of uniform inductive learners. Journal of Computer and System Sciences, 70:510-538,2005.