Implementation and Evaluation of Exact and Approximate Dynamic Bayesian Network Inference Algorithms
Hongfei Guo guo@cs.wisc.edu
Wei Luo luo@cs.wisc.edu
Abstract:
Particle filtering is currently an area of intensive study. Because it is a sampling algorithm, particle
filtering can be used easily with hybrid and continuous Dynamic Baysian Network (DBN)s. However, particle
filtering is not a panacea for all dynamic Bayesian networks. In this project, we implemented three
alternative inference algorithms for DBNs, namely, unrolling with generic variable elimination, unrolling
with customized variable elimination (customized algorithm), and particle filtering. We designed and
conducted a series of experiments using those alternatives respectively on different synthetic networks,
of which the complexity is adjusted by two parameters: one is the number of state variales, the other is
the average number of parents. Based on a thorough analysis of the experiment results, we reached our
conclutions, which fit well with a quatitively analysis of each algorithm: (1) The number of samples
needed is exponential to the number of state variables, and it is correlated with the belief state
distribution skewness; It is not correlated to the average number of parents for the state varaibles.
(2) The efficiency of particle filtering decreased sharply as the number of samples increases.
(3) The efficiency of the customized algorithm decreases sharply with the increase of the average number
of parents of the state variables; It is not sensitive to the number of state varaibles. And hence
(4) Particle filtering outperforms the customized algorithm for networks of which state variables have more
than 4 parents in average; For networks with large number of state variables yet a small average number of
parents, e.g. 2, the customized algorithm is the ideal choice.
[Full Paper]