In computational learning theory

Computational learning theory

In theoretical computer science, computational learning theory is a mathematical field related to the analysis of machine learning algorithms.-Overview:Theoretical results in machine learning mainly deal with a type of...

, the teaching dimension of a concept class

Concept class

A concept over a domain X is a total Boolean function over X. A concept class is a class of concepts. Concept class is a subject of computational learning theory....

 C is defined to be , where is the minimum size of a witness set

Witness set

In computational learning theory, let C be a concept class over a domain X and c be a concept in C. A subset S of X is a witness set for c in C if c verifies c...

 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
then the teaching dimension of C is greater than k.