Practical 5 - DE424

DE424 Practical 5 - Report

Name & Surname: Robert Jaret Thompson Student Number: 24704806 Date: 13 March 2025

Plagiarism Declaration

This submission is entirely my own work, excepting the inclusion of resources explicitly permitted for this assignment, and assistance as noted in the following two items.

• DE424 Practical 3 outline
• Emdw userguide
• Emdw devguide

I have not and will not facilitate plagiarism, such as by distributing any written work or source code created by fellow students. I understand that any code I submit may be inspected for plagiarism detection (either manually or by automated systems).

Signed:

---

Introduction

In this practical, the belief propagation and belief update algorithms are manually implemented for the Hamming (7,4) error-correction code using a junction tree. The junction tree structure is derived from the variable elimination (VE) order: $b_4,b_5,b_6,b_1,b_2,b_3,b_0$.

Figure 1: Markov Network (MN)

In an MN, the joint distribution is represented as a product of factors $\varphi$ over maximal cliques:

$p(b_0,...,b_6)\propto {\varphi }_1(b_0,b_1,b_2){\varphi }_2(b_0,b_2,b_3){\varphi }_3(b_0,b_1,b_3)$ where ${\varphi }_1:(b_0,b_1,b_2,b_4),{\varphi }_2:(b_0,b_2,b_3,b_5)$ and ${\varphi }_3:(b_0,b_1,b_3,b_6)$

The goals:

• Question 4.2: a) Manually implement the belief-update/absorption/Lauritzen-Spiegelhalter algorithm on the Junction Tree and b) a valid message-passing schedule to extract the marginal beliefs.
• Question 4.3: a) Manually implement the belief-update/absorption/Lauritzen-Spiegelhalter algorithm on the Loopy Cluster Graph and b) after message-passing, extract the marginal beliefs and compare.
• Question 4.4: Use emdw’s built-in loopy belief update function loopyBU CG

The Lauritzen-Spiegelhalter algorithm is a fundamental approach for performing exact inference in probabilistic graphical models, particularly in a junction tree. Unlike belief propagation, which relies on message passing, this approach leverages the concept of belief update and absorption through sepsets and cluster potentials.

4.2 Belief-update/absorption/Lauritzen-Spiegelhalter Algorithm in a Junction Tree

Using the given VE order, the junction tree is constructed as shown in Figure 2.

Figure 2: Junction Tree

Cliques: $C_1=\{b_0,b_1,b_2,b_3\}$, $C_2=\{b_0,b_1,b_2,b_4\}$, $C_3=\{b_0,b_2,b_3,b_5\}$, $C_4=\{b_0,b_1,b_3,b_6\}$

Sepsets: $S_{12}=\{b_0,b_1,b_2\}$, $S_{13}=\{b_0,b_2,b_3\}$, $S_{14}=\{b_0,b_1,b_3\}$

The belief update process involves two main passes: the inward pass and the outward pass, where factors are marginalized over the sepsets and absorbed back into the cliques. The goal is to ensure consistency between the cluster beliefs and the sepset beliefs.

Inward Pass

In the inward pass, the algorithm marginalizes each factor over the sepsets and updates the clique potential by absorbing the information from neighboring cliques.

Initialize: ${\beta }_2(C_2)\leftarrow {\psi }_2(b_0,b_1,b_2,b_4)$, ${\beta }_3(C_3)\leftarrow {\psi }_3(b_0,b_2,b_3,b_5)$, ${\beta }_4(C_4)\leftarrow {\psi }_4(b_0,b_1,b_3,b_6)$ ${\mu }_{1,2}(S_{12})\leftarrow 1$, ${\mu }_{1,3}(S_{13})\leftarrow 1$, ${\mu }_{1,4}(S_{14})\leftarrow 1$

“Message” from 1 $\to$ 2: ${\mu }_{1,2}^{{}^{\prime }}(S_{12})\leftarrow {\sum }_{b_4}(b_0,b_1,b_2,b_4)$ & ${\beta }_2(C_2)\leftarrow normalize[\frac{{\mu }_{1,2}^{{}^{\prime }}(S_{12})}{{\mu }_{1,2}(S_{12})}{\beta }_2(C_2)]$ & ${\mu }_{1,2}(S_{12})\leftarrow {\mu }_{1,2}^{{}^{\prime }}(S_{12})$

“Message” from 1 $\to$ 3: ${\mu }_{1,3}^{{}^{\prime }}(S_{13})={\sum }_{b_5}(b_0,b_2,b_3,b_5)$ & ${\beta }_3(C_3)\leftarrow normalize[\frac{{\mu }_{1,3}^{{}^{\prime }}(S_{13})}{{\mu }_{1,3}(S_{13})}{\beta }_3(C_3)]$ & ${\mu }_{1,3}(S_{13})\leftarrow {\mu }_{1,3}^{{}^{\prime }}(S_{13})$

