Approximate testing and learnability

摘要

A model for approximate testing of concepts, which relates to the PAC model of learning, has been developed. In this model an approximate testing algorithm produces a finite set of examples that distinguishes one concept from others that differ from it by more than a given error bound. This model corresponds closely to the helpful teacher learning model. In this paper we examine properties of a concept class that make it testable or untestable. We define a new measure that is a dual to the VC-dimension, called the testing dimension of a concept class, and show how it yields untestability results for certain concept classes.