UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

On exact specification by examples

Anthony, M; Brightwell, G; Cohen, D; Shawe-Taylor, J; (1992) On exact specification by examples. In: UNSPECIFIED (pp. 311-318).

Full text not available from this repository.


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
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item