Forming Concepts for Fast Inference
Henry Kautz, Bart Selman · 1994
Knowledge compilation speeds inference by creating tractable approximations of a knowledge base, but this advantage is lost if the approximations are too large. We show how learning concept generalizations can allow for a more compact representation of the tractable theory. We also give a general induction rule for generating such concept generalizations. Finally, we prove that unless NP ` non-uniform P, not all theories have small Horn least upper-bound approximations. 1 Introduction Work in machine learning has traditionally been divided into two main camps: concept learning (e.g. [ Kearns, 1990 ] ) and speed-up learning (e.g. [ Minton, 1988 ] ). The work reported in this paper bridges these two areas by showing how concept learning can be used to speed up inference by allowing a more compact and efficient representation of a knowledge base. We have been studying techniques for boosting the performance of knowledge representation systems by compiling expressive but intractable repre...