Generality's price inescapable deficiencies in machine-learned programs

John Case, Keh Jiann Chen, Sanjay Jain, Wolfgang Merkle, James S. Royer

Research output: Contribution to journalConference article

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. The paper is on the borderline between learning theory, complexity theory and logic.

Original languageEnglish (US)
Pages (from-to)684-698
Number of pages15
JournalLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
Volume2777
StatePublished - Dec 1 2003
Event16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003 - Washington, DC, United States
Duration: Aug 24 2003Aug 27 2003

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Generality's price inescapable deficiencies in machine-learned programs'. Together they form a unique fingerprint.

  • Cite this