Risk Assessment and Decision Analysis with Bayesian Networks

465

Appendix D: Dynamic Discretization

The ability to include numeric variables in a Bayesian network (BN) without having to predene a set of

static states for each such variable is achieved through a dynamic discretization algorithm together with

a various heuristics to ensure a good balance between accuracy and efciency. This appendix provides

a formal description of the dynamic discretization algorithm and associated heuristics for readers with

a keen interest in the underlying theory.

Our approach to dynamic discretization allows us to automatically estimate the conditional probability densities for all

deterministic and statistical functions specied in the BN. No separate analytical calculation needs to be performed,

no simulation methods are required, and no tables need to be populated. Because of this you do not need to use tech-

niques like Monte Carlo simulation alongside BNs and can instead use this algorithm as the all-in-one solution.

In Section D.1 we introduce the notation and provide an overview of the dynamic discretization

approach. The core algorithm is described in detail Section D.2. Section D.3 describes the methods used

for approximating the statistical and deterministic functions we need to manipulate using the dynamic

discretization algorithm. Section D.4 describes the various methods that are used in practice to ensure

the algorithm works efciently and accurately.

D.1 Overview of Dynamic Discretization Approach

Let X be a continuous numeric node in a BN. The range of X is denoted by Ω

X

, and the probability density

function (pdf) of X is denoted by f

X

. The idea of discretization is to approximate f

X

by, rst, partitioning Ω

X

into a set of intervals

w{}

Xj

Ψ=

, and second, dening a locally constant function

f

X



on the partitioning

intervals. The task consists of nding an optimal discretization set

{}

Xi

Ψ=ω

and optimal values for the

discretized probability density function

f

X



. Discretization operates in much the same way when X takes

integer values, but here we will focus on the case where X is continuous.

The approach to dynamic discretization described here searches Ω

X

for the most accurate specica-

tion of the high-density regions (i.e., around the modes), given the model and the evidence by calculating

a sequence of discretization intervals in Ω

X

iteratively. At each stage in the iterative process a candidate

discretization,

X

Ψ

, is tested to determine whether the resulting discretized probability density

f

X



has

converged to the true probability density f

X

within an acceptable degree of precision. At convergence, f

X

is

then approximated by

f

X



.

By dynamically discretizing the model we achieve more accuracy in the regions that matter and incur

less storage space compared with static discretizations. Moreover, we can adjust the discretization anytime

in response to new evidence to achieve greater accuracy.

The approach to dynamic discretization presented here is inuenced by the work of Kozlov and Koller

on using nonuniform discretization in hybrid BNs. The key features of the approach include

A BN containing both discrete and continuous numeric nodes is called a hybrid BN (HBN).