1,721,002 research outputs found
Learning Recursive Functions from Approximations (Extended Abstract)
No full text) Appeared In: EuroCOLT'95, LNCS 904, 140--153, Springer-Verlag, 1995. John Case 1 , Susanne Kaufmann 2 , Efim Kinber 1 , Martin Kummer 2 1 Department of Computer and Information Sciences, University of Delaware, Newark, Delaware 19176, USA. fcase; [email protected] 2 Institut fur Logik, Komplexitat und Deduktionssysteme, Universitat Karlsruhe, D-76128 Karlsruhe, Germany. fkaufmann; [email protected] Abstract. Investigated is algorithmic learning, in the limit, of correct programs for recursive functions f from both input/output examples of f and several interesting varieties of approximate additional (algorithmic) information about f . Specifically considered, as such approximate additional information about f , are Rose's frequency computations for f and several natural generalizations from the literature, each generalization involving programs for restricted trees of recursive functions which have f as a branch. Considered as the types of trees are those w..
Mind change speed-up for learning languages from positive data
Get PDF10.1016/j.tcs.2013.04.009Theoretical Computer Science489-49037-47TCSC
Language Learning from Texts: Mind Changes, Limited Memory and Monotonicity (Extended Abstract)
No full textThe paper explores language learning in the limit under various constraints on the number of mindchanges, memory, and monotonicity. We define language learning with limited (long term) memory and prove that learning with limited memory is exactly the same as learning via set driven machines (when the order of the input string is not taken into account). Further we show that every language learnable via a set driven machine is learnable via a conservative machine (making only justifiable mindchanges). We get a variety of separation results for learning with bounded number of mindchanges or limited memory under restrictions on monotonicity. Many separation results have a variant: If a criterion A can be separated from B, then often it is possible to find a family L of languages such that L is A and B learnable, but while it is possible to restrict the number of mindchanges or long term memory..
- …