“Message” from 1 $\to$ 4: ${\mu }_{1,4}^{{}^{\prime }}(S_{14})={\sum }_{b_6}(b_0,b_1,b_3,b_6)$ & ${\beta }_3(C_3)\leftarrow normalize[\frac{{\mu }_{1,4}^{{}^{\prime }}(S_{14})}{{\mu }_{1,4}(S_{14})}{\beta }_4(C_4)]$ & ${\mu }_{1,4}(S_{14})\leftarrow {\mu }_{1,4}^{{}^{\prime }}(S_{14})$

Outwards Pass

Initialize: ${\beta }_1(C_1)\leftarrow {\psi }_1(b_0,b_1,b_2,b_3)$ ${\mu }_{1,2}(S_{12})\leftarrow {\mu }_{1,2}^{{}^{\prime }}(S_{12})$ & ${\mu }_{1,3}(S_{13})\leftarrow {\mu }_{1,3}^{{}^{\prime }}(S_{13})$ & ${\mu }_{1,4}(S_{14})\leftarrow {\mu }_{1,4}^{{}^{\prime }}(S_{14})$

“Message” from 2 $\to$ 1: ${\mu }_{1,2}^{{}^{\prime }}(S_{12})\leftarrow {\sum }_{b_3}(b_0,b_1,b_2,b_3)$ & ${\beta }_1(C_1)\leftarrow normalize[\frac{{\mu }_{1,2}^{{}^{\prime }}(S_{12})}{{\mu }_{1,2}(S_{12})}{\beta }_1(C_1)]$ & ${\mu }_{1,2}(S_{12})\leftarrow {\mu }_{1,2}^{{}^{\prime }}(S_{12})$

“Message” from 3 $\to$ 1: ${\mu }_{1,3}^{{}^{\prime }}(S_{13})\leftarrow {\sum }_{b_1}(b_0,b_1,b_2,b_3)$ & ${\beta }_1(C_1)\leftarrow normalize[\frac{{\mu }_{1,3}^{{}^{\prime }}(S_{13})}{{\mu }_{1,3}(S_{13})}{\beta }_1(C_1)]$ & ${\mu }_{1,3}(S_{13})\leftarrow {\mu }_{1,3}^{{}^{\prime }}(S_{13})$

“Message” from 4 $\to$ 1: ${\mu }_{1,4}^{{}^{\prime }}(S_{14})\leftarrow {\sum }_{b_2}(b_0,b_1,b_2,b_3)$ & ${\beta }_1(C_1)\leftarrow normalize[\frac{{\mu }_{1,4}^{{}^{\prime }}(S_{14})}{{\mu }_{1,4}(S_{14})}{\beta }_1(C_1)]$ & ${\mu }_{1,4}(S_{14})\leftarrow {\mu }_{1,4}^{{}^{\prime }}(S_{14})$

Figure 3: Belief-update algorithm for Junction Tree with emdw

Figure 4: Extracting marginal beliefs

Figure 5: Marginal belief of $b_0$ and $b_1$

	$0$	$1$	$belief$
$b_0$	1	3.47419e-10	0
$b_1$	0.999983	1.69858e-05	0
$b_2$	0.99863	0.00136968	1
$b_3$	0.00136968	0.99863	1
The Belief-update/absorption/Lauritzen-Spiegelhalter algorithm successfully propagates the beliefs in a junction tree. This method leverages the tree structure to efficiently compute the marginal probabilities, however it did not seem to return the desired results when compared to Question 4.1. which returned results that was more expected.

Figure 6: Results from Question 4.1

4.3 Belief-update/absorption/Lauritzen-Spiegelhalter Algorithm in a Loopy Cluster Graph

Figure 6: Loopy Cluster Graph

Cliques: $C_2=\{b_0,b_1,b_2,b_4\}$, $C_3=\{b_0,b_2,b_3,b_5\}$, $C_4=\{b_0,b_1,b_3,b_6\}$

Sepsets: $S_{23}=\{b_0,b_2\}$, $S_{34}=\{b_0,b_3\}$, $S_{24}=\{b_0,b_1\}$

Forwards

Initialize: ${\beta }_2(C_2)\leftarrow {\psi }_2(b_0,b_1,b_2,b_4)$ & ${\beta }_3(C_3)\leftarrow {\psi }_3(b_0,b_2,b_3,b_5)$ & ${\beta }_4(C_4)\leftarrow {\psi }_2(b_0,b_1,b_3,b_6)$ ${\mu }_{2,3}(S_{23})\leftarrow 1$, ${\mu }_{3,4}(S_{34})\leftarrow 1$, ${\mu }_{2,4}(S_{24})\leftarrow 1$

