# Concept class > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Concept_class > Markdown URL: https://mediated.wiki/source/Concept_class.md > Source: https://en.wikipedia.org/wiki/Concept_class > Source revision: 1179525705 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Computational learning theory This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these 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. Relevant discussion may be found on the talk page. You can help. The talk page may contain suggestions. (December 2021) (Learn how and when to remove this message) In [computational learning theory](/source/Computational_learning_theory) in [mathematics](/source/Mathematics), a **concept** over a domain *X* is a total [Boolean function](/source/Boolean_function) over *X*. A **concept class** is a class of concepts. Concept classes are a subject of [computational learning theory](/source/Computational_learning_theory). Concept class terminology frequently appears in [model theory](/source/Model_theory) associated with [probably approximately correct](/source/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 c : X → Y {\displaystyle c:X\to Y} , i.e. from examples to classifier labels (where Y = { 0 , 1 } {\displaystyle Y=\{0,1\}} and where *c* is a subset of *X*), *c* is then said to be a *concept*. A *concept class* C {\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?](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] ## Background This section needs expansion. You can help by adding missing information. (December 2021) A *sample* s {\displaystyle s} is a [partial function](/source/Partial_function) from X {\displaystyle X} [*[clarification needed](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] to { 0 , 1 } {\displaystyle \{0,1\}} .[2] Identifying a concept with its characteristic function mapping X {\displaystyle X} to { 0 , 1 } {\displaystyle \{0,1\}} , it is a special case of a sample.[2] Two samples are *consistent* if they agree on the intersection of their domains.[2] A sample s ′ {\displaystyle s'} *extends* another sample s {\displaystyle s} if the two are consistent and the domain of s {\displaystyle s} is contained in the domain of s ′ {\displaystyle s'} .[2] ## Examples Suppose that C = S + ( X ) {\displaystyle C=S^{+}(X)} . Then: - the subclass { { x } } {\displaystyle \{\{x\}\}} is reachable with the sample s = { ( x , 1 ) } {\displaystyle s=\{(x,1)\}} ;[2][*[why?](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] - the subclass S + ( Y ) {\displaystyle S^{+}(Y)} for Y ⊆ X {\displaystyle Y\subseteq X} are reachable with a sample that maps the elements of X − Y {\displaystyle X-Y} to zero;[2][*[why?](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] - the subclass S ( X ) {\displaystyle S(X)} , which consists of the singleton sets, is *not* reachable.[2][*[why?](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] ## Applications Let C {\displaystyle C} be some concept class. For any concept c ∈ C {\displaystyle c\in C} , we call this concept 1 / d {\displaystyle 1/d} *-good* for a positive integer d {\displaystyle d} if, for all x ∈ X {\displaystyle x\in X} , at least 1 / d {\displaystyle 1/d} of the concepts in C {\displaystyle C} agree with c {\displaystyle c} on the classification of x {\displaystyle x} .[2] The *fingerprint dimension* F D ( C ) {\displaystyle FD(C)} of the entire concept class C {\displaystyle C} is the least positive integer d {\displaystyle d} such that every reachable subclass C ′ ⊆ C {\displaystyle C'\subseteq C} contains a concept that is 1 / d {\displaystyle 1/d} -good for it.[2] This quantity can be used to bound the minimum number of equivalence queries[*[clarification needed](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] needed to learn a class of concepts according to the following [inequality](/source/Inequality_(mathematics)): F D ( C ) − 1 ≤ # E Q ( C ) ≤ ⌈ F D ( C ) ln ⁡ ( | C | ) ⌉ {\textstyle FD(C)-1\leq \#EQ(C)\leq \lceil FD(C)\ln(|C|)\rceil } .[2] ## References 1. **[^](#cite_ref-1)** [Chase, H., & Freitag, J. (2018). *Model Theory and Machine Learning*. arXiv preprint arXiv:1801.06566](https://arxiv.org/abs/1801.06566). 1. ^ [***a***](#cite_ref-:0_2-0) [***b***](#cite_ref-:0_2-1) [***c***](#cite_ref-:0_2-2) [***d***](#cite_ref-:0_2-3) [***e***](#cite_ref-:0_2-4) [***f***](#cite_ref-:0_2-5) [***g***](#cite_ref-:0_2-6) [***h***](#cite_ref-:0_2-7) [***i***](#cite_ref-:0_2-8) [***j***](#cite_ref-:0_2-9) [***k***](#cite_ref-:0_2-10) [***l***](#cite_ref-:0_2-11) Angluin, D. (2004). ["Queries revisited"](https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf) (PDF). *Theoretical Computer Science*. **313** (2): 188–191. [doi](/source/Doi_(identifier)):[10.1016/j.tcs.2003.11.004](https://doi.org/10.1016%2Fj.tcs.2003.11.004). --- Adapted from the Wikipedia article [Concept class](https://en.wikipedia.org/wiki/Concept_class) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Concept_class?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.