In computational learning theory in mathematics, a concept over a domain X is a total Boolean function over X.
Concept classes are a subject of computational learning theory.
Concept class terminology frequently appears in model theory associated with probably approximately correct (PAC) learning.
[1] In this setting, if one takes a set Y as a set of (classifier output) labels, and X is a set of examples, the map
, i.e. from examples to classifier labels (where
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.[2] Not every subclass is reachable.[2][why?]
is a partial function from
[clarification needed] to
[2] Identifying a concept with its characteristic function mapping
, it is a special case of a sample.
[2] Two samples are consistent if they agree on the intersection of their domains.
extends another sample
if the two are consistent and the domain of
is contained in the domain of
-good for a positive integer
[2] The fingerprint dimension
of the entire concept class
is the least positive integer
such that every reachable subclass
[2] This quantity can be used to bound the minimum number of equivalence queries[clarification needed] needed to learn a class of concepts according to the following inequality: