Abstract: Speeding up inferences made from large knowledge bases is a key to scaling up Artificial Intelligence systems. Often, the source of inefficient performance is that an inference method considers many facts that are irrelevant to a specific goal. Identifying which parts of a knowledge base are relevant to a goal is also key to enabling reasoning in environments in which several systems interoperate. This dissertation presents a general framework and specific methods for enabling a system to exploit knowledge about irrelevance. Such knowledge can either be derived automatically by the system, or given by a user. The framework, which identifies several classes of irrelevance, is based on a proof-theoretic analysis of irrelevance. As such, it enables the two key issues of relevance reasoning to be addressed, namely the utility of relevance reasoning and the development of methods for automatically identifying irrelevant parts of a knowledge base.

The research develops a general tool, the query-tree, for reasoning about irrelevance. Based on the query-tree, we developed several algorithms for deciding what facts are irrelevant to a goal. These algorithms dramatically speed up inference, especially when the knowledge base includes a large data base of ground facts. The query-tree has been investigated primarily for Horn rule knowledge bases with interpretable constraints (e.g., order and sort constraints), and several more expressive extensions. For certain cases, the algorithms are shown to be complete, in that they detect all the irrelevant facts. An important aspect of the query-tree is that it can be built by examining only a small part of the knowledge base (e.g., only the rules), and therefore, can be built efficiently. The query-tree is also used to detect when an update is irrelevant to a query, and to derive the consequences of irrelevance knowledge given by a user. The dissertation also presents an empirical analysis of the algorithms when doing backward chaining on Horn rules, showing that in practice, significant savings are obtained by relevance reasoning.

The dissertation also explores the use of relevance reasoning in the domain of modeling physical devices. It considers the task of automatically creating a model for a given device and given query, by composing model-fragments from a given library of models. We describe a novel model-composition algorithm based on irrelevance reasoning that composes a model with appropriate abstractions and perspectives for answering the query. The algorithm is implemented as part of the Device Modeling Environment system at Stanford's Knowledge Systems Laboratory.