4

As far as I understand, the "junction tree algorithm" is a general inference framework which roughly consists of the four steps 1) triangulate, 2) construct junction tree, 3) propagate probabilities/pass messages and 4) perform intra-clique inference in order to calculate marginals.

During my study of the JT algorithm i encountered the terms "Hugin algorithm" and "Shafer-Shenoy algorithm", which to me seem to be two different ways to perform the third step in the JT algorithm as described above. However, I'm unclear as to what exactly the definitions of these two algorithms are. The definition of each does not seem to be consistent, and some sources appear to treat them as essentially the same algorithm (or at least seem to imply that the Shafer-Shenoy algorithm is used by the Hugin PGM software, whereas my understanding was that the Hugin algorithm was developed specifically for this software).

Adding to the confusion, the main tome on the topic (Koller and Friedman) does not use any of these terms, but instead uses terms like "sum-product algorithm", "sum-product-division algorithm" and "Lauritz-Spiegelhalter algorithm".

Can anybody clarify the correspondence between all these terms for me, and point me to a "canonical" definition of the Hugin and Shafer-Shenoy algorithms? Currently I'm thoroughly confused by the extreme diversity of terms for algorithms that seem to be very similar, for the most part.

haroba
  • 187
  • 8

1 Answers1

4

The Shafer-Shenoy and the Hugin algorithms are two variants of variable elimination which differ in their efficiency (Hugin takes less computations but Shafer-Shenoy allows to perform certain queries more efficiently).

Both algorithms start with a given junction tree which has been precalculated in a first stage. First a node is selected as a root, and then messages are propagated from the leaves to the root and viceversa. The difference between them is how this message passing is calculated and what information is kept in the nodes.

In Shafer Shenoy the message from, say, node i to node j has the form, $$ m_{i \rightarrow j} = \sum_{i} \phi_{i} \prod_{k \neq j} m_{ki} $$ where $\phi_{i}$ is the corresponding potential associated with the node. The same calculation is done in the opposite direction in a second round, and these results are kept (which is quadratic with the number of nodes).

The Hugin algorithm algorithm proceeds as follows: instead of calculating $$ \phi_{i} \prod_{k \neq j} m_{ki} $$ as the message from node k to i, compute the whole product, $$ p_{i} = \phi_{i} \prod_{k \neq i} m_{ki} $$ just once. Then, you can recover the previous message by dividing, $$ p_{i} / m_{kj} $$

If $m_{kj} = 0$, then set that message to zero (as it should otherwise be). The disadvantage of the Hugin algorithm is that, if a later point you wish to ask a different question to the model, and set some other evidence, you need to do more recalculations than in the first algorithm. So actually, which one you use depends on the application.

jpmuc
  • 12,986
  • 1
  • 34
  • 64
  • I think $\sum_i$ should be $\sum_{i\backslash j}$, where $i\backslash j$ is the set-theoretic difference. Also write _"...$ \phi_{i} \prod_{k \neq j} m_{ki} $ as the message from node k to i, compute the whole product"_, but I can't figure out how it is the message from $k$ to $i$. Could you clarify that? – paperskilltrees Aug 11 '21 at 18:54