If evidence is given as, for example, "low intelligence", then what would be the chances of getting a "good letter" as shown in Figure 3, in the top right quadrant? This is addressed by causal reasoning. As shown in the first quadrant, causal reasoning flows from the top down.

If evidence such as a "bad letter" is given, what would be the chances that the student got a "good grade"? This question, as shown in Figure 3 in the top left quadrant, is addressed by evidential reasoning. As shown in the second quadrant, evidential reasoning flows from the bottom up.

Obtaining interesting patterns from finding a "related cause" is the objective of intercausal reasoning. If evidence of "grade C" and "high intelligence" is given, then what would be the chance of course difficulty being "high"? This type of reasoning is also called "explaining away" as one cause explains the reason for another cause and this is illustrated in the third quadrant, in the bottom-left of Figure 3.

If a student takes an "easy" course and has a "bad letter", what would be the chances of him getting a "grade C" ? This is explained by queries with combined reasoning patterns. Note that it has mixed information and does not a flow in a single fixed direction as in the case of other reasoning patterns and is shown in the bottom-right of the figure, in quadrant 4:

Influence is the effect of how the condition or outcome of one variable changes the value or the belief associated with another variable. We have seen this from the reasoning patterns that influence flows from variables in direct relationships (parent/child), causal/evidential (parent and child with intermediates) and in combined structures.

The only case where the influence doesn't flow is when there is a "v-structure". That is, given edges between three variables there is a v-structure and no influence flows between X_{i - 1} and X_{i + 1}. For example, no influence flows between the Difficulty of the course and the Intelligence of the student.

Random variables X and Y are said to be d-separated in the graph G, given there is no active trail between X and Y in G given Z. It is formally denoted by:

dsep_G (X,Y|Z)

The point of d-separation is that it maps perfectly to the conditional independence between the points. This gives to an interesting property that in a Bayesian network any variable is independent of its non-descendants given the parents of the node.

In the Student network example, the node/variable Letter is d-separated from Difficulty, Intelligence, and SAT given the grade.

From the d-separation, in graph G, we can collect all the independencies from the d-separations and these independencies are formally represented as:

If P satisfies I(G) then we say the G is an independency-map or I-Map of P.

The main point of I-Map is it can be formally proven that a factorization relationship to the independency holds. The converse can also be proved.

In simple terms, one can read in the Bayesian network graph G, all the independencies that hold in the distribution P regardless of any parameters!

Consider the student network—its whole distribution can be shown as:

P(D,I,G,S,L) = P(D)P(I|D)P(G¦D,I)P(S¦D,I,G)P(L¦D,I,G,S)

Now, consider the independence from I-Maps:

Thus, we have shown that I-Map helps in factorization given just the graph network!

The basics of the Variable elimination (VE) algorithm lie in the distributive property as shown:

(ab+ac+ad)= a (b+c+d)

In other words, five arithmetic operations of three multiplications and two additions can be reduced to four arithmetic operations of one multiplication and three additions by taking a common factor a out.

Let us understand the reduction of the computations by taking a simple example in the student network. If we have to compute a probability query such as the difficulty of the exam given the letter was good, that is, P(D¦L=good)=?.

Using Bayes theorem:

To compute P(D¦L=good)=? we can use the chain rule and joint probability:

If we rearrange the terms on the right-hand side:

If we now replace since the factor is independent of the variable I that S is conditioned on, we get:

Thus, if we proceed carefully, eliminating one variable at a time, we have effectively converted O(2ⁿ) factors to O(nk²) factors where n is the number of variables and k is the number of observed values for each.

Thus, the main idea of the VE algorithm is to impose an order on the variables such that the query variable comes last. A list of factors is maintained over the ordered list of variables and summation is performed. Generally, we use dynamic programming in the implementation of the VE algorithm (References [4]).

Junction tree or Clique Trees are more efficient forms of variable elimination-based techniques.

Belief propagation is one of the most practical inference techniques that has applicability across most probabilistic graph models including directed, undirected, chain-based, and temporal graphs. To understand the belief propagation algorithm, we need to first define factor graphs.

Factor graph

We know from basic probability theory that the entire joint distribution can be represented as a factor over a subset of variables as

In DAG or Bayesian networks f_s(X_s) is a conditional distribution. Thus, there is a great advantage in expressing the joint distribution over factors over the subset of variables.

Factor graph is a representation of the network where the variables and the factors involving the variables are both made into explicit nodes (References [11]). In a simplified student network from the previous section, the factor graph is shown in Figure 9.

Figure 9. Factor graph of simplified "Student" network

A factor graph is a bipartite graph, that is, it has two types of nodes, variables and factors.

The edges flow between two opposite types, that is, from variables to factors and vice versa.

Converting the Bayesian network to a factor graph is a straightforward procedure as shown previously where you start adding variable nodes and conditional probability distributions as factor nodes. The relationship between the Bayesian network and factor graphs is one-to-many, that is, the same Bayesian network can be represented in many factor graphs and is not unique.

Messaging in factor graph

There are two distinct messages that flow in these factor graphs that form the bulk of all computations through communication.

• Message from factor nodes to variable nodes: The message that is sent from a factor node to the variable node can be mathematically represented as follows:
  
  
  where Thus, is the message from factor node f_s to x and the product of all such messages from neighbors of x to x gives the combined probability to x:
  

  Figure 10. Message-passing from factor node to variable node

• Message from variable nodes to factor nodes: Similar to the previous example, messages from variable to factor can be shown to be
  
  

