Please use this identifier to cite or link to this item: https://doi.org/10.1006/inco.1996.0064
Title: Machine Induction without Revolutionary Changes in Hypothesis Size
Authors: Case, J.
Jain, S. 
Sharma, A.
Issue Date: 1-Aug-1996
Source: Case, J., Jain, S., Sharma, A. (1996-08-01). Machine Induction without Revolutionary Changes in Hypothesis Size. Information and Computation 128 (2) : 73-86. ScholarBank@NUS Repository. https://doi.org/10.1006/inco.1996.0064
Abstract: This paper provides a beginning study of the effects on inductive inference of paradigm shifts whose absence is approximately modeled by various formal approaches to forbidding large changes in the size of programs conjectured. One approach, called severely parsimonious, requires all the programs conjectured on the way to success to be nearly (i.e., within a recursive function of) minimal size. It is shown that this very conservative constraint allows learning infinite classes of functions, but not infinite r.e. classes of functions. Another approach, called non-revolutionary, requires all conjectures to be nearly the same size as one another. This quite conservative constraint is, nonetheless, shown to permit learning some infinite r.e. classes of functions. Allowing up to one extra bounded size mind change towards a final program learned certainly does not appear revolutionary. However, somewhat surprisingly for scientific (inductive) inference, it is shown that there are classes learnable with the non-revolutionary constraint (respectively, with severe parsimony), up to (i + 1) mind changes, and no anomalies, which classes cannot be learned with no size constraint, an unbounded, finite number of anomalies in the final program, but with no more than i mind changes. Hence, in some cases, the possibility of one extra mind change is considerably more liberating than removal of very conservative size shift constraints. The proofs of these results are also combinatorially interesting. © 1996 Academic Press, Inc.
Source Title: Information and Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/99332
ISSN: 08905401
DOI: 10.1006/inco.1996.0064
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

2
checked on Feb 13, 2018

WEB OF SCIENCETM
Citations

2
checked on Jan 8, 2018

Page view(s)

22
checked on Feb 11, 2018

Google ScholarTM

Check

Altmetric


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