TY - JOUR
T1 - Generality's price inescapable deficiencies in machine-learned programs
AU - Case, John
AU - Chen, Keh Jiann
AU - Jain, Sanjay
AU - Merkle, Wolfgang
AU - Royer, James S.
N1 - Funding Information:
Thanks to the anonymous referee for several suggestions that helped tighten and improve the paper. Special thanks go to Prof. Dr. Klaus Ambos-Spies for some very helpful suggestions and observations. Grant support was received by J. Case from NSF grant CCR-0208616, by S. Jain from NUS grant R252-000-127-112, and by J. Royer from NSF grant CCR-0098198.
PY - 2003
Y1 - 2003
N2 - 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. The paper is on the borderline between learning theory, complexity theory and logic.
AB - 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. The paper is on the borderline between learning theory, complexity theory and logic.
UR - http://www.scopus.com/inward/record.url?scp=9444273997&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=9444273997&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-45167-9_50
DO - 10.1007/978-3-540-45167-9_50
M3 - Conference article
AN - SCOPUS:9444273997
VL - 2777
SP - 684
EP - 698
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
SN - 0302-9743
T2 - 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003
Y2 - 24 August 2003 through 27 August 2003
ER -