## Approximate Inference over a BN using Belief Propagation

Consider the following joint probability distribution:
\begin{align}
p(x_1,x2,x3)=p(x_1)p(x_2|x_1)p(x_3|x_1,x_2)p(x_4|x_2)
\end{align}

where $x_1\in\{0,1\}$, $x_2\in\{0,1\}$, $x_3\in\{0,1,2\}$ and $x_4\in\{0,1,2,3\}$

The values of the CPD factors are know. Here we simply worry about inference. The goal is to learn how to use and interpret the provided library.

Note now that the associated factor graph contains cycles!!


```python
import numpy as np
from lib import Message_passing_BN as mp
import warnings
warnings.filterwarnings('ignore')
from IPython.display import Image

Image(filename='files/BN2.png')
```


```python

#p(x1)
CPD_1=np.array([0.5, 0.5])

#p(x2|x1)
CPD_2=np.array([0.75, 0.25, 0.3, 0.7])

#p(x3|x2)
CPD_3=np.array([0.1, 0.67,0.23,0.1,0.3,0.6,0.1, 0.6,0.3,0.2,0.3,0.5])

#p(x4|x2)
CPD_4=np.array([0.05,0.8,0.05,0.1,0.2,0.2,0.5,0.1])
```

### Defining the factor graph associated to the BN

Before running inference using BP, we will define the variable nodes and the graph. 


```python
v_card=[2,2,3,4]         #Vector of cardinalities

node_x1=mp.create_var_node(ID=1,cardinality=v_card[0],neighbor_order=[1,2,3],observed_value_index=-1)
node_x2=mp.create_var_node(ID=2,cardinality=v_card[1],neighbor_order=[2,3,4],observed_value_index=-1)
node_x3=mp.create_var_node(ID=3,cardinality=v_card[2],neighbor_order=[3],observed_value_index=-1)
node_x4=mp.create_var_node(ID=4,cardinality=v_card[3],neighbor_order=[4],observed_value_index=-1)

list_var_nodes=[node_x1,node_x2,node_x3,node_x4]

factor_1=mp.create_factor_node(ID=1,neighbors=[node_x1],CPD=CPD_1)
factor_2=mp.create_factor_node(ID=2,neighbors=[node_x1,node_x2],CPD=CPD_2)
factor_3=mp.create_factor_node(ID=3,neighbors=[node_x1,node_x2,node_x3],CPD=CPD_3)
factor_4=mp.create_factor_node(ID=4,neighbors=[node_x2,node_x4],CPD=CPD_4)

list_factor_nodes=[factor_1,factor_2,factor_3,factor_4]
```

### Running BP message passing

This is straightforward given the functions provided. The factor graph is not a tree, so the algorithm may not converge (in this case it will because we have a single loop, but in general we losse converge and we have to stop after a few iterations)


```python
L=5 #BP iterations

for l in range(L):
    
    #Factor update
    for factor_node in list_factor_nodes:
        mp.update_factor_to_var(factor_node)
        
    #Variable update
    for var_node in list_var_nodes:
        mp.update_var_to_factor(var_node)

list_marg=[]

for var_node in list_var_nodes:
    marg=mp.compute_var_marginal(var_node)
    list_marg.append(marg)
    print("The marginal pmf of node x_%d is=" %(var_node['ID']))
    print(marg)

```

    The marginal pmf of node x_1 is=
    [[ 0.5]
     [ 0.5]]
    The marginal pmf of node x_2 is=
    [[ 0.525]
     [ 0.475]]
    The marginal pmf of node x_3 is=
    [[ 0.12375 ]
     [ 0.475875]
     [ 0.400375]]
    The marginal pmf of node x_4 is=
    [[ 0.12125]
     [ 0.515  ]
     [ 0.26375]
     [ 0.1    ]]


### Inference with partial observations

Note that if we observe either x1 or x2, the FG becomes a tree and BP converges


```python
# The function mp.initialize_variable set the value to their current observed state

mp.initialize_variable(var_node=node_x1,observed_value_index=0)

#IMPORTANT, we have to re-initialize all factor nodes!! Intermediate messages were not erased from the previous BP

mp.initialize_factor_msgs(factor_1,neighbors=[node_x1])
mp.initialize_factor_msgs(factor_2,neighbors=[node_x1,node_x2])
mp.initialize_factor_msgs(factor_3,neighbors=[node_x1,node_x2,node_x3])
mp.initialize_factor_msgs(factor_4,neighbors=[node_x2,node_x4])
```

And now we can run BP again ...


