Please use this identifier to cite or link to this item:
Title: Synthesizing learners tolerating computable noisy data
Authors: Case, J.
Jain, S. 
Issue Date: 2001
Citation: Case, J., Jain, S. (2001). Synthesizing learners tolerating computable noisy data. Journal of Computer and System Sciences 62 (3) : 413-441. ScholarBank@NUS Repository.
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
ISSN: 00220000
DOI: 10.1006/jcss.2000.1736
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Oct 15, 2018


checked on Oct 15, 2018

Page view(s)

checked on Oct 20, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.