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 $C$ be a concept class over a domain $X$ (that is, a family of Boolean functions over $X$) and $c$ be a concept in $X$ (a single Boolean function). A subset $S$ of $X$ is a witness set for $c$ in $X$ if $S$ distinguishes $c$ from all the other functions in $C$, in the sense that no other function in $C$ has the same values on $S$.Template:R

For a concept class with $|C|$ concepts, there exists a concept that has a witness of size at most ${\log }_2|C|$; this bound is tight when $C$ consists of all Boolean functions over $X$.Template:R By a result of Template:Harvtxt there exists a single witness set of size at most $|C|-1$ that is valid for all concepts in $C$; this bound is tight when $C$ consists of the indicator functions of the empty set and some singleton sets.Template:R 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.Template:R

The minimum size of a witness set for $c$ is called the witness size or specification number and is denoted by $w_C(c)$. The value $\max \{w_C(c):c\in C\}$ is called the teaching dimension of $C$. 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.Template:R

Witness sets have also been called teaching sets, keys, specifying sets, or discriminants.Template:R The "witness set" terminology is from Template:Harvtxt,Template:R who trace the concept of witness sets to work by Template:Harvtxt.Template:R

References

Template:Comp-sci-theory-stub Template:Machine-learning-stub