Generality’s price: Inescapable deficiencies in machine-learned programs

Annals of Pure and Applied Logic 139 (1):303-326 (2006)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 74,429

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The Mind-Body Problem and the Intertwining [Spanish].James Mensch - 2011 - Eidos: Revista de Filosofía de la Universidad Del Norte 15:76-95.
Interconsequence Generality of Learned Helplessness.Michael D. Mauk & Edward J. Pavur - 1979 - Bulletin of the Psychonomic Society 14 (6):421-423.
Spaces of Difference: The Contradictions of Alternative Educational Programs.Jennifer A. Vadeboncoeur - 2009 - Educational Studies: A Jrnl of the American Educ. Studies Assoc 45 (3):280-299.
Human and Machine Logic: A Rejoinder.John R. Lucas - 1968 - British Journal for the Philosophy of Science 19 (2):155-6.
Hume's Analysis of Generality.Kingsley Blake Price - 1950 - Philosophical Review 59 (1):58-76.


Added to PP

6 (#1,096,230)

6 months
1 (#417,143)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

General Recursive Functions of Natural Numbers.S. C. Kleene - 1937 - Journal of Symbolic Logic 2 (1):38-38.
[Omnibus Review].James S. Royer - 1999 - Journal of Symbolic Logic 64 (2):914-916.
On the Computational Complexity of Algorithms.J. Hartmanis & R. E. Stearns - 1967 - Journal of Symbolic Logic 32 (1):120-121.

Add more references