Inference Algorithms (To Train the Graph)

In the context of Bayesian networks, inference algorithms are computational methods used to perform probabilistic reasoning over the network. They are designed to compute the conditional probability distributions of certain variables, given the values of other variables in the network. In other words, they are used to answer queries about the relationships among variables in the Bayesian network.

There are several types of inference algorithms, such as:

• Exact inference algorithms: These algorithms compute the exact probability distributions for the queried variables. Examples include Variable Elimination, the Clique Tree Algorithm, and the Junction Tree Algorithm.

• Approximate inference algorithms: These algorithms provide an approximation of the probability distributions for the queried variables. They are often used when exact inference is computationally infeasible due to the size or complexity of the network. Examples include Monte Carlo methods, like Markov Chain Monte Carlo (MCMC) Gibbs sampling, and Loopy Belief Propagation.

The main difference between inference algorithms and learning algorithms in Bayesian networks is their purpose. Inference algorithms are used to compute the conditional probability distributions of variables given observed evidence, whereas learning algorithms are employed to learn the structure of the network and/or the parameters of the conditional probability distributions.

Exact inference algorithms

Let's consider a simple example using the Variable Elimination algorithm, which is an exact inference method. Let's go through the code step by step, using a simple Bayesian network with three binary variables: $A$, $B$, and $C$. The network structure is $A -> B$, and $A -> C$.

1. We define the Conditional Probability Distribution Tables (CPD) for the variables in the Bayesian network: $P(A)$, $P(B | A)$, and $P(C | A)$.

2. We set the evidence for the variables, in this case, we observe that $B = 0$.

3. We perform inference using Variable Elimination to compute $P(C | B=0)$:

   1. Step 1: Eliminate variable A by summing over its possible values. We compute the joint probability $P(C, B=0)$ using the chain rule: $P(C, B=0) = Σ P(A) \times P(B=0 | A) P(C | A)$. This is essentially a sum-product operation on the CPD.

   2. Step 2: Normalize the result of Step 1 to obtain the conditional probability distribution $P(C | B=0)$.

4. Finally, we print the probability distribution of $P(C | B=0)$.

The next code demonstrates the basic idea behind the Variable Elimination algorithm. It involves eliminating variables by summing over their possible values and updating the joint probability distribution. After eliminating all the irrelevant variables, the result is normalized to obtain the conditional probability distribution of the query variable given the evidence.