Knowledge retrieval as specialized inference

Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 1986.Artificial Intelligence reasoning systems commonly contain a large corpus of declarative knowledge, called a knowledge base (KB), and provide facilities with which the system's components can retrieve this knowledge. This thesis sets out to study the very nature of retrieval. Formal specifications that capture certain informal intuitions about retrieval are developed, studied, and implemented by retrieval algorithms. Consistent with the necessity for fast retrieval is the guiding intuition that a retriever is, at least in simple cases, a pattern matcher, though in more complex cases it may perform selected inferences such as property inheritance. Seemingly at odds with this intuition, this thesis views the entire process of retrieval as a form of inference and hence the KB as a representation, not merely a data structure. A retriever makes a limited attempt to prove that a queried sentence is a logical consequence of the KB. When constrained by the no-chaining restriction, inference becomes indistinguishable from pattern-matching. Imagining the KB divided into quanta, a retriever that respects this restriction cannot combine two quanta in order to derive a third. The techniques of model theory are adapted to build non-procedural specifications of retrievability relations, which determine what sentences are retrievable from what KB's. Model-theoretic specifications are presented for four retrievers, each extending the capabilities of the previous one. Each is accompanied by a rigorous investigation into its properties, and a presentation of an efficient, terminating algorithm that provably meets the specification. The first retriever, which operates on a propositional language, handles only yes/no queries, the second also handles wh-queries, and the third allows quantifiers in the KB and the query. Each is shown to be, in some sense, the strongest retriever that meets the no-chaining restriction. The third retriever forms an excellent basis for integrating a specialized set of inferences that chain in a controllable manner. This is achieved by incorporating taxonomic inference, such as inheritance, to form the fourth retriever, an idealized version of the retriever incorporated in the ARGOT natural language dialogue system. It is characterized by its ability to infer all consequences of its taxonomic knowledge without otherwise chaining