Inference in Bayesian networks¶

Inference¶

from observed events assumes on probability of other events,
observations ( $E$ – a set of evidence variables, $e$ – a particular event),
target variables ( $Q$ – a set of query variables, $q$ – a particular query variable),
$Pr(q|e)$ to be found,
network is known (both graph and CPTs)
marginalization $Pr(X) = \sum_{y} Pr(X, y)$

alt text

Inference by enumeration¶

\begin{aligned} P r (\neg p_{3}) & = \sum_{P_{1}, P_{2}, P_{4}} P r (P_{1}, P_{2}, \neg p_{3}, P_{4}) = \sum_{P_{1}, P_{2}, P_{4}} P r (P_{1}) P r (P_{2} | P_{1}) P r (\neg p_{3} | P_{2}) P r (P_{4} | P_{2}) \\ P r (p_{2} | \neg p_{3}) & = \frac{P r (p_{2}, \neg p_{3})}{P r (\neg p_{3})} \\ P r (p_{1}, \neg p_{3}, p_{4}) & = \sum_{P_{2}} P r (p_{1}, P_{2}, \neg p_{3}, p_{4}) = \sum_{P_{2}} P r (p_{1}) P r (P_{2} | p_{1}) P r (\neg p_{3} | P_{2}) P r (p_{4} | P_{2}) \end{aligned}

$\begin{align} Pr(¬p_3) &= \sum_{P_1,P_2, P_4} Pr(P_1 , P_2 , ¬p_3 , P_4 ) = \sum_{P_1,P_2, P_4} Pr(P_1)Pr(P_2|P_1)Pr(¬p_3|P_2)Pr(P_4|P_2) \\ Pr(p_2| ¬p_3) &=\frac{Pr(p_2, ¬p_3)}{Pr(¬p_3)} \\ Pr(p_1, ¬p_3, p_4) &= \sum_{P_2} Pr(p_1, P_2, ¬p_3, p_4) = \sum_{P_2} Pr(p_1)Pr(P_2|p_1)Pr(¬p_3|P_2)Pr(p_4|P_2) \end{align}$

Variable elimination¶

pre-computes factors to remove the inefficiency
- factors serve for recycling the earlier computed intermediate results
- some variables are eliminated by summing them out
does not consider variables irrelevant to the query
- all the leaves that are neither query nor evidence variable
- the rule can be applied recursively.

Excercise¶

calculate $Pr(¬p_3)$ and $Pr(p_2|¬p_3)$

(ii)¶

\begin{aligned} f_{P_{1}} (P_{2}) & = \sum_{P_{1}} P r (P_{1}, P_{2}) & = \sum_{P_{1}} P r (P_{1}) P r (P_{2} | P_{1}) \\ f_{P_{1}} (p_{2}) & = \sum_{P_{1}} P r (P_{1}, p_{2}) & = \sum_{P_{1}} P r (P_{1}) P r (p_{2} | P_{1}) & = .4 \times .8 + .6 \times .5 = .62 \\ f_{P_{1}} (\neg p_{2}) & = \sum_{P_{1}} P r (P_{1}, \neg p_{2}) & = \sum_{P_{1}} P r (P_{1}) P r (\neg p_{2} | P_{1}) & = .4 \times .2 + .6 \times .5 = .38 \end{aligned}

$\begin{align} f_{P_1} (P_2) &= \sum_{P_1} Pr(P_1 , P_2 ) &= \sum_{P_1} Pr(P_1)Pr(P_2 | P_1) & \\ f_{P_1} (p_2) &= \sum_{P_1} Pr(P_1 , p_2 ) &= \sum_{P_1} Pr(P_1)Pr(p_2 | P_1) &= .4 × .8 + .6 × .5 = .62 \\ f_{P_1} (¬p_2) &= \sum_{P_1} Pr(P_1 , ¬p_2 ) &= \sum_{P_1} Pr(P_1)Pr(¬p_2 | P_1) &= .4 × .2 + .6 × .5 = .38 \end{align}$

(iii)¶

\begin{aligned} f_{P_{1}, P_{2}} (P_{3}) & = \sum_{P_{2}} f_{P_{1}} (P_{2}) P r (P_{3} | P_{2}) \\ f_{P_{1}, P_{2}} (p_{3}) & = \sum_{P_{2}} f_{P_{1}} (P_{2}) P r (p_{3} | P_{2}) = .62 \times .2 + .38 \times .3 = .238 \\ f_{P_{1}, P_{2}} (\neg p_{3}) & = \sum_{P_{2}} f_{P_{1}} (P_{2}) P r (\neg p_{3} | P_{2}) = .62 \times .8 + .38 \times .7 = .762 \end{aligned}

