Learning to reason

ABSTRACT

We introduce a new framework for the study of reasoning. The Learning (in order) to Reason approach developed here views learning as an integral part of the inference process, and suggests that learning and reasoning should be studied together.The Learning to Reason framework combines the interfaces to the world used by known learning models with the reasoning task and a performance criterion suitable for it. In this framework, the intelligent agent is given access to its favorite learning interface, and is also given a grace period in with it can interact with this interface and construct a representation KB of the world W. The reasoning performance is measured only after this period, when the agent is presented with queries &agr; from some query language, relevant to the world, and has to answer whether W implies &agr;.The approach is meant to overcome the main computational difficulties in the traditional treatment of reasoning which stem from its separation from the “world”. Since the agent interacts with the world when construction its knowledge representation it can choose a representation that is useful for the task at hand. Moreover, we can now make explicit the dependence of the reasoning performance on the environment the agent interacts with.We show how previous results from learning theory and reasoning fit into this framwork and illustrate the usefulness of the Learning to Reason approach by exhibiting new results that are not possible in the traditional setting. First, we give Learning to Reason algorithms for classes of propositional languages for which there are no efficient reasoning algorithms, when represented as a traditional (formula-based) knowledge base. Second, we exhibit a Learning to Reason algorithm for a class of propositional languages that is not know to be learnable in the traditional sense.

REFERENCES

