Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Expectation Propagation(EP) is now quite a standard technique to approximate marginal in graphical model. Moreover, EP can replace sum-product algorithm in factor graph. For this reason, I try to understand it by using very simple model but because of my limitation of knowledge, the result could not be reached. So would you please revise my progress to show me my errors?

My problem is simple. $x_1$ is the variable which is followed Gaussian distribution with the mean $\alpha$ and variance $\beta$. $x_2$ is the variable which satisfies $x_1 = x_2$. So the factor graph can be represented by

Gaussian ---$x_1$ ---- $f(x_1, x_2) $--- $x_2$

f is the factor function in factor graph and it is Dirac delta function.

$f(x_1, x_2) = \delta(x_1 - x_2)$

Based on the properties of factor graph, we have:

$p(x_1, x_2) = g(x_1) f(x_1, x_2)$

with $g(x_1)$ is the Gaussian distribution. When we take the integral over the variable $x_1$ of $p(x_1, x_2)$, we get that the marginal of $x_2$ is the Gaussian distribution with the same parameters with $x_1$.

However, I want to use EP technique to solve this problem. First of all, I will separate $f$ here like in Tom Minka's thesis

Gaussian ----- $x_1$ ------ $\tilde{f}_1(x_1)$ $\tilde{f}_2(x_2)$ ----- $x_2$

Now, I want to find the function $q(x)$ that is

$q(x_1, x_2) = g(x_1) \tilde{f}_1(x_1) \tilde{f}_2(x_2)$

$q$ is the approximate function of $p(x_1, x_2)$

I want to refine the function $\tilde{f}(x_1, x_2) = \tilde{f}_1(x_1)\tilde{f}_2(x_2)$, environment without $f$ is calculated

$q^{\f}(x_1, x_2) = g(x_1)$


$\hat{p}(x_1, x_2) = q^{\f}(x_1, x_2) f(x_1, x_2) = g(x_1) f(x_1, x_2)$

$\hat{p}(x_1) = g(x_1) \int_{x_2} f(x_1, x_2) dx_2$

$\hat{p}(x_2) = \int_{x_1} f(x_1, x_2) dx_1$

$q^{new} (x_1, x_2) = \hat{p}(x_1) \hat{p}(x_2)$


$\tilde{f}(x_1, x_2) = \frac{q^{new}(x_1, x_2)}{q^{\f}} = \int_{x_1} f(x_1, x_2) dx_1 \int_{x_2} f(x_1, x_2) dx_2$


$\tilde{f}_1(x_1) = \int_{x_2} f(x_1, x_2) dx_2$

$\tilde{f}_2(x_2) = \int_{x_1} f(x_1, x_2) dx_1$

Then I guess $\tilde{f}_1$ and $\tilde{f}_2$ are convergence, so

$q(x_1, x_2) = g(x_1) \int_{x_1} f(x_1, x_2) dx_1 \int_{x_2} f(x_1, x_2) dx_2$

Hence, I get stuck at this point. Would you please show me, what wrong did I do?

Thank you and looking forward to seeing your helps

share|improve this question
add comment

1 Answer 1

The way you are doing is not quite correct. Take a look at these tutorials - http://homepages.inf.ed.ac.uk/csutton/publications/ep-tutorial.pdf - http://web.engr.illinois.edu/~khashab2/learn/ep.pdf

Go over the algorithms which show the EP procedures. Also note the way they explain the projection of the distributions using KL projection.

share|improve this answer
Hi. I posted this question when I was so junior. Actually, IMO, the better tutorial is in Chapter 10 of PRML (Bishop 2006). After that, the slide from Cambridge may be the best illustration mlg.eng.cam.ac.uk/teaching/4f13/1213/lect0809.pdf. Anyway, thanks for your answer. –  tndoan Nov 7 '13 at 6:16
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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