Bayesian Networks

Introduction

A Bayesian network is a directed graph in which each node is annotated with quantitative probability information. The full specification is as follows:

Each node corresponds to a random variable, which may be discrete or continuous.
A set of directed links or arrows connects pairs of nodes. If there is an arrow from node $X$ to node $Y$ , $X$ is said to be a parent of $Y$ . The graph has no directed cycles (and hence is a directed acyclic graph, or DAG.
Each node $X_{i}$ has a conditional probability distribution $P (X_{i} | P a r e n t s (X_{i}))$ that quantifies the effect of the parents on the node.

Semantics of a bayesian network:

The network is a representation of a joint probability distribution
Encoding of a collection of conditional independence statements

Full joint distribution

Given by:

\begin{array}{r} (1) & P (x_{1}, \dots, x_{n}) = \prod_{i = 1}^{N} P (x_{i} | P a r e n t s (X_{i})) \end{array}

Which can be rewritten as:

\begin{aligned} P (x_{1}, \dots, x_{n}) & = P (x_{n} | x_{n - 1}, \dots x_{1}) P (x_{n - 1}, \dots, x_{1}) \\ = P (x_{n} | x_{n - 1}, \dots x_{1}) P (x_{n - 1} | x_{n - 2}, \dots, x_{1}) \dots P (x_{2} | x_{1}) P (x_{1}) \\ = \prod_{i = 1}^{N} P (x_{i} | x_{i - 1}, \dots x_{1}) (identity known as chain rule) \end{aligned}

The above is equivalent to

P (X_{i} | X_{i - 1}, \dots X_{1}) = P (X_{i} | P a r e n t s (X_{i}))

Provided that $P a r e n t s (X_{i}) \subseteq X_{i - 1}, \dots, X_{1}$

Conditional independence relations in bayesian networks

Steps to determine if two variables are conditionally independent

Draw the ancestral graph Construct the “ancestral graph” of all variables mentioned in the probability expression. This is a reduced version of the original net, consisting only of the variables mentioned and all of their ancestors (parents, parents’ parents, etc.)
Moralize the ancestral graph by marrying the parents For each pair of variables with a common child, draw an undirected edge (line) between them. (If a variable has more than two parents, draw lines between every pair of parents.)
Disorient the graph by replacing the directed edges (arrows) with undirected edges (lines).
Delete the givens and their edges. If the independence question had any given variables, erase those variables from the graph and erase all of their connections, too.
Given a query between two variables A, B
If the variables are disconnected then they’re independent
If the variables are connected then they’re dependent
If the variables are missing because they were a given, they’re independent

In the following example we skip step 1 and moralize the entire bayesian network

Some conditional independence queries ( $⊥ ⊥$ meaning conditionally independent of), delete the givens and their edges to check the connection between the query variables:

Is $A ⊥ ⊥ B | C$ ? No, there is a path A-B
Is $A ⊥ ⊥ E | C$ ? No, there is a path A-B-D-E
Is $A ⊥ ⊥ E | C, D$ ? Yes, there isn’t a path between A and E
Is $A ⊥ ⊥ D | C$ ? No, there is a path A-B-D
Is $B ⊥ ⊥ E | C$ ? No, there is a path B-D-E
Is $A ⊥ ⊥ F | C$ ? No, there is a path A-B-D-E-F
Is $A ⊥ ⊥ F | C, D$ ? Yes, there isn’t a path between A and F

Exact inference

Compute the posterior probability distribution for a set of query values given some observed event (set of evidence variables)

By enumeration

Any conditional probability can be computed by summing terms from the full joint distribution

P (X | e) = α P (X, e) = α \sum_{y} P (X, e, y)

Working with the example below we can answer some queries:

\begin{aligned} P (c | a) & = α \sum_{b} P (a) P (b) P (c | a, b) \\ = α P (a) \sum_{b} P (b) P (c | a, b) \\ = α P (a) \sum_{b} \begin{array}{c} \begin{matrix} b & \neg b \end{matrix} \\ \begin{matrix}  \end{matrix} & [\begin{matrix} 0.4 & 0.6 \end{matrix}] \end{array} \begin{array}{c} \begin{matrix} b & \neg b \end{matrix} \\ \begin{matrix} c \\ \neg c \end{matrix} & [\begin{matrix} 0.55 & 0.5 \\ 0.45 & 0.5 \end{matrix}] \end{array} \\ = α P (a) \sum_{b} \begin{array}{c} \begin{matrix} b & \neg b \end{matrix} \\ \begin{matrix} c \\ \neg c \end{matrix} & [\begin{matrix} 0.22 & 0.3 \\ 0.18 & 0.3 \end{matrix}] \end{array} \\ = α 0.2 \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} c \\ \neg c \end{matrix} & [\begin{matrix} 0.52 \\ 0.48 \end{matrix}] \end{array} \\ = \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} c \\ \neg c \end{matrix} & [\begin{matrix} 0.104 \\ 0.096 \end{matrix}] \end{array} \\ = α [.104, .096] \\ = [0.52, 0.48] \end{aligned}

