Concept class
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 learning. In this setting, if one takes a set Y as a set of labels, and X is a set of examples, the map, i.e. from examples to classifier labels, 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 from to. Identifying a concept with its characteristic function mapping to, it is a special case of a sample.Two samples are consistent if they agree on the intersection of their domains. A sample extends another sample if the two are consistent and the domain of is contained in the domain of.
Examples
Suppose that. Then:- the subclass is reachable with the sample ;
- the subclass for are reachable with a sample that maps the elements of to zero;
- the subclass, which consists of the singleton sets, is not reachable.