Answer any question a Bayesian network can answer.
What to build
A program that computes P(X = true | evidence) in a Bayesian network by enumeration.
Requirements
- The network format is that of the previous exercise. The query is
XorX | NAME=T NAME=F …. - Print
P = Xwith four decimal places.
Input
Line 1: n. Then n node lines. Last line: the query.
Output
One line.
Constraints
n ≤ 10.
Example
Input:
4
Cloudy : 0.5
Sprinkler Cloudy : 0.1 0.4
Rain Cloudy : 0.7 0.2
Wet Sprinkler Rain : 0.95 0.9 0.8 0.05
Rain | Wet=T
Output:
P = 0.6781
Why it works
The joint distribution is the product of the tables, so summing it over every unknown variable and normalizing gives the exact conditional probability.
Examples
Example 1 · Input
4 Cloudy : 0.5 Sprinkler Cloudy : 0.1 0.4 Rain Cloudy : 0.7 0.2 Wet Sprinkler Rain : 0.95 0.9 0.8 0.05 Rain | Wet=T
Expected output
P = 0.6781
Example 2 · Input
4 Cloudy : 0.5 Sprinkler Cloudy : 0.1 0.4 Rain Cloudy : 0.7 0.2 Wet Sprinkler Rain : 0.95 0.9 0.8 0.05 Sprinkler | Wet=T Rain=T
Expected output
P = 0.1919
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
List the hidden variables (neither the query nor evidence) and try every combination of their values with itertools.product.
Hint 2
Sum the joint probability for query = true and for query = false separately, then normalize.
Solution
Show one correct solution (try it yourself first)
import itertools
nodes = []
for _ in range(int(input())):
left, right = input().split(":")
name, *parents = left.split()
probs = list(map(float, right.split()))
combos = list(itertools.product([True, False], repeat=len(parents)))
nodes.append((name, parents, dict(zip(combos, probs))))
query, _, rest = input().partition("|")
x = query.strip()
evidence = {k: v == "T" for k, v in (item.split("=") for item in rest.split())}
def joint(world):
result = 1.0
for name, parents, table in nodes:
p_true = table[tuple(world[q] for q in parents)]
result *= p_true if world[name] else 1 - p_true
return result
hidden = [name for name, _, _ in nodes if name != x and name not in evidence]
weight = {True: 0.0, False: 0.0}
for value in (True, False):
for values in itertools.product([True, False], repeat=len(hidden)):
weight[value] += joint({**evidence, x: value, **dict(zip(hidden, values))})
print(f"P = {weight[True] / (weight[True] + weight[False]):.4f}")