My home page
My group
Professional activities

Daphne Koller Publications

Nonuniform dynamic discretization in hybrid networks (1997)

by A. V. Kozlov and D. Koller

Abstract: We consider probabilistic inference in general hybrid networks, which include continuous and discrete variables in an arbitrary topology. We reexamine the question of variable discretization in a hybrid network aiming at minimizing the information loss induced by the discretization. We show that a nonuniform partition across all variables as opposed to uniform partition of each variable separately reduces the size of the data structures needed to represent a continuous function. We also provide a simple but efficient procedure for nonuniform partition. To represent a nonuniform discretization in the computer memory, we introduce a new data structure, which we call a Binary Split Partition (BSP) tree. We show that BSP trees can be an exponential factor smaller than the data structures in the standard uniform discretization in multiple dimensions and show how the BSP trees can be used in the standard join tree algorithm. We show that the accuracy of the inference process can be significantly improved by adjusting discretization with evidence. We construct an iterative anytime algorithm that gradually improves the quality of the discretization and the accuracy of the answer on a query. We provide empirical evidence that the algorithm converges.

Download Information

A. V. Kozlov and D. Koller (1997). "Nonuniform dynamic discretization in hybrid networks." Proc. Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI) (pp. 314-325). pdf ps.gz

Bibtex citation

  author =       "A. V. Kozlov and D. Koller",
  booktitle =    "Proc. Thirteenth Conference on Uncertainty in
                 Artificial Intelligence (UAI)",
  title =        "Nonuniform dynamic discretization in hybrid networks",
  pages =        "314--325",
  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