Optimizing inference in Bayesian networks and semiring valuation algebras

Abstract. Previous work on context-specific independence in Bayesian networks is driven by a common goal, namely to represent the condi-tional probability tables in a most compact way. In this paper, we argue from the view point of the knowledge compilation map and conclude that the language of Ordered Binary Decision Diagrams (OBDD) is the most suitable one for representing probability tables, in addition to the language of Algebraic Decision Diagrams (ADD). We thus suggest the replacement of the current practice of using tree-based or rule-based rep-resentations. This holds not only for inference in Bayesian networks, but is more generally applicable in the generic framework of semiring valu-ation algebras, which can be applied to solve a variety of inference and optimization problems in different domains.