This talk is based on two main ideas, one concerning exact probabilistic inference and the second concerning approximate probabilistic inference. Both ideas have their roots in symbolic inference and do complement each other. The first idea shows how one can reduce exact probabilistic inference to a problem of knowledge compilation: transforming propositional knowledge bases so they attain certain syntactic properties [8]. In particular, I will discuss two syntactic properties of propositional knowledge bases, called decomposability and determinism, and show that an ability to enforce these two properties efficiently leads to an ability to efficiently do inference on probabilistic graphical models. This connection is not recent - see [7] for one of the first formulations. Yet, it is important to highlight as it helps in showing the relevance of work on symbolic knowledge compilation to probabilistic inference. I will in particular highlight some of the open problems and computational bottlenecks in this area, in addition to recent advances in this direction (e.g., [11]). My goal here is to motivate further work on knowledge compilation by the symbolic logic reasoning community. In logical terms, decomposability is about expressing an event γ as a conjunction, say, α ∧ β, where the conjuncts do not share variables. By decomposing 7 in this fashion, we will able to decompose computations on γ into independent computations on α and on β. Sometimes, we cannot perform this decomposition, especially when the variables of α and β are already predetermined. The solution to this problem is to express 7 as a disjunction α_1 ∧ β_1 ∨ ... ∨ α_n ∧ β_n, where each disjunct α_i ∧ β_i is a decomposition. This is always possible, but one would clearly want to minimize the size of such disjunctions. One may not be able to escape exponential growth in some cases, however, especially that each α_i and β_i would generally need to be decomposed recursively as well. Moreover, when the ultimate goal is to perform probabilistic reasoning, one would want the disjuncts to be mutually exclusive as well. That is, no pair of disjuncts can be satisfied by the same model. This is the property of determinism.
展开▼
