In computational learning theory in mathematics, a concept over a domain X is a total Boolean function over X. A concept class is a class of concepts. Concept classes are a subject of computational learning theory.

Concept class terminology frequently appears in model theory associated with probably approximately correct (PAC) learning. In this setting, if one takes a set Y as a set of (classifier output) labels, and X and where c is a subset of X), c is then said to be a concept. A concept class is then a collection of such concepts.

Given a class of concepts C, a subclass D is reachable if there exists a sample s such that D contains exactly those concepts in C that are extensions to s. Not every subclass is reachable.

Background

A sample is a partial function., it is a special case of a sample.

Two samples are consistent if they agree on the intersection of their domains. extends.

Examples

. Then:

• ;

• to zero;

• , which consists of the singleton sets, is not reachable.

Applications

-good. The fingerprint dimension-good for it. This quantity can be used to bound the minimum number of equivalence queries needed to learn a class of concepts according to the following inequality.

References