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 that you have read and understand our privacy policy and code of conduct.

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