Learning Functions from Examples.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1987
- Accession Number
- ADA187725
Entities
People
- B. K. Natarajan
Organizations
- Carnegie Mellon University