{{Short description|Computational learning theory}} {{Multiple issues|{{context|date=December 2021}} {{rewrite|the article should cover more aspects of concept classes in a more balanced way, so as to avoid violating [[WP:UNDUE]]|date=December 2021}}}}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.<ref> [https://arxiv.org/abs/1801.06566 Chase, H., & Freitag, J. (2018). ''Model Theory and Machine Learning''. arXiv preprint arXiv:1801.06566].</ref> 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 <math>c: X\to Y</math>, i.e. from examples to classifier labels (where <math>Y = \{0, 1\}</math> and where ''c'' is a subset of ''X''), ''c'' is then said to be a ''concept''. A ''concept class'' <math>C</math> 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''.<ref name=":0" /> Not every subclass is reachable.<ref name=":0">{{cite journal|last=Angluin|first=D.|year=2004|title=Queries revisited|url=https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf|journal=Theoretical Computer Science|volume=313|issue=2|pages=188–191|doi=10.1016/j.tcs.2003.11.004 }}</ref>{{Why|date=December 2021}}<!-- I got rid of the reference to the book (https://books.google.com/books?id=snJrCQAAQBAJ&newbks=0&printsec=frontcover), as it seems that the article titled "Queries revisited" and the relevant section of the book are actually the same source. Also, the PDF is more accessible.
I still haven't been able to find other sources about the idea of a reachable subclass (as described in Angluin 2004) rather than just a reachability problem in general. ~Duckmather -->
== Background == {{Expand section|date=December 2021}} A ''sample'' <math>s</math> is a [[partial function]] from <math>X</math>{{What|date=December 2021|reason=What is "X"?}} to <math>\{0, 1\}</math>.<ref name=":0" /> Identifying a concept with its characteristic function mapping <math>X</math> to <math>\{0, 1\}</math>, it is a special case of a sample.<ref name=":0" />
Two samples are ''consistent'' if they agree on the intersection of their domains.<ref name=":0" /> A sample <math>s'</math> ''extends'' another sample <math>s</math> if the two are consistent and the domain of <math>s</math> is contained in the domain of <math>s'</math>.<ref name=":0" />
== Examples == Suppose that <math>C = S^+(X)</math>. Then:
* the subclass <math>\{\{x\}\}</math> is reachable with the sample <math>s = \{(x, 1)\}</math>;<ref name=":0" />{{Why|date=December 2021}} * the subclass <math>S^+(Y)</math> for <math>Y\subseteq X</math> are reachable with a sample that maps the elements of <math>X - Y</math> to zero;<ref name=":0" />{{Why|date=December 2021}} * the subclass <math>S(X)</math>, which consists of the singleton sets, is ''not'' reachable.<ref name=":0" />{{Why|date=December 2021}}
== Applications == Let <math>C</math> be some concept class. For any concept <math>c\in C</math>, we call this concept <math>1/d</math>''-good'' for a positive integer <math>d</math> if, for all <math>x\in X</math>, at least <math>1/d</math> of the concepts in <math>C</math> agree with <math>c</math> on the classification of <math>x</math>.<ref name=":0" /> The ''fingerprint dimension'' <math>FD(C)</math> of the entire concept class <math>C</math> is the least positive integer <math>d</math> such that every reachable subclass <math>C'\subseteq C</math> contains a concept that is <math>1/d</math>-good for it.<ref name=":0" /> This quantity can be used to bound the minimum number of equivalence queries{{What|date=December 2021|reason=What is an "equivalence query"?}} needed to learn a class of concepts according to the following [[Inequality (mathematics)|inequality]]:<math display="inline">FD(C) - 1\leq \#EQ(C)\leq \lceil FD(C)\ln(|C|)\rceil</math>.<ref name=":0" />
== References == {{Reflist}}
{{DEFAULTSORT:Concept Class}} [[Category:Computational learning theory]]