• 1: AMSTERDAM, J. 1988. Extending the Valiant learning model. In Proceeding of the 5th International Workshop on Machine Learning. pp. 364-375.
• 2: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 3: Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129746]
• 4: Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
• 5: Dana Angluin , Donna K. Slonim, Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle, Machine Learning, v.14 n.1, p.7-26, Jan. 1994 [doi>10.1023/A:1022642604085]
• 6: BACCHUS, F., GROVE, A., HALPERN, J. Y., AND KOLLER, D. 1993. Statistical foundations for default reasoning. In Proceedings of the International Joint Conference of Artificial Intelligence. 563-569.
• 7: Fahiem Bacchus , Adam J. Grove , Joseph Y. Halpern , Daphne Koller, From statistical knowledge bases to degrees of belief, Artificial Intelligence, v.87 n.1-2, p.75-143, Nov. 1996 [doi>10.1016/S0004-3702(96)00003-3]
• 8: Rodney A. Brooks, Intelligence without representation, Artificial Intelligence, v.47 n.1-3, p.139-159, Jan. 1991 [doi>10.1016/0004-3702(91)90053-M]
• 9: Nader H. Bshouty, Exact learning Boolean functions via the monotone theory, Information and Computation, v.123 n.1, p.146-153, Nov. 15, 1995 [doi>10.1006/inco.1995.1164]
• 10: Marco Cadoli, Tractable Reasoning in Artificial Intelligence, Springer-Verlag New York, Inc., Secaucus, NJ, 1995
• 11: Rina Dechter , Judea Pearl, Structure identification in relational data, Artificial Intelligence, v.58 n.1-3, p.237-270, Dec. 1992 [doi>10.1016/0004-3702(92)90009-M]
• 12: Jon Doyle , Ramesh S. Patil, Two theses of knowledge representation: language restrictions, taxonomic classification, and the utility of representation services, Artificial Intelligence, v.48 n.3, p.261-297, April 1991 [doi>10.1016/0004-3702(91)90029-J]
• 13: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 14: FRAZIER, M., AND PITT. L. 1993. Learning from entailment: An application to propositional Horn sentences. In Proceedings of the International Conference on Machine Learning. Morgan-Kaufmann, San Mateo, Calif.
• 15: GREINER, R., GROVE, A., AND ROTH, D. 1996. Learning active classifiers. In Proceedings of the International Conference on Machine Learning.
• 16: HAUSSLER, D. 1987. Bias, version spaces and Valiant's learning framework. In Proceedings of the 4th International Workshop on Machine Learning. Univ. California, Irvine, Irvine, Calif.
• 17: HENRION, M. 1988. Propagating uncertainty in Bayesian networks by probabilistic logic sampling. In Uncertainty in Artificial Intelligence.
• 18: JACKSON, J. 1994. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. In Proceedings of the IEEE Symposium on Foundation of Computer Science. IEEE, New York, pp. 42-53.
• 19: KAUTZ, H., KEARNS, M., AND SELMAN, B. 1993. Reasoning with characteristic models. In Proceedings of the National Conference on Artificial Intelligence. pp. 34-39.
• 20: Henry Kautz , Michael Kearns , Bart Selman, Horn approximations of empirical data, Artificial Intelligence, v.74 n.1, p.129-145, March 1995 [doi>10.1016/0004-3702(94)00072-9]
• 21: KEARNS, M. 1992. Oblivious pac learning of concepts hierarchies. In Proceedings of the National Conference on Artificial Intelligence. pp. 215-222.
• 22: Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
• 23: KHARDON, R. 1996. Learning to take actions. In Proceedings of the National Conference on Artificial Intelligence. pp. 787-792.
• 24: Roni Khardon , Dan Roth, Learning to reason with a restricted view, Proceedings of the eighth annual conference on Computational learning theory, p.301-310, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225335]
• 25: Roni Khardon , Dan Roth, Reasoning with models, Artificial Intelligence, v.87 n.1-2, p.187-213, Nov. 1996 [doi>10.1016/S0004-3702(96)00006-9]
• 26: Roni Khardon , Dan Roth, Reasoning with models, Artificial Intelligence, v.87 n.1-2, p.187-213, Nov. 1996 [doi>10.1016/S0004-3702(96)00006-9]
• 27: David Kirsh, Foundations of AI: the big issues, Artificial Intelligence, v.47 n.1-3, p.3-30, Jan. 1991 [doi>10.1016/0004-3702(91)90048-O]
• 28: Hector J. Levesque, Foundations of a functional approach to knowledge representation., Artificial Intelligence, v.23 n.2, p.155-212, July 1984 [doi>10.1016/0004-3702(84)90009-2]
• 29: H J Levesque, Making believers out of computers, Artificial Intelligence, v.30 n.1, p.81-108, Oct. 1986 [doi>10.1016/0004-3702(86)90068-8]
• 30: LEVESQUE, H. 1992. Is reasoning too hard? In Proceeding of the 3rd NEC Research Symposium.
• 31: LEVESQUE, H., AND BRACHMAN, R. 1985. A fundamental tradeoff in knowledge representation and reasoning. In Readings in Knowledge Representation, R. Brachman and H. Levesque, eds. Morgan- Kaufman, San Mateo, Calif.
• 32: 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]
• 33: MCCARTHY, J. 1985. Programs with common sense. In Readings in Knowledge Representation, 1985, R. Brachman and H. Levesque, eds. Morgan-Kaufmann, San Mateo, Calif.
• 34: Yoram Moses , Moshe Tennenholtz, Off-line reasoning for on-line efficiency: knowledge bases, Artificial Intelligence, v.83 n.2, p.229-239, June 1996 [doi>10.1016/0004-3702(95)00015-1]
• 35: Nils J. Nilsson, Probabilistic logic, Artificial Intelligence, v.28 n.1, p.71-88, Feb. 1986 [doi>10.1016/0004-3702(86)90031-7]
• 36: Nils J. Nilsson, Logic and artificial intelligence, Artificial Intelligence, v.47 n.1-3, p.31-56, Jan. 1991 [doi>10.1016/0004-3702(91)90049-P]
• 37: Christos H. Papadimitriou, On selecting a satisfying truth assignment (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.163-169, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185365]
• 38: ROTH, D. 1995. Learning to reason: The non-monotonic case. In Proceedings of the International Joint Conference of Artificial Intelligence. pp. 1178-1184.
• 39: Dan Roth, On the hardness of approximate reasoning, Artificial Intelligence, v.82 n.1-2, p.273-302, April 1996 [doi>10.1016/0004-3702(94)00092-1]
• 40: Bart Selman, Tractable default reasoning, University of Toronto, Toronto, Ont., Canada, 1992
• 41: Bart Selman , Henry Kautz, Knowledge compilation and theory approximation, Journal of the ACM (JACM), v.43 n.2, p.193-224, March 1996 [doi>10.1145/226643.226644]
• 42: SHASTRI, L. 1993. A computational model of tractable reasoning--Taking inspiration from cognition. In Proceeding of the International Joint Conference of /trtificial Intelligence (Aug.). pp. 202-207.
• 43: 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]
• 44: VALIANT, L. G. 1985. Learning disjunctions of conjunctions. In Proceedings of the International Joint Conference of/trtificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 560-566.
• 45: Leslie G. Valiant, Circuits of the mind, Oxford University Press, Inc., New York, NY, 1994
• 46: 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]
• 47: L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms, Theory

Keywords:
common sense reasoning, computational learning, knowledge representation, model-based reasoning