TL;DR
This paper introduces "Semi-Deterministic Reasoning" (SDR), a novel approach to improve the efficiency of non-deterministic reasoning (NDR) systems, common in AI. SDR achieves this by "off-line" pruning of search spaces, reorganizing knowledge bases into independent sub-knowledge bases (SKBs) that are activated one at a time, significantly reducing computational effort.
What Problem Does This Paper Address?
Many AI systems, particularly those dealing with complex tasks like natural language processing, rely on Non-Deterministic Reasoning (NDR). NDR involves systematic search with backtracking through a problem's search space, which is defined by a knowledge base (KB). While NDR is conceptually straightforward and easy to program, its major drawback is poor efficiency due to the vastness of search spaces. Existing methods to improve efficiency, such as separating domain and control knowledge or using machine learning to automatically build control knowledge, often face limitations like the "utility problem" or only perform "on-line" pruning, which doesn't fundamentally alter the search space organization. This paper tackles the fundamental efficiency problem of NDR by proposing a method to reorganize the search space itself.
Methods
The core of the proposed solution is "Semi-Deterministic Reasoning" (SDR). SDR achieves "off-line" pruning by computationally analyzing the search space defined by a KB. This analysis leads to the reorganization of the KB into a set of independent sub-knowledge bases (SKBs). The key idea is that for any given problem instance, only one SKB is activated at any time. This organization is termed a "solution-oriented KB organization" (SOK). When solving a problem, SDR first deterministically selects an SKB and then performs NDR within that chosen SKB. If the selected SKB fails to find a solution, SDR declares that no solution exists, without exploring other SKBs.
To implement this, the authors use Prolog as the NDR inference engine. Their integrated learning system, THOUGHT-PROLOG, transforms a standard Prolog KB into an SOK. This involves:
- Running a Prolog interpreter to perform NDR and recording the inference paths.
- Classifying these inference paths into disjoint groups, which then form the SKBs.
- Generating control knowledge that specifies which problem instances can be solved by each SKB.
Datasets
Not discussed in the paper. The paper mentions a "small scale experiment on a Prolog program with 22 rules and 33 facts," but this is presented as an example rather than a formal dataset.
Key Insights and Ideas
- "Off-line" vs. "On-line" Pruning: The paper highlights a crucial distinction. Most existing methods prune search spaces "on-line" during execution. SDR's innovation is "off-line" pruning, which fundamentally restructures the search space before execution, leading to potentially greater efficiency gains.
- Knowledge Base Reorganization: The core idea of reorganizing the KB into independent SKBs is powerful. It shifts the burden of efficiency from runtime search management to a pre-computation phase.
- Determinism as a Control Mechanism: The deterministic selection of an SKB is the key to SDR's efficiency. By committing to one path early, it avoids exploring many irrelevant branches.
- Meta-Meta Knowledge: The authors frame KB organization as "meta-meta knowledge," which dictates how "meta-knowledge" (control knowledge) guides the use of "domain knowledge." This provides a useful hierarchical perspective on knowledge representation and reasoning.
Key Results
The paper reports a significant reduction in activated rules in their experimental setup. For a Prolog program with 22 rules and 33 facts, the THOUGHT-PROLOG system reduced the average number of activated rules by 41.3%. This demonstrates the practical impact of SDR in making reasoning more efficient.
Limitations and Future Work
- Scalability of KB Reorganization: While the experiment shows promise, the paper doesn't deeply discuss the scalability of the KB reorganization process itself, especially for very large and complex KBs.
- Determinism and Completeness: The deterministic nature of SDR means that if the chosen SKB doesn't contain a solution, the system concludes no solution exists. This implies that the correctness of SDR relies heavily on the accuracy and completeness of the SKB partitioning and the control knowledge generated. The paper doesn't explicitly detail how to guarantee that the chosen SKB is the "correct" one or how to handle cases where a solution might exist in a different SKB.
- Future Work: The paper suggests that their work can be viewed as learning for knowledge base organization, implying further research into automated KB organization techniques. The concept of meta-meta knowledge also opens avenues for exploring how different levels of knowledge can be learned and utilized.
Summary updated