Efficient Reasoning.(in knowledge-based computers)

1. INTRODUCTION

Many information systems use a corpus of explicitly stored information (a.k.a. a "knowledge base," KB) to solve their range of problems. For example, medical diagnostic systems use general facts about diseases, as well as the specific details of a particular patient, to determine which diseases the patient might have, and which treatment is appropriate. Similarly, configuration and synthesis systems use their stored descriptions of various components, along with the specifications for a proposed device (VLSI chip, software program, factory, or whatever), to design a device that satisfies those requirements. Scheduling and planning systems likewise synthesize schedules sufficient to achieve some specified objective.

In each case, the underlying system must reason--that is, derive conclusions (e.g., diagnoses, designs, schedules) that are sanctioned by its knowledge. Typically, an expert first, at "compile time," provides a corpus of general background facts--about medicine, or types of components, etc. At "run time," a user then specifies the details of a specific situation (e.g., the symptoms of a specific patient, or the specifications of a particular desired artifact), and then poses some specific questions (Which disease? What should be connected to what? ...); the reasoning system then produces appropriate answers, based on its current KB which includes both the specifics of this problem and the general background knowledge. As there is a potentially infinite set of possible situations, these conclusions are typically not explicitly stored in the KB, but instead are computed as needed. This computation is called "reasoning" (aka "derivation," "deduction," "inference").

In general, we will identify a reasoner with its symbolic knowledge base KB; the user can pose queries [Chi] to that reasoner and receive answers--e.g., that [Chi] is true or not. Section 2 motivates the use of such symbolic knowledge-based reasoners, and presents broad categories of such systems: logic-based (typically using Horn clauses) and probabilitic (using Bayesian belief nets). It also argues that we should evaluate a reasoner based on its facility in answering queries, using as quality measures: correctness, precision, expressiveness, and efficiency.

We clearly prefer a reasoner that always returns all-and-only the correct and precise answers, immediately, to arbitrary queries. Unfortunately, we will see that this is not always possible (Section 2.4). Many implemented reasoning systems, therefore, sacrifice something--correctness, precision, or expressiveness--to gain efficiency. The remainder of this paper presents various approaches: Section 3 (resp., Section 4, Section 5) overviews ways of improving worst-case efficiency by reducing expressiveness (resp., by allowing imprecise answers, by allowing occasional incorrect responses). Section 6 considers ways of producing (expressive, precise, and correct) systems whose "average-case" efficiency is as high as possible. It also discusses ways to produce a system with high average performance, where the "performance" measure is a combination of these various criteria. Appendix A provides additional relevant details about belief nets.

2. SYMBOLIC REASONERS

2.1 Why Symbolic Reasoners?