Concept class

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 is a set of examples, the map ${\displaystyle c:X\to Y}$, i.e. from examples to classifier labels (where ${\displaystyle Y=\{0,1\}}$ and where c is a subset of X), c is then said to be a concept. A concept class ${\displaystyle C}$ 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 ${\displaystyle s}$ is a partial function from ${\displaystyle X}$ to ${\displaystyle \{0,1\}}$. Identifying a concept with its characteristic function mapping ${\displaystyle X}$ to ${\displaystyle \{0,1\}}$, it is a special case of a sample.

Two samples are consistent if they agree on the intersection of their domains. A sample ${\displaystyle s^{\prime }}$ extends another sample ${\displaystyle s}$ if the two are consistent and the domain of ${\displaystyle s}$ is contained in the domain of ${\displaystyle s^{\prime }}$.