\begin{aligned} P (e | \neg c, b) & = α \sum_{a, d, f} P (a) P (b) P (\neg c | a, b) P (d | b) P (e | \neg c, d) P (f | e) \\ = α P (b) \sum_{a} P (a) P (\neg c | a, b) \sum_{d} P (d | b) P (e | \neg c, d) \sum_{f} P (f | e) \\ = α P (b) \sum_{a} P (a) P (\neg c | a, b) \sum_{d} P (d | b) P (e | \neg c, d) \sum_{f} \begin{array}{c} \begin{matrix} f & \neg f \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.7 & 0.3 \\ 0.2 & 0.8 \end{matrix}] \end{array} \\ = α P (b) \sum_{a} P (a) P (\neg c | a, b) \sum_{d} P (d | b) P (e | \neg c, d) \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 1 \\ 1 \end{matrix}] \end{array} \\ = α P (b) \sum_{a} P (a) P (\neg c | a, b) \sum_{d} \begin{array}{c} \begin{matrix} d & \neg d \end{matrix} \\ \begin{matrix}  \end{matrix} & [\begin{matrix} 0.6 & 0.4 \end{matrix}] \end{array} \begin{array}{c} \begin{matrix} d & \neg d \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.45 & 0.2 \\ 0.55 & 0.8 \end{matrix}] \end{array} \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 1 \\ 1 \end{matrix}] \end{array} \\ = α P (b) \sum_{a} P (a) P (\neg c | a, b) \sum_{d} \begin{array}{c} \begin{matrix} d & \neg d \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.27 & 0.08 \\ 0.33 & 0.32 \end{matrix}] \end{array} \\ = α P (b) \sum_{a} P (a) P (\neg c | a, b) \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.35 \\ 0.65 \end{matrix}] \end{array} \\ = α P (b) \sum_{a} \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} a \\ \neg a \end{matrix} & [\begin{matrix} 0.2 \\ 0.8 \end{matrix}] \end{array} \begin{array}{c} \begin{matrix} \neg c, b \end{matrix} \\ \begin{matrix} a \\ \neg a \end{matrix} & [\begin{matrix} 0.45 \\ 0.55 \end{matrix}] \end{array} \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.35 \\ 0.65 \end{matrix}] \end{array} \\ = α P (b) \sum_{a} \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} a \\ \neg a \end{matrix} & [\begin{matrix} 0.09 \\ 0.44 \end{matrix}] \end{array} \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.35 \\ 0.65 \end{matrix}] \end{array} the element wise product is with unrelated bases so we do with a^{T} \\ = α P (b) \sum_{a} \begin{array}{c} \begin{matrix} a & \neg a \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.0315 & 0.154 \\ 0.0585 & 0.2275 \end{matrix}] \end{array} \\ = \begin{array}{c} \begin{matrix}  \end{matrix} \\ \begin{matrix} e \\ \neg e \end{matrix} & [\begin{matrix} 0.1855 \\ 0.286 \end{matrix}] \end{array} P (b) is not a factor, it's an evidence \\ = α [0.1855, 0.286] \\ = [0.393425239, 0.606574761] \end{aligned}