Computational limitations on learning from examples

ABSTRACT

The computational complexity of learning Boolean concepts from examples is investigated. It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP. These classes include (a) disjunctions of two monomials, (b) Boolean threshold functions, and (c) Boolean formulas in which each variable occurs at most once. Relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.

REFERENCES

• 1: ANGLUIN, D. On the complexity of minimum inference of regular sets. Inf. Control 39 (1978), 337-350.
• 2: ANGLUIN, D. Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21 (1980), 46-62.
• 3: ANGLUIN, D.Inductive inference of formal languages from positive data. Inf. Control 45 (1980), 117-135.
• 4: Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982 [doi>10.1145/322326.322334]
• 5: ANGLUIN, D. Remarks on the difficulty of finding a minimal disjunctive normal form for Boolean functions. Unpublished manuscript.
• 6: ANGLUIN, n. Learning regular sets from queries and counter-examples. Yale University Tech. Rep. YALEU/DCS/464, 1986.
• 7: 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]
• 8: BLUM, L., AND BLUM, M. Toward a mathematical theory of inductive inference. Inf. Control 28 (1975), 125-155.
• 9: 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]
• 10: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 11: CASE, J., AND SMITH, C. Comparison of identification criteria for machine inductive inference. Theoret. Comput. Sci. 25 (1983), 193-220.
• 12: CHVATAL, V. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 3 (1979), 233-235.
• 13: DALEY, R. On the error correcting power of pluralism in BC-type inductive inference. Theoret. Comput. Sci. 24 (1983), 95-104.
• 14: DIETTERICH, T. C., AND MICHALSKI, R.S. A comparative review of selected methods for learning from examples. In Machine Learning. An Artificial Intelligence Approach. Tioga, Palo Alto, Calif., 1983.
• 15: R. V. Freivald, Functions Computable in the Limit by Probabilistic Machines, Proceedings of the 3rd Symposium on Mathematical Foundations of Computer Science, p.77-87, June 17-22, 1974
• 16: FREIVALD, R.V. Finite identification of general recursive functions by probabilistic strategies. In Proceedings of the Conference on Algebraic, Arithmetic, and Categorial Methods in Computation Theory. Akadamie-Verlag, New York, 1979, pp. 138-145.
• 17: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 18: 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
• 19: GILL, J. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 675-695.
• 20: GOLD, E.M. Complexity of automaton identification from given data. Inf. Control 37 (1978), 302-320.
• 21: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 22: HA USSLER, D. Quantifying the inductive bias in concept learning. In Proceedings of AAAI-86 (Philadelphia, Pa.). Morgan Kaufman, Los Altos, Calif., 1986, pp. 485-489.
• 23: James Jay Horning, A study of grammatical inference, 1969
• 24: JOHNSON, D. S. Worst case behaviour of graph coloring algorithms. In Proceedings of the 5th South-Eastern Conference on Combinatorics, Graph Theory, and Computing. Utilitas Mathematica, Winnipeg, Canada, 1974, pp. 513-528.
• 25: LEVIN, L. Universal sorting problems. Prob. Pered. Inf. 9, 3 (1973), pp. I 15-116.
• 26: 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
• 27: PITT, L. A characterization of probabilistic inference. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Washington, D.C., 1984, pp. 485-494.
• 28: PODNIEKS, K.M. Probabilistic synthesis of enumerated classes of functions. Soy. Math. Dokl. 16 (1975), I042-1045.
• 29: James S Royer, Inductive inference of approximations, Information and Control, v.70 n.2-3, p.156-178, Aug/Sept. 1986 [doi>10.1016/S0019-9958(86)80002-X]
• 30: RUDICH, S. Inferring the structure of a Markov chain from its output. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Washington, D.C., 1985, pp. 321-325.
• 31: SMITH, C. H., AND VELAUTHAPILLAI, M. On the inference of approximate programs. Tech. Rep. 1427, Dept. of Computer Science, Univ. of Maryland, College Park, Md.
• 32: 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]
• 33: VALIANT, L. G. Learning disjunctions of conjunctions. In Proceedings of the 9th IJCAI (Los Angeles, Calif., Aug. 1985), vol. 1. Morgan Kaufman, Los Altos, Calif., 1985, pp. 560-566.
• 34: WIEHAGEN, R., FREIVALD, R., AND KINBER, E. B. On the power of probabilistic strategies in inductive inference. Theoret. Comput. Sci. 28 (1984), I I 1-133.
• 35: Avi Wigderson, A new approximate graph coloring algorithm, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.325-329, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802207]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning; Induction

General Terms:
Experimentation, Theory, Verification