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
Distribution Statement : APPROVED FOR PUBLIC RELEASE