July 4, 2013 at 21:20Probabilistic Models: The Art of Parenthesis
- Tutorial
After a long break, we continue the cycle on graphical probabilistic models ( part 1 , part 2 ). Today, we will finally move on from task definitions to algorithms; we’ll talk about the simplest but often useful factor-graph output algorithm — the message passing algorithm. Or, as it can be called, an algorithm for the correct placement of brackets.
by sergey-lesiuk
And let's start right away with a specific example - suppose you need to calculate the expression.
Here, formally speaking, there are four terms, each of three factors, only three additions and eight multiplications.
Let's show the wonders of quick wits and notice that the double sum is decomposed into the product of two single sums:
Suddenly, there are only two additions and two multiplications here - the benefit is obvious. As you probably understand, if I had not been too lazy to write a larger amount, the benefit would have increased exponentially - we are folding the sum of the exponential number of terms into a product of a linear number of small brackets.
“Think of Newton’s binom!” Readers will tell me; and they’ll be right, it really is very similar to Newton’s bin. And attentive readers will also be surprised why a game was needed here at all - indeed, in this example it looks clearly superfluous.
Let's try to generalize the same example - now let some unknown function happen with our variables instead of multiplication:
Does the same trick that goes above go through? No, it doesn’t work - we don’t know any connection between the different values of the function, it is a black box for us, and there’s nothing to put out of the bracket, you have to honestly apply the function four times and add the results.
The trick will take place in the intermediate case - we will still leave a rather general function in consideration, but now we will assume that it decomposes into the product of a function of x and y and a function of y and z (finally, y will ):
With this formulation of the question, we can decompose a large sum in the same way into the product of two small ones:
and save a lot on calculations. Note that although we assumed some additional structure of the function of three variables, it is not true that the variables x and z met in it completely independently - they were connected via yaccording to which, by a happy coincidence, we did not need to summarize. By the way, notice that the result of this summation is a function of y .
What is the moral of this example? That if we need to summarize a large function, and it decomposes into a product of smaller functions, it is possible that we can find a successful expansion into a product of brackets ...
... but this is the situation of inference on a graphical probabilistic model! Recall the consistent relationship between the variables that we discussed in the first series :
From a probabilistic point of view, it means that the joint distribution decomposes as
And this means that the function of the three variables x , y and z is decomposed into the product of the function of x and y and the function from y and z , exactly like in our naive example. And the summation corresponds to the marginalization problem : according to this model and, possibly, the values of some variables, find the marginal probability distribution
and we now understand that this expression can be greatly simplified as the
Marginalization task is the main one for graphic models, through it everything that we talked about last time is formalized : how to train regression weights, how to recognize speech using a ready-made model and how to train a recognition model from test cases, how to find the ratings of players after the next tournament, how to find the degree to which topics appear in documents from the corps, and so on.
The beauty of all this is that such arguments do not need to be invented every time anew, but can be generalized. The most direct generalization is to a chain of several events connected by serial communication:
At this point it will be convenient to slightly change the picture. So far, we have drawn only variables, and functions (probability distributions) are implied. In particular, it was intended to factor the large function; for example, the picture above leads to decomposition.
Now let's draw it explicitly:
We have a bipartite graph in which two varieties of vertices correspond to variables and functions. Each function is associated with those variables on which it depends, and the graph itself determines the decomposition of a large function into a product of small ones. This construction is called the factor graph.- note that this is a more general construction than the Bayesian trust network, now the probabilistic content has disappeared, and in principle we can talk about decompositions of abstract functions (not necessarily distributions) into a product of smaller abstract functions (not necessarily conditional distributions).
Now let's apply our trick to the marginalization problem with respect to x k . First, we bring in the first amount, then the second, then the third, and so on up to the kth ; the result is a more compact representation of the left side of the summation, which also does not intersect with the right side (sorry for the long formula, but it is much more visual than words): The
same can be done with the right side, and the result is
Pay attention to which calculation algorithm matches our trick: we start from the edges of the graph (from the innermost brackets) and gradually go to the middle (more precisely, to the kth variable), folding the sums along the way. This can be thought of as sending messages from the sides of the chain to the middle. At each step, we essentially do the same thing - we get the result of previous summations as a function of one variable h i ( x i ), and then we collapse it with the following:
The general case of the messaging algorithm is the case when the factor graph is a tree (i.e., it has no cycles). In this case, we can prove that for marginalization with respect to some vertex it is enough:
And in order to determine when it is already possible to send messages above, a very simple and comprehensive rule for sending messages is useful : the top of the factor graph can transmit a message to its neighbor if it has already received messages from all other neighbors . In particular, the leaves have only one neighbor, so they begin to send messages there immediately. This is how messages will go in a typical tree (numbers indicate on which “measure” this message will be generated; we now consider only messages going from the bottom up).
The message that the variable node transmits is simply the product of all the messages it receives (in the case of a sheet, the identity unit):
To recalculate the message of the node-function, it is necessary to carry out partial marginalization; if function
Already received messages 
from all variables 
, it can pass the
function-list message to the variable x
, respectively, passes itself to its only neighbor (the product is empty). We assume here that each function involved in the decomposition depends on a sufficiently small number of variables so that these summations can be carried out by “brute force” (well, or at least somehow, if you suddenly get a particularly tricky case).
The messaging algorithm only works when the factor graph is a tree. If there are cycles in the factor graph, the algorithm does not work (imagine that there is nothing besides the cycle - where to start?). However, situations come to life all the time when cycles are still present in the factor graph; for example, the LDA model for thematic modeling from the last series generally consists of several almost complete bipartite graphs, each document is associated with each topic, there are continuous cycles in the factor graph.
Next time we’ll talk about what you can do in a situation where loops are present in the graph. We are already approaching the border of what, while remaining in our minds, can be explained in detail in a popular article intended for a wide audience, but I will try to give some intuition the next time. And then, let's move on to specific examples.
by sergey-lesiuk
Example
And let's start right away with a specific example - suppose you need to calculate the expression.
Here, formally speaking, there are four terms, each of three factors, only three additions and eight multiplications.
Let's show the wonders of quick wits and notice that the double sum is decomposed into the product of two single sums:
Suddenly, there are only two additions and two multiplications here - the benefit is obvious. As you probably understand, if I had not been too lazy to write a larger amount, the benefit would have increased exponentially - we are folding the sum of the exponential number of terms into a product of a linear number of small brackets.
“Think of Newton’s binom!” Readers will tell me; and they’ll be right, it really is very similar to Newton’s bin. And attentive readers will also be surprised why a game was needed here at all - indeed, in this example it looks clearly superfluous.
Let's try to generalize the same example - now let some unknown function happen with our variables instead of multiplication:
Does the same trick that goes above go through? No, it doesn’t work - we don’t know any connection between the different values of the function, it is a black box for us, and there’s nothing to put out of the bracket, you have to honestly apply the function four times and add the results.
The trick will take place in the intermediate case - we will still leave a rather general function in consideration, but now we will assume that it decomposes into the product of a function of x and y and a function of y and z (finally, y will ):
With this formulation of the question, we can decompose a large sum in the same way into the product of two small ones:
and save a lot on calculations. Note that although we assumed some additional structure of the function of three variables, it is not true that the variables x and z met in it completely independently - they were connected via yaccording to which, by a happy coincidence, we did not need to summarize. By the way, notice that the result of this summation is a function of y .
What is the moral of this example? That if we need to summarize a large function, and it decomposes into a product of smaller functions, it is possible that we can find a successful expansion into a product of brackets ...
To probabilistic models
... but this is the situation of inference on a graphical probabilistic model! Recall the consistent relationship between the variables that we discussed in the first series :
From a probabilistic point of view, it means that the joint distribution decomposes as
And this means that the function of the three variables x , y and z is decomposed into the product of the function of x and y and the function from y and z , exactly like in our naive example. And the summation corresponds to the marginalization problem : according to this model and, possibly, the values of some variables, find the marginal probability distribution
and we now understand that this expression can be greatly simplified as the
Marginalization task is the main one for graphic models, through it everything that we talked about last time is formalized : how to train regression weights, how to recognize speech using a ready-made model and how to train a recognition model from test cases, how to find the ratings of players after the next tournament, how to find the degree to which topics appear in documents from the corps, and so on.
Factor graphs and graph in the form of a chain
The beauty of all this is that such arguments do not need to be invented every time anew, but can be generalized. The most direct generalization is to a chain of several events connected by serial communication:
At this point it will be convenient to slightly change the picture. So far, we have drawn only variables, and functions (probability distributions) are implied. In particular, it was intended to factor the large function; for example, the picture above leads to decomposition.
Now let's draw it explicitly:
We have a bipartite graph in which two varieties of vertices correspond to variables and functions. Each function is associated with those variables on which it depends, and the graph itself determines the decomposition of a large function into a product of small ones. This construction is called the factor graph.- note that this is a more general construction than the Bayesian trust network, now the probabilistic content has disappeared, and in principle we can talk about decompositions of abstract functions (not necessarily distributions) into a product of smaller abstract functions (not necessarily conditional distributions).
Now let's apply our trick to the marginalization problem with respect to x k . First, we bring in the first amount, then the second, then the third, and so on up to the kth ; the result is a more compact representation of the left side of the summation, which also does not intersect with the right side (sorry for the long formula, but it is much more visual than words): The
same can be done with the right side, and the result is
Pay attention to which calculation algorithm matches our trick: we start from the edges of the graph (from the innermost brackets) and gradually go to the middle (more precisely, to the kth variable), folding the sums along the way. This can be thought of as sending messages from the sides of the chain to the middle. At each step, we essentially do the same thing - we get the result of previous summations as a function of one variable h i ( x i ), and then we collapse it with the following:
General case
The general case of the messaging algorithm is the case when the factor graph is a tree (i.e., it has no cycles). In this case, we can prove that for marginalization with respect to some vertex it is enough:
- consider this peak as a temporary root of a tree;
- send messages from the leaves towards the root; each message is a function of exactly one variable - one that is adjacent to the edge along which this message goes;
- multiply all messages that have come to the root.
And in order to determine when it is already possible to send messages above, a very simple and comprehensive rule for sending messages is useful : the top of the factor graph can transmit a message to its neighbor if it has already received messages from all other neighbors . In particular, the leaves have only one neighbor, so they begin to send messages there immediately. This is how messages will go in a typical tree (numbers indicate on which “measure” this message will be generated; we now consider only messages going from the bottom up).
The message that the variable node transmits is simply the product of all the messages it receives (in the case of a sheet, the identity unit):
To recalculate the message of the node-function, it is necessary to carry out partial marginalization; if function
Already received messages from all variables , it can pass the
function-list message to the variable x, respectively, passes itself to its only neighbor (the product is empty). We assume here that each function involved in the decomposition depends on a sufficiently small number of variables so that these summations can be carried out by “brute force” (well, or at least somehow, if you suddenly get a particularly tricky case).
Conclusion and announcement of the next series
The messaging algorithm only works when the factor graph is a tree. If there are cycles in the factor graph, the algorithm does not work (imagine that there is nothing besides the cycle - where to start?). However, situations come to life all the time when cycles are still present in the factor graph; for example, the LDA model for thematic modeling from the last series generally consists of several almost complete bipartite graphs, each document is associated with each topic, there are continuous cycles in the factor graph.
Next time we’ll talk about what you can do in a situation where loops are present in the graph. We are already approaching the border of what, while remaining in our minds, can be explained in detail in a popular article intended for a wide audience, but I will try to give some intuition the next time. And then, let's move on to specific examples.
