Please use this identifier to cite or link to this item:
|Title:||Anomalous learning helps succinctness||Authors:||Case, J.
|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.
checked on Jan 11, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.