Edge Ordering

Edge ordering makes a difference on the on the join tree and potentials produced. Let’s take the BBN network structure below where all nodes are binary having the values on and off.

a –> c <– b

Note how c has 2 parents, a and b. The potential (or conditional probability table CPT) for c is specified as a list of probabilities as follows.

[0.7, 0.3, 0.2, 0.8, 0.6, 0.4, 0.6, 0.4]

Let’s say that this list of probabilities represents the CPT below.

|       |       | c=on | c=off |
|-------|-------|------|-------|
| a=on  | b=on  | 0.7  | 0.3   |
| a=on  | b=off | 0.2  | 0.8   |
| a=off | b=on  | 0.6  | 0.4   |
| a=off | b=off | 0.6  | 0.4   |

When we define a BBN structure (be it programmatically in code/Python or declaratively in JSON), we should define and add the edge a -> c to the graph before the edge b -> c. Below is the code where we do so.

from pybbn.graph.dag import Bbn
from pybbn.graph.edge import Edge, EdgeType
from pybbn.graph.node import BbnNode
from pybbn.graph.variable import Variable

def get_bbn1():
    a = BbnNode(Variable(0, 'a', ['on', 'off']), [0.2, 0.8])
    b = BbnNode(Variable(1, 'b', ['on', 'off']), [0.8, 0.2])
    c = BbnNode(Variable(2, 'c', ['on', 'off']), [0.7, 0.3, 0.2, 0.8, 0.6, 0.4, 0.6, 0.4])

    bbn = Bbn() \
        .add_node(a) \
        .add_node(b) \
        .add_node(c) \
        .add_edge(Edge(a, c, EdgeType.DIRECTED)) \
        .add_edge(Edge(b, c, EdgeType.DIRECTED))

    return bbn

When we add the edge b -> c to the network structure before a -> c, then the induced CPT for c will be as follows. This second CPT for c is not the same at all for the first one!

|       |       | c=on | c=off |
|-------|-------|------|-------|
| b=on  | a=on  | 0.7  | 0.3   |
| b=on  | a=off | 0.2  | 0.8   |
| b=off | a=on  | 0.6  | 0.4   |
| b=off | a=off | 0.6  | 0.4   |

Here is the code for creating a BBN where we add b -> c before a -> c.

def get_bbn2():
    a = BbnNode(Variable(0, 'a', ['on', 'off']), [0.2, 0.8])
    b = BbnNode(Variable(1, 'b', ['on', 'off']), [0.8, 0.2])
    c = BbnNode(Variable(2, 'c', ['on', 'off']), [0.7, 0.3, 0.2, 0.8, 0.6, 0.4, 0.6, 0.4])

    bbn = Bbn() \
        .add_node(a) \
        .add_node(b) \
        .add_node(c) \
        .add_edge(Edge(b, c, EdgeType.DIRECTED)) \
        .add_edge(Edge(a, c, EdgeType.DIRECTED))

    return bbn

Although the networks (regardless of the order of how we add the edges) are the same in both cases, the parameters induced are NOT and sensitive to the order of how the edges are added. Now, let’s compare the posteriors of of these 2 BBNs.

from pybbn.pptc.inferencecontroller import InferenceController

b1 = get_bbn1()
b2 = get_bbn2()

j1 = InferenceController.apply(b1)
j2 = InferenceController.apply(b2)

Here are the posteriors for the first BBN. Note that the id-to-name as defined above are as follows.

• 0: a

• 1: b

• 2: c

Keep an eye on id 2, thus.

for node in j1.get_bbn_nodes():
    potential = j1.get_bbn_potential(node)
    print(potential)
    print('-' * 10)

1=on|0.80000
1=off|0.20000
----------
2=on|0.60000
2=off|0.40000
----------
0=on|0.20000
0=off|0.80000
----------

Here are the posteriors for the second BBN.

for node in j2.get_bbn_nodes():
    potential = j2.get_bbn_potential(node)
    print(potential)
    print('-' * 10)

1=on|0.80000
1=off|0.20000
----------
2=on|0.36000
2=off|0.64000
----------
0=on|0.20000
0=off|0.80000
----------

For now, there is no workaround for this issue of logically identical specified BBNs producing different potentials as a result of edge insertion order. Just make sure you are aware and careful.

