Learning to Reason with a Restricted View

Roni Khardon, Dan RothMachine Learning 1999 · OpenReview

Abstract

The Learning to Reason (L2R) framework integrates the traditionally separate tasks of learning and reasoning into a unified computational process. In this paradigm, learning is conducted specifically to facilitate subsequent reasoning with the acquired knowledge. This paper investigates L2R problems where the agent's interaction with the environment is limited to partial information, represented as partial assignments. By exploring various interpretations of these partial views—Universal, Existential, and Abbreviated—we develop algorithms that demonstrate a fundamental tradeoff between learnability, the strength of available oracles, and the range of reasoning queries that can be accurately answered. Our results show that the combined task of learning and reasoning can be computationally tractable even when the individual components are not.

Introduction: Beyond the Silos of AI

In classical Artificial Intelligence, learning and reasoning are often treated as distinct silos. "Learning to Classify" focuses on predicting labels for new examples, while "Reasoning" focuses on deducing whether a statement ($\alpha$) follows from a known world model ($W$). This separation faces two major hurdles:

  1. Computational Intractability: Standard deductive reasoning, such as checking if a formula entails another, is often NP-hard.
  2. Partial Information: In real-world scenarios, agents rarely observe "total assignments" where every variable is known. Instead, they must operate with partial observations where many attributes are simply unknown.

The L2R framework addresses these by asking: Can an agent learn a representation of the world from partial observations that allows it to reason efficiently and accurately?

Methodology: Model-Based Reasoning

The authors utilize a Model-Based Reasoning (MBR) approach. Rather than storing a complex logical formula as a Knowledge Base (KB), the agent stores a collection of characteristic models (assignments of truth values). Reasoning then becomes a simple matter of checking if these models satisfy a query.

To handle the "Restricted View," three interpretations for partial assignments (where unknown variables are marked as *) are introduced:

  • Universal: The property holds for all possible ways to fill in the unknowns.
  • Existential: There is at least one way to fill in the unknowns such that the property holds.
  • Abbreviated: Unknowns are treated as 0, following a "closed-world" assumption.

Algorithms for Reasoning with Partial Views

The paper introduces several key algorithms designed to navigate these partial views:

  • Sample and Reason: A PAC-style (Probably Approximately Correct) algorithm that builds its KB from a random sample of partial observations. It is shown to be a valid PAC-L2R algorithm for any class of functions, provided the query distribution is "fair."
  • Lazy-MBR: A reasoning algorithm that works directly with partial models by checking if any model in the KB falsifies a clause in a query.
  • A-OL-NIMP: An on-line algorithm that updates its internal model whenever it makes a reasoning mistake. This algorithm specifically targets $k$-CNF queries and maintains a polynomial mistake bound.

Key Insights and Theoretical Results

The Combined Advantage

The most striking insight is that the joint task of learning-to-reason can be easier than the individual tasks. A world representation might be hard to learn and a query might be hard to reason about in isolation, but a learner can specifically seek out the "useful" parts of the world needed to answer a specific class of queries.

Tractability Boundaries

The research identifies $k$-CNF (clauses with at most $k$ literals) as a tractable boundary. If queries are restricted to $k$-CNF, reasoning with partial views remains efficient. However, the authors prove that reconstructing a full world model from these partial "windows" becomes impossible once the complexity exceeds certain thresholds.

Oracle Strength vs. Query Power

There is a direct tradeoff between the strength of the "oracles" an agent can access (like a Membership Oracle that answers questions about specific partial states) and the range of reasoning queries it can answer. The paper also bridges sub-fields by proving that Entailment Membership Oracles used in Inductive Logic Programming are essentially as powerful as Partial Membership Oracles in the L2R framework.

Conclusion and Future Directions

While currently limited to propositional logic, the L2R framework provides a robust path forward for efficient AI. Future work aims to extend these results to First-Order Logic (FOL) and develop "attribute-efficient" algorithms capable of handling environments with millions of features. By focusing on the end goal—reasoning—the L2R framework bypasses many of the computational bottlenecks inherent in traditional, siloed AI architectures.

Summary updated

Abstract

The Learning to Reason framework combines the study of Learning and Reasoning into a single task. Within it, learning is done specifically for the purpose of reasoning with the learned knowledge. Computational considerations show that this is a useful paradigm; in some cases learning and reasoning problems that are intractable when studied separately become tractable when performed as a task of Learning to Reason.In this paper we study Learning to Reason problems where the interaction with the world supplies the learner only partial information in the form of partial assignments. Several natural interpretations of partial assignments are considered and learning and reasoning algorithms using these are developed. The results presented exhibit a tradeoff between learnability, the strength of the oracles used in the interface, and the range of reasoning queries the learner is guaranteed to answer correctly.
BibTeX
@article{khardon1999learning,
  author = {Roni Khardon and Dan Roth},
  title = {{Learning to Reason with a Restricted View}},
  journal = {Machine Learning},
  year = {1999},
  url = {https://openreview.net/forum?id=C4D6ZLSphc},
}
Figure