Structured Arc Reversal and Simulation of Dynamic Probabilistic Networks
Adrian Cheuk, Craig Boutilier
We present an algorithm for arc reversal in Bayesian networks with tree-structured conditional probability tables, and consider some of its advantages, especially for the simulation of dynamic probabilistic networks. In particular, the method allows one to produce CPTs for nodes involved in the reversal that exploit regularities in the conditional distributions. We argue that this approach alleviates some of the overhead associated with arc reversal, plays an important role in evidence integration and can be used to restrict sampling of variables in DPNs. We also provide an algorithm that detects the dynamic irrelevance of state variables in forward simulation. This algorithm exploits the structured CPTs in a reversed network to determine, in a time-independent fashion, the conditions under which a variable does or does not need to be sampled.
Keywords: Context-specific independence, arc reversal, dynamic probabilistic networks,
PS Link: http://www.cs.ubc.ca/spider/cebly/Papers/simulation.ps
PDF Link: /papers/97/p72-cheuk.pdf
AUTHOR = "Adrian Cheuk
and Craig Boutilier",
TITLE = "Structured Arc Reversal and Simulation of Dynamic Probabilistic Networks",
BOOKTITLE = "Proceedings of the Thirteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1997",
PAGES = "72--79"