On learning Boolean functions

ABSTRACT

This paper deals with the learnability of Boolean functions. An intuitively appealing notion of dimensionality is developed and used to identify the most general class of Boolean function families that are learnable from polynomially many positive examples with one-sided error. It is then argued that although bounded DNF expressions lie outside this class, they must have efficient learning algorithms as they are well suited for expressing many human concepts. A framework that permits efficient learning of bounded DNF functions is identified.

REFERENCES

• 1: Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
• 2: A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
• 3: Feller, W. (1957). An introduction to Probability Theory and its Applications, John Wiley and Sons.
• 4: S Ryszard Michalski , G Jaime Carbonell , M Tom Mitchell, Machine learning an artificial intelligence approach volume II, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• 5: L. G. Valiant, A theory of the learnable, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.436-445, December 1984 [doi>10.1145/800057.808710]
• 6: Vapnik, V.N. & Chervonenkis, A.Ya. (1971). Theory of Probability and its Applications, Vol 16, pp264-280.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification