Subclass reachability

A sample ${\displaystyle s}$ is a partial function from ${\displaystyle X}$ to ${\displaystyle \{0,1\}}$.[1] Identifying a concept with its characteristic function mapping ${\displaystyle X}$ to ${\displaystyle \{0,1\}}$, it is a special case of a sample.[1]

Two samples are consistent if they agree on the intersection of their domains.[1] A sample ${\displaystyle s'}$ extends another sample ${\displaystyle s}$ if the two are consistent and the domain of ${\displaystyle s}$ is contained in the domain of ${\displaystyle s'}$.[1]

Suppose that ${\displaystyle C=S^{+}(X)}$. Then:

• the subclass ${\displaystyle \{\{x\}\}}$ is reachable with the sample ${\displaystyle s=\{(x,1)\}}$;[1]
• the subclass ${\displaystyle S^{+}(Y)}$ for ${\displaystyle Y\subseteq X}$ are reachable with a sample that maps the elements of ${\displaystyle X-Y}$ to zero;[1]
• the subclass ${\displaystyle S(X)}$, which consists of the singleton sets, is not reachable.[1]

Let ${\displaystyle C}$ be some concept class. For any concept ${\displaystyle c\in C}$, we call this concept ${\displaystyle 1/d}$-good for a positive integer ${\displaystyle d}$ if, for all ${\displaystyle x\in X}$, at least ${\displaystyle 1/d}$ of the concepts in ${\displaystyle C}$ agree with ${\displaystyle c}$ on the classification of ${\displaystyle x}$.[1] The fingerprint dimension ${\displaystyle FD(C)}$ of the entire concept class ${\displaystyle C}$ is the least positive integer ${\displaystyle d}$ such that every reachable subclass ${\displaystyle C'\subseteq C}$ contains a concept that is ${\displaystyle 1/d}$-good for it.[1] This quantity can be used to bound the minimum number of equivalence queries needed to learn a class of concepts according to the following inequality:${\textstyle FD(C)-1\leq \#EQ(C)\leq \lceil FD(C)\ln(|C|)\rceil }$.[1]