Naive Bayes Assumption

In naive Bayes, one assumes that

$$P({\text{Cause, Effect}}_1,\dots ,{\text{Effect}}_n)=P(\text{Cause})\prod _{i}P({\text{Effect}}_i|\text{Cause})$$

(conditional independence is an example of naive Bayes)

Total number of parameters is linear in the number of conditionally independent effects $n$. We call this ‘naive’ because it is oversimplifying as in many cases the ‘effect’ variables aren’t actually conditionally independent given the cause variable.

Link to original

Bayesian Network

A Bayesian network is a simple, graphical notation for conditional independence assertions => compact specification of full joint distributions.

• Each node corresponds to a random variable (discrete or continuous).
• Directed edge from node $u$ to node $v$ means $u$ is parent of $v$. Likewise, $v$ is the child.
• Graph is a Directed Acyclic Graph (no directed cycles).
• Each node $u$ has a conditional probability $P(u|\text{Parents}(u))$ that quantifies the effect of the parent nodes.

Link to original

Example

Weather is independent of other variables. Toothache and Catch are conditionally independent given Cavity.

graph LR;
	weather;
	cavity-->toothache;
	cavity-->catch;

Global Semantics

Full Joint Distribution (Bayesian Network)

We can calculate the full joint distribution as the product of the local conditional distributions:

$$P(x_1,\dots ,x_n)=\prod _{i=1}^{n}P(x_i|\text{parents}(X_i))$$Link to original

Example: Compute $P(j\wedge m\wedge a\wedge \neg b\wedge \neg e)$

$$\begin{array}{rl}P(j\wedge m\wedge a\wedge \neg b\wedge \neg e)& =P(j|a)P(m|a)P(a|\neg b,\neg e)P(\neg b)P(\neg e)\\ & =0.9\cdot 0.7\cdot 0.001\cdot 0.999\cdot 0.998\\ & \approx 0.00063\end{array}$$

Compactness

Compactness of Bayes Network

A conditional probability table for Boolean $X_i$ with $k$ Boolean parents has $2^k$ rows for the combinations of parent values. Each row requires just one number for $p$ for $X_i=\text{true}$ (as we can find the false equivalent by taking $1-p$).

If each variable has no more than $k$ parents, the complete network requires $O(n\cdot 2^k)$ numbers. This grows linearly with $n$ compared to $O(2^n)$ for the full joint distribution.

Link to original

Local semantics

Local semantics of conditional independence

A node $X$ is conditionally independent of its non-descendants (e.g. $Z_{i,j}$) given its parents ($U_i$).

Link to original

Markov Blanket

Each node is conditionally independent of all others given its Markov blanket $B(x)$: parents + children + children’s parents

Formally if $V$ is the set of all variables, let $R=V\{B(X)\cup X\}$ be the remaining nodes then $X\perp R|B(X)$ .

$$X\perp \perp R|B(X)$$Link to original

Example

Given the following relationships:

The Markov blanket of $X$ is $B,C,E,F,G$.

Inference tasks

Simple queries: compute posterior marginal Conjunctive queries: $P(X_i,X_j|E=e)=P(x_i|E=e)P(X_j|X_i,E=e)$ Optimal decisions: decision networks include utility information; probabilistic inference required for $P(\text{outcome}|\text{action},\text{evidence})$. Value of information: “which evidence to seek next?” Sensitivity analysis: “which probability values are most critical?” Explanation: “why do I need a new starter motor?”

Simple Queries

We look at a few ways of computing the posterior marginal:

1. Enumeration
2. Rejection sampling (using prior sampling)
3. Likelihood weighting
4. Gibbs sampling

Inference by enumeration

Inference by enumeration

Use the structure of the network to tell us which sets of joint probabilities to use. Gives us a slightly intelligent way to sum out variables from the joint without actually constructing the explicit representation.

Link to original

Simple query on burglary network

graph LR;
	b-->a;
	e-->a;
	a-->j;
	a-->m;

$$\begin{array}{rl}P(B|j,m)& =\frac{P(B,j,m)}{P(j,m)}\\ & =\alpha P(B,j,m)\\ & =\alpha \sum _e\sum _{a}P(B,e,a,j,m)\\ & \\ & \text{rewrite full joint entries taking network into account}:\\ & =\alpha \sum _e\sum _{a}P(B)P(e)P(a|B,e)P(j,a)P(m|a)\\ & =\alpha P(B)\sum _{e}P(e)\sum _{a}P(a|B,e)P(j|a)P(m|a)\end{array}$$

We evaluate the expression by going through the variables in order, multiplying CPT entries along the way. At each point, we need to loop through the possible values of the variable.

Enumeration Algorithm

Improving exact approach

• Variable elimination evaluates the enumeration tree bottom up, remembering intermediate values.
• Clustering algorithms can be more efficient for multiple queries: group variables together.

Complexity of exact inference

