We talked about Bayes net structure
learning as the problem of optimizing a
scoring function over the space of network
structures. And we also talked about how
the likelihood score, which is the
simplest score that one could come up
with, has significant issues relative to
over fitting. We're now going to look at a
different score that's derived from
Bayesian principles. And we're going to
see how that score, although it has some
surface similarity to the likelihood
score, is a considerably better score in
terms of, it, avoiding of over fitting. So
the Bayesian score is derived from the
Bayesian paradigm, that says that anything
that we have uncertainty over, needs to
have a probability distribution over it.
And so if we have uncertainty over graphs,
then we need to have a prior over graphs.
And if you have uncertainty over
parameters, we need to have uncertainty
over parameters, a probability
distribution. And so if we now define our
optimization problem as that of finding
the graph g that maximizes the probability
of g given d. Now if we rewrite the
probability of G given D using Bayes rule,
we end up with the following expression, P
of D given G times P of G divided by P of
D. So let's look at each of those terms
separately. The first of these is a term
called the marginal likelihood, P of D
given G is the probability of the data
given, the graph. The second of these
terms, P of G, is a prior over graph
structures. And the final term, p of D,
the denominator, is the margi, is called
the marginal probability of the data. Now,
importantly, this marginal probability of
the data is independent of G. And so it's
not going to affect the choice of which
graph we select. And therefore, we can
ignore it in the context of a model
selection problem that is defining, the
single graph, or a graph that maximizes
the score. And so we're going to define
the Bayesian score, score B of G of
relative to data set D, as the log of the
numerator of this expression. So the log
of the marginal likelihood plus the log of
the prior over graphs. Now we might think,
that this score is going to avoid over
fitting because of its use of the prior
over graphs. And although that
prior can play a role, actually is turns
out to be a significantly less important
role than the first of these terms which
is the marginal likelihood. So let's look
at the marginal likelihood in a little bit
more depth. So, the marginal likelihood, P
of D given G, is not as it happens. The
same as the log likelihood. Because
that marginal likelihood is something that
integrates over all possible settings of
the parameters. And so from a mathematical
perspective, what we're going to do is,
we're going to introduce a variable,
theta G, into the probability expression.
And then we're going to integrate it out.
Which is the same as summing it out only
it's a continuous space so we're going to
use integrals. So P of D given G, is the
integral over all possible model
parameterizations, Theta-G, of the
probability of D given G and Theta-G,
times the probability of Theta-G given G.
Now, the first of these two terms is the
likelihood. Which is exactly the, the
component that we used in the log
likelihood score. But, importantly, unlike
the likelihood score, we're not computing
P of D, given G. And theta G, just for the
maximum likelihood parameters, theta hat
G. Rather, we're computing this
probability averaged out over all possible
parameter settings. Which gives us a
considerably less optimistic assessment of
the probability of the data, given a
particular structure. Because we have to
take into consideration, not just a single
parameter setting that is geared
exactly to our data set, which is this
theta hat set of parameters. But rather,
averaging out over all possible parameter
settings Theta G using the prior over
parameters. So that less optimistic
assessment is sort of one intuition as to
why this might not over fit as much. But
it turns out there is another perhaps even
more intuitive explanation as to why this
score reduces over fitting. So let's look
at the, this marginal likelihood term, P
of D given G. And just, wri-, rewrite
it as the probability of all of the
instances X1 up to XM given G. And what
we're going to do is we're going to now
break up this joint distribution using the
chain rule for probabilities. Not the
chain rule for Bayesian networks, just the
chain rule for probabilities. And we can
write that as the probability of X1 given
G, times the probability of X2 given X1
and G, times the probability of X3 given
X1 and X2, times blah, blah, blah, up to
the probability of XM, given all the
previous ones, X1 up to XM minus one, and
G. And if we look at each of these terms,
each of these is effectively making a
prediction over an unseen instance, say XM
given X1 up to XM minus one. So you can
think of it as a almost doing some kind of
cross validation or generalization or
estimate of generalization ability,
because we're estimating the ability to
predict an unseen instance given the
previous ones. And so the probability of d
in some sense incorporates into it some
kind of analysis of generalization
ability. Now, you might say, well, surely
the likelihood does, the, the standard
likelihood score does exactly the same
thing. But a little bit more thought
reveals that if we want to do this kind of
analysis for the maximum likelihood set of
parameters, that maximum likelihood set of
parameters, theta hat g, depends on all.
Of D, all of the instances D. In D. And
so we can't break it down in this way
because if we had, theta hat G on
the right hand side, it's already
incorporating into it all of the instances
including the unseen ones, which is yet
another intuition as to why that, like the
maximum likelihood score tends to over
fit. Now. The maximum, now, the Bayesian
score might look a little bit scary,
because it has all this integral in it.
And, and who knows how we would ever
compute it. It turns out that, for the
case of multinomial Bayesian networks the,
the likelihood, the, the Bayesian score
can actually be written in closed form,
using a function called the gamma
function. The gamma function is. As
written over here, it's also an integral
but, it turns out that the gamma function
is really just a continuous extension of
the factorial function, because gamma X
satisfies the equality gamma X is equal to
X times gamma X minus one. And most
computers have an implementation of the
gamma function in them. So, with the gamma
function we can actually rewrite the
probability of the given G as a product
that looks as follows. The first is first
we have a product over all variables I.
And then we have a, two different products
included in this big, this big outer
product. The first is a product over. The
parent set UI, of, multiplying over all
possible values of the parent set. And
here we have an expression involving gamma
functions, where this expression involves
both dirichlet prior parameters. The
alpha, as well as the sufficient
statistics. So the first product,
enumerates over all possible assignments
to the parents. And then we have an inner
product, yet another inner product, which
enumerates over all possible values of the
variable itself. So, the variable of all
possible values, XIJ of the variable XI.
And once again, we have, gamma terms that
involve both the prior as well as the
sufficient statistics. And the, while this
expression might look still a little bit
scary, it it's something that one can just
plug in to the computer and, and compute
quite easily. Another valuable property of
this marginal likelihood, if we look at it
a little bit more and that we also take
its algorithm is we see that this.
Expression is, which was originally a
product over variables I of some
complicated expression relating to XI, is
actually something that, if we take the
log, it turns into a sum over I of the
family score. Something that can be viewed
as the family score, for, the variable XI
and its parent set. Together. And so just
like other scores that we've seen before,
this, this scoring function can de,
decomposes as a sum over I of terms
involving only X I and its parents and
that we'll see that this property can be
quite important from a computational
perspective. How do we, so now, building
up. From the marginal likelihood. The
second term in this expression is log of P
of G. And so, in order to accommodate for
that, we need to have a prior over P of G.
And, there's a variety of different priors
that people have used. It turns out that a
quite common choice is to simply make P of
G constant, and that. Although that
doesn't impose explicitly any penalty on
complexity it turns out that it works
quite well because of the penalty imposed
on complexity by the marginal likelihood.
But if I want to build in additional
penalties on complexity, we can make the
prior, some, be something that
exponentially penalizes the number of
edges, or penalizes the number of
parameters, and that induces additional
sparsity. Now. Importantly, we don't
actually want to define a prior
probability over graph structures, and
make sure that it correctly normalizes
over all possible structures and even more
so, over all possible acyclic structures.
But fortunately, we don't have to, because
the normalizing constant in this
distribution, T of G, is this constant
across different networks and, and can
therefore be ignored completely, and we
only need to consider the term that
changes with the graph structure, and
ignore the normalizing constant or
partition function. That's the structure
prior. What about the parameter prior. The
parameter prior that we use in the context
of the Bayesian score, the one that's most
commonly used is something called the BDE
prior. And the BDE prior is something that
we've actually seen before, when we were
talking about parameter estimation for
Bayesian networks. And as a reminder, the
BDE prior is defined by two components.
One is an equivalent sample size alpha,
which is the total number of instances
that we might have seen in some imaginary
universe. And the second is a probability
distribution, P zero, typically encoded by
a prior Bayesian network. Zero which in
culture of our prior beliefs about, about
the universe. And the and so we define now
the imaginary counts that we might have
seen for a particular combination of
values for little Xi and a particular
s?ance for its parents to be alpha. Which
is the total number of counts that we've
seen times the probability of that
particular event Xi comma PAi of G in the
network, in a prior network would be zero.
Now, an important note is that the parents
of. The variable x I in the graph G is not
the same as the parents of x I in the
prior network B zero. In fact, in many
cases we choose the network in, the
network B zero to be one that has no
edges, where all variables are
independent. But we compute the
probability distribution in B zero and
then use that to compute the, the
hyperparameters alpha that are used in the
context of the of the, of the learning
problem for, for given graph G. And the
important thing is now that the single
network BO. Provides us with priors for
all of the candidate networks. So we don't
need to elicit priors for exponentially
many networks. We have a single network be
zero in a single equivalent sample size
and we can use that to compute the
parameter prior, P of theta given G, over
all possible networks that we're
interested in evaluating. Now other than
its convenience why this prior is opposed
to others, it turns out that one can show
that this prior is unique. Prior. Over
multinomial Bayesian networks with the
important property that if two networks
are equivalent then they have the same
Bayesian score. That is if we use the
different set of [inaudible] priors other
than one that fits this mould, we would
have a situation where we might have two.
Networks G and G prime that were
equivalent that have different Bayesian
scores and there's really no
justifications for that in terms of
incorporating that into the parameter
priors because these networks are
completely equivalent in their ability to
represent the probability distribution or
the same set of probability distribution
so why would we have one of them have
different Bayesian score than others or.
Rather if we do have some prior knowledge
that one of these graphs is, is more
suitable then the other, we should put
that into our structure prior, not into
our parameter prior. One interesting
property of the BDE score has to do with
its [inaudible] behavior. So, let's
consider what happens to the BDE score as,
or, in fact, a Bayesian score, in general,
and M goes to infinity. And it turns out
that as M goes to infinity, and network G
[inaudible] priors, satisfies the
following in terms of the marginal
likelihood. That the log of the marginal
likelihood is equal to the sum of these
three terms. The first of these. Is just
the log likelihood. Of the data. Given the
maximum likelihood of parameters. Theta
half G. So this is just the likelihood
score. Which we've already seen, has some
good properties, in terms of trying to fit
the data. But on the other hand, is also
liable to over fit. The second terms,
however, is log of M over two, where M is
the number of instances, times [inaudible]
G, which is the number of independent
parameters. Which as we've seen in the
context of a multinomial distribution, is
the number of entries in distribution m
minus one. And this term has a negative
sign, which means that, we are going, this
log, the, the, log, of the marginal
likelihood, is going to be decreased as we
increase the number of parameters. And so
there is a tension between those two
terms. The first of these, tries to have
more complicated networks, in order to
maximize the fit to data, as we've already
scene, and the second, tries to reduce the
complexity of the model by increasing, by
decreasing the number of parameters. The
third term, is this term O of one, which
indicates in a formal notation that this
third term is effectively constant
relative to M, which means it doesn't
grow. With M. With the number of
instances, which means that as the number
of instances grows, only these first two
terms are going to play a role in terms of
evaluating which structure is going to be
selected. Now these first two terms, as it
happens, have a name. And that, name is
something called the BIC score, which
really looks just at the likelihood
component and the penalty term. And as,
and in a different part of this course, we
talk about the BIC score and some of the
properties that it has, specifically, for
example, the fact that as M rose to
infinity, the score is consistent. Which
means that the graph or one of its I, is
the correct graph for one of its I
equivalent graphs is going to have the
highest score among all possible graphs
that we're considering. So, this is yet
another demonstration that the Bayesian
score is a way of avoiding over fitting
because at the large sample limit we will
learn a correct graph. Either the correct
graph for one of its equivalent
structures. To summarize, the Bayesian
score uses Bayesian principles,
specifically averaging out over parameters
that we have uncertainty over, to avoid
over fitting. The Bayesian score is most
often instantiated as a particular variant
called BDE, which requires that we assess
a prior network in order to compute, the
prior [inaudible] parameters. But that
also allows us to nat, a natural place to
incorporate prior knowledge, into the
learning algorithm. And the BDE prior has
the important property that I-equivalent
networks have the same score. The Bayesian
score is at the large sample limit.
Equivalent to a different score called
BIC, which we analyze separately in this
course, and as a consequence of this
equivalence one can show that it's
ascetically consistent in that it learns
the correct Network as M goes to infinity.
Now while this asymptotic behavior is an
important one, it's also important to
realize that we don't often have a, a
very, very large number of samples or at
least not an, a large number of
applications, and so it's important to
consider also the behavior for a more
reasonable number of samples and, and in
this case it's it can be shown that the
BIC score tends to under fit the Number of
tends to under fit the model structure in
the sense that it'll learn models that are
to sparse.