View source for Witness set

{{Short description|Computational learning concept}}
{{Use list-defined references|date=April 2025}}
{{CS1 config|mode=cs2}}

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

For a concept class with <math>|C|</math> concepts, there exists a concept that has a witness of size at most <math>\log_2|C|</math>; this bound is tight when <math>C</math> consists of all Boolean functions over <math>X</math>.{{r|jukna}} By a result of {{harvtxt|Bondy|1972}} there exists a single witness set of size at most <math>|C|-1</math> that is valid for all concepts in <math>C</math>; this bound is tight when <math>C</math> consists of the [[indicator function]]s of the [[empty set]] and some [[Singleton (mathematics)|singleton sets]].{{r|jukna|bondy}} One way to construct this set is to interpret the concepts as [[bitstring]]s, 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.{{r|fusion}}

The minimum size of a witness set for <math>c</math> is called the ''witness size'' or ''specification number'' and is denoted by <math>w_C(c)</math>. The value <math>\max\{w_C(c):c\in C\}</math> is called the [[teaching dimension]] of <math>C</math>. It represents the number of examples of a concept that need to be presented by a teacher to a learner, in the [[worst case analysis|worst case]], to enable the learner to determine which concept is being presented.{{r|gk}}

Witness sets have also been called teaching sets, keys, specifying sets, or discriminants.{{r|balbach}} The "witness set" terminology is from {{harvtxt|Kushilevitz|Linial|Rabinovich|Saks|1996}},{{r|balbach|klrs}} who trace the concept of witness sets to work by {{harvtxt|Cover|1965}}.{{r|klrs|cover}}

==References==
{{reflist|refs=

<ref name=balbach>{{citation
 | last = Balbach | first = Frank J.
 | doi = 10.1016/j.tcs.2008.02.025
 | issue = 1–3
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 2401488
 | pages = 94–113
 | title = Measuring teachability using variants of the teaching dimension
 | url = https://core.ac.uk/download/pdf/82471792.pdf
 | volume = 397
 | year = 2008}}</ref>

<ref name=bondy>{{citation
 | last = Bondy | first = J. A. | author-link = John Adrian Bondy
 | doi = 10.1016/0095-8956(72)90025-1
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | mr = 319773
 | pages = 201–202
 | title = Induced subsets
 | volume = 12
 | year = 1972| issue = 2 }}</ref>

<ref name=cover>{{citation
 | last = Cover | first = Thomas M. | author-link = Thomas M. Cover
 | date = June 1965
 | doi = 10.1109/pgec.1965.264137
 | issue = 3
 | journal = [[IEEE Transactions on Electronic Computers]]
 | pages = 326–334
 | title = Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition
 | volume = EC-14}}</ref>

<ref name=fusion>{{citation
 | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman
 | last2 = Willard | first2 = Dan E. | author2-link = Dan Willard
 | doi = 10.1016/0022-0000(93)90040-4
 | issue = 3
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 1248864
 | pages = 424–436
 | title = Surpassing the information-theoretic bound with fusion trees
 | volume = 47
 | year = 1993}}</ref>

<ref name=gk>{{citation
 | last1 = Goldman | first1 = Sally A. | author1-link = Sally Goldman
 | last2 = Kearns | first2 = Michael J. | author2-link = Michael Kearns (computer scientist)
 | doi = 10.1006/jcss.1995.1003
 | issue = 1
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 1322630
 | pages = 20–31
 | title = On the complexity of teaching
 | volume = 50
 | year = 1995}}</ref>

<ref name=jukna>{{citation
 | last = Jukna | first = Stasys
 | contribution = Chapter 11: Witness sets and isolation
 | doi = 10.1007/978-3-642-17364-6
 | isbn = 978-3-642-17363-9
 | pages = 155–163
 | publisher = Springer
 | title = Extremal Combinatorics
 | series = Texts in Theoretical Computer Science. An EATCS Series
 | year = 2011}}</ref>

<ref name=klrs>{{citation
 | last1 = Kushilevitz | first1 = Eyal
 | last2 = Linial | first2 = Nathan | author2-link = Nati Linial
 | last3 = Rabinovich | first3 = Yuri
 | last4 = Saks | first4 = Michael | author4-link = Michael Saks (mathematician)
 | doi = 10.1016/S0097-3165(96)80015-X
 | issue = 2
 | journal = [[Journal of Combinatorial Theory, Series A]]
 | mr = 1370141
 | pages = 376–380
 | series = 
 | title = Witness sets for families of binary vectors
 | url = https://www.cs.huji.ac.il/~nati/PAPERS/klrs.pdf
 | volume = 73
 | year = 1996}}</ref>

}}

{{DEFAULTSORT:Witness Set}}
[[Category:Computational learning theory]]


{{Comp-sci-theory-stub}}
{{machine-learning-stub}}