Open Collections

A clique tree algorithm exploiting context specific independence

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2009-09-28

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/13264

Computer Science

University of British Columbia

UBCV

DSpace