Inheritance Comes of Age: Applying Nonmonotonic Techniques to Problems in Industry

TL;DR

This paper argues that nonmonotonic reasoning, a powerful AI technique for handling plausible reasoning with exceptions, has been largely ignored by industry due to a focus on irrelevant "toy problems" and a lack of practical tools. The authors propose a strategy to bridge this gap by focusing on industry-relevant problems and developing tractable solutions, exemplified by a novel "Formula-Augmented Network" (FAN) for medical insurance benefits inquiry.

What Problem Does This Paper Address?

Artificial Intelligence (AI) research has long grappled with "nonmonotonic reasoning," a form of logic that allows for conclusions to be retracted when new information arises (e.g., inferring a bird can fly, then retracting that if it's a penguin). Despite its potential for handling real-world uncertainty and exceptions, this field has remained largely absent from industrial applications. The author posits two primary reasons for this disconnect:

  1. Focus on Irrelevant Problems: Much of the research in nonmonotonic reasoning has centered on abstract "commonsense reasoning" problems like the "Tweety" or "Yale Shooting" problems. While these are intellectually challenging, they don't directly address the practical, often data-driven, problems faced by industries.
  2. Lack of Practical Tools and Tractable Algorithms: Even when industry problems are considered, the computational complexity (decidability and tractability issues) of nonmonotonic logic and the absence of readily available, industrial-strength tools have hindered adoption. This creates a situation where researchers are isolated from industry, and industry has little to gain from engaging with the field.

The paper aims to demonstrate that nonmonotonic reasoning can be made relevant and useful to industry by focusing on practical problems and developing efficient, implementable solutions.

Methods

The core contribution of this paper is the introduction of a Formula-Augmented Network (FAN). This novel knowledge representation structure aims to bridge the gap between taxonomic (hierarchical) information and non-taxonomic (rule-based) information, which is crucial for many industry problems.

Here's how it works:

  • Inheritance Network with Exceptions: The foundation is a standard inheritance network, similar to those used in AI for representing class hierarchies (e.g., "a robin is a bird"). However, this network is extended to handle exceptions. For instance, while birds typically fly, a penguin is a bird that does not fly. This is achieved through "defeasible" links that can be canceled.
  • Formula Attachment: The key innovation is the ability to attach sets of logical formulas (wffs) directly to nodes in the inheritance network. These formulas represent "business rules" or other non-taxonomic information. For example, a rule about a 20% co-pay for diagnostic services could be attached to the "Diagnostic Services" node.
  • Wff-Inheritance Algorithm: The paper proposes an algorithm for "wff-inheritance." This algorithm determines which attached formulas (business rules) apply to a specific node, considering both the taxonomic hierarchy and potential exceptions. It prioritizes more specific rules and uses a "preferred maximally consistent subset" approach to handle potential conflicts between inherited rules. This algorithm is designed to be more efficient than simply combining all rules and then resolving conflicts.
  • Focus on Tractability: The authors emphasize the need for efficient algorithms. While general nonmonotonic logic can be undecidable, they highlight that inheritance with exceptions has tractable algorithms, and their FAN approach builds upon this.

Datasets

Not discussed in the paper. The paper focuses on a specific industrial problem (medical insurance benefits inquiry) and uses a conceptual example to illustrate its approach rather than relying on pre-existing datasets.

Key Insights and Ideas

  • The "Toy Problem" Trap: The paper powerfully argues that the continued focus on abstract commonsense reasoning problems is actively hindering the practical adoption of nonmonotonic reasoning. Industry needs solutions to their problems, not just elegant theoretical puzzles.
  • Bridging the Taxonomic and Rule-Based Divide: The FAN concept is a significant insight. It recognizes that real-world domains often have both hierarchical structures (taxonomies) and complex, exception-laden rules. The FAN provides a unified framework to represent and reason with both.
  • Inheritance of Rules is Non-Trivial: The paper demonstrates that simply inheriting attributes in a hierarchy is different from inheriting logical rules. The "wff-inheritance" algorithm is necessary because direct inheritance can lead to inconsistencies, and a more sophisticated approach is needed to select applicable rules.
  • Specificity and Preference Matter: The algorithm's reliance on specificity (more specific rules override general ones) and path ordering is a crucial mechanism for resolving conflicts and ensuring that the most relevant rules are applied. This mirrors how humans often reason.
  • The "Dilbertian" Nature of Industry: The anecdote about preferring an existing, but inadequate, tool over building a new, correct one highlights a pragmatic, albeit sometimes frustrating, reality of industrial software development. This underscores the need for not just good algorithms but also good tools.

Key Results

The paper doesn't present quantitative results in terms of accuracy or speedup on a benchmark dataset. Instead, its key results are:

  • A Novel Knowledge Representation (FAN): The introduction of the Formula-Augmented Network (FAN) as a mechanism to integrate taxonomic and non-taxonomic information.
  • A Wff-Inheritance Algorithm: The development of an algorithm for inheriting logical formulas (business rules) within the FAN framework, designed to handle exceptions and prioritize rules based on specificity.
  • Demonstration of Practical Applicability: The paper successfully applies these techniques to the complex domain of medical insurance benefits inquiry, showing how nonmonotonic reasoning can be used to determine coverage and associated rules.
  • Identification of Generalizable Principles: The authors outline criteria for identifying other industrial domains where FANs and wff-inheritance could be beneficial (domains with taxonomic information, linked non-taxonomic information, and mappable rules).

Limitations and Future Work

  • Computational Complexity: While the paper highlights tractable algorithms for inheritance with exceptions, inheriting general first-order wffs is still undecidable. The proposed wff-inheritance is NP-hard in the propositional case. The authors note that iterative computation and potential divide-and-conquer strategies can mitigate this in practice, but it remains a concern for very large or complex rule sets.
  • Tool Development: A significant limitation acknowledged is the lack of industrial-strength tools for implementing these nonmonotonic techniques. The authors emphasize the need to develop general tools for inheritance with exceptions and for wff-inheritance to facilitate broader adoption.
  • Preference Criteria: The current system implements specificity and path ordering for preference. However, the authors suggest future work could incorporate other preference criteria, such as explicit rule priorities or rules based on their entailments.
  • Mapping Rules to Wffs: The paper acknowledges that mapping complex business or legal rules into formal wffs can be non-trivial and requires further research.
  • Broader Industrial Adoption: The paper calls for continued effort to identify and solve industry problems using nonmonotonic reasoning, emphasizing the need for researchers to actively engage with industry and for management to support such initiatives.

Summary updated

BibTeX
@inproceedings{1997inheritance,
  title = {{Inheritance Comes of Age: Applying Nonmonotonic Techniques to Problems in Industry}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure