Semi-Deterministic Reasoning

Abstract

In typical AI systems, we employ so-called nondeterministic reasoning (NDR), which resorts to some systematic search with backtracking in the search spaces defined by knowledge bases (KBs) . An eminent property of NDR is that it facilitates programming, especially programming for those difficult AI problems such as natural language processing for which it is difficult to find algorithms to tell computers what to do at every step. However, poor efficiency of NDR is still an open problem. Our work aims at overcoming this efficiency problem. There exists a lot of work done for this problem. For example, separation of domain knowledge from control knowledge to facilitate pruning search spaces has been employed in many knowledge based systems such as blackboard systems. However, the improvement is restricted by the fact that it is difficult for programmers to acquire precise control knowledge by analyzing search spaces with only the help of their intuition. Meanwhile, researches in machine learning, such as chunking and explanation-based learning, provide some means of automatic construction of control knowledge to prune search spaces. Unfortunately, improvement of efficiency is limited by a so-called utility problem. The common strategy underlying these various existing techniques is that they prune search spaces at every step of search by matching control knowledge against the current working memory (i.e., the current state in a search space). This “on-line” pruning of search spaces does not change the static organization of search spaces, and it keeps the NDR behavior throughout. Different from the above techniques, our work introduces a way of “off-line” pruning of search spaces. It computationally analyzes the search space defined by a KB by learning NDR implementation results based on the KB, and then reorganizes the search space into a new organization which supports semi-deterministic reasoning (SDR) as defined in the following. For any problem instance to be solved, SDR first deterministically chooses a sub-search space and then does nondeterministic search in the chosen sub-search space until the end of the whole process of search. Reorganization of a search space defined by a KB can be realized by reorganizing the KB into independent sub-knowledge bases (SKBs). Two SKBs are independent i# throughout the problem solving process for any problem instance, at most one of the two SKBs is activated. The KB organization with independent SKBs is called a solution-oriented KB organization (SOK) (Mao, 1992). B ase on the SOK, SDR first determind istically chooses an SKB, and then does NDR based on the chosen SKB. The determinism of SDR indicates that for any problem instance, at most one SKB can be activated. If an activated SKB fails to deduce a solution, then, without checking any other SKBs, SDR will claim that there is no solution for the problem instance. In our work, we choose Prolog as an NDR inference engine. To transform a typically unorganized firstorder logic based Prolog KB (i.e., a Prolog program) into an SOK organized KB, an integrated learning system THOUGHT-PROLOG (Mao & Chester, 1996) first calls a Prolog interpreter to do NDR and records the inference paths, and then classifies these inference paths into disjoint groups which form SKBs, and finally generates control knowledge to describe what problem instances can be solved in each SKB. A small scale experiment on a Prolog program with 22 rules and 33 facts shows that the average activated rules are reduced by 41.3% by THOUGHT-PROLOG. Our work can also be viewed as learning for knowledge base organization. It recognizes knowledge base organization as the meta-meta knowledge which defines the ways for control knowledge (met a-knowledge) to guide the use of domain knowledge.