Witness set
Encyclopedia
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(S) verifies c (i.e., c is the only consistent concept with respect to c(S)). The minimum size of a witness set for c is called the witness size or specification number and is denoted by
. The value 
is called the teaching dimension of C.
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...
, let C be 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....
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(S) verifies c (i.e., c is the only consistent concept with respect to c(S)). The minimum size of a witness set for c is called the witness size or specification number and is denoted by
. The value is called the teaching dimension of C.