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$ .{{r|jukna}}

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$ .{{r|jukna}} By a result of {{harvtxt|Bondy|1972}} 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.{{r|jukna|bondy}} 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.{{r|fusion}}

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.{{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=

{{citation

| last = Balbach | first = Frank J.

| doi = 10.1016/j.tcs.2008.02.025

| issue = 1–3

| 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}}

{{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 }}

{{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}}

{{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}}

{{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}}

{{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}}

{{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}}

}}

Category:Computational learning theory