I'm reading Michael I. Jordan's book on probabilistic graphical models, and I don't understand the elimination algorithm presented in chapter 3. To narrow the question down, consider page 6. In equation (3.10), we see that $$m_5(x_2,x_3) = \sum_{x_5}p(x_5|x_3)p(\bar{x}_6|x_2,x_5)$$

where the $x_i$ are random variables and $\bar{x}_i$ indicates a fixed/realized value of $x_i$.

Given that all $x_i$ are discrete random variables (as is the case in chapter 3), both $p(x_5|x_3)$ and $p(\bar{x}_6|x_2,x_5)$ are represented by two-dimensional matrices. And since $m_5$ is a function of as-yet unrealized variables $x_2$ and $x_3$, it is also a two-dimensional matrix.

How then do we perform the multiplication and the summation above?


1 Answer 1


I'm realizing now that it's just regular matrix multiplication.

For the case above, let $p(x_5|x_3)$ and $p(\bar{x_6}|x_2,x_5)$ be represented by $r\!\times\!s$ and $s\!\times\! t$ matrices, respectively, where $x_5$ can take on $s$ different values. Then, for each element $m_{ij}$ of $m_5$, we have that

$$m_{ij}=\sum_{k=1}^s p_{ik}(x_5|x_3)p_{kj}(\bar{x_6}|x_2,x_5)$$

where $1\leq i \leq r$ and $1 \leq j \leq t$.

This is matrix multiplication. Also, intuitively, the dimensions will always work out, since each factor in the product will always be a function of the variable we're summing over.

I think the notation is what was tripping me up. I usually don't see matrix multiplication written explicitly as a sum of products.


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.