```python
L=20 #BP iterations

for l in range(L):
    
    #Factor update
    for factor_node in list_factor_nodes:
        mp.update_factor_to_var(factor_node)
        
    #Variable update
    for var_node in list_var_nodes:
        mp.update_var_to_factor(var_node)

list_marg=[]

for var_node in list_var_nodes:
    marg=mp.compute_var_marginal(var_node)
    list_marg.append(marg)
    print("The marginal pmf of node x_%d is=" %(var_node['ID']))
    print(marg)
```

    The marginal pmf of node x_1 is=
    [[  1.00000000e+00]
     [  1.38389653e-87]]
    The marginal pmf of node x_2 is=
    [[ 0.75]
     [ 0.25]]
    The marginal pmf of node x_3 is=
    [[ 0.33333333]
     [ 0.33333333]
     [ 0.33333333]]
    The marginal pmf of node x_4 is=
    [[ 0.125]
     [ 0.5  ]
     [ 0.275]
     [ 0.1  ]]


### Exact Inference via node clustering

The optimal inference algorithm for **any** BN, no matter if the factor graph contains cycles or not, is the *Junction Tree Algorithm (JTA)*. In a nutshell, it is based on creating cluster of nodes so that the resulting fg with the cluster nodes is cycle-free and BP con be run over it. JTA finds the most efficient way to achieve such graph. **However its complexity is in general prohibitive. Unless the dimension is very small or the graph has a sparse structure**.

Lets show that we can run exact inference in the current BP **by merging nodes x1 and x2**

Again, we make use of a provided function to create the cluster-node. ** Some CPDs have to be re-defined! Now we have a cluster node that can take up to 4 values!**


```python
Image(filename='files/BN22.png')
```


```python
#p(x1,x2)
CPD_12_joint=CPD_2
CPD_12_joint[0:2]*=CPD_1[0]          #This exploits the Tree-structure
CPD_12_joint[2:4]*=CPD_1[1]

node_x1=mp.create_var_node(ID=1,cardinality=v_card[0],neighbor_order=[1,2,3],observed_value_index=-1)
node_x2=mp.create_var_node(ID=2,cardinality=v_card[1],neighbor_order=[2,3,4],observed_value_index=-1)
node_x3=mp.create_var_node(ID=3,cardinality=v_card[2],neighbor_order=[3],observed_value_index=-1)
node_x4=mp.create_var_node(ID=4,cardinality=v_card[3],neighbor_order=[4],observed_value_index=-1)

node_x12=mp.create_joint_node(5,node_members=[node_x1,node_x2],neighbor_order=[5],observed_values_indexes=-1)

list_var_nodes=[node_x12,node_x3,node_x4]

factor_1=mp.create_factor_node(ID=1,neighbors=[node_x1],CPD=CPD_1)
factor_2=mp.create_factor_node(ID=2,neighbors=[node_x1,node_x2],CPD=CPD_2)
factor_3=mp.create_factor_node(ID=3,neighbors=[node_x1,node_x2,node_x3],CPD=CPD_3)
factor_4=mp.create_factor_node(ID=4,neighbors=[node_x2,node_x4],CPD=CPD_4)

factor_12=mp.create_factor_node(5,neighbors=[node_x12],CPD=CPD_12_joint)

list_factor_nodes=[factor_12,factor_3,factor_4]


```


```python
L=3 #BP iterations

for l in range(L):
    
    #Factor update
    for factor_node in list_factor_nodes:
        mp.update_factor_to_var(factor_node)
        
    #Variable update
    for var_node in list_var_nodes:
        mp.update_var_to_factor(var_node)

list_marg=[]

for var_node in list_var_nodes:
    marg=mp.compute_var_marginal(var_node)
    list_marg.append(marg)
    print("The marginal pmf of node x_%d is=" %(var_node['ID']))
    print(marg)

```

    The marginal pmf of node x_5 is=
    [[ 0.375]
     [ 0.125]
     [ 0.15 ]
     [ 0.35 ]]
    The marginal pmf of node x_3 is=
    [[ 0.125 ]
     [ 0.4675]
     [ 0.4075]]
    The marginal pmf of node x_4 is=
    [[ 0.125]
     [ 0.5  ]
     [ 0.275]
     [ 0.1  ]]


BP marginals are close to the exact ones, but they are not equal!


```python

```

0e7aa80d3d611a52bd8d300ee430f6143a60376d
ipynb
Jupyter Notebook
Notebooks/Second Example Message Passing.ipynb
olmosUC3M/Inference-and-Learning-in-discrete-Bayesian-Networks
12e08f2e3f34146638806212be54837cc22c0516
MIT
2019-05-19T11:26:42.000Z
2021-07-31T07:28:35.000Z
Notebooks/Second Example Message Passing.ipynb
olmosUC3M/Inference-and-Learning-in-discrete-Bayesian-Networks
12e08f2e3f34146638806212be54837cc22c0516
MIT
Notebooks/Second Example Message Passing.ipynb
olmosUC3M/Inference-and-Learning-in-discrete-Bayesian-Networks
12e08f2e3f34146638806212be54837cc22c0516
MIT
Qwen/Qwen-72B
1. YES
2. YES