Simple Example

Let’s say you have a DAG with 5 variables: \(X_1, X_2, X_3, X_4, X_5\) and the structure represented by an edge list is as follows.

• \(X_1 \rightarrow X_5\)

• \(X_2 \rightarrow X_5\)

• \(X_3 \rightarrow X_5\)

• \(X_4 \rightarrow X_5\)

The domains (or number of values) for each variable is as follows.

• \(X_1 \in \{v_1, v_2\}\)

• \(X_2 \in \{v_1, v_2, v_3\}\)

• \(X_3 \in \{v_1, v_2\}\)

• \(X_4 \in \{v_1, v_2, v_3, v_4, v_5\}\)

• \(X_5 \in \{v_1, v_2, v_3\}\)

The question is, how do we build the parameters for \(X_5\)?

Let’s create some fake data.

import pandas as pd
import numpy as np
import random

np.random.seed(37)
random.seed(37)

def get_data(n_values, n_samples):
    return [f'v{v}' for v in np.random.randint(0, n_values, n_samples)]

N = 1_000
df = pd.DataFrame({
    'x1': get_data(2, N),
    'x2': get_data(3, N),
    'x3': get_data(2, N),
    'x4': get_data(5, N),
    'x5': get_data(3, N)
})

df.shape

(1000, 5)

df.head()

	x1	x2	x3	x4	x5
0	v1	v2	v0	v4	v2
1	v1	v0	v1	v3	v0
2	v0	v1	v1	v2	v2
3	v1	v2	v0	v1	v2
4	v0	v2	v1	v1	v2

Now, let’s verify the domains.

def get_domains(df):
    return {c: sorted(list(df[c].unique())) for c in df.columns}

domains = get_domains(df)
domains

{'x1': ['v0', 'v1'],
 'x2': ['v0', 'v1', 'v2'],
 'x3': ['v0', 'v1'],
 'x4': ['v0', 'v1', 'v2', 'v3', 'v4'],
 'x5': ['v0', 'v1', 'v2']}

You want to create a conditional probability table CPT for \(X_5\) that looks like the following. Note that we simply show you the CPT shape and not the actual values. We will go into computing the actual value in a bit.

import itertools

pas = [c for c in domains if c != 'x5']

cpt = (domains[pa] for pa in pas)
cpt = itertools.product(*cpt)
cpt = pd.DataFrame(cpt, columns=pas) \
    .assign(**{v: 0.0 for v in domains['x5']}) \
    .set_index(pas)
cpt

				v0	v1	v2
x1	x2	x3	x4
v0	v0	v0	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
		v1	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
	v1	v0	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
		v1	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
	v2	v0	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
		v1	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
v1	v0	v0	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
		v1	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
	v1	v0	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
		v1	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
	v2	v0	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0
		v1	v0	0.0	0.0	0.0
			v1	0.0	0.0	0.0
			v2	0.0	0.0	0.0
			v3	0.0	0.0	0.0
			v4	0.0	0.0	0.0

Ok, so how do we create the CPT for \(X_5\) given the data? Here’s some code to demonstrate how to build the CPT.

def get_cond_probs(q, d, pas, ch, df):
    def save_divide(num, den):
        try:
            return num / den
        except:
            return 0.0

    p_b = df.query(q).shape[0]

    cp_pa = {f'x{i+1}': p for i, p in enumerate(pas)}
    cp_ch = {v: save_divide(df.query(f'{q} and {ch}=="{v}"').shape[0], p_b) for v in d}
    cp = {**cp_pa, **cp_ch}

    return cp

pa_values = list(itertools.product(*(domains[pa] for pa in pas)))

queries = map(lambda tup: [f'x{i+1}=="{v}"' for i, v in enumerate(tup)], pa_values)
queries = map(lambda arr: ' and '.join(arr), queries)
queries = list(queries)

cpt = pd.DataFrame((get_cond_probs(q, domains['x5'], pas, 'x5', df) for q, pas in zip(queries, pa_values))) \
    .set_index(['x1', 'x2', 'x3', 'x4'])
cpt

				v0	v1	v2
