Learning Boolean formulas

ABSTRACT

Efficient distribution-free learning of Boolean formulas from positive and negative examples is considered. It is shown that classes of formulas that are efficiently learnable from only positive examples or only negative examples have certain closure properties. A new substitution technique is used to show that in the distribution-free case learning DNF (disjunctive normal form formulas) is no harder than learning monotone DNF. We prove that monomials cannot be efficiently learned from negative examples alone, even if the negative examples are uniformly distributed. It is also shown that, if the examples are drawn from uniform distributions, then the class of DNF in which each variable occurs at most once is efficiently weakly learnable (i.e., individual examples are correctly classified with a probability larger than 1/2 + 1/p, where p is a polynomial in the relevant parameters of the learning problem). We then show an equivalence between the notion of weak learning and the notion of group learning, where a group of examples of polynomial size, either all positive or all negative, must be correctly classified with high probability.

REFERENCES

• 1: ~ALDOUS, D. 1986. On the Markov chain simulation method for uniform combinatorial distribu- ~tions and simulated annealing. Tech. Rep. 60 Statistics Dept. Univ. California at Berkeley, ~Berkeley, Cahf.
• 2: ~ANGLUIN, D. AND VALIANT, L. G. 1979. Fast probabilistic algorithms for Hamfitoman circuits ~and matchings..I. Comput. Svst. Sc't. 18, 155-193.
• 3: Gyora M. Benedek , Alon Itai, Learnability by fixed distributions, Proceedings of the first annual workshop on Computational learning theory, p.80-90, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 4: 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]
• 5: ~CHERNOFF, H. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the ~sum of observations. Ann Math. Statistics 23, 493 509
• 6: A. Ehrenfeucht , David Haussler , Michael Kearns , Leslie Valiant, A general lower bound on the number of examples needed for learning, Proceedings of the first annual workshop on Computational learning theory, p.139-154, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 7: 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
• 8: ~GEREB-GRAuS, M. 1989. Complexity of learning from one-sided examples. Harvard Umv., ~Cambridge, Mass., unpublished manuscnpt.
• 9: D. Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Artificial Intelligence, v.36 n.2, p.177-221, September 1988 [doi>10.1016/0004-3702(88)90002-1]
• 10: David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 11: ~HELMBOLD, D., S/OAN, R., AND WARMU~H, M. 1988. Bootstrapping one-sided learning. Unpub- ~lished manuscript.
• 12: M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
• 13: ~KEARNS, M., Li, M., PITT, L, AND VALIANT, L. G. 1987b. Recent results on Boolean concept ~learning. In Proceedings of the 4th International B?;rkshop on Machine Lear?ring, Morgan-Kauf- ~mann, San Mateo, Calif., pp. 337-352.
• 14: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• 15: 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]
• 16: B. K. Natarajan, On learning Boolean functions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.296-304, January 1987, New York, New York, United States [doi>10.1145/28395.28427]
• 17: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• 18: ~PFIT, L., AND WARMUTH, M. K. 1988. Reductions among prediction problems: on the difficulty ~of predicting automata. In Proceedings of the 3rd IEEE Conference on Stnzcture t;z Complexity ~Theory. IEEE, New York, pp. 60-69.
• 19: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• 20: Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
• 21: Haim Shvaytser, A Necessary Condition for Learning from Positive Examples, Machine Learning, v.5 n.1, p.101-113, Mar. 1990 [doi>10.1023/A:1022663809420]
• 22: 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]
• 23: ~VALIANT, L. G. 1985. Learmng disjunctions of conjunctions. In Proceedings o} the 9th Interna- ~tional Joint Conference on Artificial Intelhgence. Morgan-Kaufmann, San Mateo, Calif., pp. ~560-566.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Theory

Keywords:
inductive inference, machine learning