Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99192
Title: Anomalous learning helps succinctness
Authors: Case, J.
Jain, S. 
Sharma, A.
Issue Date: 10-Sep-1996
Citation: Case, J.,Jain, S.,Sharma, A. (1996-09-10). Anomalous learning helps succinctness. Theoretical Computer Science 164 (1-2) : 13-28. ScholarBank@NUS Repository.
Abstract: It is shown that allowing a bounded number of anomalies (mistakes) in the final programs learned by an algorithmic procedure can considerably "succinctify" those final programs. Naturally, only those contexts are investigated in which the presence of anomalies is not actually required for successful inference (learning). The contexts considered are certain infinite subclasses of the class of characteristic functions of finite sets. For each finite set D, these subclasses have a finite set containing D. This latter prevents the anomalies from wiping out all the information in the sets featured in these subclasses and shows the context to be fairly robust. Some of the results in the present paper are shown to be provably more constructive than others. The results of this paper can also be interpreted as facts about succinctness of coding finite sets, which facts have interesting consequences for learnability of decision procedures for finite sets.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/99192
ISSN: 03043975
Appears in Collections:Staff Publications

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

Page view(s)

17
checked on May 4, 2018

Google ScholarTM

Check


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