Probabilistic graphical models (PGMs) are a rich framework for encoding probability distributions over complex domains: joint (multivariate) distributions over large numbers of random variables that interact with each other. These representations sit at the intersection of statistics and computer science, relying on concepts from probability theory, graph algorithms, machine learning, and more. They are the basis for the state-of-the-art methods in a wide variety of applications, such as medical diagnosis, image understanding, speech recognition, natural language processing, and many, many more. They are also a foundational tool in formulating many machine learning problems. This course is the second in a sequence of three. Following the first course, which focused on representation, this course addresses the question of probabilistic inference: how a PGM can be used to answer questions. Even though a PGM generally describes a very high dimensional distribution, its structure is designed so as to allow questions to be answered efficiently. The course presents both exact and approximate algorithms for different types of inference tasks, and discusses where each could best be applied. The (highly recommended) honors track contains two hands-on programming assignments, in which key routines of the most commonly used exact and approximate algorithms are implemented and applied to a real-world problem.
Properties of Belief Propagation
Loading...
En provenance du cours de Stanford University
Probabilistic Graphical Models 2: Inference
268 notes
À partir de la leçon
Belief Propagation Algorithms
This module describes an alternative view of exact inference in graphical models: that of message passing between clusters each of which encodes a factor over a subset of variables. This framework provides a basis for a variety of exact and approximate inference algorithms. We focus here on the basic framework and on its instantiation in the exact case of clique tree propagation. An optional lesson describes the loopy belief propagation (LBP) algorithm and its properties.
Rencontrer les enseignants
Daphne KollerProfessor
School of Engineering
So now, we're going to look more closely into the belief propagation algorithm and
understands some of the important properties that it has.
So here's our example, cluster graph with the four clusters over the loop.
And now, let's remind ourselves that the cluster beliefs are defined to be the
product of the clust, of the factors assigned to the to the clusters of psi
one up to psi four times the product of the messages that were incoming into the
clusters. So for example, the beliefs over cluster
one is psi one of a b times the message coming in from cluster four, whose scope
is a, and the message coming in from cluster two, whose scope is b.
Now a cluster graph is said to be calibrated.
If the clusters agree with each other, so specifically if in terms of their beliefs
beta I, if we were to ask cluster one what it thinks about say variable B, and
we were to ask cluster two what it thinks about the variable B, they would agree
with each other. Formally, this says that if we
marginalize out the belief that say cluster I and, marginalize out the
beliefs in cluster J and we ask them what they agree about their joint subset.
S I J, they would agree with each other in terms of the marginal beliefs.
Now, an important property of cluster graph belief propagation is that
convergence of the belief propagation algorithm implies calibration.
So, to understand why that's the case, let's go through a simple derivation.
So the convergence of belief propagation occurs when the message at the next time
step equals the message at the previous time step.
So now, let's see what the implications of that are.
So if this is the, message it's the next time step.
It's computed. As the product of the.
psi Is, which are the factors assigned to the cluster I times all of the messages
other, except for.
cluster J. And those are all multiplied together,
and marginalized out over the subset. So now let's remind ourselves of what the
beliefs would be at this point in the process if we were to compute them.
And that's derived from this expression over here.
So this is the same psi I that we had over here.
And this is the product of all messages. So if this is, if, if here we have the
product of psi I, and all messages except one and here we have psi I and all
messages we can equally well, rewrite it, in this form over here where we multiply
in all the messages, and the divide out, the one that wasn't included, delta JI.
So now, because of convergence we have the this is equal to this is equal to
delta IJ because of this equality over here.
And so if we rewrite that, we can see that we have that delta IJ times delta JI
is equal to this summation over here. Because we can multiply delta JI on the
right-hand side by delta IJ on the left-hand side.
So we have shown that delta JI times Delta IJ is,
is effectively the marginal over the beliefs at that point in the process.
But we can equally well, using the identical argument, show that Delta JI
times Delta IJ is also the marginal over the beliefs for cluster J.
So if is the beliefs for cluster I, this is the beliefs for cluster j, and so and
that we've shown that in both cases. The marginals are equal to the same
expression, which is the product of the messages on both sides of the link.
And so, because both expressions are equal to the same thing, they must be
equal to each other. And this is exactly the calibration
property that we were trying to prove. So we've shown the convergence of the
belief propagation algorithm implies calibration.
This expression, which corresponds to the, subset beliefs.
because it's the marginal over the cluster beliefs, is called u I j, and
it's an expression that we'll use, a little bit later.
In particular, one of the important properties that we get by putting these
pieces together is another property called reparameterization.
Now, that's a bit of a mouthful. So, let's first do the derivation.
And then understand what the word means. so remember that, as we run belief
propagation. At the end of it, we have these, beliefs
over the clusters. Which are defined in this expression.
So specifically, for example, we have for cluster one we would have psi one times
delta four one times delta two one. And similarly for the other clusters.
We've also just now defined these clusters, these subset beliefs.
Which are, which we've just shown are a product of two messages on the two
different dir going in each direction. So, specifically here we would have for
example that mu of one two is equal to delta one two times delta two one.
Now if we look at this graph with all these all these little factors attached
to the clusters and the subsets. We see that there's a lot of repetition
here. So delta four one appears for example,
here, but it also appears there. And in fact, if we look at it, we see
that each of these expressions appears, each of these message expressions appears
exactly twice. So delta four one appears here and here.
And for example, delta one two appears here and and here.
And, so, if we write all of these together in in a different form.
We can see that we, can, if we multiply all of the beliefs, and divide by all of
the subsets. We would end up with multiplying in delta
four one for example on the on the belief side but then canceling it out when we
divide by mu 1,4. S, and, similarly, delta one two would be
multiplied in, on. In terms of theta two but then cancelling
out in the denominator in U one two. So if we, want to drade this in a little
bit of a broader, setting, so if we have a product of the beliefs over here,
multiplied, and then divide by a product of all of the sub sets, we can, see that
this, numerator is equal to the product over I, of, psi I, times the product of
all thee, incoming messages into cleek I. The denominator is simply equal, to, the
product of all, of, the messages on, each direction.
And we can see that here we're just counting the same message in two
different ways. and so each message appears once in the
numerator and once in the denominator, which means that they all cancel with
each other. And so what we end up with is the product
of all of the initial potentials of psi I.
And that product is simply the unnormalized measure.
and so. The implication of this is that this
expression over here. This ratio is simply a different set of
parameters that captures the original un-normalized measure that defined our
distribution. And so we haven't lost information.
No information loss as, as a result of the belief propagation algorithm.
The representation of the un-normalized measure is still there, just using a
different set of parameters. Specifically the cluster subsets, the
cluster beliefs and the subset beliefs. So to summarize, we see the add
convergence of belief propagation, the cluster graph beliefs all agree with each
other on the variables that are shared among them.
And, as a consequence of that, the cluster graphs beliefs are simply an
alternative parameterization of the original un normalized density, but one
that has this nice calibration property which allows us to ready off information
about a variable from any clique in which it appears.
And so, we have reparameterized the original distribution into a more
convenient and easily usable form.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
