On exact specification by examples

ABSTRACT

Some recent work [7, 14, 15] 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 S***X if the only function in H which agrees with t on S is t itself. The specification number &sgr;(t) of t is the least cardinality of such an S. For a general hypothesis space, we show that the specification number of any hypotheis 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 Hn of linearly separable boolean functions: We present general methods for finding upper bounds on &sgr;(t) and we characterise those t which have largest &sgr;(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 t &egr; Hn, there is exactly one set of examples of minimal cardinality (i.e., of cardinality &sgr;(t)) which specifies t. We then discuss those t &egr; Hn 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 &sgr;(t) for such hypotheses. In the final section of the paper, we address the complexity of computing specification numbers and related parameters.

REFERENCES

• 1: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 2: Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
• 3: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 4: Béla Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, New York, NY, 1986
• 5: John C. Cherniavsky , Mahendran Velauthapillai , Richard Statman, Inductive inference: an abstract approach, Proceedings of the first annual workshop on Computational learning theory, p.251-266, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Sally A. Goldman , Michael J. Kearns, On the complexity of teaching, Proceedings of the fourth annual workshop on Computational learning theory, p.303-314, August 05-07, 1991, Santa Cruz, California, United States
• 8: Sally A. Goldman, Michael J. Kearns and Robert E. Schapire, Exact identification of circuits using fixed points of amplification functions, In Proceedings of the Thirty-First Annual Symposium on Foundations of Computer Sczence, 1990.
• 9: S E Hampson , D J Volper, Linear function neurons: Structure and training, Biological Cybernetics, v.53 n.4, p.203-218, Feb. 1986 [doi>10.1007/BF00336991]
• 10: D.S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and Systems Sciences, 9: 256-278, 1974.
• 11: R.M. Karp, Reducibility among combinatorial problems. In Complezity of Computer Computations (ed. R.E. Miller and J.W. Thatcher): Plenum Press, New York, 1972.
• 12: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 13: S. Muroga, Threshold Logic and its Applications: Wiley, New York, 1971.
• 14: Kathleen Romanik and Carl Smith, Testing geometric objects, to appear.
• 15: Kathleen Romanik, Testing as a dual to learning, University of Maryland at College Park, College Park, MD, 1991
• 16: N. Sauer, On the density of families of sets, J. Comb. Theory (A), 13, 1972: 145-147.
• 17: Ayumi Shinohara , Satoru Miyano, Teachability in computational learning, New Generation Computing, v.8 n.4, p.337-347, 1991 [doi>10.1007/BF03037091]
• 18: E. Sperner, Ein Satz fiber Untermengen einer endlichen Menge, Math. Z., 27, 1928: 544-548.
• 19: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 20: V.N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2), 1971: 264-280.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory, Verification