Choosing Directions for Rules

Richard Treitel, Michael R. GeneserethAAAI 1986

Abstract

In logic programming and expert systems, a fundamental design choice involves determining whether a rule should be triggered by its data (forward inference) or by the goals it helps satisfy (backward inference). Historically, this "Directionality Dilemma" was resolved manually by programmers based on intuition. This paper presents a formal framework for optimizing the mix of forward and backward strategies. We demonstrate that for duplicate-free, recursion-free programs, the optimal strategy can be found in polynomial time using linear programming. However, the problem becomes NP-complete when duplicate answers or complex rule dependencies are introduced.

Introduction

Logic-based systems often struggle with the trade-offs between forward and backward chaining. Forward chaining starts with known facts and derives all possible conclusions, which can lead to the storage of irrelevant data. Conversely, backward chaining starts with a goal and works toward facts, which can be computationally expensive if sub-goals are repeatedly re-derived.

The challenge lies in minimizing the total computational cost—both CPU time and storage—by assigning directions to rules. Treitel and Genesereth (1986) address this by treating the selection of inference directions as a mathematical optimization problem, moving beyond the manual estimates previously used by system designers.

Methodology

The authors formalize the inference process using several key abstractions to model the flow of information and the associated costs.

The Rule Graph

A central component of the framework is the Rule Graph, a directed acyclic graph where nodes represent rules and arcs represent the flow of data (unification) between them. The graph structures the relationship between base facts, intermediate rules, and top-level goals.

Figure 1: The Rule Graph illustrates the flow of information between Facts, Rules, and Goals.

Coherent Strategies and Cost Estimation

To simplify the optimization, the authors introduce "coherent strategies." A strategy is coherent if a rule is used forwards only if all its predecessor rules (those providing its inputs) are also used forwards. This restriction prevents fragmented dependency chains and ensures a logical flow from data to goals.

To evaluate potential strategies, the authors employ cost estimation via simulation. Rather than running the full program, they represent sets of similar facts as "patterns" and apply probabilistic assumptions, such as the "Equal Frequency Assumption," to estimate the volume of results a rule will produce.

Optimization via Linear Programming

For "coherent" programs without duplicate answers, the cost-minimization problem is mapped to an integer program. A significant insight of the paper is that the specific constraints of this problem allow it to be solved using standard Linear Programming (LP) in polynomial time. Because the solution space naturally falls on integer values for this class of problem, the "Integer-to-Linear" shortcut provides an efficient path to the mathematically optimal strategy.

Complexity and Hard Cases

The paper identifies "duplicate answers" (different variable bindings leading to the same conclusion) as a primary source of complexity. When a rule's cost depends on whether a previous rule filtered out duplicates, the relationship becomes non-linear. This shift pushes the optimization problem into NP-complete territory. For these cases, the authors propose a heuristic search (A*) guided by a lower-bound estimate that assumes duplicates do not exist.

Key Results

The research establishes several theoretical and practical benchmarks for automated inference:

  • Complexity Proofs: Finding an optimal coherent strategy is proven to be polynomial-time for recursion-free, duplicate-free programs, and NP-complete otherwise.
  • Unified Objective Function: The framework successfully integrates both time (CPU cycles) and space (memory/disk for deduced facts) into a single objective function for optimization.
  • Automated Decision Making: The paper provides a roadmap for an inference engine that "compiles" logic programs by simulating costs and automatically assigning rule directions.

Limitations and Future Work

The current model is limited to acyclic rule graphs; estimating costs for recursive rules remains a significant challenge. Additionally, the optimization is static (performed at compile-time). Future research may explore adaptive or mixed methods that adjust strategies at run-time based on observed data distributions. Finally, the paper focuses on rule directionality but does not address the ordering of literals within a rule, which is another critical factor in performance.

Conclusion

Treitel and Genesereth provide a rigorous mathematical foundation for solving the Directionality Dilemma. By transforming a heuristic design choice into an optimization problem, they enable the development of more efficient, automated logic-based systems.

Reference: Treitel, R., & Genesereth, M. R. (1986). Choosing Directions for Rules. Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86), 153-157.

Summary updated

BibTeX
@inproceedings{treitel1986choosing,
  author = {Richard Treitel and Michael R. Genesereth},
  title = {{Choosing Directions for Rules}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure