Concept class

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (December 2021) (Learn how and when to remove this message) This article may need to be rewritten to comply with Wikipedia's quality standards, as the article should cover more aspects of concept classes in a more balanced way, so as to avoid violating WP:UNDUE. You can help. The talk page may contain suggestions. (December 2021) (Learn how and when to remove this message)

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.^[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 ${\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.^[2] Not every subclass is reachable.^[2][why?]