Accession Number : ADA187725

Title :   Learning Functions from Examples.

Descriptive Note : Interim rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST

Personal Author(s) : Natarajan, B K

PDF Url : ADA187725

Report Date : Aug 1987

Pagination or Media Count : 19

Abstract : This paper concerns algorithms that learn functions from examples. Functions on strings of a finite alphabet are considered and the notion of dimensionality defined for families of such functions. Using this notion, a theorem is proved identifying the most general conditions under which a family of functions can be efficiently learned from examples. Turning to some familiar families, we present strong evidence against the existence of efficient algorithms for learning the regular functions and the polynomial time computable functions, even if the size of the encoding of the function to be learned is given. Our arguments hinge in a new complexity measure--the constraint complexity.

Descriptors :   *ALGORITHMS, *LEARNING, *FUNCTIONS, ALPHABETS, EFFICIENCY, POLYNOMIALS, TIME, NUMERICAL ANALYSIS, PATTERN RECOGNITION, ARTIFICIAL INTELLIGENCE

Subject Categories : Cybernetics
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE