Abstract
Finding the most efficient explanation for a set of observations, known as abduction, is a fundamental challenge in artificial intelligence. This paper introduces a novel "cost-sharing" heuristic for minimal-cost proofs that significantly improves search efficiency. By prorating the costs of hypotheses across the multiple observations they explain, the authors develop a search method that is faster than traditional "blind" approaches while remaining mathematically guaranteed to find the optimal solution.
The Challenge of Abduction
In AI reasoning, abduction is the process of finding the best explanation for a set of observations. This is often modeled as a minimal-cost proof: given a set of logical rules and a set of possible "hypotheses" (assumptions) with associated costs, the goal is to find the set of hypotheses that proves the observations at the lowest total cost.
The primary difficulty is that finding these proofs is an NP-hard problem. Researchers typically employ a "best-first search" to navigate the vast tree of potential proofs. However, the standard heuristic previously used was "cost-so-far," which only considers the costs already incurred during the search. Because costs in these models are attached to the hypotheses—the "leaves" or endpoints of the logic tree—a search starting from the observations (the "root") is essentially "blind" until it reaches the bottom of a branch. This lack of early guidance leads to the exploration of many unnecessary paths.
The Cost-Sharing Heuristic ($)
To address this, the authors propose a new heuristic, denoted as $, which estimates the cost of a partial proof by looking "down" the logic graph toward the hypotheses. The core innovation is the concept of Cost Sharing. In many logic graphs, a single hypothesis might explain multiple observations. For instance, an expensive hypothesis like a "black-out" (costing 8 units) might be more efficient than multiple cheaper hypotheses if it explains both "neighbor's lights off" and "my power off."
The $ estimator is a recursive function that propagates costs from the leaves toward the root. It follows two primary rules:
- AND nodes: The estimate is the sum of the estimates of its children.
- OR nodes: The estimate is the minimum of its children's estimates.
Crucially, the heuristic "prorates" costs by dividing a node's estimate by the number of parents it has. This captures the "sharing" intuition numerically, assigning a fraction of a hypothesis's cost to each observation it helps explain.
To ensure the heuristic is admissible—meaning it never overestimates the actual cost and thus guarantees finding the cheapest proof—the authors demonstrate that nodes must be expanded in a specific "topological" order (parents before children).
Experimental Evaluation
The authors evaluated the cost-sharing heuristic using data from Wimp3, a natural language understanding program. The test set consisted of 140 "and-or dags" (directed acyclic graphs) derived from story interpretations, ranging in size from 7 to 168 nodes.
Performance was measured by fitting search time to an exponential equation: $time = e^{a + b \cdot |nodes|}$. The results showed a significant improvement:
- The exponent ($b$) dropped from 0.079 with the "cost-so-far" method to 0.063 with cost sharing.
- A refined version, "Multiple parent removal," further reduced the exponent to 0.058.
In the context of exponential growth, these reductions represent massive time savings as problem complexity increases. For a 168-node graph, the new heuristic is orders of magnitude more efficient than the blind search.
Limitations and Conclusion
While highly effective, the heuristic has some limitations. It requires the full "and-or dag" to be constructed before the search begins, which may not be feasible for systems that generate logic on-the-fly. Additionally, the estimator can be overly optimistic when multiple paths from an "OR" node lead to the same child, though this does not compromise its admissibility.
In conclusion, the cost-sharing heuristic provides a robust, mathematically sound method for accelerating the search for minimal-cost proofs. By recognizing and numerically accounting for the shared utility of hypotheses, it transforms a previously blind search into a guided, efficient process.
Summary updated