An Analysis of Approximate Knowledge Compilation

Abstract

Knowledge compilation is the process by which an initial theory E with respect to which inference is intractable is transformed into one or more "approximate" or equivalent theories with respect to which inference can be performed efficiently. Selman and Kautz introduced Horn lowest upper bound (LUB) approximations in [SK91], and generalized them in [KS91 ; SK95] to a number of target languages other than Horn. In this paper , we analyze the problem of knowledge compilation for arbitrary clausal target languages, generalizing in several ways previous results. We provide general characterizations of the LUB that are independent of the target language; analyze the properties of the Generate-LUB algorithm of Selman and Kautz, proving its correctness for any target language closed under subsumption (including a wide family of languages which guarantee polynomial size approximations); and generalize the procedure to arbitrary target languages. We also examine some computational aspects of these procedures and the quality of Horn approximations.