|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-95-010
On Specifying
Boolean Functions by Labelled Examples
Martin
Anthony
London School of Economics,
Graham
Brightwell
London School of Economics,
John
Shawe-Taylor
Royal Holloway, University of London
Abstract
We say a function $t$ in a set $H$ of $\{0,1\}$-valued functions defined
on a set $X$ is specified by $S \subseteq X$ if the only function
in $H$ which agrees with $t$ on $S$ is $t$ itself. The {\it specification
number} of $t$ is the least cardinality of such an $S$. For a general
finite class of functions, we show that the specification number of
any function in the class is at least equal to a parameter from~\cite{RS}
known as the testing dimension of the class. We investigate in some
detail the specification numbers of functions in the set of linearly
separable Boolean functions of $n $ variables---those functions $f$
such that $f^{-1}(\{0\})$ and $f^{-1}(\{1\})$ can be separated by
a hyperplane. We present general methods for finding upper bounds
on these specification numbers and we characterise those functions
which have largest specification number. We obtain a general lower
bound on the specification number and we show that for all {\it nested}
functions, this lower bound is attained. We give a simple proof of
the fact that for any linearly separable Boolean function, there is
exactly one set of examples of minimal cardinality which specifies
the function. We discuss those functions which have limited dependence,
in the sense that some of the variables are redundant (that is, there
are irrelevant attributes), giving tight upper and lower bounds on
the specification numbers of such functions. We then bound the average,
or expected, number of examples needed to specify a linearly separable
Boolean function. In the final section of the paper, we address the
complexity of computing specification numbers and related parameters.
Download Compressed
Postscript
|