A neuroidal architecture for cognitive computation

ABSTRACT

An architecture is described for designing systems that acquire and ma nipulate large amounts of unsystematized, or so-called commonsense, knowledge. Its aim is to exploit to the full those aspects of computational learning that are known to offer powerful solutions in the acquisition and maintenance of robust knowledge bases. The architecture makes explicit the requirements on the basic computational tasks that are to be performed and is designed to make this computationally tractable even for very large databases. The main claims are that (i) the basic learning and deduction tasks are provably tractable and (ii) tractable learning offers viable approaches to a range of issues that have been previously identified as problematic for artificial intelligence systems that are programmed. Among the issues that learning offers to resolve are robustness to inconsistencies, robustness to incomplete information and resolving among alternatives. Attribute-efficient learning algorithms, which allow learning from few examples in large dimensional systems, are fundamental to the approach. Underpinning the overall architecture is a new principled approach to manipulating relations in learning systems. This approach, of independently quantified arguments, allows propositional learning algorithms to be applied systematically to learning relational concepts in polynomial time and in modular fashion.

REFERENCES

• 1: John R. Anderson, The Architecture of Cognition, Harvard University Press, Cambridge, MA, 1983
• 2: Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
• 3: A. Blum , A. Frieze, A polynomial-time algorithm for learning noisy linear threshold functions, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.330, October 14-16, 1996
• 4: Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
• 5: E. Cohen, Learning noisy perceptrons by a perceptron in polynomial time, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.514, October 19-22, 1997
• 6: Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
• 7: Matthew L. Ginsberg, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 8: Andrew R. Golding , Dan Roth, A Winnow-Based Approach to Context-Sensitive Spelling Correction, Machine Learning, v.34 n.1-3, p.107-130, Feb. 1999 [doi>10.1023/A:1007545901558]
• 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, Learning Conjunctive Concepts in Structural Domains, Machine Learning, v.4 n.1, p.7-40, October 1989 [doi>10.1023/A:1022601210986]
• 11: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
• 12: Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
• 13: Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
• 14: KHARDON, R. 1996. Learning to take actions. In Proceedings of the National Conference on Artificial Intelligence. AAAI, Reston, Va., pp. 787-792.
• 15: Roni Khardon , Dan Roth , Leslie G. Valiant, Relational Learning for NLP using Linear Threshold Elements, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.911-919, July 31-August 06, 1999
• 16: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 17: 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]
• 18: Nick Littlestone, From on-line to batch learning, Proceedings of the second annual workshop on Computational learning theory, p.269-284, December 1989, Santa Cruz, California, United States
• 19: MCCARTHY, J. 1980. Circumscription-A form of non-monotonic reasoning. Artif. Int. 13, 27-39.
• 20: MCCARTHY, J., AND HAYES, P. J. 1969. Some philosophical problems from the standpoint of artificial intelligence. In Machine Intelligence, vol. 4. D. Michie, ed. American Elsevier, New York.
• 21: MCDERMOTT, D., AND DOYLE, J. 1980. Nonmonotonic logic I. Artif. Int. 13, 1, 41-72.
• 22: MILLER, G. A. 1956. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psych. Rev. 63, 81-97.
• 23: MINSKY, M. 1975. A framework for representing knowledge. In The Psychology of Computer Vision, P. H. Winston, ed. McGraw-Hill, New York.
• 24: Allen Newell, Unified theories of cognition, Harvard University Press, Cambridge, MA, 1990
• 25: Allen Newell, Human Problem Solving, Prentice-Hall, Inc., Upper Saddle River, NJ, 1972
• 26: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 27: 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]
• 28: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• 29: Ronald L. Rivest , Robert Sloan, A formal model of hierarchical concept learning, Information and Computation, v.114 n.1, p.88-114, Oct. 1994 [doi>10.1006/inco.1994.1081]
• 30: ROTH, D. 1995. Learning to reason: The non-monotonic case. In Proceedings of the International Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Francisco, Calif., pp. 1178-118.
• 31: Dan Roth, Learning to resolve natural language ambiguities: a unified approach, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.806-813, July 1998, Madison, Wisconsin, United States
• 32: ROTH, D., YANG, M.-H., AND AHUJA, N. 2000. A SNOW-based face detector. NIPS, To appear.
• 33: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 34: TURING, A. M. 1950. Computing machinery and intelligence. Mind 59, 433-460. (Reprinted in Collected Works of A. M. Turing: Mechanical Intelligence, (D.C. Ince, ed.), North-Holland, 1992).
• 35: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 36: 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]
• 37: VALIANT, L. G. 1985. Learning disjunctions of conjunctions. In Proceedings of the International Joint Conference on Artificial Intelligence (Los Angeles, Calif.). Morgan-Kaufmann, San Francisco, Calif.
• 38: Leslie G. Valiant, Circuits of the mind, Oxford University Press, Inc., New York, NY, 1994
• 39: Leslie G. Valiant, Rationality, Proceedings of the eighth annual conference on Computational learning theory, p.3-14, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225299]
• 40: Leslie G. Valiant, Projection Learning, Machine Learning, v.37 n.2, p.115-130, Nov.1.1999 [doi>10.1023/A:1007678005361]
• 41: Leslie G. Valiant, Robust logics, Artificial Intelligence, v.117 n.2, p.231-253, March 2000 [doi>10.1016/S0004-3702(00)00002-3]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.0 General
          Subjects: Cognitive simulation

General Terms:
Algorithms, Theory

Keywords:
PAC learning, cognitive computation, computational learning, learning relations, nonmonotonic reasoning, robust reasoning