Reference: Keller, R. M. Learning Approximate Concept Descriptions. July 1988, 1988.
Abstract: Sometimes it is critical for a learning system to form an approximate concept description - a description that intentionally misclassifies some of the training instances. In particular, sometimes an exact description cannot be formed or is prohibitvely expensive to use. In these cases, a learning system must explicitly reason about the performance trade-offs involved in learning one approximation versus another. Concept learning systems developed to date lack this reasoning capability. This paper discusses an approach to learning approximations and reports on a program that successfully implements a method for learning approximations.
Notes: 15 pages.