1 Answers
In computational learning theory, the teaching dimension of a concept class C is defined to be max c ∈ C { w C } {\displaystyle \max _{c\in C}\{w_{C}\}} , where w C {\displaystyle {w_{C}}} is the minimum size of a witness set for c in C.
The teaching dimension of a finite concept class can be used to give a lower and an upper bound on the membership query cost of the concept class.
In Stasys Jukna's book "Extremal Combinatorics", a lower bound is given for the teaching dimension:
Let C be a concept class over a finite domain X. If the size of C is greater than
4 views
Answered