Bias-Driven Revision of Logical Domain Theories

Moshe Koppel, Ronen Feldman, Alberto Maria Segre

TL;DR

This paper introduces Probabilistic Theory Revision (PTR), a novel approach to automatically refining logical domain theories using examples. PTR leverages probabilities to track "proof flow" through a theory, enabling efficient identification and correction of flawed elements, resulting in accurate and compact revised theories.

What Problem Does This Paper Address?

Building expert systems often involves creating domain theories that are initially "approximately correct" but contain inaccuracies. When these theories encounter real-world data, these inaccuracies become apparent, leading to misclassifications. The "theory revision problem" is about how to systematically update these knowledge bases based on examples that expose errors, aiming to produce a revised theory that is both consistent with the examples and as faithful as possible to the original. Existing approaches either struggle with computational complexity (proof enumeration) or lack transparency (neural networks).

Methods

PTR combines the strengths of existing methods by introducing an explicit "bias" in the form of probabilities assigned to each element (clause or literal) of the domain theory, representing the likelihood of it being flawed. This bias is made explicit from the start and is updated incrementally based on observed examples.

The core of PTR involves:

  • Probabilistic Representation: Domain theories are transformed into weighted directed graphs (dt-graphs).
  • Proof Flow Tracking: Probabilities are used to numerically track the "flow" of proofs through the dt-graph, quantifying the contribution of each element to a derivation.
  • Weight Updating: Probabilities (weights) are updated based on how well an exemplar is classified by the current theory. This is done using a bottom-up and then top-down pass through the dt-graph, similar to backpropagation but within a symbolic logic framework.
  • Flawed Element Identification: Edges whose weights drop below a "revision threshold" are identified as flawed.
  • Revision Operators: Four operators are used to repair flawed elements: adding/deleting literals from clauses, and adding/deleting clauses.
  • Bias and Radicality: The objective is to find the "most probable" revision, minimizing "radicality" (a measure of change) while ensuring correctness.

Datasets

The paper uses two main datasets:

  • Section 1 Example: A small, illustrative example of a soft-drink company investment theory.
  • PROMOTER Theory: A real-world dataset from molecular biology, previously used in theory revision literature.
  • Synthetic Theories: Artificially generated deeper theories with negated internal literals to test scalability and robustness.

Key Insights and Ideas

  • Probabilistic Bias as a Core Mechanism: Explicitly assigning probabilities to theory elements provides a principled way to define the "best" revision and enables incremental updates.
  • Proof Flow for Efficient Blame Assignment: Numerically tracking proof flow allows for efficient identification of which theory elements are responsible for misclassifications, avoiding exhaustive proof enumeration.
  • DT-Graphs for Unified Representation: Representing theories as dt-graphs allows for a unified approach to handling various types of revisions (clause, literal, negation) through edge manipulation.
  • Minimizing Radicality Balances Change and Accuracy: The concept of "radicality" provides a metric to balance syntactic changes with semantic impact, preventing overly drastic revisions.
  • Scalability to Deep Theories: PTR's approach is shown to scale well to deeper and more complex theories, unlike some previous methods.

Key Results

  • Accuracy: PTR consistently achieves high accuracy, often outperforming other methods, especially when leveraging initial bias. For the PROMOTER dataset, PTR* (a non-learning numerical system) achieved 94.3% accuracy without training examples.
  • Efficiency: PTR converges rapidly, requiring few cycles and a relatively small number of exemplars for training. The computational complexity per exemplar is linear in theory size.
  • Theory Size: Revised theories produced by PTR are generally compact and retain much of the original theory's structure, making them comprehensible.
  • Robustness: PTR is robust to random perturbations in initial weights.
  • Bias Effectiveness: User-provided guidance in initial weights significantly improves convergence speed and accuracy.

Limitations and Future Work

  • First-Order Theories: The current PTR approach is designed for propositional theories. Extending it to first-order logic, where predicate truth depends on variable assignments, is a significant area for future work.
  • Noisy Exemplars: The current framework assumes exemplars are correctly classified. Future work could involve modifying PTR to handle potentially misclassified exemplars.
  • Inductive Bias: While PTR uses bias to locate flawed elements, other types of bias (e.g., known constraints on revisions) could be incorporated to further improve performance.

Summary updated

Abstract

The theory revision problem is the problem of how best to go about revising a deficient domain theory using information contained in examples that expose inaccuracies. In this paper we present our approach to the theory revision problem for propositional domain theories. The approach described here, called PTR, uses probabilities associated with domain theory elements to numerically track the ``flow'' of proof through the theory. This allows us to measure the precise role of a clause or literal in allowing or preventing a (desired or undesired) derivation for a given example. This information is used to efficiently locate and repair flawed elements of the theory. PTR is proved to converge to a theory which correctly classifies all examples, and shown experimentally to be fast and accurate even for deep theories.
BibTeX
@article{koppel1994bias,
  author = {Moshe Koppel and Ronen Feldman and Alberto Maria Segre},
  title = {{Bias-Driven Revision of Logical Domain Theories}},
  journal = {J. Artif. Intell. Res.},
  year = {1994},
  url = {https://openreview.net/forum?id=8fmtm2XWxF},
}
Figure