x1	x2	x3	x4
v0	v0	v0	v0	0.466667	0.266667	0.266667
			v1	0.285714	0.428571	0.285714
			v2	0.583333	0.166667	0.250000
			v3	0.538462	0.307692	0.153846
			v4	0.400000	0.000000	0.600000
		v1	v0	0.533333	0.333333	0.133333
			v1	0.411765	0.117647	0.470588
			v2	0.357143	0.357143	0.285714
			v3	0.434783	0.173913	0.391304
			v4	0.368421	0.421053	0.210526
	v1	v0	v0	0.375000	0.375000	0.250000
			v1	0.266667	0.400000	0.333333
			v2	0.312500	0.250000	0.437500
			v3	0.400000	0.200000	0.400000
			v4	0.190476	0.428571	0.380952
		v1	v0	0.157895	0.368421	0.473684
			v1	0.307692	0.384615	0.307692
			v2	0.388889	0.333333	0.277778
			v3	0.250000	0.375000	0.375000
			v4	0.200000	0.250000	0.550000
	v2	v0	v0	0.333333	0.166667	0.500000
			v1	0.142857	0.428571	0.428571
			v2	0.320000	0.440000	0.240000
			v3	0.285714	0.428571	0.285714
			v4	0.500000	0.250000	0.250000
		v1	v0	0.476190	0.333333	0.190476
			v1	0.333333	0.333333	0.333333
			v2	0.307692	0.076923	0.615385
			v3	0.312500	0.375000	0.312500
			v4	0.562500	0.187500	0.250000
v1	v0	v0	v0	0.333333	0.285714	0.380952
			v1	0.222222	0.388889	0.388889
			v2	0.235294	0.411765	0.352941
			v3	0.333333	0.333333	0.333333
			v4	0.470588	0.235294	0.294118
		v1	v0	0.368421	0.315789	0.315789
			v1	0.461538	0.192308	0.346154
			v2	0.263158	0.315789	0.421053
			v3	0.411765	0.235294	0.352941
			v4	0.315789	0.368421	0.315789
	v1	v0	v0	0.304348	0.260870	0.434783
			v1	0.454545	0.454545	0.090909
			v2	0.300000	0.350000	0.350000
			v3	0.454545	0.181818	0.363636
			v4	0.214286	0.428571	0.357143
		v1	v0	0.285714	0.357143	0.357143
			v1	0.235294	0.411765	0.352941
			v2	0.315789	0.315789	0.368421
			v3	0.363636	0.227273	0.409091
			v4	0.222222	0.333333	0.444444
	v2	v0	v0	0.272727	0.181818	0.545455
			v1	0.190476	0.523810	0.285714
			v2	0.391304	0.260870	0.347826
			v3	0.428571	0.214286	0.357143
			v4	0.333333	0.166667	0.500000
		v1	v0	0.235294	0.352941	0.411765
			v1	0.166667	0.500000	0.333333
			v2	0.300000	0.200000	0.500000
			v3	0.263158	0.368421	0.368421
			v4	0.400000	0.333333	0.266667

Finally, we can flatten the CPT as follows.

cpt_x5 = np.ravel(cpt).tolist()
cpt_x5

