1
$\begingroup$

I've been trying to wrap my head around expectation propagation for a while now, but I'm struggling a bit with finding approximate factors in an efficient way and 'fully-factorized' approximations.

I'm currently trying to write my own implementation (to check if I've fully understood everything) which is based on this paper of Minka and Infer.NET (as a reference for how it could be implemented).


Finding approximate factors – computational complexity

My understanding is that factors in a factor graph represent the CPDs of my Bayesian network. For example – given random variables $x_1,x_2,x_3$ – I could define $x_3 = x_1 + x_2$. The corresponding factor $f(x_1,x_2,x_3)$ would then be defined as $p(x_3|x_1,x_2) = (pdf_{x_1} \cdot pdf_{x_2})(x_3)\rightarrow$ the convolution of $x_1$ and $x_2$.

Depending on the distributions involved marginalizing out other variables might become intractable in a bigger network as the integral gets too complicated. Because of that, you try to approximate the factors (and the joint distribution) by distributions of the same exponential family (f.e. Gaussians).

However, when refining the approximations and finding $\arg\min KL(f_a(\boldsymbol{x}) q^{\backslash a}(\boldsymbol{x}) || \hat{f}_a(\boldsymbol{x}) q^{\backslash a}(\boldsymbol{x})$ (equation 52 in the paper), I still have to take the integral over all random variables which still seems to be a computationally expensive task (especially because it has to be done several times).

Even when I'm just matching the expectations of the features of the exponential family chosen, this results in a quite computational heavy integral.

Am I misunderstanding something here or missing out some simplifications?


Fully-factorized approximation

In the paper, many algorithms 'use a fully-factorized approximation'. After my understanding this means that all factors are split up into separate factors such that each factor only depends on a single variable. So $f(x_1,x_2,x_3) \approx q(x_1)q(x_2)q(x_3)$.

Am I right when I assume that this is done 'automatically' by the algorithms? Do the messages from factors to variables represent the factors of a fully-factorized graph?


Thanks in advance for any replies.

If I'm talking nonsense feel free to tell me – this whole thing is messing with my head a bit at the moment and I keep confusing myself ;)

$\endgroup$

1 Answer 1

1
$\begingroup$

The KL minimization in EP can indeed be difficult in the general case. The key is to exploit the structure of the factor graph and use an approximating family (such as a fully-factorized one) that makes it easy. If you want some concrete examples of how to do the KL minimization then you should read a different paper such as A family of algorithms for approximate Bayesian inference.

The splitting up is done automatically. The messages from factors to variables represent the factors of a fully-factorized approximation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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