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

Daphne Koller Publications

A General Algorithm for Approximate Inference and Its Application to Hybrid Bayes Nets (1999)

by D. Koller, U. Lerner, and D. Anguelov


Abstract: The clique tree algorithm is the standard method for doing inference in Bayesian networks. It works by manipulating clique potentials - distributions over the variables in a clique. While this approach works well for many networks, it is limited by the need to maintain an exact representation of the clique potentials. This makes the clique tree algorithm impractical for certain large discrete networks, and inapplicable for most continuous and hybrid networks. This paper presents a new unified approach that combines approximate inference and the clique tree algorithm, thereby circumventing this limitation. Many known approximate inference algorithms can be viewed as instances of this approach: likelihood weighting, most approximate inference algorithms for dynamic Bayesian networks, inference for Conditional Gaussian networks, and more. The algorithm essentially does clique tree propagation, using approximate inference to estimate the densities in each clique. In many settings, the computation of the approximate clique potential can be done easily using statistical importance sampling. Unlike exact clique tree propagation, the results of a single pass may not be accurate enough. The algorithm deals with this problem using an iterative scheme: it estimates the error at each clique, and re-evaluates the potential of those where the error is large. This algorithm combines the best features of exact and approximate inference: Like approximate inference algorithms, it can deal with complex domains, including hybrid networks. Like the clique tree algorithm, it exploits the locality structure of the Bayes net to reduce the dimensionality of the probability densities involved in the computation.


Download Information

D. Koller, U. Lerner, and D. Anguelov (1999). "A General Algorithm for Approximate Inference and Its Application to Hybrid Bayes Nets." Proc. Fourteenth Annual Conference on Uncertainty in AI (UAI) (pp. 324-333). pdf ps.gz

Bibtex citation

@inproceedings{Koller+al:UAI99,
  author =       "D. Koller and U. Lerner and D. Anguelov",
  booktitle =    "Proc. Fourteenth Annual Conference on Uncertainty in
                 AI (UAI)",
  title =        "A General Algorithm for Approximate Inference and Its
                 Application to Hybrid Bayes Nets",
  pages =        "324--333",
  year =         "1999",
}

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