In this assignment, you will implement two approximate inference methods for Bayesian networks, i.e., rejection sampling and Gibbs sampling in the given attached base code.  

Input:

Bayesian network is represented as a list of nodes.  Each node is represented as a list in the following order:

name: string

parent names: a list of strings. Can be an empty list

cpt: a conditional probability table represented as an array. Each entry corresponds to the conditional probability that the variable corresponding to this node is true. The rows are ordered such that the values of the node’s parent variable(s) are enumerated in the traditional way. That is, in a table, the rightmost variable alternates T, F, T, F, …; the variable to its left T, T, F, F, T, T, F, F, …; and so on.

The nodes in the network will be ordered corresponding to the network topology, i.e., parent nodes will always come before their children. For example, the sprinkler network in Figure 13.15 and on our slides, is represented as:

nodes = [[“Cloudy”, [], [0.5]],
[“Sprinkler”, [“Cloudy”], [0.1, 0.5]],
[“Rain”, [“Cloudy”], [0.8, 0.2]],
[“WetGrass”, [“Sprinkler”, “Rain”], [0.99, 0.9, 0.9, 0.0]]]
b = BayesNet(nodes)
b.print()

You can call b.print() to see the conditional probability tables organized for each node.

Output:

A query will ask you to compute a possibly conditional probability of a single variable such as P(Rain | Cloudy = false, Sprinkler = true). Queries will always be for a distribution, not a specific event’s probability.  

The following methods will be called for queries:

rejectionSampling(queryNodeName, evidence, N)

or

gibbsSampling(queryNodeName, evidence, N)

queryNodeName: a string for the query node’s name

evidence: a set of <node name:value> pairs

N: total number of iterations

For instance, given the network b, a sample Gibbs sampling query can be called and printed as follows:

out = b.gibbsSampling(“Rain”, {“Sprinkler”:True}, 100000)

print(out)

The output will look like:

> [0.299, 0.700]

Notes

You may (actually, should) implement helper methods, but do not change the class structure or the signatures of existing methods.