A Deductive Pattern Matcher

Robert M. MacGregorAAAI 1988

TL;DR

This paper introduces LOOM, a novel pattern matcher for knowledge representation systems that goes beyond traditional matching by incorporating deductive reasoning. By blending forward and backward chaining, LOOM can infer more complex relationships and maintain knowledge more efficiently, offering a significant improvement over existing classification-based approaches.

What Problem Does This Paper Address?

Knowledge representation systems (KRS) are designed to store and reason about information. A core component of many KRS is a pattern matcher, which determines if a piece of information (an individual) fits a given description (a concept or pattern). Traditional classification-based pattern matchers, common in KL-ONE-style systems, work by abstracting an individual and then classifying this abstraction against known concepts. However, these systems often struggle with expressiveness and efficiency. They can be limited in the complexity of patterns they can handle and may recompute a lot of information unnecessarily. This paper addresses the need for a more powerful and efficient pattern matcher that can leverage deductive reasoning to better understand and manage complex knowledge.

Methods

LOOM employs a "deductive pattern matcher" built around a classifier. The key innovations are:

  • Rich Pattern-Forming Language: LOOM's language allows for complex concept definitions using relational algebra operators, including quantifiers (e.g., :at-least 1 child) and role restrictions. Crucially, it supports implications (:implies) between concepts, enabling recursive definitions and more sophisticated reasoning.
  • Abstraction/Classification (A/C) with Backward Chaining: Instead of generating a complete abstraction upfront, LOOM builds abstractions incrementally. During classification, it uses backward chaining to ask questions about the individual, effectively interrogating the knowledge base to gather necessary information. This avoids wasting computation on irrelevant details.
  • HITS and MISSES Lists: Each database object maintains lists of "HITS" (questions that received positive answers) and "MISSES" (questions that received non-positive answers). When an individual's attributes change, these lists are checked. If HITS remain positive and MISSES remain negative, the type doesn't need recomputation, significantly reducing overhead.
  • Truth Maintenance: The system continuously maintains the "type" (the set of most-specific concepts an individual matches) for all database objects. This process implicitly handles truth maintenance for unary predicates.

Datasets

Not discussed in the paper. The paper focuses on the design and architecture of the LOOM system and illustrates its functionality with examples derived from the system's own concept definitions (e.g., defining concepts like Person, Father, Successful-Father, and a Lisp list structure).

Key Insights and Ideas

  • Deduction as a Core Matching Component: The paper argues that deductive inference shouldn't be a separate step but an integral part of pattern matching. LOOM's classifier actively uses logical deductions to determine matches.
  • Incremental Abstraction is Key to Efficiency: Building abstractions piece-by-piece, guided by backward chaining, is far more efficient than pre-computing a full, potentially oversized, abstraction.
  • HITS/MISSES for Smart Recomputation: The HITS and MISSES lists are a clever mechanism to avoid redundant type recomputations. If the conditions that previously led to a match or non-match are still met, the system knows not to re-evaluate.
  • Implications Enable Powerful Patterns: The :implies construct is crucial for defining more expressive patterns, particularly for recursive structures like lists, which are difficult to handle with simpler pattern languages.
  • Bridging Terminological and Assertional Knowledge: LOOM allows implications, which are often considered assertional knowledge, to contribute to pattern definitions, blurring the lines and increasing reasoning power.

Key Results

The paper doesn't present quantitative results from large-scale experiments. Instead, it focuses on the architectural design and demonstrates its capabilities through detailed examples:

  • Increased Expressiveness: LOOM can define and match more complex patterns, including recursive ones, due to the :implies operator.
  • Improved Efficiency: The incremental abstraction and HITS/MISSES lists are expected to make LOOM significantly more efficient than previous classification-based matchers by reducing redundant computations and classifications.
  • Integrated Deductive Reasoning: The system successfully integrates deductive inference into the pattern matching process, allowing it to infer matches that would require separate reasoning steps in other systems.

Limitations and Future Work

  • Production Rule Integration: While designed for it, the paper notes that LOOM does not currently provide a production rule facility, though a separate language is being built on top of it.
  • Control Mechanism: LOOM's pattern language, with its single free variable, is not intended to be a sole control mechanism for a program. It's designed to work in conjunction with another programming language (like Lisp), and the design of such a combined language is a topic for future research.
  • Practical Implications: The paper briefly touches on the practical implications of the architecture, suggesting that the communication between database objects for truth maintenance is a key benefit.
  • Future Research: The authors suggest future work on integrating LOOM with production rule systems and designing a more comprehensive programming language that leverages LOOM's capabilities.

Summary updated

BibTeX
@inproceedings{macgregor1988deductive,
  author = {Robert M. MacGregor},
  title = {{A Deductive Pattern Matcher}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}

Loading related content...

Figure