[0.4666666666666667,
 0.26666666666666666,
 0.26666666666666666,
 0.2857142857142857,
 0.42857142857142855,
 0.2857142857142857,
 0.5833333333333334,
 0.16666666666666666,
 0.25,
 0.5384615384615384,
 0.3076923076923077,
 0.15384615384615385,
 0.4,
 0.0,
 0.6,
 0.5333333333333333,
 0.3333333333333333,
 0.13333333333333333,
 0.4117647058823529,
 0.11764705882352941,
 0.47058823529411764,
 0.35714285714285715,
 0.35714285714285715,
 0.2857142857142857,
 0.43478260869565216,
 0.17391304347826086,
 0.391304347826087,
 0.3684210526315789,
 0.42105263157894735,
 0.21052631578947367,
 0.375,
 0.375,
 0.25,
 0.26666666666666666,
 0.4,
 0.3333333333333333,
 0.3125,
 0.25,
 0.4375,
 0.4,
 0.2,
 0.4,
 0.19047619047619047,
 0.42857142857142855,
 0.38095238095238093,
 0.15789473684210525,
 0.3684210526315789,
 0.47368421052631576,
 0.3076923076923077,
 0.38461538461538464,
 0.3076923076923077,
 0.3888888888888889,
 0.3333333333333333,
 0.2777777777777778,
 0.25,
 0.375,
 0.375,
 0.2,
 0.25,
 0.55,
 0.3333333333333333,
 0.16666666666666666,
 0.5,
 0.14285714285714285,
 0.42857142857142855,
 0.42857142857142855,
 0.32,
 0.44,
 0.24,
 0.2857142857142857,
 0.42857142857142855,
 0.2857142857142857,
 0.5,
 0.25,
 0.25,
 0.47619047619047616,
 0.3333333333333333,
 0.19047619047619047,
 0.3333333333333333,
 0.3333333333333333,
 0.3333333333333333,
 0.3076923076923077,
 0.07692307692307693,
 0.6153846153846154,
 0.3125,
 0.375,
 0.3125,
 0.5625,
 0.1875,
 0.25,
 0.3333333333333333,
 0.2857142857142857,
 0.38095238095238093,
 0.2222222222222222,
 0.3888888888888889,
 0.3888888888888889,
 0.23529411764705882,
 0.4117647058823529,
 0.35294117647058826,
 0.3333333333333333,
 0.3333333333333333,
 0.3333333333333333,
 0.47058823529411764,
 0.23529411764705882,
 0.29411764705882354,
 0.3684210526315789,
 0.3157894736842105,
 0.3157894736842105,
 0.46153846153846156,
 0.19230769230769232,
 0.34615384615384615,
 0.2631578947368421,
 0.3157894736842105,
 0.42105263157894735,
 0.4117647058823529,
 0.23529411764705882,
 0.35294117647058826,
 0.3157894736842105,
 0.3684210526315789,
 0.3157894736842105,
 0.30434782608695654,
 0.2608695652173913,
 0.43478260869565216,
 0.45454545454545453,
 0.45454545454545453,
 0.09090909090909091,
 0.3,
 0.35,
 0.35,
 0.45454545454545453,
 0.18181818181818182,
 0.36363636363636365,
 0.21428571428571427,
 0.42857142857142855,
 0.35714285714285715,
 0.2857142857142857,
 0.35714285714285715,
 0.35714285714285715,
 0.23529411764705882,
 0.4117647058823529,
 0.35294117647058826,
 0.3157894736842105,
 0.3157894736842105,
 0.3684210526315789,
 0.36363636363636365,
 0.22727272727272727,
 0.4090909090909091,
 0.2222222222222222,
 0.3333333333333333,
 0.4444444444444444,
 0.2727272727272727,
 0.18181818181818182,
 0.5454545454545454,
 0.19047619047619047,
 0.5238095238095238,
 0.2857142857142857,
 0.391304347826087,
 0.2608695652173913,
 0.34782608695652173,
 0.42857142857142855,
 0.21428571428571427,
 0.35714285714285715,
 0.3333333333333333,
 0.16666666666666666,
 0.5,
 0.23529411764705882,
 0.35294117647058826,
 0.4117647058823529,
 0.16666666666666666,
 0.5,
 0.3333333333333333,
 0.3,
 0.2,
 0.5,
 0.2631578947368421,
 0.3684210526315789,
 0.3684210526315789,
 0.4,
 0.3333333333333333,
 0.26666666666666666]

For completeness, let’s compute the probabilities for the parents.

def get_prob(n, d, df):
    N = df.shape[0]
    p = {v: df.query(f'{n}=="{v}"').shape[0] / N for v in d}
    return list(p.values())

cpt_x1 = get_prob('x1', domains['x1'], df)
cpt_x2 = get_prob('x2', domains['x2'], df)
cpt_x3 = get_prob('x3', domains['x3'], df)
cpt_x4 = get_prob('x4', domains['x4'], df)

cpt_x1

[0.489, 0.511]

cpt_x2

[0.34, 0.341, 0.319]

cpt_x3

[0.477, 0.523]

cpt_x4

[0.209, 0.197, 0.206, 0.191, 0.197]

Let’s build the BBN and join tree.

x1 = BbnNode(Variable(0, 'x1', domains['x1']), cpt_x1)
x2 = BbnNode(Variable(1, 'x2', domains['x2']), cpt_x2)
x3 = BbnNode(Variable(2, 'x3', domains['x3']), cpt_x3)
x4 = BbnNode(Variable(3, 'x4', domains['x4']), cpt_x4)
x5 = BbnNode(Variable(4, 'x5', domains['x5']), cpt_x5)

