A clique tree algorithm exploiting context specific independence

Context specific independence can provide compact representation of the conditional probabilities in Bayesian networks when some variables are only relevant in specific contexts. We present eve-tree, an algorithm that exploits context specific independence in clique tree propagation. This algorithm is based on a query-based contextual variable elimination algorithm (eve) that eliminates in turn the variables not needed in an answer. We extend eve to producing the posterior probabilities of all variables efficiently and allow the incremental addition of evidence. We perform experiments that compare eve-tree and Hugin using parameterized random networks that exhibit various amounts of context specific independence, as well as a standard network, the Insurance network. Our empirical results show that eve-tree is efficient, both in time and in space, as compared to the Hugin architecture, on computing posterior probabilities for Bayesian networks that exhibit context specific independence.Science, Faculty ofComputer Science, Department ofGraduat