Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.apal.2005.06.013
Title: Generality's price: Inescapable deficiencies in machine-learned programs
Authors: Case, J.
Chen, K.-J.
Jain, S. 
Merkle, W.
Royer, J.S.
Keywords: Applications of computability theory
Computational learning theory
Issue Date: 2006
Source: Case, J., Chen, K.-J., Jain, S., Merkle, W., Royer, J.S. (2006). Generality's price: Inescapable deficiencies in machine-learned programs. Annals of Pure and Applied Logic 139 (1-3) : 303-326. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2005.06.013
Abstract: This paper investigates some delicate tradeoffs between the generality of an algorithmic learning device and the quality of the programs it learns successfully. There are results to the effect that, thanks to small increases in generality of a learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. There are also results in which the complexity of successfully learned programs is asymptotically optimal and the learning device is general, but, still thanks to the generality, some of those optimal, learned programs are provably unalterably information deficient-in some cases, deficient as to safe, algorithmic extractability/provability of the fact that they are even approximately optimal. For these results, the safe, algorithmic methods of information extraction will be by proofs in arbitrary, true, computably axiomatizable extensions of Peano Arithmetic. © 2005 Elsevier B.V. All rights reserved.
Source Title: Annals of Pure and Applied Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/39431
ISSN: 01680072
DOI: 10.1016/j.apal.2005.06.013
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

3
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

2
checked on Dec 11, 2017

Page view(s)

57
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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