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

For a concept class with ${\displaystyle |C|}$ concepts, there exists a concept that has a witness of size at most ${\displaystyle \log _{2}|C|}$ ; this bound is tight when ${\displaystyle C}$ consists of all Boolean functions over ${\displaystyle X}$ .^[1] By a result of Bondy (1972) there exists a single witness set of size at most ${\displaystyle |C|-1}$ that is valid for all concepts in ${\displaystyle C}$ ; this bound is tight when ${\displaystyle C}$ consists of the indicator functions of the empty set and some singleton sets.^[1][2] 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.^[3]

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

Witness sets have also been called teaching sets, keys, specifying sets, or discriminants.^[5] The "witness set" terminology is from Kushilevitz et al. (1996),^[5][6] who trace the concept of witness sets to work by Cover (1965).^[6][7]

References

1. Jukna, Stasys (2011), "Chapter 11: Witness sets and isolation", Extremal Combinatorics, Texts in Theoretical Computer Science. An EATCS Series, Springer, pp. 155–163, doi:10.1007/978-3-642-17364-6, ISBN 978-3-642-17363-9
2. Bondy, J. A. (1972), "Induced subsets", Journal of Combinatorial Theory, Series B, 12 (2): 201–202, doi:10.1016/0095-8956(72)90025-1, MR 0319773
3. Fredman, Michael L.; Willard, Dan E. (1993), "Surpassing the information-theoretic bound with fusion trees", Journal of Computer and System Sciences, 47 (3): 424–436, doi:10.1016/0022-0000(93)90040-4, MR 1248864
4. Goldman, Sally A.; Kearns, Michael J. (1995), "On the complexity of teaching", Journal of Computer and System Sciences, 50 (1): 20–31, doi:10.1006/jcss.1995.1003, MR 1322630
5. Balbach, Frank J. (2008), "Measuring teachability using variants of the teaching dimension" (PDF), Theoretical Computer Science, 397 (1–3): 94–113, doi:10.1016/j.tcs.2008.02.025, MR 2401488
6. Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael (1996), "Witness sets for families of binary vectors" (PDF), Journal of Combinatorial Theory, Series A, 73 (2): 376–380, doi:10.1016/S0097-3165(96)80015-X, MR 1370141
7. Cover, Thomas M. (June 1965), "Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition", IEEE Transactions on Electronic Computers, EC-14 (3): 326–334, doi:10.1109/pgec.1965.264137