Teaching dimension

In computational learning theory, the teaching dimension^[1] of a concept class C is defined to be ${\displaystyle \max _{c\in C}\{w_{C}(c)\}}$, where ${\displaystyle {w_{C}(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 of the concept class.

In '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

${\displaystyle 2^{k}{|X| \choose k},}$

then the teaching dimension of C is greater than k.

References[]

This artificial intelligence-related article is a stub. You can help Wikipedia by .

• v
• t

This robotics-related article is a stub. You can help Wikipedia by .

• v
• t