Efficient Epistemic Updates in Rank-based Belief Networks

Abstract

The thesis provides an approach for an efficient update algorithm of rank-based belief networks. The update is performed on two input values: the current doxastic state, represented by the network, and, second, a doxastic evidence that is represented as a change on a subset of the variables in the network. From these inputs, a Lauritzen-Spiegelhalter-styled update strategy can compute the updated posterior doxastic state of the network. The posterior state reflects the combination of the evidence and the prior state. This strategy is well-known for Bayesian networks. The thesis transfers the strategy to those networks whose semantics is specified by epistemic ranking functions instead of probability measures. As a foundation, the construction of rank-based belief networks is discussed, which are graphical models for ranking functions. It is shown that global, local and pairwise Markov properties are equivalent in rank-based belief networks and, furthermore, that the Hammersley-Clifford-Theorem holds for such ranking networks. This means that from the equivalence of the Markov properties it follows that a potential representation of the actual ranking function can be derived from the network structure. It is shown how by this property the update strategy of the Lauritzen-Spiegelhalter-algorithm can be transferred to ranking networks. For this purpose, the solution of the two main problems is demonstrated: first, the triangulation of the moralized input network and the decompositon of this triangulation to a clique tree. Then, second, message passing can be performed on this clique tree to incorporate the evidence into the clique tree. The entire approach is in fact a technical description of belief revision.