3
$\begingroup$

In message-passing methods, factors and random variables exchange messages that typically encode marginals, but as much as I look at their formulas, I still don't understand what those messages actually look like.

For example, in belief propagation, when using the factor graph representation, we have the following scheme:

  • Messages from a variable node $v$ to a factor node $u$

    $\forall x_v\in Dom(v),\; \mu_{v \to u} (x_v) = \prod_{u^* \in N(v)\setminus\{u\} } \mu_{u^* \to v} (x_v).$

  • Messages from a factor node $u$ to a variable node $v$ are the product of the factor with messages from all other nodes, marginalised over all variables except the one associated with $v$:

    $\forall x_v\in Dom(v),\; \mu_{u \to v} (x_v) = \sum_{\mathbf{x}'_u:x'_v = x_v } f_u (\mathbf{x}'_u) \prod_{v^* \in N(u) \setminus \{v\}} \mu_{v^* \to u} (x'_{v^*}).$

I understand that these messages represent marginals and that the eventually we end up with the marginals in every node/factor, but my question is:

  • Are these messages vectors holding real numbers?
  • What is the dimensionality of those vectors?
  • What does this dimensionality represent?

To make things more concrete let's assume a distribution over real random variables (e.g. gaussian), although I am also interested in the discrete case (e.g. categorical random variables). Also, how are these messages initialized?

$\endgroup$
1
$\begingroup$

This is a problem I am currently working on so I'm glad to share my current understanding about it. The messages are essentially computed by composing probability density functions over the variables. Remember that in a factor graph each edge has always a factor on one end and a variable on the other, so the message associated with the edge is a distribution on the variable incident on that edge. The formulas that you wrote are the same formulas found in most textbooks and they will specialize differently depending on whether you have continuous or discrete distributions. In the case of the continuous Normal distribution, for example, one can work out the products and the sums (integrals) and find closed form expressions for the messages. Note that in this case what you are propagating are actually the parameters of the distributions ($\mu$,$\sigma^2$). If you can't find closed for expressions for the messages than you have to revert to discrete distributions. As you are suggesting, in this case you are passing vectors, that are essentially histograms. So the dimension of these vectors is associated with the number of quantization intervals of the histograms.

$\endgroup$
  • $\begingroup$ Thanks. I would imagine that the quantization could drastically affect the optimality and accuracy of inference, and I am surprised I haven't seen papers discussing this in detail. It would be great to learn more about how this problem is approached in practice. $\endgroup$ – Josh Dec 19 '13 at 21:38
  • $\begingroup$ Also, how are the messages initialized? Assuming a uniform distribution perhaps? Can the initialization affect the value reached upon convergence ? $\endgroup$ – Josh Dec 19 '13 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.