“Message” from 2 $\to$ 3: ${\mu }_{2,3}^{{}^{\prime }}(S_{23})\leftarrow {\sum }_{b_1,b_4}(b_0,b_1,b_2,b_4)$ & ${\beta }_2(C_2)\leftarrow normalize[\frac{{\mu }_{2,3}^{{}^{\prime }}(S_{23})}{{\mu }_{2,3}(S_{23})}{\beta }_2(C_2)]$ & ${\mu }_{2,3}(S_{23})\leftarrow {\mu }_{2,3}^{{}^{\prime }}(S_{23})$

“Message” from 3 $\to$ 4: ${\mu }_{3,4}^{{}^{\prime }}(S_{34})\leftarrow {\sum }_{b_2,b_5}(b_0,b_2,b_3,b_5)$ & ${\beta }_3(C_3)\leftarrow normalize[\frac{{\mu }_{3,4}^{{}^{\prime }}(S_{34})}{{\mu }_{3,4}(S_{34})}{\beta }_3(C_3)]$ & ${\mu }_{3,4}(S_{34})\leftarrow {\mu }_{3,4}^{{}^{\prime }}(S_{34})$

“Message” from 4 $\to$ 2: ${\mu }_{2,4}^{{}^{\prime }}(S_{24})\leftarrow {\sum }_{b_3,b_6}(b_0,b_1,b_3,b_6)$ & ${\beta }_4(C_4)\leftarrow normalize[\frac{{\mu }_{2,4}^{{}^{\prime }}(S_{24})}{{\mu }_{2,4}(S_{24})}{\beta }_4(C_4)]$ & ${\mu }_{2,4}(S_{24})\leftarrow {\mu }_{2,4}^{{}^{\prime }}(S_{24})$

Backwards

”Message” from 2 $\to$ 4: ${\mu }_{2,4}^{{}^{\prime }}(S_{24})\leftarrow {\sum }_{b_2,b_4}(b_0,b_1,b_2,b_4)$ & ${\beta }_2(C_2)\leftarrow normalize[\frac{{\mu }_{2,4}^{{}^{\prime }}(S_{24})}{{\mu }_{2,4}(S_{24})}{\beta }_2(C_2)]$ & ${\mu }_{2,4}(S_{24})\leftarrow {\mu }_{2,4}^{{}^{\prime }}(S_{24})$

“Message” from 4 $\to$ 3: ${\mu }_{3,4}^{{}^{\prime }}(S_{34})\leftarrow {\sum }_{b_1,b_6}(b_0,b_1,b_3,b_6)$ & ${\beta }_4(C_4)\leftarrow normalize[\frac{{\mu }_{3,4}^{{}^{\prime }}(S_{34})}{{\mu }_{3,4}(S_{34})}{\beta }_4(C_4)]$ & ${\mu }_{3,4}(S_{34})\leftarrow {\mu }_{3,4}^{{}^{\prime }}(S_{34})$

“Message” from 3 $\to$ 2: ${\mu }_{2,3}^{{}^{\prime }}(S_{23})\leftarrow {\sum }_{b_3,b_5}(b_0,b_2,b_3,b_5)$ & ${\beta }_3(C_3)\leftarrow normalize[\frac{{\mu }_{2,3}^{{}^{\prime }}(S_{23})}{{\mu }_{2,3}(S_{23})}{\beta }_3(C_3)]$ & ${\mu }_{2,3}(S_{23})\leftarrow {\mu }_{2,3}^{{}^{\prime }}(S_{23})$

For a Loopy Cluster Graph, this algorithm needs to be repeated until sufficiently small distance is obtained between current and new sepset beliefs.

Figure 7: Belief-update algorithm for Loopy Cluster Graph

**Figure 8: Marginal belief of $b_0,b_1,b_2$ and $b_3$

	$0$	$1$	$belief$
$b_0$	1.25148e-16	1	1
$b_1$	0.490934	0.509066	1
$b_2$	0.00937524	0.990625	1
$b_3$	0.990625	0.00937524	0
The updated beliefs closely matched those obtained from the junction tree belief propagation in Question 4.1 but not to the belief update in Question 4.2. The convergence was slower due to the loopy structure but provided consistent results.

In Loopy Belief Propagation (LBP), messages are passed iteratively between clusters until convergence. However, this approach can be inefficient in graphs with many loops due to redundant message passing and lack of guaranteed convergence.

In Belief Update (Lauritzen-Spiegelhalter absorption algorithm), we leverage the junction tree, which is a tree-structured representation of the original graph. This allows us to pass messages exactly once along a valid schedule (inward and outward passes). Since the junction tree structure eliminates loops, message passing becomes exact and efficient.

4.4 Loopy Belief-update using emdw built-in functionality

Results from built-in emdw Belief-update loopyBU CG function:

for the bits: $r_0=1$, $r_1=1$, $r_2=1$, $r_3=0$, $r_4=0$, $r_5=0$, $r_6=1$,

This result closely matches the results achieved in Question 4.1 and Question 4.3.