Hello everybody. I am happy to announce that my Ph.D. dissertation
entitled "Optimal Inference with Local Expressions" is now available on
line at:
ftp://ftp.cs.orst.edu/pub/cs-techreports/1999/thesis/borujerdi.ps
I hope the abstract that follows will be interseting to you. Thanks.
Probabilistic inference using Bayesian networks is now a well-established
approach for reasoning under uncertainty. Among many efficiency-driven
techniques which have been developed, the Optimal Factoring Problem (OFP)
is distinguished for presenting a combinatorial optimization point of view
on the problem.
The contribution of this thesis is to extend OFP into a theoretical
framework that not only covers the standard Bayesian networks but also
includes non-standard Bayesian networks. A non-standard Bayesian network
has structures within its local distributions that are significant to the
problem. This thesis presents value sets algebra as a coherent framework
that facilitates formal treatments of inference in both standard and
non-standard Bayesian networks as a combinatorial optimization
problem.
Parallel to value sets algebra theory local expression languages allow one
to symbolically encode Bayesian network distributions. Such symbolic
encodings allow all the structural and numerical information in
distributions to be represented in the most compact form. However, the
symbolic and syntactic flexibilities in local expression languages have
the usual drawback of allowing possible incoherent expressions. Value sets
algebra leads us to an efficient coherency verification on such expressions.
This thesis views optimal inference with local expressions as an optimal
search problem. The search space for this problem is shown to be so large
that it renders any exhaustive search impractical. Hence it is necessary
to turn to heuristic solutions. Using A* heuristic framework and ideas
from OFP, which is the counterpart of this problem for standard Bayesian
networks, a heuristic algorithm for the problem is developed. As a key
feature, this algorithm differentiates between symbolic combinations of
expressions and arithmetic operations in the expressions. Cost bearing
arithmetic operations are performed only when sufficient information is
available to guarantee that no saving opportunities are lost. On the other
hand, expressions are combined in a way that quickly provides maximum
opportunity for efficient arithmetic operations.
This thesis also explores the representation of Intercausal Independencies
(ICI) in Bayesian networks and defines some new operators in local
expression language which are shown to facilitate more efficient ICI
representations.
Mohammad Borujerdi
bouyerm@cs.orst.edu
This archive was generated by hypermail 2b29 : Tue May 23 2000 - 08:55:58 PDT