A Guide to the Literature on Learning Probabilistic Networks from Data.
AbstractThis literature review discusses different methods under the general rubric of learning Bayesian networks from data, and includes some overlapping work on more general probabilistic networks. Connections are drawn between the statistical, neural network, and uncertainty communities, and between the different methodological communities, such as Bayesian, description length, and classical statistics. Basic concepts for learning and Bayesian networks are introduced and methods are then reviewed. Methods are discussed for learning parameters of a probabilistic network, for learning the structure, and for learning hidden variables. The presentation avoids formal definitions and theorems, as these are plentiful in the literature, and instead illustrates key concepts with simplified examples.
Introduction
Probabilistic networks or probabilistic graphical models
are a representation of the variables in a problem and
the probabilistic relationships among them. Bayesian net-
works, a popular kind of probabilistic network, have been
used in different applications including fault diagnosis,
medical expert systems, and software debugging [1]. In
this review of learning I focus mainly on Bayesian networks
which are based on directed graphs.
Probabilistic networks are increasingly being seen as a
convenient high-level language for structuring an otherwise
confusing morass of equations. They are an explicit
representation of dependencies or independencies between
variables that ignores the specific numeric or functional
details. Depending on interpretation, they can also represent
causality [2], [3], [4], [5]. Probabilistic networks in
this broad sense were independently developed in a number
of communities [6]: in genetics [7], in social science, in
statistics to factor multi-dimensional contingency tables;
in artificial intelligence to model probabilistic intelligent
systems [8]; and in decision theory to model complex decisions
[9]. An area not considered in this review is graphical
modeling in social science which has had rich development
and application, and strong interactions with the artificial
intelligence and statistical communities [10], [3], [11], [12].
Networks in general play the role of a high-level language,
as is seen in artificial intelligence, statistics, and to a lesser
degree in neural networks (where biological views offer an
alternative interpretation). See the survey by Ripley [13].
Networks are used to build complex models from simple
components. Networks in this broader sense include prob-
Current address: Thinkbank, 1678 Shattuck Avenue, Suite
Berkeley, CA, 94709. Email: wray@Thinkbank.COM, URL:
http://WWW.Thinkbank.COM/wray/
abilistic graphical models of the kind considered here, as
well as neural networks [14], and decision trees [15]. Probabilistic
networks have the distinguishing characteristic that
they specify a probability distribution-they therefore have
a clear semantics that allow them to be processed in order
to do diagnosis, learning, explanation and many other
inference tasks necessary for intelligent systems. For in-
stance, a new research area considered briefly in the last
section is where a probabilistic network is the input specification
for a compiler that generates a learning algorithm.
This compilation is made easier because the network defines
a probability distribution.
Why is learning probabilistic networks of particular in-
terest? Most of the earlier work in artificial intelligence on
building expert systems involved a tedious process of manual
knowledge acquisition [16]. This tedium spurred two
developments that more or less continued independently
until recently: machine learning which originally focused
on learning rule based systems [17], [18], and uncertainty
in artificial intelligence which focused on developing coherent
probabilistic knowledge structures whose elicitation
suffered less pitfalls. For instance, Henrion and Cooley give
a detailed case study [19], and Heckerman developed similarity
networks [20] which allow a complex network to be
elicited more simply than one would expect. The interest
in artificial intelligence in learning of probabilistic networks
is a result of the marriage of machine learning and uncertainty
in artificial intelligence.
Neural network learning has developed concurrently,
based almost exclusively on learning from data. The networks
in the computational side of neural networks (in-
terested in information processing as opposed to biological
modeling) have increasingly been moving in the direction
of probabilistic models. Therefore, there is some overlap
between learning of probabilistic networks and neural networks
[21], [22], [23]. In statistics, many general inference
techniques [24], [25], [26] have been developed that have
been applied to learning of probabilistic networks. Computer
scientists, for instance in artificial intelligence, have
often contributed more in terms of combining and scaling
up these techniques, and generalizing them to classes
of representations. More examples of the variety of probabilistic
networks and their applications to learning are given
in [23], [27].
Learning of probabilistic networks includes a number of
complications: learning the structure, the parameters given
a structure, hidden variables whose values are never present
in the data, and values of a variable that are sometimes
missing. This review describes some current literature addressing
these various tasks, reviews the major methodolo-
IEEE TRANSACTIONS ON KNOWLEDGE AND
gies applied, and describes some of the major algorithms.
Available software for learning Bayesian networks is not
discussed in this review. An extensive list of software for
general inference on probabilistic networks is maintained
on the World Wide Web [28]. A list of relevant online tutorial
articles and slides, several of those mentioned here, is
also available at [29]. Another area not considered in this
review is the empirical evaluation of learning algorithms for
probabilistic networks. Empirical evaluation of learning algorithms
is fraught with difficulties [30]. Notwithstanding,
interesting empirical studies appear in [31], [32], [33], [34],
[35], [36], [37], [38].
II. An introduction to probabilistic networks
This section introduces Bayesian networks, and some
more general probabilistic networks. For tutorial articles
on Bayesian networks see [39], [40], [41]. For an introduction
from the artificial intelligence perspective, see [8].
For a statistical introduction to graphical models in general
see [42], and a tutorial introduction see [43]. For an
introduction to Bayesian networks and Bayesian methods
for learning them see [44]. Other kinds of networks include
Markov (undirected) networks and Markov random fields
are considered widely in image analysis, spatial statistics
[45] and neural networks [14].
This section introduces Bayesian networks with a simple
example, and then illustrates the richness of the representation
with additional examples. Consider Bayesian networks
on discrete variables. In their simplest form these consist
of a network structure and its associated conditional probability
tables. The example below is adapted from [39].
A. The structure, S
The network structure is represented by a Directed
Acyclic Graph (DAG) as given in Fig. 1. This network
Occupation Climate
Age
Disease
Symptoms
Fig. 1. A simple Bayesian network
is by definition equivalent to the following functional decomposition
for the joint probability (full variable names
have been abbreviated):
which is in turn equivalent to the following set of conditional
independence statements:
Symptoms ?? fAge; Occ; Climg


