AI: Inference by enumeration

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 X or X | NAME=T NAME=F ….
  • Print P = X with 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}")

Lesson: Bayesian networks →