Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

The way you are doing is not quite correct. Take a look at these tutorials - -

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

share|cite|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 Anyway, thanks for your answer. – tndoan Nov 7 '13 at 6:16

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.