ASSIGNMENT 2 PART 1: JUNCTION TREE ALGORITHM

CS5340 ASSIGNMENT 2 PART 1:
JUNCTION TREE ALGORITHM
1. PART 1 OVERVIEW
In the first assignment, you wrote code to perform inference on simple tree-like graphs using
belief propagation. However, the sum-product algorithm does not work on loopy networks. For
loopy networks to be amenable to the sum-product algorithm, we must first convert these
networks into a tree-like structure.
Hence, in part 1 of the second assignment, you will write code to construct a junction tree from a
Markov Random Field and perform inference on the junction tree using the sum-product
algorithm.
References: Lecture 4 and 5.
2. SUBMISSION INSTRUCTIONS
Items to be submitted (zip file contain folders part1 and part2):
• Source code
o jt_construction.py – code for constructing the junction tree.
o main.py – code for junction tree sum-product.
o factor_utils.py – code for factor helper functions.
• Report (report1.pdf). This should describe your implementation and be no more than
one page.
Please indicate clearly your name and student number (the one that looks like A1234567X) in the
report as well as the top of your source code. Zip the two files together and name it in the
following format: A1234567X_lab2.zip (replace with your student number). The zip file
structure should contain:
• part1 – folder containing code for assignment 2 part 1
• part2 – folder containing code for assignment 2 part 2
• report1.pdf – pdf document for assignment 2 part 1
• report2.pdf – pdf document for assignment 2 part 2.
Submit your assignment by 30 September 2020, 2359HRS to LumiNUS. 25% of the total score
will be deducted for each day of late submission.
3. GETTING STARTED
 CS5340 Assignment 2 (Semester 2, AY2023/2024)
01 October 2023, 2359HRS to Canvas.
CS5340 Assignment 2 (Semester 1, AY2023/2024)
CS5340 Assignment 2 (Semester 1, AY2020/2021) 2
This assignment as well as the subsequent ones require Python 3.5, or later. You need certain
python packages, which can be installed using the following command:
 pip install -r requirements.txt
If you have any issues with the installation, please post them in the forum, so that other students
or the instructors can help accordingly.
4. TEST CASES
To help with your implementation, we have provided a few sample datasets and their expected
outputs to help you debug your code. They can be found in the data/inputs folder. The groundtruth files can be found in data/ground-truth and our answers (for cross-comparison) can be
found in the data/answers folder.
Note that the ground-truth might be slightly different from the answers we have provided due to
numerical imprecision. During grading, your code will be evaluated on hidden test cases on top
of the validation test cases we have provided.
5. BASIC FACTOR OPERATIONS
Similar to lab 1, you will have to implement the following basic factor operations in factor_utils.py:
• factor_product(): This function should compute the product of two factors.
• factor_marginalize(): This function should sum over the indicated variable(s) and
return the resulting factor.
• factor_evidence(): This function takes in a Factor and some observed values. The
factor should be reduced (take slices) to contain only unobserved variables. Note that this
is slightly different from lab1.
All the factor operations make use of a custom Factor class from lab 1. Note that
factor_evidence() is slightly different from observe_evidence() in lab1.
6. JUNCTION TREE ALGORITHM
In lab 1, you noticed that even small graphs can have large joint distribution tables and running
variable elimination for each variable inefficient compared to running the sum-product algorithm.
Hence, we want to extend the sum-product algorithm for loopy markov random fields where we
must first construct a junction tree in jt_construction.py in the following steps:
a. Build the junction tree graph structure by forming cliques and creating edges between
cliques: _get_jt_clique_and_edges()[3 points]
b. Assign factors in the original graph to the cliques: _get_clique_factors()[1 point]
Note that we will also provide evidence variables, and the graph structure must be updated with
the evidence variables.
Once the junction tree has been constructed, in main.py, we will perform:
CS5340 Assignment 2 (Semester 2, AY2023/2024) CS5340 Assignment 2 (Semester 1, AY2023/2024)
CS5340 Assignment 2 (Semester 1, AY2020/2021) 3
a. Inference of clique potentials using the sum product algorithm on the constructed
junction tree: _get_clique_potentials() [2 points]
b. Compute the node marginal probabilities e.g. 𝑝(𝑋2
|𝑋𝐸
); 𝑝(𝑋3
|𝑋𝐸
) from the clique
potentials using brute-force marginalization: _get_node_marginal_probabilities()
[2 points]
To retrieve marginal probabilities for all query nodes in the graph. Note that step (b) has 1 point
for more efficient solutions. Hint: cliques have varying sizes.
Hint: It might be useful to create additional functions for this part. Place these functions between
the designated comment blocks for each file.
CS5340 Assignment 2 (Semester 2, AY2023/2024) CS5340 Assignment 2 (Semester 1, AY2023/2024)
CS5340 Assignment 2 (Semester 1, AY2020/2021) 4
CS5340 ASSIGNMENT 2 PART 2:
PARAMETER LEARNING
7. PART 2 OVERVIEW
In part 2 of the second assignment, you will write code on parameter learning under complete
observations. In this task, our local conditional probabilities are parameterised by 𝜽 where the
where we have 𝑝(𝑥𝑢
|𝑥𝜋𝑢
, 𝜃𝑢) . Under complete observations, a set of 𝑁 observations of our
random variables 𝑿 = {𝑥1
1
, … , 𝑥𝑉
1
, 𝑥1
2
, … , 𝑥1
𝑁, … , 𝑥𝑉
𝑁} are given, and from these observations, we
derive maximum likelihood estimates (MLE) for 𝜽 = {𝜃1, … , 𝜃𝑉}.
References: Lecture 6
Honour Code. This coding assignment (part 1 and 2) constitutes 15% of your final grade in
CS5340. Note that plagiarism will not be condoned! You may discuss with your classmates and
check the internet for references, but you MUST NOT submit code/report that is copied directly
from other sources!
8. SUBMISSION INSTRUCTIONS
Items to be submitted:
• Source code
o main.py – code should only be written here.
• Report (report2.pdf). This should describe your implementation (derivations) and be
no more than one page.
Please indicate clearly your name and student number (the one that looks like A1234567X) in the
report as well as the top of your source code. Zip the two files together and name it in the
following format: A1234567X_lab1.zip (replace with your student number).
Submit your assignment by 30 September 2020, 2359HRS to LumiNUS. 25% of the total score
will be deducted for each day of late submission.
9. GETTING STARTED
This assignment as well as the subsequent ones require Python 3.5, or later. You need certain
python packages, which can be installed using the following command:
 pip install -r requirements.txt
