Worked out example of sum-product to calculate marginal at one node. Noted that . Looked at extension of sum-product to simultaneously compute marginals at all nodes using messages. Noted that max can also be used in place of sum, and in fact, updates can be done on any commutative semirings, of which sum-product and max-product are specific examples.

Looked at junction tree algorithm. Noted that, using the terminology in the paper, a junction tree is a clique tree that satisfies the running intersection property. A clique tree can be constructed for any graph, but a junction tree can only be built on a triangulated graph. The nodes in a junction tree correspond to the maximal cliques of the triangulated graph, and the edges are set using maximum spanning tree, where the weight on an edge is the size of the separator set for the two nodes connected by the edge. Potentials are kept not only over the nodes in the junction tree but also the separator sets, and messages are sent by dividing by the stored potential in the separator set in order to avoid double-counting information. Worked through Example 2.2.