I
Two of the five probability tables
Age - 45 0.54
Disease
Symptoms stomach myocardial neither
ulcer infarction
stomach pain 0.80
chest pain 0.15 0.90 0.10
neither
Here, A??BjC reads that A and B are independent given
C [8], [46]. Take the node for Symptoms as an exam-
ple. This node only has one parent, Disease, but three
other ancestors, Age; Occ; Clim. From this one reads the
assumption that the symptoms are only dependent on
age, occupation and climate indirectly through their influence
on the disease. This network substructure, by
definition, translates into the third independence statement
above. Bayesian networks therefore simplify the
full joint probability distribution for a set of variables,
show independencies
between the variables.
B. The conditional probability tables, parameters '
Conditional probability tables are needed to specify a
probability distribution based on the network. For the
structure in Fig. 1, we see from Equation (1) that the tables
for p(Age), p(Occ), p(Clim), p(DiseasejAge; Occ; Clim),
and p(SymptomsjDisease) need to be specified. These
tables may be specified in any form: implicitly by some
parametric probability distribution, or explicitly as ta-
bles. Two such tables are given below for p(Age) and
p(SymptomsjDisease). Notice that Age, while being a
real valued variable, is discretized to create a binary vari-
able. Symptoms is a three valued discrete variable, as is
Disease. Without the assumptions of the network which
leads to Equation (1), instead of five smaller tables, one
large joint table on all five variables would be required.
Networks provide a way of simplifying the representation
of a probability distribution.
C. Some extensions
While the variables above are treated as simple discrete
variables, and the conditional probabilities in the example
above are simple tables, in general a variety of variables
and functions can be used on Bayesian networks. Variables
could be real valued, integer valued, or multivariate.
A real-valued variable may have a probability density function
such as a Gaussian. Instead of giving a probability table
for it as above, the mean and variance of the Gaussian
would be given as functions of the parent variables. These
BUNTINE: A GUIDE TO THE LITERATURE ON LEARNING GRAPHICAL MODELS FROM
constructions allow Bayesian networks to represent standard
statistical models such as regression with Gaussian
error, and log-linear models [42]. Furthermore, graphical
models are not restricted to be directed. Undirected arcs
can be used in problems such as diagnosis where association
between symptoms might be represented, and image
analysis, for associations between regions of an image. The
combination of directed and undirected graphical models,
developed by Lauritzen and Wermuth [47], forms a rich representation
language. For an introduction to these combinations
see [48]. As an example of this richness, I consider
feed-forward neural networks next.
D. Connections to feed-forward neural networks
Fig. 2 shows the transformation of a feed-forward neural
network predicting real valued variables into a probabilistic
network. Fig. 2(a) shows a feed-forward network in
Sigmoid
Sigmoid
Sigmoid Sigmoid
Gaussian
Gaussian
(b)
(a)
Fig. 2. A feed-forward network to a Bayesian network
the form used in [14], and Fig. 2(b) shows a corresponding
probabilistic network with a bivariate Gaussian error distribution
grafted onto the output nodes of the network. The
feed-forward neural network has the three lower nodes filled
in to indicate they are input nodes. The bivariate Gaussian
has been represented on the probabilistic network as
two nodes with a directed arc between them; an equivalent
representation would use an undirected arc. The transformation
into the Bayesian network needs to be qualified in
several ways. Notice that the interior nodes in the Bayesian
network are labeled as Simoids, the transfer function typically
used in a feed-forward network. The nodes are also
double ovals rather than single ovals. This is short-hand to
say that the variable is a deterministic function of its in-
puts, rather than a probabilistic function. Neural networks
usually have a weight associated with each arc, giving in
some sense the strength of the association. In probabilistic
networks, the arc indicates some form of probabilistic
dependence or correlation, and any weights are instead
associated with each node, and are used to parameterize
the functions at the node instead. Furthermore, the probabilistic
network explicitly includes the measured output
variables in the network, the neural net-work
only includes the predicted output variables m 1 and
. The probabilistic network therefore explicitly represents
the error function, whereas the neural network leaves
it unspecified. In summary, the Bayesian network indicates
Class
Fig. 3. A simple clustering model
that the output variables, have a Gaussian distribution
based on the variables m 1 and m 2 , which themselves
are deterministic Sigmoid functions of the hidden variables
More sophisticated dynamic networks are the recurrent
neural networks [49]-roughly, these might be thought of as
a flexible, non-linear extension to probabilistic models like
Kalman filters and hidden Markov models. While these
networks are based on feed-forward neural networks, the
relationship of these to probabilistic networks is still under
development.
E. Connections to statistics and pattern recognition
Whittaker [42], and Wermuth and Lauritzen [50] provide
a rich set of examples of modeling statistical hypotheses
using graphical models, some using mixed graphs incorporating
both undirected and directed networks.
Consider clustering, a style of unsupervised learning. A
Bayesian network can be drawn for a clustering algorithm
such as Autoclass [51], where it is assumed that the observed
variables are independent given the hidden class. In
clustering, the cases are to be grouped in some coherent
manner. The probabilistic network in Fig. 3. suggests a
way of doing this. A discrete variable class is introduced
that is termed a latent or hidden variable. Its value never
appears in the data, and it indicates the unknown class to
which each case belongs. The advantage of this construction
is that once the class value is known for a case, the
probability distribution becomes a simple one with A, B
and C independent, needing only 3 real valued parameters
to define it. This model is called a mixture model because
the joint probability is a mixture of the data obtained for
the different classes. For a visual illustration of the power
of mixture models, consider real valued variables X;Y . A
bivariate Gaussian places an oval shaped cloud centered at
a point. A mixture of four bivariate Gaussians is illustrated
in Fig. 4 has four clouds of points. When the mixture contains
many classes, the density can become quite complex.
Popular models used in pattern recognition, speech
recognition and control, the Kalman filter and the hidden
Markov model (HMM) can also be modeled with Bayesian
networks [52], [53]. A simple hidden Markov model is given
in Fig. 5. A sequence of observations are made, such as
phonemes in an utterance. These are indicated with the
shaded nodes observe 1 , ., observe i , observe i+1 . Shading
indicates the variables have been observed. The observations
are dependent on the hidden states hidden 1 , .,
hidden i , hidden i+1 of the underlying system. If the observations
are phonemes, then the hidden states may be
letters of the underlying word being spoken, which are of
course hidden from the observer. These kinds of models are
Fig. 4. Data from a 2-dimensional mixture of Gaussians
observe 1
observe i
hidden
observe
Fig. 5. A simple hidden Markov model.
dynamic, in the sense that the network is a set of repeated
units that are expanded in time, as for instance used in
forecasting [54].
F. Causal networks
A useful trick used in the elicitation of Bayesian networks
is to assume the arcs represent causality. Consider the net-work
from [39], reproduced in Fig. 1. One could imagine
the environmental variables causing the disease, which in
turn causes the symptoms, and this is a nice way of explaining
this particular graph to the expert. When Bayesian
networks have this interpretation, they are sometimes referred
to as causal networks [2], [3], [4], [55]. Causality is of
fundamental importance in science because of the notion
of intervention [55], [5]. While identifying the observed
probabilities relating smoking, sex, and lung cancer is an
interesting task in itself, the real goal of such a study is
to establish that the act of changing someone's smoking
habits will change their susceptibility to lung cancer. This
kind of action is an external intervention on the variables.
A causal model is expected to be stable under acts of external
conclusions drawn from them are still
valid. In the probabilistic interpretation of networks used
elsewhere in this review, there is an assumption that cases
are got through passive observation of independently and
identically distributed examples. Networks can be used to
represent causality in this manner, but these networks have
a different interpretation to the probabilistic networks considered
here. Causality, networks and learning causlity are
not covered in this review. Learning and identification of
causality is considered in [56], [3], [57], [58], [59].


II
A sample database in a relational table
case A B C
III. Some simple examples, and some basic
concepts
As an example of learning, consider data about three binary
variables, A; B; C. This data would take the form of
a table, as given in the simple example in Table II. The
4 rows in the table give 4 cases, which might be different
patients. More typically, hundreds or thousands of cases
would exist in a relational database. In Table II, each case
has three variables measured and their values recorded.
The values for each variable are either true, indicated by
T or false, indicated by F . A variable could also have the
value "?". This represents a missing value, which means
the value for the variable is unknown. Missing values are
common in some domains, especially where variables are
expensive to measure.
A. The hypothesis space
Some example Bayesian networks that might match this
problem are given in Fig. 6. First consider structure (a),
A
C A
A
A
A
A
Fig. 6. Some Bayesian networks on three variables, A; B; C.
I will denote S a , which represents that the three variables
are independent. For this structure, probability tables for
p(A), p(B) and p(C) are needed. Since the variables are
binary, these three probabilities are specified by three real
numbers between 0 and 1. Denote these tables by the parameter
set ' a 2 ! 3 . For structure (c) denoted S c , probability
tables for p(A), p(B) and p(CjB), denoted ' c , are
needed. This parameter set is in ! 4 because while p(A)
and p(B) are specified by one value each, p(CjB) is specified
by two values, for instance
Consider the conditional probability
distributions that complete the network Sm . The probability
table for p(XjY ) will be a subset of the real space of
is the number of values
of the variable X. The fully connected network matching

Table

