My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Stochastic simulation algorithms for dynamic probabilistic networks (1995)

by K. Kanazawa, D. Koller, and S.J. Russell


Abstract: Stochastic simulation algorithms such as likelihood weighting often give fast, accurate approximations to posterior probabilities in probabilistic networks, and are the methods of choice for very large networks. Unfortunately, the special characteristics of dynamic probabilistic networks (DPNs), which are used to represent stochastic temporal processes, mean that standard simulation algorithms perform very poorly. In essence, the simulation trials diverge further and further from reality as the process is observed over time. In this paper, we present simulation algorithms that use the evidence observed at each time step to push the set of trials back towards reality. The first algorithm, evidence reversal (ER) restructures each time slice of the DPN so that the evidence nodes for the slice become ancestors of the state variables. The second algorithm, called survival of the fittest sampling (SOF), "repopulates" the set of trials at each time step using a stochastic reproduction rate weighted by the likelihood of the evidence according to each trial. We compare the performance of each algorithm with likelihood weighting on the original network, and also investigate the benefits of combining the ER and SOF methods. The ER/SOF combination appears to maintain bounded error independent of the number of time steps in the simulation.


Download Information

K. Kanazawa, D. Koller, and S.J. Russell (1995). "Stochastic simulation algorithms for dynamic probabilistic networks." Proceedings of the Eleventh Annual Conference on Uncertainty in AI (UAI '95) (pp. 346-351). pdf ps.gz

Bibtex citation

@inproceedings{Kanazawa+al:UAI95,
  author =       "K. Kanazawa and D. Koller and S.J. Russell",
  booktitle =    "Proceedings of the Eleventh Annual Conference on
                 Uncertainty in AI (UAI '95)",
  title =        "Stochastic simulation algorithms for dynamic
                 probabilistic networks",
  pages =        "346--351",
  year =         "1995",
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal