My home page
My group
Professional activities

Daphne Koller Publications

P-Classic: A Tractable Probabilistic Description Logic (1997)

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

Abstract: In this paper, we propose a stochastic version of a general purpose functional programming language as a method of modeling stochastic processes. The language contains random choices, conditional statements, structured values, defined functions, and recursion. By imagining an experiment in which the program is `run' and the random choices made by sampling, we can interpret a program in this language as encoding a probability distribution over a (potentially infinite) set of objects. We provide an exact algorithm for computing conditional probabilities of the form Pr(P(x) | Q(x)) where x is chosen randomly from this distribution. This algorithm terminates precisely when sampling x and computing P(x) and Q(x) terminates in all possible stochastic executions (under lazy evaluation semantics, in which only values needed to compute the output of the program are evaluated). We demonstrate the applicability of the language and the efficiency of the inference algorithm by encoding both Bayesian networks and stochastic context-free grammars in our language, and showing that our algorithm subsumes certain standard efficient inference algorithms for both. Our language easily supports interesting and useful extensions to these formalisms (e.g., recursive Bayesian networks), to which our inference algorithm will automatically apply.

Download Information

D. Koller, A. Levy, and A. Pfeffer (1997). "P-Classic: A Tractable Probabilistic Description Logic." Proceedings of the 14th National Conference on Artificial Intelligence (AAAI) (pp. 390-397). pdf ps.gz

Bibtex citation

  author =       "D. Koller and A. Levy and A. Pfeffer",
  booktitle =    "Proceedings of the 14th National Conference on
                 Artificial Intelligence (AAAI)",
  title =        "{P}-Classic: {A} Tractable Probabilistic Description
  pages =        "390--397",
  year =         "1997",

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