II, where every two variables are connected, will have
BUNTINE: A GUIDE TO THE LITERATURE ON LEARNING GRAPHICAL MODELS FROM
7 real values, where 7 is calculated from 2 3 \Gamma 1. So a net-work
of k binary variables needs between k and 2
values to specify its conditional probability tables. A real-valued
node whose conditional probability distribution is a
Gaussian with k parents will require k(k + 1)=2 real values
to specify the mean and the covariance matrix. In gen-
eral, the real values used to specify conditional probability
tables either explicitly (in a table) or implicitly (in some
are referred to as the parameters of the network.
A simple counting argument shows there are 25 different
networks on just the three variables in Fig. 6. However, it
happens that several of these are equivalent in the sense
that they represent equivalent independence statements.
For these networks there are only 11 different equivalence
classes of networks on three variables. For instance, consider
the last three networks given in Fig. 6, (d), (e) and (f).
The networks have the following functional decompositions
respectively (labeled d, e and f):
Some basic algebra using the laws of conditional probability
show that the Bayesian networks (d) and (e) have
equivalent functional decompositions and therefore equivalent
independence properties, but the Bayesian network
for (f) is different. The structures S d and S e are said to
be equivalent probability models. Properties of this equivalence
relation have been worked out in general for Bayesian
networks [2] (this is discussed further in Section V). Since
there are k(k \Gamma 1)=2 different undirected arcs one can place
on a network of k variables, that means there are 2 k(k\Gamma1)=2
different undirected networks on the k variables. If the
variables are ordered ahead of time so that an arc can only
point towards a variable later in the ordering, then there
are 2 k(k\Gamma1)=2 different directed networks. There would be
many more if the ordering is allowed to vary (although
some will be equivalent probability models).
B. The sample likelihood
The maximum likelihood approach is the starting point of
most statistical theory, so it is introduced here. First, fix a
structure Sm and its parameters ' m for the model matching
the problem of Table II, and calculate the likelihood of the
sample as follows:
Y
p(case
where the case probabilities p(case are calculated
using the probability tables given by ' m . This formulation
assumes that each case is independent of the others given
the "true" model Sm that is they are independently
and identically distributed. The "true" model is the unknown
model believed to represent the process generating
the data, and is assumed to exist for purposes of modeling
(perhaps a reasonable approximation exists, perhaps not).
For instance, for structure S d from Fig. 6,
p(case 1 jS d ; ' d
The three terms on the right of this equation are found
from the corresponding entries in the probability tables ' d .
This quantity Equation (2) is called the sample likelihood.
The maximum likelihood approach for fixed structure Sm
chooses the parameters ' m to maximize the sample likelihood

It is important to notice the structure of the maximum
likelihood calculation. The probability appearing
in the likelihood for case 1 is a function of the parameters
used in the conditional probability table for the
variable A. The parameters ' d for the Bayesian network
structure S d can be partitioned into the different parameters
at each node (A; B and C):
where ' d;B represents the parameters for the conditional
probability table for the variable B. The sample likelihood
now becomes:
Y
Notice this product has separate terms for ' d;A , ' d;B , and
likelihood optimization of ' can be decomposed
into maximum likelihood optimization of these
three different variable sets individually. This can be represented
as
to show we have three local maximum likelihood problems,
one for each node. The sample likelihood is said to decompose
for Bayesian networks which have neither deterministic
variables, missing or hidden values, nor undirected arcs
This decomposition also applies
as a network is incrementally modified, for instance during
search [23], [60].
If all the parameters ' d describe probability tables for
binary variables, as in Table II, then Equation (3) corresponds
to a product of binomials. For instance,
where the counts pA and nA give the occurences of
and respectively in the data. As is the case for the
binomial, the maximum likelihood is given by the observed
frequency, d
nA+pA . Likewise for the other variables
and all the entries in the other tables.
An important and common assumption used in computing
the sample likelihood is the complete data assumption.
This holds when no case has missing values. This can be an
6 IEEE TRANSACTIONS ON KNOWLEDGE AND
unrealistic assumption. For instance, if data comes from a
historical medical database it is likely that expensive measurements
would not have been taken and recorded if they
were not considered critical to the diagnosis. The complete
data assumption simplifies calculation of the sample likelihood
for a network. For instance, consider the model for
Fig. 6(f), and consider the likelihood for case 3. Suppose
the variable C had a missing value, "?".
p(case 3 jS d ; ' d
C2fT;Fg
As before, the three terms on the right of this equation are
simply the corresponding entries in the probability tables
f . However, notice the summation outside this. When
there are many of these summations, there is no longer a
simple closed form solution for maximizing the sample like-
lihood. Furthermore, the optimization problem no longer
decomposes, as was demonstrated with Equation (3). Hidden
variables lead to the same problem, and violate the
complete data assumption, because the summations above
always appear in the sample likelihood.
A concept central to these and subsequent techniques is
the family of statistical distributions known as the exponential
family [26], [63]. An introduction in the context of
probabilistic networks appears in [23]. This family, which
includes the Gaussian, the Bernoulli, and the Poisson has
the general functional form of
which lends itself to many convenient computational properties
including compact storage of the training sample,
simple calculation of derivatives, and fitting guaranteed to
be linear in the size of the sample. One needs to become familiar
with these features of the exponential family in order
to understand many of the recent developments in learning
probabilistic models. Many of the properties of the sample
likelihood, the impact of complete data assumption, exact
solutions to the maximum likelihood equations and so
forth follow directly from standard results for the exponential
family-the effort is usually expended in formulating
the probabilistic network as a member of the exponential
family, and then the standard results for exponential family
follow [26], [63].
C. Basic statistical considerations
Suppose the structure Sm of a network on discrete or
Gaussian variables is fixed. Then it remains to learn the
. For the probability tables considered earlier
and with enough data, the sample likelihood is a well-behaved
differentiable function of its parameters. This is
often called a parametric problem. A non-parametric prob-
lem, in contrast, has potentially an infinite number of pa-
rameters, or no coherent likelihood function is defined so
it is un-parameterized. This is not always clear from the
literature because in some cases a model is presented in a
non-parametric manner, whereas it can be given a parametric
basis (classification trees are an example [64], [15]).
Now consider the problem of learning the structures as well,
and remember there are a finite number of them. A fixed
network structure has its own distinct set of parameters.
When allowing a set of different structures, each with its
own parameters, the full probability density has no single,
natural, global real-valued parameterization, but has different
parameterizations depending on which structure is
used. Such problems are sometimes referred to as semi-
parametric, but the same qualifications apply. Of course, a
clever mathematician can coerce a full specification of the
network and its parameters into some single real number.
However, this would be an artificial construct with complex
non-continuous derivatives. Furthermore, for the structures
of Fig. 6, the probability distributions represented
by structure S a are a set of measure zero in the probability
distributions with structure S b , which themselves are a
set of measure zero within S e
1 . By offering these structures
as valid alternatives, the set of measure zero is not to
be ignored. I will refer to this combination of detail-for a
given structure their is a neat parametric model, and structures
form nested hierarchies with some being a subset of
measure zero of others-as the parametric structure of the
problem.
Learning network structures from data is sometimes
termed a model selection problem in the sense that each
network corresponds to a distinct model, and one is to be
selected based on the data. Both non-parametric methods
and model selection are active research areas in modern
statistics [65], [25], [66]. More recently, researchers
in statistics have focused on model uncertainty because it
is accepted that selection of a single "best" model from
an exponential-sized family of models-as is the case for
learning Bayesian networks-is often infeasible [67], [68],
[25]. Rather than selecting a single best model, one looks
at a subset of "reasonable" models, attempting to quantify
uncertainty about them.
D. The complexity of learning
network learning involves choosing from, possibly, an
exponential number of network structures, and giving values
to, possibly, an exponential number of real values. Why
is this a problem? Basic results from computational learning
theory show how difficult this can be, both in terms of
the number of cases required for training, and the time or
space required for the optimization. These two aspects are
referred to as sample complexity and computational complexity
respectively.
In learning there are roughly three distinct phases as
more cases are obtained to learn from: the small sample,
medium sample, and large sample phases. Initially with
1 For the purposes of this paper, a subspace has measure zero if its
integrated area relative to the full space is zero. Usually this means
it is a space of lower dimension. A line has measure zero in a finite
plane, but a rectangle on the finite plane has non-zero measure. A
two-dimensional slice of a cube has measure zero in the full three-dimensional
cube.
BUNTINE: A GUIDE TO THE LITERATURE ON LEARNING GRAPHICAL MODELS FROM
a small sample, learning corresponds to going with one's
biases or priors. With a large sample, learning close to
the "true" model is possible with high probability, where
"close" is measured according to some reasonable utility
criteria such as mean-square error or Kullback-Leibler dis-
tance. This learning should be possible by many reasonable
algorithms that asymptotically converge to the "truth". In
between the small and large sample phase is a medium
sample phase where some algorithms should perform better
than others, depending on how well their particular
biases align with the "true" model. I use the term biases
here in a loose sense. As more cases are obtained to learn
performance may increase gradually or sometimes in
jumps as the algorithm better approximates the "truth".
This is illustrated by the learning curve in Fig. 7 which
plots error of some idealized algorithm as it gains more
cases (represented by the sample size N ). The asymptotic
error0.0
Bayes optimal error
small
sample
medium
sample
large
sample
Fig. 7. An idealized learning curve.
error in this example approaches the Bayes optimal error
rate from above. Without prescience, there will be a lower
bound on what error rate can be achieved by any algorithm
(for instance, in predicting coin tosses from a fair coin, the
Bayes optimal error rate is 50%). The theory of learning
curves is developed, for instance, in [69]. Suppose the hypothesis
space is a family of probabilistic networks (S
K. Results from computational learning theory
[70] show that under many conditions the transition
to the large sample phase is made when the sample size is
given by
This sample size is the sample complexity. For the discrete
Bayesian networks discussed earlier, the first term will be
exponential in k (the number of variables), and the second
term quadratic.
Of course, this ignores the issue of computational com-
plexity. Given that there are an exponential number of
networks, it should not be surprising that in some formula-
tions, learning a Bayesian network is an NP-complete problem
[71], [72], [36]. In some formulations, learning is viewed
as a maximization problem: find the network maximizing
some quality measure. As is the case for the the sample
likelihood, these scores usually decompose, often because
they are based on the sample likelihood, see for instance
[61], [23], [37], [62]. The optimization problem is to find a
network S on variables X maximizing some function of the
quality(xjparents S (x); sample)
where the network S influences the quality measure
through the parents function, parents S (:), and the quality
measure may be a log-probability, log-likelihood, or a
complexity measure (to be minimized). These measures
are discussed further in Section VIII. This maximization
problem is an instance of a maximum branchings problem
(see the discussion in [37]) which in general (allowing
any quality function at the nodes) is NP-complete even if
variables in network are restricted to have at most 2 par-
ents. It is polynomial if each variable has at most 1 parent.
Another variation of this problem, discussed in [37], is to
find the best l networks in terms of the quality measure.
For Bayesian networks, this search problem is also confounded
because of the existence of equivalent networks.
Nevertheless, experience with existing systems shows that
standard search algorithms such as greedy algorithms and
iterated local search algorithms often perform well. Basic
greedy search is explored in [35]. Furthermore, the search
problem adapts nicely to branch and bound using some
standard methods from information theory to provide the
bounds [73], and savings over an exhaustive search appear
to be many orders of magnitude.
IV. Parameter fitting
For a fixed graphical structure, Sm , the parameter fitting
problem is to learn the parameters ' m from data. The
mathematics of fitting parameters to a Bayesian/Markov
network is an extension of standard fitting procedures in
statistics. Fitting algorithms exist for Bayesian networks
and more general probabilistic networks in the cases of
complete and missing data [74], [42], [75], [76]. See Whittaker
for a more extensive discussion and review of methods
and theory. In the case of a Bayesian network with
complete data, where the distributions at the nodes are
discrete probability tables or Gaussians, fast close form solutions
exist that can be computed in time proportional
to the size of the data set. As an example, consider fitting
the model of Fig. 6(a) to the data in Table 6. Each
of the probabilities OE in this model occurs in the sample
likelihood in the form OE which has a maximum
at -
n+m . The maximum likelihood solution for the
parameters is therefore equal to the observed frequency of
the relevant probabilities:
In other cases, a variety of iterative algorithms exist that
make use of these fast closed form solutions as a subrou-
tine. Some common techniques I shall not explain here are
the expectation maximization (EM) algorithm [77] and the
iterative proportional fitting (IPF) algorithm [75]. Once
again, the exponential family is important here.
Maximum likelihood approaches suffer from so-called
sparse data because, for instance, they may become undefined
whenever a table of counts total to zero. Consider the
model of Fig. 6(e) and consider estimating
there are no instances of in the sam-
ple, so the maximum likelihood estimate for this probability
is undefined since the sample likelihood does not exist.
For k binary variables and a fully connected Bayesian net-work
(where every two variables are directly connected),
clearly need greater than 2 cases in the sample for the
maximum likelihood estimate to be defined.
A related problem is the problem of over-fitting. Suppose
sparse data is not a problem. Observe the maximum likelihood
estimate above for This was equal to
1.0 because in the data, all observed cases of the variable C
had the value T . Now this is based on four cases. It would
seem reasonable that the "true" value could be 0.9, and
by chance have all T 's in the data. The estimate 1.0 must
be an upper bound on the probability. By definition, the
maximum likelihood value (1:0 4 ) must be an over-estimate
of the "true" sample likelihood (0:9 4 ). As the sample size
gets larger and larger, the over-estimate will gradually converge
to the "true" value; assured in most cases by large
sample properties of maximum likelihood theory (for an
introduction see [78]). However, for small samples, the
maximum likelihood value may be much larger than the
"true" likelihood, and in general the maximum likelihood
solution will attempt to fit the data as well as possible-for
instance, regression using 10 degree polynomials will fit 11
data points exactly, whereas for 11 data points one might
more reasonably attempt to fit a 2 or 3 degree polynomial
and assume the remaining lack of fit is due to noise in the
data. The maximum likelihood parameter values are therefore
said to over-fit the data. This is a well-known problem
in supervised learning, for instance as addressed by pruning
methods for classification trees [64], [15].
The Bayesian Maximum a-posterior (MAP) approach extends
the maximum likelihood approach by introducing a
prior probability. Good introductions to this simplified
Bayesian approach and some of its extensions can be found
in [79], [80]. The approach places a probability distribution
on the unknown parameters ' and reasons about them
using the axioms of probability theory. The likelihood is
augmented with a prior that gives the initial belief about
before seeing any data. Consider just the column of data
for A in Table II, and consider ' A , the parameter giving
the probability of A. By Bayes Theorem:
p(sample)
where the numerator contains the sample likelihood and
the prior, and the denominator is obtained by integrating
the numerator,
Z
Again, these computations become simplified in some cases
of the exponential family, mentioned previously, Gaussians,
Bernoulli, and so forth. An example is given in Fig. 8. The
Fig. 8. Priors, likelihoods and posteriors for ' A .
left graph shows two different priors. These priors are Beta
distributions with parameters ff marked on the plot. The
second prior with has a mild preference for ' to
be about 0.625, whereas the other prior is agnostic. The
middle graph shows the likelihoods for 3 different samples
(0,1 or 2 counts of in a sample size of 4), and the
right graph shows the resulting posterior for the (2 \Theta
posteriors resulting. The cluster of three peaks at the top
are three posteriors for the prior how
the agnostic prior more influenced by
the likelihood, whereas the three posterior peaks for the
mild prior reflect the shape of the prior quite strongly. The
maximum posterior value is the value of ' at the maximum
of each curve. Notice how it is effected by both the prior
and the likelihood.
Many general algorithms exist for addressing parameter
fitting problems of probabilistic networks: missing and latent
variables, large samples, recursive or incremental tech-
niques, special nodes, and subjective priors [26], [24], [81],
[25], [23], [42]

Table

III lists the major techniques and their
application. References given are introductions, new extensions
or examples of their use, and are by no means
a thorough list of references in the area. The common
versions of the EM and IPF algorithms, and mean field
theory are based on the exponential family, although generalizations
exist. Used in conjunction with these methods
are a large number of optimization techniques, for
finding a MAP, or computing the various quantities used
in the Laplace approximation. Several optimization techniques
are specific to parameter fitting in learning. This
includes the Fisher Scoring method [89], which is an approximate
Newton-Raphson algorithm, and stochastic optimization
which computes gradients on subsamples or individual
cases at a time [90]. Variations of this method are
popular in neural networks [91], having been a feature of
early methods [92], and have proven to yield computational
BUNTINE: A GUIDE TO THE LITERATURE ON LEARNING GRAPHICAL MODELS FROM
Algorithm Problems Refs.
MAP general [25]
Laplace 2nd-order approx. [25], [82]
EM missing and hidden values [77], [76], [83]
IPF undirected network [75]
mean field approximate moments [84], [22]
Gibbs approximate moments [85], [86]
MCMC approximate moments [87], [88]


III
Some general algorithms for parameter fitting
savings in many studies.
An extension of parameter fitting to handle sequential
(on-line) learning and missing data is described in [93].
This uses Bayesian methods to overcome the problems of
sparse data, by defining a Dirichlet prior of entries for the
probability tables. A full implementation in described in
[94]. Extensions have been made to Gaussians and other
popular nodes types for the Bayesian network [95]. When
combined with some structure elicitation, techniques for
parameter fitting can prove powerful in applications, for
instance in dynamic models in the medical domain [96],
[54].
V. Structure identification methods
Ignoring the issue of sample size for the moment, a difficult
question is whether particular network structures with
or without latent variables are identifiable in the limit with
probability 1. That is, assuming there are large amounts of
data to accurately estimate various probabilities, can the
"true" probabilistic network be reconstructed at all in the
sense that a learning algorithm, given a sufficiently large
sample, will invariably return a hypothesis (graphical structure
and parameters) close to the "truth"? This question is
formalized and addressed from several angles in computational
learning theory [97] under the name of identification
and learnability, as well as in statistics [78], [26] under the
name of consistency. This is the situation of N ! 1 in
Fig. 7.
In Bayesian networks, this question is confounded by
the existence of equivalence classes of graphs (one example
of a redundant model [78]) and by the use of hidden
or latent variables. For instance, consider the networks
given in Fig. 6 again. The Bayesian networks (d) and (e)
have equivalent probability models but the Bayesian net-work
for (f) is different. Therefore, Bayesian networks (d)
and (e) have equivalent sample likelihoods and cannot be
distinguished from data without some additional criteria or
knowledge, whereas the Bayesian network (f) could be identified
from data alone. A theoretical tool used to analyze
identifiability is the equivalence of graphical models with
latent variables [98], [56], [99] and without [100], [101], [2],
[102], and more recently involving causality where variables
are manipulated [57]. A thorough treatment of the issues
of equivalence, latent variables, and causality appears in
[3]. In some cases, only a class of equivalent graphs can be
reconstructed from data, and in other cases latent variables
and their properties cannot be identified uniquely.
These identification methods have lead to some of the
earliest algorithms for learning structure from data [103],
[56], and a related approach that also combines cross validation
to address model selection is [104]. Identification
methods are also used in TETRAD II, the successor to
TETRAD [12].
The theory of network identification from data and net-work
equivalence are a precursor to techniques for learning
from medium sized samples of Fig. 7. Network equivalence
is an important concept used in some Bayesian techniques
for learning Bayesian networks from data, used in advanced
work on priors for Bayesian networks [105], [37]. This will
be discussed later.
VI. Diagnostics, elicitation and assessment
The day to day practice of learning and data analysis
may have a learning algorithm at its core but a lot of the
work involves modeling and assessment: building a model
and trying to find out what is going on with the data, and
with the expert's opinions. Some of the work relevant to
learning here comes from statisticians who generally have
more experience [106], [107] and decision analysts who use
these methods in constructing systems and working with
experts [41], [108].
The basic problem of elicitation is a twist on the problem
of knowledge acquisition for expert systems.
ffl In the medium sample regime, which applies fre-
quently, data should be complemented with prior
knowledge and constraints if reliable and useful results
are to be obtained.
ffl Prior knowledge can often only be obtained from the
domain experts by the manual process of knowledge
elicitation.
ffl Domain experts can be poor at judging their own limitations
and capabilities, and estimating probabilities
[109]. One of the common mistakes of beginners is to
assume that the expert's claims are valid.
In applications these issues are crucial because a learning
problem does not come prepackaged in its own neat wrapper
with instructions for assembly: "here's the data, use
these five variables, and try the C4.5 tree program." A
learning problem is usually embedded in some larger prob-
lem. A domain expert may be needed just to circumscribe
the learning component: which variables might be used,
what is being predicted from what, and so forth. Sometimes
this is crucial to success, and the learning algorithm
used is almost incidental [110].
A number of techniques exist at the interface of learning
and knowledge acquisition. Diagnostics are measures
used to evaluate particular model assumptions [111], [112]
[113]. Sensitivity analysis [114] measures the sensitivity of
the results of a study to the model assumptions, using the
same techniques taught to engineers everywhere: wiggle
the inputs to the model (in the case of learning, this means
the constraints and priors) and watch how the output of
the model wiggles. Assessment and elicitation is the usual
process discussed in manual knowledge acquisition of interviewing
an expert in order to obtain prior estimates of
relevant quantities. Because the elicitation and evaluation
of probabilistic networks is a well developed area, the further
refinement of networks via learning is made possible,
as is discussed later under priors.
VII. Learning structure from data
The earliest result in structure learning was the Chow
and Liu algorithm for learning trees from data [115]. This
algorithm learns a Bayesian network whose shape is a tree.
If there are k variables, then there are O(k 2 ) trees, much
less than the exponential number of Bayesian networks.
The sample complexity is thus O(2 log more than the
sample complexity for each tree, which is O(k), thus learning
is feasible from small samples. Furthermore, the computational
complexity of searching for a tree shaped net-work
requires at most a quadratic number of network eval-
uations. Herskovits and Cooper [116] demonstrated on a
problem of significant size that complex structure learning
was possible from quite reasonable sample sizes (in their
case, about 10,000), despite being faced with a potentially
exponential sample complexity and an NP-complete search
problem. Other early work on structure learning was often
based on the identification results discussed in the previous
section, for instance [103], [56], [104], [117].
Problems like learning the structure of a Bayesian net-work
suffer when samples are smaller. This happens because
of over-fitting in the structure space, similar to over-fitting
in the parameter space discussed previously. Maximum
likelihood and hypothesis-testing methods provide
techniques for comparing one structure to another, "shall
add an arc here?" "Is model S c better than model S f ?"
This is done, for instance, using the likelihood ratio test
[42], [43]. Repeated use of this test can lead to problems
because, by chance, hypothesis tests at the 95% confidence
level should fail 1 in 20 times, and hundreds of such tests
may need to be made when learning a network structure
from data. A comparable problem in the statistics literature
is variable subset selection in regression. In this prob-
lem, one seeks to find a subset of variables on which to
base a linear regression. The pitfalls of hypothesis testing
in this context are discussed in [67]. The basic problem
is that model selection focuses on choosing a single "best"
model.
For discrete variables at least, the problem of learning
Bayesian networks from complete data is related to the
problem of learning classification trees, exemplified by the
CART algorithm [64] in statistics and ID3 and C4 in artificial
intelligence [15]. This relationship holds because
the sample likelihood for a binary classification tree can be
represented as a product of independent binomial distribu-
tions, just like the sample likelihood for the Bayesian networks
on binary variables described in Section III. Both
problems also have a similar parametric structure. The
classification tree problem has a long history and has been
studied from the perspective of applied statistics [64], artificial
intelligence [15], Bayesian statistics [118], minimum
description length (MDL) [119], [120], genetic algorithms,
and computational learning theory. An adaptation of a successful
tree algorithm to an algorithm for learning Bayesian
networks appears in [121], and the relationship between the
two approaches is discussed in [122].
Another adaptation, which is not quite as direct, is
the Constructor algorithm of [104] which adapts the cost-
complexity technique from the CART algorithm for trees.
There are a variety of heuristic techniques developed for
trees, including the handling of missing values [123] and the
discretization of real-valued attributes [124], which have yet
to find their way into algorithms for probabilistic networks.
VIII. Statistical Methodology
In most work on learning structure, researchers have applied
standard statistical methodology for fitting models
and handling over-fitting. It is therefore appropriate to
discuss these standard methodologies, done so in this sec-
tion. The problem of over-fitting was encountered and addressed
by the earliest methods. It is important to note
that the role of a statistical methodology is to convert a
learning problem into an optimization problem. Some of
the statistical methodologies, despite their wide philosophical
differences, reduce a learning problem to the same kind
of optimization problem, so the practitioner could well be
left wondering what all the differences are about. It is
also important to note that most structure learning is built
around some form of parameter learning as a sub-problem.
In general, the many different structure learning methods
are extensions of the general algorithms summarized in Table
III. In some cases, this can be as simple as placing a
model selection wrapper around a parameter fitting system
[125], in other cases more sophistication is layered on top.
It is perhaps unfortunate that so many different, competing
statistical methodologies exist to address essentially
the same problem. Partly, this stems from the apparent impossibility
of handling smaller sample learning problems in
any objective manner, and the difficulty of establishing a
basis on which a statistical methodology can be judged.
See, for instance, the efforts made to compare different
learning algorithms in [30], and consider that a statistical
methodology is a higher level of abstraction than a learning
algorithm. A discussion of the Bayesian perspective
on the issues of learning appears in [26], touching on prior
probabilities, and subjective statistical analysis. Different
disciplines have addressed these problems in parallel while
they attempted to extend the classical maximum likelihood
and hypothesis testing approaches from statistics. Each
methodology comes with a cast of staunch protagonists
and antagonists and a litany of standard claims, dogma,
paradoxes, and counter-claims. It is useful to become familiar
with the different approaches and the mappings and
approximations between them to better understand their
differences, however this can be difficult given the confusing
state of the literature. Each methodology has its particular
strengths that make it suitable under certain conditions:
ease of implementation, adequate for large samples, more
BUNTINE: A GUIDE TO THE LITERATURE ON LEARNING GRAPHICAL MODELS FROM
appropriate for the engineer, availability of software and
training. and so forth. I believe no one methodology is
superior in all respects.
My comments in this review are colored from a Bayesian
perspective. I have tried to keep my comments below to the
realm of what is "generally believed" by those knowledgeable
in this area rather than merely repeating the dogma of
each community. Also, this section is not an introduction
to these methodologies. I include appropriate tutorial references
below. Finally, there are really hundreds of different
methodologies, one for each small cluster of researchers.
The list below presents different corners in a continuum.
A. Maximum likelihood and Minimum cross entropy method

The maximum likelihood approach says to find the net-work
structure Sm whose maximum likelihood over parameters
' m is the largest
'm
The minimum cross entropy approach says to find the
structure whose minimum cross entropy with the data is
the smallest. These two approaches are equivalent [126],
and they are also well known to suffer from over-fitting, as
discussed in Section IV. If the "true" model has one single
equivalent representative in the hypothesis space, then
the maximum likelihood approach is consistent in the sense
that in the limit of a large sample it will converge on this
"truth" [78]. The maximum likelihood method can also be
viewed as a simplification of most other approaches, so it is
an important starting point for everyone. When in a large
sample regime, the best strategy is to use the maximum
likelihood approach to avoid all the mathematical or implementation
details of the more complex approaches. The
results from computational learning theory for bounding
the onset of the large sample phase are useful for deciding
when to do this. For Bayesian networks, the maximum
likelihood approach has been applied by [127], [116].
The paper by Herskovits and Cooper was the major break-through
in learning Bayesian networks. It was clear from
this paper that MDL and Bayesian methods, which extend
the maximum likelihood approach, could be applied in all
their detail.
B. Hypothesis testing approaches
Hypothesis testing is the standard model selection strategy
from classical statistics. For probabilistic networks
methods are well developed and a variety of statistical software
exists [28], [43], [13]. As mentioned before, the problem
is that this is only a viable approach if a small number
of hypotheses are being tested. Clever or greedy search
techniques can help here [128] by reducing the number of
hypothesis tests required. Another way for thinking about
this is to deal with multiple hypotheses: let hypothesis testing
return a set of possible models rather than expecting it
to isolate a single one [128]. This strategy then resembles a
Bayesian approach where multiple models are considered.
This is discussed in the context of probabilistic networks
below.
C. Extended likelihood approaches
A number of extensions to the maximum likelihood approach
have been proposed to overcome the problem of
over-fitting, and to overcome the problems inherent in hypothesis
testing. These approaches replace the sample likelihood
by a modified score that is to be maximized. Examples
include the penalized likelihood, Akaike information
criteria (AIC), the Bayesian information criteria (BIC) and
others [66], [129]. Typically, this involves minimizing a formula
such as the BIC formula
BIC(Sm jsample)
where c
' m is the maximum likelihood estimate of ' m fixing
the structure to be Sm , N is the sample size and dim('m )
is the dimensionality. The BIC criteria and some related
variations are asymtotically Bayesian but avoid specification
of the prior, and are similar to variations of the minimum
information complexity approaches described below.
Examples for undirected probabilistic networks with the
BIC criteria appear in [67].
D. Minimum information complexity approaches
There are several different schools under the general
rubric of minimizing some information complexity measure
("code length"), for instance minimum description length
(MDL) [130], minimum message length [131], and minimum
complexity [132]. A simple approximation for MDL
is equivalent to the BIC above, but other variations involve
statistical quantities such as the Fisher Information,
and hypothesis dependent complexity measures chosen particularly
for the domain. These approaches are popular
among engineers and computer scientists who learn coding
and information theory as undergraduates. From one
perspective, these methods are related to Bayesian MAP
methods although there are subtle differences [133]. One
advantage that some proponents claim of this approach
(particularly those in the MDL school) is that it requires
no prior and is hence objective. In most instances a corresponding
"implicit prior" can be constructed from the
code. Some authors use this approach so that they can
use Bayesian methods in disguise without being ridiculed
by their anti-Bayesian colleagues. Search bounds, for instance
[134], are one area where the information complexity
approach takes advantage of the techniques developed
in information theory. Suzuki has developed a branch and
bound technique for learning Bayesian networks based on
information-theoretic bounds [73]. For Bayesian networks,
MDL has been applied by [61], [135], [136].
Resampling approaches
Modern statistics has developed a variety of resampling
schemes for addressing over-fitting in parametric situations
like learning networks. Resampling refers to the fact that
pseudo-samples are created from the original sample. A
popular approach is cross validation, applied by [104]. Re-sampling
schemes have been used to great success in applied
multivariate statistics, see for instance a tutorial in
[137]. Their strength lies in the fact that they are reliable
black box method that can be used without requiring
some of the complex mathematical treatment found in the
Bayesian or minimum complexity methods [138]. These
resampling schemes therefore provide a good benchmark
for comparison with more complex schemes which have additional
mathematical and implementation pitfalls. Their
theoretical justification is large sample, although they have
empirical successes in the small sample case for a wide
range of problems.
F. Bayesian approaches
There are a rich variety of Bayesian methods, and depending
on the approximations and shortcuts made, most
of the previous methodologies can be reproduced with
some form of Bayesian approximation. In its full form the
Bayesian approach requires specification of a prior probability
(for a tutorial and a list of references, see [139]). A
good general introduction to Bayesian methods for learning
Bayesian networks can be found in [79]. Advanced introductions
and reviews of Bayesian methods for learning can
be found in [25], [26], [24].
The Bayesian approach has many different approxima-
tions. The simplest MAP approach seeks to find the structure
Sm maximizing the log-probability
log
The term p(samplejSm ) is called the evidence and differs
from the likelihood p(samplejSm The evidence is the
average sample likelihood rather than the maximumsample
likelihood used in the earlier techniques:
Z
'm
Sometimes a relative value is calculated instead,
for some base structure S 0 . This is called the Bayes factor
and a variety of techniques and approximations exist for
computing it [25], [26], [23].
The basic technique for Bayesian learning of Bayesian
network structures from complete data uses standard
Bayesian methods, and was worked out in one form or an-
other, by many [140], [35], [121], [111], [112], [68], [141],
[142], [143], [37], [38]. Certainly, these techniques use standard
Bayesian manipulations and should be obvious to
most students of Bayesian theory. The general case for
the exponential family is worked through in [105]. Good
summaries of this line of work can be found in [111], [68],
[144], [37], [23], and a thesis covering many of the issues is
[36].
The full Bayesian approach is a predictive one: rather
than returning the single "best" network, the aim might
be to perform prediction or estimate probabilities for new
cases. For instance, one might be interested in the probability
of new cases based on the sample, p(new-casejsample).
In general this is estimated by averaging the predictions
across all possible networks using the probability identity
Sm
This situation is represented in Fig. 9. This approaches
GIBBS
New Data
|Sample)
p(New
* =Fig. 9. Averaging over multiple Bayesian networks
matches the intuition: "five different networks all seem
quite reasonable so let's hedge our bets and combine them.''
In practice this full summation is not possible so approximations
are used. Bayesian methods for learning probabilistic
networks in this more general sense can be found in
[121], [68], [143], [144], [145], [35], [146], [147]. Computational
aspects of finding the best l networks are discussed
in [37]. A related concern is how to combine the posterior
network probabilities efficiently and to compute conditional
posterior probabilities [148], [111], [32].
A general Bayesian algorithm family for inference that
applies in any context, parameter fitting or structure learn-
ing, is the Markov Chain Monte Carlo (MCMC) family of
algorithms. An introduction is given in [149], [23], and an
extensive review is given by [87]. This family uses the following
kind of trick. Suppose we wish to sample from the
distribution p(A; B; C). In general this might be a complex
distribution and no convenient sampling algorithm
may be known. When the complete data assumption is
violated for instance, as discussed in Section III-B, it is
quite easy to get an intractible sample likelihood distribution
for network parameters, and hence the posterior distribution
for network parameters may have no convenient
functional form to sample from-this is exactly the kind
of problem that MCMC methods were designed for. They
can even be used for instance, to estimate posterior predictions
when learning with complex parametric systems such
as sigmoidal feed-forward neural networks [88]. To sample
from p(A; B; C) using the Gibbs sampler, the simplest
kind of MCMC method, we start at A 0
repeatedly re-sample each variable in turn according to its
current conditional distribution ("-" should be read as "to
BUNTINE: A GUIDE TO THE LITERATURE ON LEARNING GRAPHICAL MODELS FROM
be sampled
Probabilistic networks are an ideal framework for developing
MCMC methods because these conditional distributions
can be generated automatically from the network.
MCMC methods can be used for parameter fitting, to sample
different network parameters, and for structure learn-
ing, to sample from different possible probabilistic network
structures. Use of MCMC methods for learning probabilistic
networks is discussed in [85], [144], [147], [146],
[23]. Madigan, Gavrin and Raftery [146] refer to the use of
MCMC methods for averaging over multiple probabilistic
networks-the full predictive approach-as Markov Chain
Monte Carlo Model Composition (MC 3 ).
The key distinction between Bayesian and non-Bayesian
methods is the use of priors. Priors can unfortunately
be complex mathematically, so poorly chosen priors can
make a Bayesian method perform poorly against other
methods-a real danger in the case of Bayesian networks
because of their semi-parametric nature. Both informative
priors [68], [111], [121], [37], [35], [38], [146], [147], and non-informative
priors can be used. A fundamental assumption
is that equivalent network structures should have equivalent
priors on their parameters [121], [60], [37], [150]. For
instance, consider structures S d and S e from Fig. 6. The
prior probability p(' d jS d ), by virtue of equivalence, can be
converted into a prior for ' e using a change of variables
with the Jacobian for the transformation:
Notice this prior is constructed from the prior for S d , and
is not necessarily equal to the prior actually used for S e ,
The assumption of prior equivalence sets these
two priors equal, something not applicable if the network
has a causal interpretation [58]. This gives a set of functional
equations that the prior should satisfy. This basic
theory and other properties of priors for Bayesian networks
is discussed in [105], extending techniques presented in [37].
The ability to use a variety of informative, subjective
priors for Bayesian networks is one of their strengths. Informative
priors can include constraints and preferences on
the structure of the network [121], [37], as well as preferences
on the probabilities, and even using the expert to
generate "imaginary data" [146]. An example in the language
of chain graphs (an extension to Bayesian networks)
is given by [38]. The potential for using Bayesian networks
as a basis for knowledge refinement has been suggested by
[121], [37], [111], [146], and in applications this offers an
integrated approach to the development and maintenance
of intelligent systems, long considered one of the potential
fruits of artificial intelligence.
IX. More on Learning Structure
An exact algorithm for handling incomplete data or missing
values can be found in [151]. The problems involved
here for exact methods were previously explained in [35].
While impractical for larger problems, this could serve as
a tool to benchmark on non-trivial sized problems for the
many approximate algorithms that exist, for instance, some
are mentioned in Table III.
Simple clustering algorithms learn Bayesian networks
with a single latent/hidden variable at the root of the net-
work. So these kinds of problems have been addressed in a
limited sense for many years in the AI and statistics community
[152]. A Bayesian method is [153], [51]. Likewise.
missing values can be handled by the well known EM algorithm
[76], or more accurately by Gibbs sampling [85].
More recent versions of these clustering algorithms search
over possible structures as well [51].
Some algorithms do not fit neatly into the categories
above. Learning Markov (undirected) networks from data
is related to the early Boltzmann machine from neural networks
[21]. Also the earlier Bayesian methods seemed to
require as input a strict ordering of variables [35], [121],
whereas the identification algorithms did not require this.
one thought is a combination of Bayesian with identification
algorithms [33]. But Bayesian methods do equivalent
things in the large sample case to the independence tests
used by identification algorithms, and the strict ordering
is not entirely necessary for the Bayesian algorithms [32],
[37]. A variety of hybrid algorithms exist [59], [104], [12],
[73] that provide a rich source of ideas for future development

X. Constructing learning software
For a variety of network structures with latent variables
and different parametric nodes (Logistic, Poisson,
and other forms), the BUGS program can generate Gibbs
samplers automatically [154], [86]. This effectively allows
data analysis algorithms to be compiled from specifications
given as a probabilistic network, and the technique
addresses a number of non-trivial data analysis problems
[155], [86]. Unfortunately, Gibbs sampling without much
thought to domain specific optimization can be time intensive
because convergence may be slow, so other methods
need to be developed to make this approach more
widely applicable. Other algorithm schemas from Table
III can be applied within this compilation framework
as well, so it may be possible to construct more efficient
algorithms automatically. An exposition of the techniques
used by algorithms for learning Bayesian networks-
exact Bayes factors, and differentiation-
all readily automated-can be found in [23], [156].



--R

"Real-world applications of Bayesian networks: Introduction"
"Equivalence and synthesis of causal models"

"A definition and graphical representation for causality"
"Graphical models, causality, and intervention"
"Local computations with probabilities on graphical structures and their application to expert systems (with discussion)"
"Correlation and causation"
Probabilistic Reasoning in Intelligent Systems
"Influence diagrams"

"Attitude formation models: Insights from TETRAD"
"Inferring causal structure among unmeasured variables"
"Network methods in statistics"
Introduction to the Theory of Neural Computation

Building Expert Systems
"Current developments in expert systems"
"In- ductive knowledge acquisition: A case study"
"An experimental comparison of knowledge engineering for expert systems and for decision anal- ysis"
"Probabilistic similarity networks"
"Connectionist learning of belief networks"
"Mean field theory for sigmoid belief networks"
"Operations for learning with graphical models"
Tools for
"Bayes factors and model uncer- tainty"
Bayesian Theory
"Graphical models for discovering knowl- edge"
"Software for belief networks"

Machine Learning
"Diagnos- tic systems created by model selection methods: A case study"
"Properties of Bayesian belief network learning algorithms"
"An algorithm for the construction of Bayesian network structures from data"
"An evaluation of an algorithm for inductive learning of Bayesian belief networks using simulated data sets"
"A Bayesian method for the induction of probabilistic networks from data"
Networks: from Inference to Construction
"Learning Bayesian networks: The combination of knowledge and statistical data"
recursive models Induced From Relevant knowledge, Observa- tions, and Statistical Techniques"
"Thinking backwards for knowledge acquisition"
"Bayesian networks without tears"
"Decision analysis and expert systems"
Graphical Models in Applied Multivariate Statis- tics
Introduction to Graphical Modelling
"Bayesian networks for knowledge representation and learning"
Spatial Statistics
"Independence properties of directed Markov fields"
"Graphical models for associations between variables, some of which are qualitative and some quantitative"
"Chain graphs for learning"
"Finite state machines and recurrent neural networks -automata and dynamical systems approaches"
"On substantive research hy- potheses, conditional independence graphs and graphical chain models"
"Bayesian classification with correlation and inheritance"
Planning and Control
Decision Analysis with Continuous and Discrete Variables: A Mixture Distribution Approach
"Uncertain reasoning and forecasting"
"Causal diagrams for empirical research"
"A theory of inferred causation"
"On the identification of nonparametric structural equations"
"A Bayesian approach to learning causal net- works"
"Causal inference in the presence of latent variables and selection bias"
"Hyper Markov laws in the statistical analysis of decomposable graphical models"
"Using causal information and local measures to learn Bayesian networks"
"Learning Bayesian networks: A unification for discrete and Gaussian domains"
Information and exponential families in statistical theory
Classification and Regression Trees

"Small-sample and large-sample statistical model selection criteria"
"Bayesian model selection in social research (with discussion by gelman & rubin, and hauser, and a rejoiner)"
"Model selection and accounting for model uncertainty in graphical models using Occam's window"
"Rigor- ous learning curve bounds from statistical mechanics"
"Decision theoretic generalizations of the PAC model for neural net and other learning applications"
"Learning bayesian networks is np-complete"
"Learning and robust learning of product dis- tributions"
"On an efficient mdl learning procedure using branch and bound technique"
"Hierarchical interaction models"
"On the effective implementation of the iterative proportional fitting procedure"
"The EM algorithm for graphical association models with missing data"
"Maximum likelihood from incomplete data via the EM algorithm"

"A tutorial on learning Bayesian networks"
"Decision analysis: perspectives on inference, decision, and experimentation"
"Decision theoretic sub-sampling for induction on large databases"
"Laplace's method approximations for probabilistic inference in belief networks with continuous variables"
"Accelerated quantification of Bayesian networks with incomplete data"
"Factorial learning and the EM algorithm"
"Markov chain Monte Carlo methods for hierarchical Bayesian expert systems"
"A language and program for complex Bayesian modelling"
"Probabilistic inference using Markov chain Monte Carlo methods"
Bayesian Learning for Neural Networks
Chapman and Hall
"A stochastic optimizationmethod"
Efficient Training of Feed-Forward Neural Net- works
McClelland, and the PDP Re-search Group
"Sequential updating of conditional probabilities on directed graphical structures"
"aHUGIN: A systems creating adaptive causal probabilistic networks"
"Parameter adjustment in Bayesian networks. the generalized noisy OR-gate"
"Tradeoffs in constructing and evaluating temporal influence diagrams"
"On learning in the limit and non-uniform (ffl; ffi)-learning"
"Equivalence of causal models with latent variables"
"An algorithm for deciding if a set of observed independencies has a causal explanation"
"The chain graph Markov property"
"Identifying independence in Bayesian networks"
"On the Markov equivalence of chain graphs, undirected graphs, and acyclic digraphs"
"An algorithm for fast recovery of sparse causal graphs"
"A system for induction of probabilistic models"
"A characterization of the Dirichlet distribution with application to learning Bayesian net- works"
"The quantification of judgment: Some methodological suggestions"
"Assessment, criticism and improvement of imprecise subjective probabilities for a medical expert system"
Uncertainty: A Guide to Dealing with Uncertainty in Quantitative Risk and Policy Analysis
Judgement under Un- certainty: Heuristics and Biases
"Applications of machine learning and rule induction"
"Bayesian analysis in expert systems"
"Learning in probabilistic expert systems"
"Sequential model criticism in probabilistic expert systems"
"Sensitivity analysis for probability assessments in Bayesian networks"
"Approximating discrete probability distributions with dependence trees"
"Kutat'o: An entropy-driven system for construction of probabilistic expert systems from databases"
"Automated construction of sparse Bayesian networks"
"Learning classification trees"
Stochastic Complexity in Statistical Enquiry
"Coding decision trees"
"Theory refinement of Bayesian networks"
"Classifiers: A theoretical and empirical study"
"Unknown attribute values in induction"
"Multi-valued interval discretization of continuous-valued attributes for classification learning"
"MLC++: A machine learning library in C++"
Information Theory and Statistics
"An entropy-based learning algorithm of Bayesian conditional trees"
"A fast model selection procedure for large families of models"
"Three approaches to probability model selection"
"Stochastic complexity"
"Estimation and inference by compact encoding"
"Minimum complexity density estimation"
"Mml and bayesianism: similarities and differences"
"Admissible stochastic complexity models for classification problems"
"Learning Bayesian belief networks: An approach based on the MDL principle"
"A construction of Bayesian networks from databases based on an MDL scheme"
"Statistical data analysis in the computer age"
"A study of cross validation and bootstrap for accuracy estimation and model selection"
"Prior probabilities"
"A Bayesian method for the induction of probabilistic networks from data"
"An influence diagram approach to medical technology assessment"
"Learning in probabilistic expert systems"
Bayesian Methods for the Analysis of Misclassified and Incomplete Multivariate Discrete Data
"Bayesian graphical models for discrete data"
"Strategies for graphical model selection"
"Eliciting prior information to enhance the predictive performance of bayesian graphical models"
"Estimation of the proportion of congenital malformations using double sam- pling: Incorporating covariates and accounting for model un- certainty"
"Minimal assumption distribution propogation in belief networks"
John Wiley
"Learning Bayesian networks: The combination of knowledge and statistical data"
"A method for learning belief networks that contain hidden variables"
Statistical Analysis of Finite Mixture Distributions
"Bayesian classification"
"BUGS: A program to perform Bayesian inference using Gibbs sampling"
"Modelling complexity: BUNTINE: A GUIDE TO THE LITERATURE ON LEARNING GRAPHICAL MODELS FROM applications of Gibbs sampling in medicine"
"Networks for learning"

Uncertainty in Artificial In- telligence: <Proceedings>Proceedings of the Eleventh Conference</Proceedings>
Selecting Models from Data: Artificial Intelligence and Statistics IV

Uncertainty in Artificial Intelligence:

Uncertainty in Artificial Intelligence:
Uncertainty in Artificial Intelligence 5
Bayesian Statistics 4
Artificial Intelligence Frontiers in Statistics
--TR

--CTR
Marek J. Druzdzel , Linda C. van der Gaag, Building Probabilistic Networks: 'Where Do the Numbers Come From?' Guest Editors' Introduction, IEEE Transactions on Knowledge and Data Engineering, v.12 n.4, p.481-486, July 2000
Peter L. Spirtes, Data mining tasks and methods: Probabilistic and casual networks: mining for probabilistic networks, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Sajjad Haider, Belief Functions Based Parameter and Structure Learning of Bayesian Networks in the Presence of Missing Data, International Journal of Hybrid Intelligent Systems, v.1 n.3,4, p.164-175, December 2004
Xiaoming Zhou , Cristina Conati, Inferring user goals from personality and behavior in a causal model of user affect, Proceedings of the 8th international conference on Intelligent user interfaces, January 12-15, 2003, Miami, Florida, USA
Wei Yi Liu , Ning Song, Fuzzy functional dependencies and Bayesian networks, Journal of Computer Science and Technology, v.18 n.1, p.56-66, January
David Maxwell Chickering, Optimal structure identification with greedy search, The Journal of Machine Learning Research, 3, p.507-554, 3/1/2003
Jie Cheng , David A. Bell , Weiru Liu, Learning belief networks from data: an information theory based approach, Proceedings of the sixth international conference on Information and knowledge management, p.325-331, November 10-14, 1997, Las Vegas, Nevada, United States
Jiaying Shen , Victor Lesser, Communication management using abstraction in distributed Bayesian networks, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
Sajjad Haider, A hybrid approach for learning parameters of probabilistic networks from incomplete databases, Design and application of hybrid intelligent systems, IOS Press, Amsterdam, The Netherlands,
Peggy Wright, Knowledge discovery in databases: tools and techniques, Crossroads, v.5 n.2, p.23-26, Winter 1998
Marina Meila , Michael I. Jordan, Learning with mixtures of trees, The Journal of Machine Learning Research, 1, p.1-48, 9/1/2001
Nir Friedman , Dan Geiger , Moises Goldszmidt, Bayesian Network Classifiers, Machine Learning, v.29 n.2-3, p.131-163, Nov./Dec. 1997
Padhraic Smyth , David Heckerman , Michael I. Jordan, Probabilistic independence networks for hidden Markov probability models, Neural Computation, v.9 n.2, p.227-269, Feb. 15, 1997
Thomas D. Nielsen , Finn V. Jensen, Learning a decision maker's utility function from (possibly) inconsistent behavior, Artificial Intelligence, v.160 n.1, p.53-78, December 2004
Peter L. Spirtes, Data mining tasks and methods: Probabilistic and casual networks: methodology for probabilistic networks, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Rong Chen , Edward H. Herskovits, A Bayesian network classifier with inverse tree structure for voxelwise magnetic resonance image analysis, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Clifford S. Thomas , Catherine A. Howie , Leslie S. Smith, A New Singly Connected Network Classifier based on Mutual Information, Intelligent Data Analysis, v.9 n.2, p.189-205, March 2005
Helge Langseth , Thomas D. Nielsen, Fusion of domain knowledge with data for structural learning in object oriented domains, The Journal of Machine Learning Research, 4, 12/1/2003
David J. Miller , Lian Yan, Approximate Maximum Entropy Joint Feature Inference Consistent with Arbitrary Lower-Order Probability Constraints: Application to Statistical Classification, Neural Computation, v.12 n.9, p.2175-2207, September 1, 2000
Russell Greiner , Xiaoyuan Su , Bin Shen , Wei Zhou, Structural Extension to Logistic Regression: Discriminative Parameter Learning of Belief Net Classifiers, Machine Learning, v.59 n.3, p.297-322, June      2005
David W. Albrecht , Ingrid Zukerman , An E. Nicholson, Bayesian Models for Keyhole Plan Recognition in an Adventure Game, User Modeling and User-Adapted Interaction, v.8 n.1-2, p.5-47, 1998
David Maxwell Chickering, Learning equivalence classes of bayesian-network structures, The Journal of Machine Learning Research, 2, p.445-498, 3/1/2002
John Binder , Daphne Koller , Stuart Russell , Keiji Kanazawa, Adaptive Probabilistic Networks with Hidden Variables, Machine Learning, v.29 n.2-3, p.213-244, Nov./Dec. 1997
Jie Cheng , Russell Greiner , Jonathan Kelly , David Bell , Weiru Liu, Learning Bayesian networks from data: an information-theory based approach, Artificial Intelligence, v.137 n.1-2, p.43-90, May 2002
David Maxwell Chickering , David Heckerman, Efficient Approximations for the MarginalLikelihood of Bayesian Networks with Hidden Variables, Machine Learning, v.29 n.2-3, p.181-212, Nov./Dec. 1997
Luc De Raedt , Kristian Kersting, Probabilistic logic learning, ACM SIGKDD Explorations Newsletter, v.5 n.1, July
David Heckerman, Bayesian Networks for Data Mining, Data Mining and Knowledge Discovery, v.1 n.1, p.79-119, 1997
Paolo Frasconi , Marco Gori , Giovanni Soda, Data Categorization Using Decision Trellises, IEEE Transactions on Knowledge and Data Engineering, v.11 n.5, p.697-712, September 1999
Rebecca F. Bruce , Janyce M. Wiebe, Decomposable modeling in natural language processing, Computational Linguistics, v.25 n.2, p.195-207, June 1999
Paul J. Krause, Learning probabilistic networks, The Knowledge Engineering Review, v.13 n.4, p.321-351, February 1999
P. I. Bidyuk , A. N. Terent'Ev , A. S. Gasanov, Construction and Methods of Learning of Bayesian Networks, Cybernetics and Systems Analysis, v.41 n.4, p.587-598, July      2005
Anthony Hunter, Hybrid argumentation systems for structured news reports, The Knowledge Engineering Review, v.16 n.4, p.295-329, December 2001
Nuria M. Oliver , Barbara Rosario , Alex P. Pentland, A Bayesian Computer Vision System for Modeling Human Interactions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.831-843, August 2000
Sreerama K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery, v.2 n.4, p.345-389, December 1998
bayesian networks;learning;graphical models;hidden variables;knowledge discovery;learning structure;probabilistic networks