Sample exclusion dimension

In <a href="/facts/Computational_learning_theory/DKMoukIr">computational learning theory</a>, sample exclusion dimensions arise in the study of exact <a href="/facts/Concept_learning/9oao7d53">concept learning</a> with queries. 
In <a href="/facts/Algorithmic_learning_theory/1NMh5bn3">algorithmic learning theory</a>, a concept over a domain X is a <a href="/facts/Boolean_function/uT7E8pqC">Boolean function</a> over X. Here we only consider finite domains. A partial approximation S of a concept c is a Boolean function over 
 
 
 
 Y
 ⊆
 X
 
 
 {\displaystyle Y\subseteq X}
 
 such that c is an extension to S.
Let C be a class of concepts and c be a concept (not necessarily in C). Then a specifying set for c w.r.t. C, denoted by S is a partial approximation S of c such that C contains at most one extension to S. If we have observed a specifying set for some concept w.r.t. C, then we have enough information to verify a concept in C with at most one more mind change.
The exclusion dimension, denoted by XD(C), of a concept class is the maximum of the size of the minimum specifying set of c' with respect to C, where c' is a concept not in C.

Sample exclusion dimension open-in-new

Sample exclusion dimension