Please use this identifier to cite or link to this item:
|Title:||Synthesizing learners tolerating computable noisy data|
|Source:||Case, J., Jain, S. (2001). Synthesizing learners tolerating computable noisy data. Journal of Computer and System Sciences 62 (3) : 413-441. ScholarBank@NUS Repository. https://doi.org/10.1006/jcss.2000.1736|
|Abstract:||An index for an r.e. class of languages (by definition) generates a sequence of grammars defining the class. An index for an indexed family of recursive languages (by definition) generates a sequence of decision procedures defining the family. F. Stephan's model of noisy data is employed, in which, roughly, correct data crops up infinitely often and incorrect data only finitely often. In a computable universe, all data sequences, even noisy ones, are computable. New to the present paper is the restriction that noisy data sequences be, nonetheless, computable. This restriction is interesting since we may live in a computable universe. Studied, then, is the synthesis from indices for r.e. classes and for indexed families of recursite languages of various kinds of noise-tolerant language-learners for the corresponding classes or families indexed, where the noisy input data sequences are restricted to being computable. Many positive results, as well as some negative results, are presented regarding the existence of such synthesizers. The main positive result is: grammars for each indexed family can be learned behaviorally correctly from computable, noisy, positive data. The proof of another positive synthesis result yields, as a pleasant corollary, a strict subset-principle or telltale style characterization, for the computable noise-tolerant behaviorally correct learnability of grammars from positive and negative data, of the corresponding families indexed.|
|Source Title:||Journal of Computer and System Sciences|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 17, 2018
WEB OF SCIENCETM
checked on Dec 11, 2017
checked on Jan 21, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.