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)

## Reviews

There are no reviews yet.