Anthony, M;
Brightwell, G;
Cohen, D;
Shawe-Taylor, J;
(1992)
On exact specification by examples.
In:
UNSPECIFIED
(pp. 311-318).
Abstract
Some recent work in computational learning theory has discussed learning in situations where the teacher is helpful, and can choose to present carefully chosen sequences of labelled examples to the learner. We say a function t in a set H of functions (a hypothesis space) defined on a set X is specified by SqqX if the only function in H which agrees with t on S is t itself. The specification number σ(t) of t is the least cardinality of such an S. For a general hypothesis space, we show that the specification number of any hypothesis is at least equal to a parameter from [14] known as the testing dimension of H. We investigate in some detail the specification numbers of hypotheses in the set H n of linearly separable boolean functions: We present general methods for finding upper bounds on σ(t) and we characterize those t which have largest σ(t). We obtain a general lower bound on the number of examples required and we show that for all nested hypotheses, this lower bound is attained. We prove that for any tqqH n , there is exactly one set of examples of minimal cardinality (i.e., of cardinality σ(t)) which specifies t. We then discuss those tqqH n which have limited dependence, in the sense that some of the variables are redundant (i.e., there are irrelevant attributes), giving tight upper and lower bounds on σ(t) for such hypotheses. In the final section of the paper, we address the complexity of computing specification numbers and related parameters.
| Type: | Book chapter |
|---|---|
| Title: | On exact specification by examples |
| ISBN: | 089791497X |
| UCL classification: | UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | http://discovery.ucl.ac.uk/id/eprint/79086 |
Archive Staff Only
 |
View Item |