Inference in Large Knowledge Bases

Bill MaCartney1, Sheila McIlraith2, Eyal Amir3, and Tomas Uribe4
(Professor Stuart J. Russell)
(DOD-ONR) MURI FD N00014-01-1-0890, (DOD-ONR) MURI FD N00014-00-1-0637, and (NSF) ECS-9873474

There is growing interest in building large knowledge bases (KBs) of everyday knowledge about the world, comprising tens or hundreds of thousands of assertions. But with large KBs, general-purpose reasoners used to answer queries tend to suffer from combinatorial explosion. One promising approach to grappling with the complexity of such KBs is to structure the content into multiple domain- or task-specific partitions. But how are the partitions created, and how do we exploit them in reasoning?

Our research concerns detecting and exploiting the implicit structure of knowledge to make reasoning more focused and efficient. In particular, we investigate how two closely related questions: (1) How can we automatically decompose a large KB into a network of tightly-focused, minimally-connected partitions? (2) Given a network of (possibly heterogeneous) knowledge systems, how can we achieve efficient global reasoning?

In our approach, a first-order or propositional theory is partitioned into tightly coupled subtheories according to the language of the axioms in the theory [1]. This partitioning induces a graphical representation where a node represents a particular partition or subtheory and an arc represents the shared language between subtheories [2].

We developed a family of message-passing (MP) algorithms [1,3] for reasoning with partitions of axioms in propositional logic (PL) and first-order logic (FOL). We analyzed the computational benefit of our algorithms and detected those parameters of a partitioning that influence the efficiency of computation. These inference algorithms are sound and complete, i.e., provide all the correct answers and only those answers. The efficiency of our algorithms has been shown empirically to be superiour to widely used inference strategies.

[1]
E. Amir and S. McIlraith, "Partition-based Logical Reasoning," Int. Conf. Principles of Knowledge Representation and Reasoning, Breckenridge, CO, April 2000.
[2]
E. Amir, "Efficient Approximation for Triangulation of Minimum Treewidth," Conf. Uncertainty in Artificial Intelligence, Seattle, WA, August 2001.
[3]
S. McIlraith and E. Amir, "Theorem Proving with Structured Theories," Int. Joint Conf. Artificial Intelligence, Seattle, WA, August 2001.
1Staff, Stanford University
2Staff, Stanford University
3Postdoctoral Researcher
4Staff, SRI International

More information (http://www.ksl.stanford.edu/projects/RKF/Partitioning) or

Send mail to the author : (eyal@eecs.berkeley.edu)


Edit this abstract