Witness set
In combinatorics and computational learning theory, a witness set is a set of elements that distinguishes a given Boolean function from a given class of other Boolean functions. Let be a concept class over a domain and be a concept in . A subset of is a witness set for in if distinguishes from all the other functions in, in the sense that no other function in has the same values on.
For a concept class with concepts, there exists a concept that has a witness of size at most ; this bound is tight when consists of all Boolean functions over. By a result of there exists a single witness set of size at most that is valid for all concepts in ; this bound is tight when consists of the indicator functions of the empty set and some singleton sets. One way to construct this set is to interpret the concepts as bitstrings, and the domain elements as positions in these bitstrings. Then the set of positions at which a trie of the bitstrings branches forms the desired witness set. This construction is central to the operation of the fusion tree data structure.
The minimum size of a witness set for is called the witness size or specification number and is denoted by. The value is called the teaching dimension of. It represents the number of examples of a concept that need to be presented by a teacher to a learner, in the worst case, to enable the learner to determine which concept is being presented.
Witness sets have also been called teaching sets, keys, specifying sets, or discriminants. The "witness set" terminology is from, who trace the concept of witness sets to work by.