My home page
My group
Professional activities

Daphne Koller Publications

Effective Bayesian Inference for Stochastic Programs (1997)

by D. Koller, D. McAllester, and A. Pfeffer

Abstract: Knowledge representation languages invariably reflect a trade-off between expressivity and tractability. Evidence suggests that the compromise chosen by description logics is a particularly successful one. However, description logic (as for all variants of first-order logic) is severely limited in its ability to express uncertainty. In this paper, we present P-Classic, a probabilistic version of the description logic Classic. In addition to terminological knowledge, the language utilizes Bayesian networks to express uncertainty about the basic properties of an individual, the number of fillers for its roles, and the properties of these fillers. We provide a semantics for P-Classic and an effective inference procedure for probabilistic subsumption: computing the probability that a random individual in class C is also in class D. The effectiveness of the algorithm relies on independence assumptions and on our ability to execute lifted inference: reasoning about similar individuals as a group rather than as separate ground terms. We show that the complexity of the inference algorithm is the best that can be hoped for in a language that combines description logic with Bayesian networks. In particular, if we restrict to Bayesian networks that support polynomial time inference, the complexity of our inference procedure is also polynomial time.

Download Information

D. Koller, D. McAllester, and A. Pfeffer (1997). "Effective Bayesian Inference for Stochastic Programs." Proceedings of the 14th National Conference on Artificial Intelligence (AAAI) (pp. 740-747). pdf ps.gz

Bibtex citation

  author =       "D. Koller and D. McAllester and A. Pfeffer",
  booktitle =    "Proceedings of the 14th National Conference on Artificial Intelligence (AAAI)",
  title =        "Effective {B}ayesian Inference for Stochastic
  year =         "1997",
  pages  = "740--747",

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