For singly connected networks:

• Any two nodes are connected by at most one undirected path.
• Time and space cost of variable elimination is $O(d^{k}n)$ for $k$ parents, $d$ values.

For multiply connected networks:

• Exponential time and space complexity (even when no. of parents of node are bounded)
• Inference is NP-hard

Prior sampling

Prior Sampling

We use a stochastic simulation, taking $n$ random samples from the network.

We repeat this process many times, and in the case that we try to find $P(c,\neg s,r,w)$, we find the proportion of results that is equal to $[true,false,true,true]$, i.e. $[\text{Cloudy}=true,\text{Sprinkler}=false,\text{Rain}=true,\text{WetGrass}=true]$.

The more runs we do, the more accurate the probability.

Link to original

Prior Sampling Algorithm

Rejection sampling

Rejection Sampling

In cases where we want to estimate $P(X|e)$, we cannot use prior sampling, but we can use rejection sampling. We generate samples as in prior sampling and only keep samples where $e$ holds to build the estimate, otherwise we ignore the sample.

Link to original

Inefficiency with rejection sampling

For unlikely events, we may have to wait a long time to get enough matching samples. Say we want to estimate $P(C|A)$:

Rejection sampling would reject $80\%$ of samples. In this case, we want to use likelihood weighting instead.

Rejection Sampling Algorithm

Likelihood weighting

Likelihood Weighting

Likelihood weighting is a version of “importance sampling” where we fix the evidence variable to $true$ (we only sample relevant events). We have to weight them with the likelihood that they fit the evidence and use the probabilities we know to do so.

Link to original

Example of likelihood weighting

Consider we have the network:

We want to establish $P(Rain|Cloudy=true,WetGrass=true)$. We pick a variable ordering, e.g. Cloudy, Sprinkler, Rain, WetGrass. Set the weight $w=1$ and deal with each variable in order:

1. Cloudy is an evidence variable with the value true so: $\begin{array}{rl}w& \leftarrow w\cdot P(Cloudy=true)\\ w& \leftarrow 0.5\end{array}$
2. Sprinkler is not an evidence variable, so we sample a value like we did with prior sampling. $P(Sprinkler,Cloudy=true)=\left(\begin{array}{c}0.1\\ 0.9\end{array}\right)$ Let’s assume this returns false, $w$ remains the same.
3. Rain is not an evidence variable, so we sample a value like we did with prior sampling. $P(Rain|Cloudy=true)=\left(\begin{array}{c}0.8\\ 0.2\end{array}\right)$ Let’s assume this returns true, $w$ remains the same.
4. WetGrass is an evidence variable with the value true so: $\begin{array}{rl}w& \leftarrow w\cdot P(WetGrass=true|Sprinkler=false,Rain=true)\\ w& \leftarrow 0.45\end{array}$

Hence we are left with Cloudy, Rain, WetGrass being true and Sprinkler being false. So we have the event $[true,false,true,true]$ with the weight $0.45$.

To find a probability we tally up all relevant events weighted with their weights. We would tally the event we found just now under $Rain=true$.

Likelihood Algorithm

Gibbs sampling

Gibbs Sampling

Gibbs Sampling is a different approach to sampling where we generate samples by making a random change to the previous sample.

• Select an arbitrary state in the Bayesian network. Pick state with evidence variables fixed at observed values. e.g. if we know Cloudy is true, we pick that.
• Generate next state by randomly sampling from a non-evidence value.
• Do sampling conditional on current values of Markov blanket.

Link to original

Example of Gibbs sampling

Consider the query $P(Cloudy|Sprinkler=true,WetGrass=true)$:

• Evidence variables are fixed to their observed values.
• Non-evidence variables are initialised randomly: Cloudy = true, Rain = false

Initial state is $[Cloudy=true,Sprinkler=true,Rain=false,WetGrass=true]$.

First we sample Cloudy given the current state of its Markov blanket. Markov blanket is Sprinkler and Rain. So we sample from $P(Cloudy|Sprinkler=true,Rain=false)$. Suppose we get $Cloudy=false$, the new state is:

$[Cloudy=false,Sprinkler=true,Rain=false,WetGrass=true]$

Next we sample Rain, and repeat for both variables. Each state visited contributes to our estimate for $P(Cloudy|Sprinkler=true,WetGrass=true)$

Say we visit 80 states, and in 20 of those Cloudy is true and the rest false. Therefore:

$$P(Cloudy|Sprinkler=true,WetGrass=true)=\alpha \left(\begin{array}{c}20\\ 60\end{array}\right)=\left(\begin{array}{c}0.25\\ 0.75\end{array}\right)$$

Sampling variables given state of Markov blanket

For a value $x$ of a variable $X$:

$$P(X|mb(X))=\alpha P(X|parents(X))\prod _{Y\in children(X)}P(Y|parents(Y))$$

where $mb(X)$ is the Markov blanket of $X$.