Towards a More Efficient Computation of Weighted Conditional Impacts for Relational Probabilistic Knowledge Bases Under Maximum Entropy Semantics

摘要

While the complexity of the optimization problem to be solved when computing the Maximum Entropy distribution P_R~* of a knowledge base R grows dramatically when moving to the relational case, it has been shown that having the weighted conditional impacts (WCI) of R available, P_R~* can be computed much faster. Computing WCI in a straightforward manner readily gets infeasible due to the size of the set Ω of possible worlds. In this paper, we propose a new approach for computing the WCI without considering the worlds in Ω at all. We introduce the notion of sat-pairs and show how to determine the set CSP of all possible combinations of sat-pairs by employing combinatorial means. Using CSP instead of Ω for computing the WCI is a significant performance gain since CSP is typically much smaller than Ω. For a start, we focus on simple knowledge bases consisting of a single conditional. First evaluation results of an implemented algorithm illustrate the benefits of our approach.