CS5340代写、代写C++，Java程序

日期：2022-10-29 11:38

S5340 Assignment 4 (Semester 1, AY2022/2023) 1

CS5340 ASSIGNMENT 4:

MONTE CARLO INFERENCE

1. OVERVIEW

In this assignment, you will write code to perform Monte Carlo inference i.e. Importance sampling

and Gibbs sampling. Often, marginalization over large/continuous probability distributions can

be intractable. In Monte Carlo inference, we circumvent this problem by sampling from simpler

proposal distributions to approximate our target distribution, making the problem much more

tractable for complex distributions.

References: Lecture 9

Honour Code. This coding assignment 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!

2. SUBMISSION INSTRUCTIONS

Items to be submitted:

Source code (zip file containing folders part1 and part2):

o part1/main.py– code for importance sampling.

o part2/main.py – code for Gibbs sampling.

Report (report.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_lab4.zip (replace with your student number).

Submit your assignment by 2022 , 2359HRS to LumiNUS. 25% of the total score

will be deducted for each day of late submission.

3. 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.

31O October

CS5340 Assignment 4 (Semester 1, AY2022/2023) 2

4. TEST CASES

To help with your implementation, we have provided a few sample inputs. They can be found in

the data/inputs folder. The ground-truth files can be found in data/ground-truth. Your

predictions will be stored in data/predictions. For test cases 1 and 2, the inputs will be on the

example given in Lecture 9:

For case 3, we will use a slightly larger graph. Note that the ground-truth might be slightly

different from your answers. We will assume a tolerance up to 1 decimal place. During grading,

your code will be evaluated on hidden test cases on top of the validation test cases we have

provided.

Additionally, we expect your code to run in a reasonable amount of time, any time within 2-3x of

our timings below is reasonable:

Case 1 2 3 4

Importance

Sampling

10s 5s 15s 19s

Gibbs Sampling 13s 7s 29s 21s

Table 1: Timings on i5-1035G1 CPU @ 1.00GHz.

For fairness, we will evaluate your timings on the same system.

5. IMPORTANCE SAMPLING

In part 1 i.e. importance sampling, you will be provided with local target conditional distribution

(|) and local proposal conditional probabilities i.e. (|) where is are the

parents of node . In this assignment, we will assume our proposal distribution has the form i.e.

() = ∏ (|) and the target distribution has the form () = ∏(|) . Each

sample is then weighted by the ratio between

()

()

to obtain the approximate distribution. You are

expected to return the conditional probability distribution (|) where the nodes in the

graph are = ∪ , with being the query nodes and being the evidence nodes.

CS5340 Assignment 4 (Semester 1, AY2022/2023) 3

Note that during sampling, students are expected to perform sampling in a topological order i.e.

parent nodes should be sampled before child nodes, and the input samples should be updated

with the parent samples before sampling from the child node.

You will implement the following functions:

? Performs sampling for a single iteration (all nodes sampled once): _sample_step()[3

points]

o Students are expected to sample from the local proposal distributions for each

node. Do not sample from a joint proposal distribution.

o Sampling should be done in topological order. For example, in the example from

Lecture 9, sampling in the order 1, 2, 3, 4, 5 would be one way to sample

topologically.

o Once the parent node is sampled, use the sample from the parent node as the

observation of the parent into the child node’s probability distribution.

? Performs sampling for iterations, weight the samples and return the approximate

conditional probability (|): _get_conditional_probability()[4 points]

o Do not compute the joint proposal distribution or joint target distribution to get

(|) and (|) . You are expected to take the output these values by

taking the scalar product of the local proposal/conditional distribution values.

Note that we will also provide evidence variables, and the graph structure must be updated with

the evidence variables.

Hint: It might be useful to create additional functions for this part. Place these functions between

the designated comment blocks for each file.

6. GIBBS SAMPLING

In part 2 i.e. Gibbs sampling, you will be provided with conditional probabilities i.e. (| ?

{}) for each node . You will sample from the conditional distributions for each node, by

holding other nodes fixed. The samples are then weighted equally to obtain the approximate

distribution (|) where are the query nodes and are the evidence nodes.

Performs sampling for a single iteration (all nodes sampled once): _sample_step()[3

points]

o Sampling should be done like Lecture 9’s example on Gibbs sampling.

Performs sampling for iterations, and return the approximate distribution

_get_conditional_probability()[5 points]

o Students are expected to reduce the proposal distributions for each node to its

Markov Blanket. Students are not allowed to use networkx.markov_blanket() to

compute it.

Note that we will also provide evidence variables, and the graph structure must be updated with

the evidence variables.

Hint: It might be useful to create additional functions for this part. Place these functions between

the designated comment blocks for each file. Some points are attributable to more efficient

implementations.