ON SPECIFYING BOOLEAN FUNCTIONS BY LABELED EXAMPLES

We say a function t in a set H of {0,1}-valued functions defined on a set X is specified by S subset of or equal to X if the only function i n H which agrees with t on S is t itself. The 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 t he class is at least equal to a parameter from Romanik and Smith (1990 ) known as the testing dimension of the class. We investigate in some detail the specification numbers of functions in the set of linearly s eparable Boolean functions of n variables - those functions f such tha t f(-1)({0}) and f(-1)({1}) can be separated by a hyperplane. We prese nt general methods for finding upper bounds on these specification num bers and we characterise those functions which have largest specificat ion number. We obtain a general lower bound on the specification numbe r and we show that for all nested functions, this lower bound is attai ned. We give a simple proof of the fact that for any linearly separabl e Boolean function, there is exactly one set of examples of minimal ca rdinality which specifies the function. We discuss those functions whi ch have limited dependence, in the sense that some of the variables ar e redundant (that is, there are irrelevant attributes), giving tight u pper and lower bounds on the specification numbers of such functions. We then bound the average, or expected, number of examples needed to s pecify a linearly separable Boolean function. In the final section of the paper, we address the complexity of computing specification number s and related parameters.