Thus, all the factors coming to the node x_m are multiplied except for the factor it is sending to.

Figure 11. Message-passing from variable node to factor node

The key idea is to generate i.i.d. samples iterating over the variables using a topological order. In case of some evidence, for example, P(X|E = e) that contradicts the sample generated, the easiest way is to reject the sample and proceed.

Maximum likelihood estimation (MLE) is a very generic method and it can be defined as: given a data set D, choose parameters that satisfy:

Maximum likelihood is the technique of choosing parameters of the Bayesian network given the training data. For a detailed discussion, see (References [6]).

Given the known Bayesian network structure of graph G and training data , we want to learn the parameters or CPDs—or CPTs to be precise. This can be formulated as:

Now each example or instance can be written in terms of variables. If there are i variables represented by x_i and the parents of each is given by parent_Xi then:

Interchanging the variables and instances:

The term is:

This is the conditional likelihood of a particular variable x _i given its parents parent_Xi. Thus, parameters for these conditional likelihoods are a subset of parameters given by . Thus:

Here, is called the local likelihood function. This becomes very important as the total likelihood decomposes into independent terms of local likelihood and is known as the global decomposition property of the likelihood function. The idea is that these local likelihood functions can be further decomposed for a tabular CPD by simply using the count of different outcomes from the training data.

Let N_ijk be the number of times we observe variable or node i in the state k_, given the parent node configuration j:

For example, we can have a simple entry corresponding to X_i = a and parent_Xi = b by estimating the likelihood function from the training data as:

Consider two cases, as an example. In the first, is satisfied by 10 instances with parent_Xi = b =100. In the second, is satisfied by 100 when parent_Xi = b =1000. Notice both probabilities come to the same value, whereas the second has 10 times more data and is the "more likely" estimate! Similarly, familiarity with domain or prior knowledge, or lack of it due to uncertainty, is not captured by MLE. Thus, when the number of samples are limited or when the domain experts are aware of the priors, then this method suffers from serious issues.

This technique overcomes the issue of MLE by encoding prior knowledge about the parameter ? with a probability distribution. Thus, we can encode our beliefs or prior knowledge about the parameter space as a probability distribution and then the joint distribution of variables and parameters are used in estimation.

Let us consider single variable parameter learning where we have instances x[1], x[2] … x[M] and they all have parameter ?_X.

Figure 13. Single variable parameter learning

Thus, the network is a joint probability model over parameters and data. The advantage is we can use it for the posterior distribution:

, P(?) = prior,

Thus, the difference between the maximum likelihood and Bayesian estimation is the use of the priors.

Generalizing it to a Bayesian network G given the dataset D:

If we assume global independence of parameters

Thus, we get

Again, as before, subset ?_Xi | parent_Xi of ? is local and thus the entire posterior can be computed in local terms!

Prior and posterior using the Dirichlet distribution

Often, in practice, a continuous probability distribution known as Dirichlet distribution—which is a Beta distribution—is used to represent priors over the parameters.

Probability Density Function:

Here, , The alpha terms are known as hyperparameters and a_ijri > 0. The is the pseudo count, also known as equivalent sample size and it gives us a measure of the prior.

The Beta function, B(a_ij) is normally expressed in terms of gamma function as follows

The advantage of using Dirichlet distribution is it is conjugate in nature, that is, irrespective of the likelihood, the posterior is also a Dirichlet if the prior is Dirichlet!

It can be shown that the posterior distribution for the parameters ?_ijk is a Dirichlet with updated hyperparameters and has a closed form solution!

a_ijk = a_ijk + N_ijk

If we use maximum a posteriori estimate and posterior means they can be shown to be:

The measures used to evaluate a Bayes network structure, given the dataset, can be broadly divided into the following categories and details of many are available here (References [14]).

The penalty function is logarithmic in M, so, as it increases, the penalty is less severe for complex structures.

The Akaike information score (AIC), similar to BIC, has similar penalty based scoring and is:

Bayesian scores discussed in parameter learning are also employed as scoring measures.

We will discuss a few algorithms that are used for learning structures in this section; details can be found here (References [15]).

Search and score-based techniques

The search and score method can be seen as a heuristic optimization method where iteratively, structure is changed through small perturbations, and measures such as BIC or MLE are used to give score to the structures to find the optimal score and structure. Hill climbing, depth-first search, genetic algorithms, and so on, have all been used to search and score.

Inputs and outputs

Input is dataset D with all the variables {X,Y..} known for every instance {1,2, ... m} and no missing values. The output is a Bayesian network graph G with all edges and directions known in E.

How does it work?

Figure 14. Search and Score

1. Initialize the Graph G, either based on domain knowledge or empty or full. Initialize the Edge set E based on the graph and initialize the CPT tables T based on the graph G, E, and the data D. Normally terminating conditions are also mentioned such as maxIterations:
2. maxScore= -8, score=computeScore(G,E, T)
3. Do
   1. maxScore=score
   2. For each variable pair (X, Y)
      1. For each
      2. New Graph G' based on parents and variables with edge changes.
      3. Compute new CPTs T' ? computeCPT(G',E',D).
      4. currentScore = computeScore(G',E',T')
      5. If currentScore > score:
         1. score = currentScore
         2. G' = G, E' = E
4. Repeat 3 while (

Advantages and limitations

• Getting stuck in a local optimum, which is the drawback of most of these heuristic search methods, is one of the biggest disadvantages.
• Convergence or theoretical guarantees are not available in heuristic search, so searching for termination is very much by guess work.