bbn = Bbn() \
    .add_node(x1) \
    .add_node(x2) \
    .add_node(x3) \
    .add_node(x4) \
    .add_node(x5) \
    .add_edge(Edge(x1, x5, EdgeType.DIRECTED)) \
    .add_edge(Edge(x2, x5, EdgeType.DIRECTED)) \
    .add_edge(Edge(x3, x5, EdgeType.DIRECTED)) \
    .add_edge(Edge(x4, x5, EdgeType.DIRECTED))

join_tree = InferenceController.apply(bbn)

Here are the posteriors.

for node in join_tree.get_bbn_nodes():
    potential = join_tree.get_bbn_potential(node)
    print(node)
    print(potential)
    print('-' * 15)

1|x2|v0,v1,v2
1=v0|0.34000
1=v1|0.34100
1=v2|0.31900
---------------
2|x3|v0,v1
2=v0|0.47700
2=v1|0.52300
---------------
3|x4|v0,v1,v2,v3,v4
3=v0|0.20900
3=v1|0.19700
3=v2|0.20600
3=v3|0.19100
3=v4|0.19700
---------------
4|x5|v0,v1,v2
4=v0|0.33850
4=v1|0.30794
4=v2|0.35356
---------------
0|x1|v0,v1
0=v0|0.48900
0=v1|0.51100
---------------

Let’s assert evidence and observe the posteriors.

from pybbn.graph.jointree import EvidenceBuilder

ev1 = EvidenceBuilder() \
    .with_node(join_tree.get_bbn_node_by_name('x1')) \
    .with_evidence('v0', 1.0) \
    .build()

join_tree.unobserve_all()
join_tree.update_evidences([ev1])

for node in join_tree.get_bbn_nodes():
    potential = join_tree.get_bbn_potential(node)
    print(node)
    print(potential)
    print('-' * 15)

1|x2|v0,v1,v2
1=v0|0.34000
1=v1|0.34100
1=v2|0.31900
---------------
2|x3|v0,v1
2=v0|0.47700
2=v1|0.52300
---------------
3|x4|v0,v1,v2,v3,v4
3=v0|0.20900
3=v1|0.19700
3=v2|0.20600
3=v3|0.19100
3=v4|0.19700
---------------
4|x5|v0,v1,v2
4=v0|0.36050
4=v1|0.29824
4=v2|0.34126
---------------
0|x1|v0,v1
0=v0|1.00000
0=v1|0.00000
---------------

Let’s assert multiple evidences. The posterior for \(X_5\) should be the same as the CPT when all parents are set to v0.

ev1 = EvidenceBuilder() \
    .with_node(join_tree.get_bbn_node_by_name('x1')) \
    .with_evidence('v0', 1.0) \
    .build()
ev2 = EvidenceBuilder() \
    .with_node(join_tree.get_bbn_node_by_name('x2')) \
    .with_evidence('v0', 1.0) \
    .build()
ev3 = EvidenceBuilder() \
    .with_node(join_tree.get_bbn_node_by_name('x3')) \
    .with_evidence('v0', 1.0) \
    .build()
ev4 = EvidenceBuilder() \
    .with_node(join_tree.get_bbn_node_by_name('x4')) \
    .with_evidence('v0', 1.0) \
    .build()

join_tree.unobserve_all()
join_tree.update_evidences([ev1, ev2, ev3, ev4])

for node in join_tree.get_bbn_nodes():
    potential = join_tree.get_bbn_potential(node)
    print(node)
    print(potential)
    print('-' * 15)

1|x2|v0,v1,v2
1=v0|1.00000
1=v1|0.00000
1=v2|0.00000
---------------
2|x3|v0,v1
2=v0|1.00000
2=v1|0.00000
---------------
3|x4|v0,v1,v2,v3,v4
3=v0|1.00000
3=v1|0.00000
3=v2|0.00000
3=v3|0.00000
3=v4|0.00000
---------------
4|x5|v0,v1,v2
4=v0|0.46667
4=v1|0.26667
4=v2|0.26667
---------------
0|x1|v0,v1
0=v0|1.00000
0=v1|0.00000
---------------