Statistical Learning of Probabilistic BDDs
(invited lecture for SAGA 2009)
Author: Taisuke Sato
Affiliation:
Department of Computer Science
Graduate School of Information Science and Engineering
Tokyo Institute of Technology
Abstract.
BDDs (binary decision diagrams) are a graphical data
structure which compactly represents boolean functions
and has been extensively used in VLSI CAD. In this
talk, I will describe how BDDs are applied to machine
learning, or more concretely how they are used in
probability computation and statistical parameter
learning for probabilistic modeling. The basic idea is
that of PPC (propositionalized probabilistic
computation) which considers "X = x", a random variable X
taking a value x, as a probabilistic proposition. A
complex (discrete) probabilistic model such as a
Bayesian network is representable by way of PPC as a
probabilistic boolean formula, thus by a probabilistic
BDD.
We developed an efficient sumproduct probability
computation algorithm on BDDs and also derived a
parameter learning algorithm called the BDDEM
algorithm for maximum likelihood estimation in
statistics. We applied the BDDEM algorithm to the
problem of finding a most probable hypothesis about a
metabolic pathway in systems biology.
©Copyright 2009 Author
