Bayesian Networks

Probability Basics

Before going into the details of Bayesian Network, let us revise the basics of probability. For event $A$ and $B$,

1. $0 \leq \Pr(A) \leq 1$,
2. $\Pr(A \cup B)=\Pr(A)+\Pr(B)-\Pr(A \cap B)$,
3. $\Pr(True)=\Pr(U)=1$ where $U$ is the universal set,
4. $\Pr(False)=\Pr(\phi)=0$ where $\phi$ is the empty set.

Definition 1 Independence: Events $A$ and $B$ are independent if $\Pr(A|B)=\Pr(A)$

Definition 2 Conditional Independence: Given event $B$, event $A$ is conditionally independent of event $C$ if $\Pr(A|B \cap C)=\Pr(A|B)$.

Additionally, we define the joint probability of events $A$ and $B$ as $\Pr(A,B)\equiv \Pr(A\cap B)$.

Theorem 3 Bayes’ Rule: The conditional probability of event $A$ given event $B$ is computed based on their joint and independent probability using the following formula.

By extension,

Theorem 4 Law of Total Probability states that if $B_1, B_2, B_3, \cdots $ serve as a partition of the sample space $S$, then for any event $A$, we have

Probability in Partially Observable Environments

Suppose there are two coins in a jar: $C_{50}$ and $C_{90}$. The subscripts for each of the coin represents the bias of the coin.

1. Coin $C_{50}$ where the probability of heads given that the coin is flipped is $\Pr(H| C_{50})=50\%$

2. Coin $C_{90}$ where the probability of heads given that the coin is flipped is $\Pr(H|C_{90})=90\%$

A man walks to the jar, picks a coin from the jar and tosses the coin repeatedly 6 times. The goal of the agent is to make an educated guess of which coin the man had picked. The agent is unable to identify whether the coin is $C_{50}$ or $C_{90}$ through its sensors; however, he/she is able to observe the results for each of the man’s toss.

Prior to the toss, with no further information, it is equally likely to the agent that either coin be picked. Thus, the unconditional probability of the man picking $C_{50}$ or $C_{90}$ are $50\%$. However, with the information observed from the man’s repeated tosss of the coin, a more accurate judgment can be made. Let consider that the agent observed the following results of all 6 coin tosses $\langle HTTHTH \rangle$. The agent can use Bayes’ rule to update the probability estimates of the coin being $C_{50}$ or $C_{90}$ conditioned on this new information. At this point, the agent needs to models its beliefs.

To calculate $\Pr(C_{50}|\text{Toss})$ and $\Pr(C_{90}|\text{Toss})$, we can use Bayes’s rule and law of total probability. By applying these two rules, we get $\Pr(C_{50}| \text{Toss}) > \Pr(C_{90}|\text{Toss}).$

The method of updating the agent’s beliefs on the probability of outcomes is summaries by Figure 1, where initially there are two contending models: $M_1:$ Coin $C_{50}$ is chosen and $M_2:$ Coin $C_{90}$ is chosen. Through some partial observations of the coin toss, the agent is able to use conditional probabilities to determine which model to chose.

Figure 1: Model classification with conditional probabilities

In fact, this can be generalized to a case of $n$ coins. However, as $n$ grows large, it can be increasingly cumbersome to compute the conditional probabilities. For example, let’s consider the case of having 100 coin $C_1,C_2,C_3, \cdots , C_{100}$ where the subscripts indicate the percentage point probabilities of each coin landing a heads when tossed. Suppose you observe $k$ tosses, denoted $Toss$. Then the following probabilities have to be computed.

where each $\Pr(Toss)$ is computed as,

Computing $\Pr(Toss)$ is cumbersome and also unnecessary for the agent to find which coin is most likely to be picked. Since the denominator in conditional probability of $\Pr(C_i|Toss)$ have the same $\Pr(Toss)$ for all the coins $C_i$, we only need to compute the numerator for comparison. In other-words,$\forall i,j$

Thus, we only need to find the coin with the highest $\Pr(C_i)\Pr(Toss|C_i)$ values for that coin to be most likely to be picked.

Now, the important question is how to store this conditional probabilities and use them in an efficient manner to chose a model.

Consider a situation where a researcher is interested in predicting how likely a graduate student performs well in a job interview. Some factors to consider could be the graduate’s grades or even whether the graduate has to pay a road toll (ERP) on the way to the interview.

Events that have to be tracked are as follows.

1. Grades ($G$), where $G$ means that the graduate’s grades are high, and $\bar{G}$ means the graduate’s grades are low.

2. Having to pay Electronic Road Pricing ($E$) where $E$ means that a graduate has been charged for ERP, and $\bar{E}$ means the graduate was not charged.

3. Job Interview ($I$), where $I$ means that the graduate’s interview goes well, and $\bar{I}$ means the graduate’s interview goes awry.

Let’s assume that the researcher had collected data from a sample of 600 students, and the joint frequency for every combination of $G$, $E$ and $I$ had been tallied. A naive way to store the values will be a simple table as shown below.

Table 1: The tabulated joint probabilities for combination of events.

From the above table, we can compute both conditional and unconditional probabilities. For example, the probability of $\Pr(G)$ is the sum of all the joint probabilities in the table where the value of $G$ is true (T).

Similarly, the conditional probability of $G$ given $E$ can be computed as the sum of the joint probabilities of where both $G$ and $E$ in the row are true divided by the sum of joint probabilities where $E$ is true.

Space and Computational Complexity

One major drawback in the tabular form is that the tables can be huge when there are more variables. This means that the method of storing the joint probabilities in a tabular form is not scalable to larger problems. If there are 5 variables, then there will need to be $2^5=32$ entries. However, to be precise, as the sum of probabilities is 1, we can exclude the last entry (and compute it by subtracting all the other probabilities from 1).

