Content deleted Content added
+sentence, +reference, -single source template |
Duckmather (talk | contribs) wrote text, removed redundant reference, proposed merge |
||
Line 3:
<!-- Once discussion is closed, please place on talk page: {{Old AfD multi|page=Subclass reachability|date=25 November 2021|result='''keep'''}} -->
<!-- End of AfD message, feel free to edit beyond this point -->
{{Multiple issues|{{one source|date=December 2021}}
{{orphan|date=November 2011}}
{{context|date=February 2011}}}}{{Merge|Concept class
| date = December 2021
}}
In [[computational learning theory]] in [[mathematics]], given a [[Concept class|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"
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 -->
▲In [[computational learning theory]] in [[mathematics]], given a [[Concept class|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">{{Cite book|last=Abe|first=Naoki|url=https://books.google.com/books?id=snJrCQAAQBAJ&newbks=0&printsec=frontcover|title=Algorithmic Learning Theory: 12th International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001. Proceedings.|last2=Khardon|first2=Roni|last3=Zeugmann|first3=Thomas|date=2003-06-30|publisher=Springer|isbn=978-3-540-45583-7|language=en}}</ref> Not every subclass ''D'' is reachable.<ref>{{cite journal |url=https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf |format=pdf |pages=188-191 |last=Angluin |first=D. |year=2004 |title=Queries revisited |journal=Theoretical Computer Science |volume=313 |issue=2}}</ref>
== 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 ==
| |||