If you have any issues with the installation, please post them in the forum, so that other students
or the instructors can help accordingly.
10. TEST CASES
To help with your implementation, we have provided a few sample datasets and their expected
outputs to help you debug your code. They can be found in the data/inputs folder. The groundCS5340 Assignment 2 (Semester 2, AY2023/2024)
01 October 2023, 2359HRS to Canvas.
CS5340 Assignment 2 (Semester 1, AY2023/2024)
CS5340 Assignment 2 (Semester 1, AY2020/2021) 5
truth parameters can be found in data/gt-parameters and our answers (for cross-comparison)
can be found in the data/answers folder.
Note that the ground-truth might be slightly different from the answers we have provided since
we have a finite number of observations. During grading, your code will be evaluated on hidden
test cases on top of the validation test cases we have provided.
Test cases 1 and 2 uses the simple single node graph example in Lecture 6, and test cases 3 and 4
use the slightly more complex three node graph example in Lecture 6, with different number of
observations.
Note that our hidden test cases will consist of slightly more complex graphs. Your code should scale.
We will not introduce evidence (for the parameters 𝜽) in any test case.
11. PARAMETER LEARNING UNDER COMPLETE OBSERVATIONS
In part 2, we assume that observations are generated using a linear-Gaussian model i.e.
𝑝(𝑥𝑢|𝑥𝜋𝑢
, 𝜃𝑢) = 𝒩𝑢
[𝑤𝑢0, . . , 𝑤𝑢𝐶, 𝜎𝑢
2
] =
1
√2𝜋𝜎2
exp
{


−0.5
(𝑥𝑢 − (∑𝑐∈𝑥𝜋 𝑤𝑢𝑐𝑥𝑢𝑐 + 𝑤𝑢0 𝑢
))
2
𝜎𝑢
2
}


To derive the MLE estimates of 𝜽, we can equivalently find the maximum log-likelihood estimate:
argmax
𝜃𝑢
∑log 𝑝(𝑥𝑢
|𝑥𝜋𝑢
, 𝜃𝑥𝑢|𝑥𝜋𝑢
)
𝑁
𝑛=1
= argmax
𝜃𝑢
∑
{


−
1
2
log 2𝜋𝜎𝑢
2 −
1
2𝜎𝑢
2 (𝑥𝑢,𝑛 − ( ∑ 𝑤𝑢𝑐𝑥𝑢𝑐,𝑛 + 𝑤𝑢0
𝑐∈𝑥𝜋𝑢
))
2
}

𝑁
𝑛=1
And taking the derivatives, we derive linear equations for each parameter {𝑤𝑢0, … , 𝑤𝑢𝐶, 𝜎𝑢} and
solve for their MLE estimates using the following steps:
a. Solve for the linear equations for {𝑤𝑢0, … , 𝑤𝑢𝐶 } : _learn_node_parameter_w()[3
points].
b. Solve for the linear equation for the variance 𝜎
2 using {𝑤𝑢0, … , 𝑤𝑢𝐶}:
_learn_node_parameter_var()[1 point]
You will call the above steps for each node in _get_learned_parameters() [2 points] to
learn all parameters. Your derivations in the report are also important [1 point].
Hint: It might be useful to create additional functions for this part. Place these functions between
the designated comment blocks for each file.
CS5340 Assignment 2 (Semester 2, AY2023/2024) CS5340 Assignment 2 (Semester 1, AY2023/2024)