In particular, if there are $n$ variables with two values (true or false), then the space and computational complexity is $\mathcal{O}(2^n)$.

Representing Information as Directed Acyclic Graph: Bayesian network

Suppose there are 5 variables:

1. Grades(G)
2. ER\Pr(E)
3. Interview (I)
4. Job Offer (J)
5. Driver’s Mood(D)

We can represent the causal information of these variables in the form of a Directed Acyclic Graph (DAG). For example, we know that Grades and having to pay ERP are causal factors of Interview performance. Interview performance in turn directly affects the Job offer. However, we know that having to pay ERP can causally affects the Driver’s mood, but the Driver’s mood cannot causally affect any other variable. With that we form the graph as shown in Figure 2.

Figure 2: Bayesian Network

In Figure 2, each variable is represented by a node. The causal relation is represented by a directed edge from one variable to another. The network captures how well the interview goes based on grades and ERP.

Next, we want to store the conditional probabilities associated with each node in the form of a table. Given parents, the probability of a node is independent of its non-descendants, i.e. each node in a Bayesian network is independent of all non-descendants node, given its parents. As in Figure 2, $\Pr(I|G,E,D) = \Pr(I|G,E)$.

Figure 3 represents a Bayesian Network or an Inference Network. Each table of Figure 3 is called a conditional probability table (CPT). For tables associated with nodes such as Grades, ERP with no causal factor, the conditional probability of those nodes is the same as their unconditional probability.

Figure 3: Conditional Probability Table

How did we come up CPT from Table 1?

We processed Table 1 in row by row manner to fill up CPTs.

Space Complexity of Bayesian Network

As discussed earlier, tabular representation requires 32 entries for 5 variables. With Bayesian network representation, it requires 10 rows. Assuming that in the DAG, the maximum number of parents is a positive integer $q$, the number of entries required in the worst case is $n2^q$ in a Bayesian network. This makes the space complexity $\mathcal{O}(n2^q)$, which is an improvement from $2^n$.

Computing Probabilities in a Bayesian Network

Now that we have the network, we can compute the joint probabilities of multiple variables efficiently. We can use the chain rule formula to break the computation into a multiplication of a series of conditional probabilities.

The joint probability of events $X_1,X_2,\cdots ,X_n$ is the following,

In our example, one way to compute the joint probability of $G,I,J,E,D$ is,

However, we encounter a problem with this particular order in the chain rule. None of the conditional probabilities in the expression above are readily extractable from the Bayesian Network. Instead, we can reorder the variables and apply the chain rule in a specific order that allows us to extract the conditional probabilities from the Bayesian network. One way to find such an order is to first pick a variable that has no children, remove the node and repeat. Since Bayesian network is a DAG, there must exists at least one node with no children. One such ordering for the example in Figure 2 is $J,I,G,D,E$.

Deciding the Optimal Model

Suppose we are given two different models of Bayesian network and an evidence. Now the question is which of the Bayesian network would we choose? For example, instead of believing that Driver’s mood depends on ERP, we may believe that Driver’s mood depends on Student’s grades. Now, as shown in Figure 4, we have 2 Bayesian networks. Also, we have 2 evidences:

1. $e_1 :G = T, E = T, D = F, I = T, J = F$

2. $e_2 : G = T, E = F, D = T, I = T, J = F$

Bayesian Network M1	Bayesian Network M2

Figure 4: Two Bayesian Networks.

We want to decide which of the two models is a more likely description of evidences $e_1$ and $e_2$. Thus we need to determine if

We know that

Since we are interested in computing the ratio of \({\Pr(M_1|\{e_1,e_2\})}\) and \({ \Pr(M_1|\{e_1,e_2\})}\), we don’t need to compute \({\Pr(\{e_1,e_2\})}\) as it is cancelled out in the ratio. We also assume that the data collected are independent of each other. Thus, \(\Pr(\{e_1,e_2\}|M_1)=\Pr(e_1|M_1)\Pr(e_2|M_1)\) and \(\Pr(\{e_1,e_2\}|M_2)=\Pr(e_1|M_2)\Pr(e_2|M_2)\). Finally, we require to compute $\Pr(M_1)$ and $\Pr(M_2)$, as discuessed next.

$\Pr(M_1)$ and $\Pr(M_2)$ reflect the probabilities of each of the models occurring in real life. In fact, it is often difficult to obtain these probabilities. There are several possible ways to compute these probabilities.

1. We may choose to start with prior distributions for $\Pr(M_1)$ and $\Pr(M_2)$ based on our own past experiences.

2. We may also compute the values of $\Pr(M_1)$ and $\Pr(M_2)$ on historical information from the usage of either of these models.

However, it is only necessary for us to compute the ratio $\Pr(M_1)/\Pr(M_2)$, since we compare the magnitude of \(\Pr(M_1|\{e_1,e_2\})\) with \(\Pr(M_2|\{e_1,e_2\})\).

How to come up with models $M_1$ and $M_2$

We can use any of the local search algorithms to find a good model to work with. In local search, we start with an arbitrary state and make a transition to another state depending on the value assigned to that state. For example, we can start with model $M_1$, where $M_2$ is its neighboring model. We make a transition from $M_1$ to $M_2$, if given an evidence $e_1$, $\Pr(M_1|{e_1}) < \Pr(M_2|{e_1})$.

Thus, the algorithm for obtaining an optimal model based on evidences is in the following:

1. Initialize a random model.

2. At every step, look for a neighbor $N(M)$ of the current model.

3. Compute $\tfrac{\Pr(\text{evidence}|N(M))}{\Pr(\text{evidence}|M)}$, where $N(M)$ is a neighbor of model $M$.

4. Make a transition to a new model only if ratio is greater than $1$, else terminate with model $M$.