$\begin{align} f_{P_1, P_2} (P_3) &= \sum_{P_2} f_{P_1} (P_2) Pr(P_3 | P_2 )\\ f_{P_1, P_2} (p_3) &= \sum_{P_2} f_{P_1} (P_2) Pr(p_3 | P_2 ) = .62 × .2 + .38 × .3 = .238\\ f_{P_1, P_2} (¬p_3) &= \sum_{P_2} f_{P_1} (P_2) Pr(¬p_3 | P_2 ) = .62 × .8 + .38 × .7 = .762 \end{align}$

(iv)¶

\begin{aligned} f_{P_{1}, \neg p_{3}} (P_{2}) & = f_{P_{1}} (P_{2}) P r (\neg p_{3} | P_{2}) \\ f_{P_{1}, \neg p_{3}} (p_{2}) & = .62 \times .8 = .496 \\ f_{P_{1}, \neg p_{3}} (\neg p_{2}) & = .38 \times .7 = .266 \end{aligned}

$\begin{align} f_{P_1 ,¬p_3} (P_2) &= f_{P_1}(P_2)Pr(¬p_3|P_2)\\ f_{P_1 ,¬p_3} (p_2) &= .62 × .8 = .496\\ f_{P_1 ,¬p_3} (¬p_2) &= .38 × .7 = .266 \end{align}$

solution¶

\begin{aligned} P r (\neg p_{3}) & = f_{P_{1}, P_{2}} (\neg p 3) = .762 \\ P r (p_{2} | \neg p_{3}) & = \frac{f_{P_{1}, \neg p_{3}} (p_{2})}{f_{P_{1}, \neg p_{3}} (p_{2}) + f_{P_{1}, \neg p_{3}} (\neg p_{2})} = \frac{.496}{.496 + .266} = .6509 \end{aligned}

$\begin{align} Pr(¬p_3 ) &= f_{P_1, P_2} (¬p 3 ) = .762 \\ Pr(p_2 | ¬p_3 ) &= \frac{f_{P_1 ,¬p_3} (p_2) }{f_{P_1 ,¬p_3} (p_2) + f_{P_1 ,¬p_3} (¬p_2) } = \frac{.496}{.496 + .266} = .6509 \end{align}$

Forward sampling¶

topologically sort the network nodes
- for every edge it holds that parent comes before its children in the ordering,
instantiate variables along the topological ordering
- take $Pr(P_j|parents(P_j))$ , randomly sample $P_j$ ,
repeat step 2 for all the samples (the sample size M is given a priori)

samples that contradict evidence not used
forward sampling gets inefficient if $Pr(e)$ is small,

Randomly generated numbers for estimating $Pr(p_1 |p_2 , ¬p_3)$ ¶

Rejection sampling¶

rejects partially generated samples as soon as they violate the evidence event e
sample generation may stop early → slight improvement

	s1	s2	s3	s4	s5	s6	s7	s8
P1	T	F	F	T	T	F	F	F
P2	T	F	T	F	F	T	F	T
P3	F	?	T	?	?	F	?	F
P4	?	?	?	?	?	?	?	?

Likelihood weighting¶

avoids necessity to reject samples
the values of E fixed, the rest of variables sampled only
however, not all events are equally probable, samples must be weighted
the weight equals to the likelihood of the event given the evidence

	p1	p2	p3	p4	p5	p6
P1	T	F	F	F	F	F
P2	T	T	T	T	T	T
P3	F	F	F	F	F	F
P4	?	?	?	?	?	?
$w^i$	.64	.40	.40	.40	.40	.40

$w^i = Pr(p_2 |P_1^i)Pr(¬p_3|p_2)$

$Pr(p_1|p_2, ¬p_3) \approx \frac{\sum_i w^i \delta(p_1^i , p_1)}{\sum_i w^i} = 0.24$

Gibbs sampling¶

generate sequence of samples
$\forall p^m = \{P_1 = p_1^m , . . . , P_n = p_n^m \}, m \in \{1, . . . , M \}:$

fix states of all observed variables from E (in all samples)
the other variables initialized in $p^0$ randomly
generate from ()
- $p_1^m \leftarrow Pr(P_1 |p_1^{m−1}, . . . , p_{n−1}^{m−1})$
- $...$
- $p_n^m \leftarrow Pr(P_n |p_1, . . . , p_{n−1})$
repeat step 3 for $m \in {1, . . . , M }$

ignore samples at the beginning (burn-in period)
we don't have $Pr(P_i |P_1 , . . . , P_{i−1} , P_{i+1} , . . . , P_n )$
we can use instead
- Markov blanket (MB) is the neighborhood,
- MB covers the node, its parents, its children and their parents
- $MB(P_i)$ is the minimum set of nodes that d-separates $P_i$ from the rest of the network.