A theory of the learnable

ABSTRACT

Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. We find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. The methodology and results suggest concrete principles for designing realistic learning systems.

REFERENCES

• 1: D. Angluin and C.H. Smith. "A Survey of Inductive Inference: Theory and Methods." Yale University, Computer Science Department Tech. Report 250, October 1982.
• 2: Avron Barr , Edward A. Feigenbaum, Handbook of AI, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 4: R.O. Duda and P.F. Hart.Pattern Classification and Scene Analysis. Wiley, New York (1973).
• 5: P. Erdös and J. Spencer. Probabilistic Methods in Combinatorics. Academic Press, New York (1974).
• 6: 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
• 7: S. Skyum and L.G. Valiant. "A Complexity Theory based on Boolean Algebra." Proc. of 22nd IEEE Symp. on Foundations of Computer Science, (1981), 244-253.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Human Factors, Theory