Concept class

<h2 id="background">Background</h2>

A sample 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> from 
 
 
 
 X
 
 
 {\displaystyle X}
 
 to 
 
 
 
 {
 0
 ,
 1
 }
 
 
 {\displaystyle \{0,1\}}
 
.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> 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.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
Two samples are consistent if they agree on the intersection of their domains.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> 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'}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="examples">Examples</h2>
Suppose that 
 
 
 
 C
 =
 
 S
 
 +
 
 
 (
 X
 )
 
 
 {\displaystyle C=S^{+}(X)}
 
. Then:

<ul><li>the subclass 
 
 
 
 {
 {
 x
 }
 }
 
 
 {\displaystyle \{\{x\}\}}
 
 is reachable with the sample 
 
 
 
 s
 =
 {
 (
 x
 ,
 1
 )
 }
 
 
 {\displaystyle s=\{(x,1)\}}
 
;<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>[why?]</li>
<li>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;<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>[why?]</li>
<li>the subclass 
 
 
 
 S
 (
 X
 )
 
 
 {\displaystyle S(X)}
 
, which consists of the singleton sets, is not reachable.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>[why?]</li></ul>
<h2 id="applications">Applications</h2>
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}
 
.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> 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.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> This quantity can be used to bound the minimum number of equivalence queries needed to learn a class of concepts according to the following <a href="/facts/Inequality_(mathematics)/qkze4zdI">inequality</a>:
 
 
 
 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 }
 
.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Chase, H., & Freitag, J. (2018). Model Theory and Machine Learning. arXiv preprint arXiv:1801.06566. <a href="https://arxiv.org/abs/1801.06566" target="_blank">https://arxiv.org/abs/1801.06566</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf" target="_blank">https://www.sciencedirect.com/science/article/pii/S030439750300608X/pdf?md5=c06f6d6f5b10d73c3e05a1321128a67e&pid=1-s2.0-S030439750300608X-main.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

Concept class open-in-new

Concept class