Learning to Reason

Abstract

We introduce a new framework for the study of reasoning. The Learning (in order) to Reason approach developed here 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 her favorite learning interface, and is also given a grace period in which she can interact with this interface and construct her representation KB of the world W. Her reasoning performance is measured only after this period, when she is presented with queries a from some query language, relevant to the world, and has to answer whether W implies a. The approach is meant to overcome the main computational difficulties in the traditional treatment of reasoning which stem from its separation from the "world". First, by allowing the reasoning task to interface the world (as in the known learning models), we avoid the rigid syntactic restriction on the intermediate knowledge representation. Second, we make explicit the dependence of the reasoning performance on the input from the environment. This is possible only because the agent interacts with the world when constructing her knowledge representation. We show how previous results from learning theory and reasoning illustrate the usefulness of the Learning to Reason approach by exhibiting new results that are not possible in the traditional setting. First, we give a Learning to Reason algorithm for a class 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 known to be learnable in the traditional sense.