Bayesian Network Variable Elimination

Inference in graphical models involves computing conditional probability answers to queries:

• Compute the posterior probability distributions, given values $e$ for some evidence nodes $E$
• Belief updating or probabilistic inference $P(Q\mid E=e)$

Types of inference:

1. Exact inference: variable elimination
2. Approximate inference

Naive inference algorithm for computing conditional probability $P(Q\mid E=e)$ in a Bayesian network, involves the following 3 steps:

1. Step 1: Get joint probability distribution $P(\mathcal{X})$ over the set $\mathcal{X}$ of ALL variables by multiplying conditional probability (chain rule)
2. Step 2: Marginalization: to find $P(Q,E)$ and then $P(E)$$$P(Q,E)=\sum _{X\sim Q\cup E}P(X)$$$$P(E)=\sum _{Q}P(Q,E)$$$X-Q\cup E$ is the set of non-query, non-evidence variables.
3. Step 3: Renormalization: Calculate the conditional probability: based on the evidence $E=e$$$P(Q\mid E=e)=\frac{P(Q,E=e)}{P(E=e)}$$

---

To perform inference effectively:

1. Structure of the Bayesian network: DAG and CPDs
2. Conditional independence assertion
3. Factorization of the joint distribution

Conditional Probability Query

Posterior Probability Query

It means finding the probability of some variable(s) after knowing certain evidence.

• (a) Given the values of some variables (the evidence).
• (b) Compute the posterior probability of other variables — used for prediction, explanation, or reasoning.
• (c) Example:
  If John and Mary both called the police because of an alarm, what’s the probability that there was actually an earthquake?

$$P(E=y\mid J=y,M=y)$$

General form of query

$$P(Q\mid E=e)=\frac{P(Q,e)}{P(e)}$$

(a) Notations:

• $Q$ is a list of query variables, sometimes we use letter $Y$ as well.
• $E$ is a list (set) of evidence variables
• $e$ is the corresponding list observed values
• $W=X-Q-E$: random variables that are neither query nor evidence,
• $X$ are ALL the random variables of the joint distribution $P$.

(b) Computing probabilities

i. $P(y,e)$, an instantiation can be computed by summing out all entries in the joint (summing over $w$) excluding $Y$ and $E$ where $P(y,e,w)$ is an entry in the full joint distributions.

$$P(y,e)=\sum _{w}P(y,e,w)$$

ii. The probability of evidence $P(e)$ is computed directly by summing over all possible values of $Y$.

$$P(e)=\sum _{y}P(y,e)$$

(c) Deriving conditional probabilities

$$P(y\mid e)=\frac{P(y,e)}{P(e)}$$

if $Y$ has $k$ different values $\{y^1,y^2,...,y^k\}$, then we can compute the joint probability

$$P(y^1,e),P(y^2,e),...,P(y^k,e)$$

and renormalizing the entries to 1 by dividing the sum of them $\sum _{y}P(y,e)$ which is less than 1.

(d) Inference: the process of computing the answer to a query.

Types of exact inferences

(a) Predictive/Causal inference:

Determining the likelihood of an effect given a cause. From causes to effects
If burglary $B$ happens, will Mary report alarm $P(M\mid B=y)$?

(b) Diagnostic (evidential/abductive)

It seeks to identify the causes given an observed effect. From effect to causes:
Mary calls $M$, what’s wrong, what is the probability there was a burglary? $P(B\mid M=y)$.

(c) Inter-causal inference (explaining away)

Inter-causal inference deals with the relationship between different causes of a common effect. It can demonstrate how one cause can reduce the probability of another cause given the effect.
Between causes of a common effect

$$P(B\mid A=y)>P(B\mid A=y,E=y)$$

Earthquake $E=y$ explains away (reduces) Burglary $B=y$ when an alarm is triggered. Conversely,

$$P(B\mid A=y)<P(B\mid A=y,E=n)$$

(d) Mixed inference

• $P(A\mid J=y,E=y)$ simultaneous use of diagnostic and causal inference
• $P(B\mid J=y,E=n)$ simultaneous use of diagnostic and inter-causal inference

Naive Inference

• $P(Q\mid E=e)$

1. Step 1: Get the joint distribution: $P(X)$
2. Step 2: Marginalize: to compute the marginal probability of a given variable in our model after summing everything else out

$$P(Q,E)=\sum _{X-Q\cup E}P(X)$$$$P(E)=\sum _{Q}P(Q,E)$$

e.g.,

$$P(B,J,M)=\sum _{E,A}P(B,E,A,J,M)$$

3. Step 3: Condition inference (Baye’s Theorem):

$$P(Q\mid E=e)=\frac{P(Q,E=e)}{P(E=e)}$$

• The naive algorithm does not make use of the factorization, and has exponential complexity (bad!!).
• Eliminating a variable $X_1$ from the joint distribution $P(X_1,X_2,...,X_m)$ is to compute:

$$P(X_2,...,X_m)=\sum _{X_1}P(X_1,X_2,...,X_m)$$

But the complexity is exponential in $m$.
We need better ways to eliminate variables with much less computation using factorization. How to use the factorization to reduce the complexity.

Variable Elimination Simple Chain Example

We have a simple Bayesian network:

$$A\to B\to C\to D$$

and we want to compute

$$P(D)=\sum _{A,B,C}P(A)P(B|A)P(C|B)P(D|C)$$

Compute $P(D)$ efficiently by reducing repeated summations.

Naive Method

• 做法：先求出完整的联合分布 $P(A,B,C,D)$，再逐一消除变量。
• 复杂度计算：$2^3+2^2+2$   - $2^3$：消除 $A$ 时，需要处理关于 $(B,C,D)$ 的因子，大小为 $2\times 2\times 2=8$。   - $2^2$：消除 $B$ 时，需要处理关于 $(C,D)$ 的因子，大小为 $2\times 2=4$。   - $2$：消除 $C$ 时，需要处理关于 $(D)$ 的因子，大小为 $2$。
• 缺点：复杂度随变量增加呈 指数级增长 ($O(2^n)$)。

Variable Elimination

• 做法：利用因子分解，每次只对局部相关的变量求和。
• 复杂度计算：$2+2+2$   - $2$：计算 $\sum _{A}P(A)P(B|A)$，只涉及 2 个变量，生成关于 $B$ 的因子。   - $2$：计算 $\sum _{B}P(C|B)\tau (B)$，只涉及 2 个变量，生成关于 $C$ 的因子。   - $2$：计算 $\sum _{C}P(D|C)\tau (C)$，只涉及 2 个变量，生成关于 $D$ 的因子。
• 优点：复杂度随变量增加呈 线性增长 ($O(n\times 2)$)。

---

Theorem

Suppose $\mathcal{F}$ is a factorization of a joint distribution $P(X_1,X_2,...,X_n)$, then the result of eliminating $(\mathcal{F},X_1)$ is a factorization of the marginal probability distribution $P(X_2,X_3,...,X_n)$.

假设你有一个由很多小因子（函数）相乘构成的系统。当你对其中一个变量 $X_1$ 求和（即“消除”它）时，那些不包含 $X_1$ 的因子就像常数一样，可以从求和符号中提取出来。 最终剩下的部分是一个新的函数 $h$，它和原来剩下的因子一起，构成了剩余变量的联合分布。

Proof:
Suppose $P(X_1,X_2,...,X_n)=f_1\times f_2\times \cdots \times f_n$ and $X_1$ appears in and only in factors $f_1,f_2,...,f_k$, then
the factors where $X_1$ does not appear are $f_{k+1},f_{k+2},...,f_n$.

$$P(X_2,X_3,...,X_n)=\sum _{X_1}P(X_1,X_2,...,X_n)$$$$=\sum _{X_1}\prod _{i=1}^n{f}_i$$$$=\sum _{X_1}\prod _{i=1}^k{f}_i\prod _{i=k+1}^n{f}_i$$$$=\left(\sum _{X_1}\prod _{i=1}^k{f}_i\right)\prod _{i=k+1}^n{f}_i$$$$=h\prod _{i=k+1}^n{f}_i$$

Factor Marginalization

Definition of factor marginalization: Let $X$ be a set of variables and $Y\not\subset X$. Let $\varphi (X,Y)$ be a factor, we define the factor marginalization of $Y$ in $\varphi$ (denoted as $\sum _Y\varphi$), to be a factor $\psi$ over $X$ as:

$$\psi (X)=\sum _Y\varphi (X,Y)$$

We sum up entries in the table where the values of $X$ match up. The process of marginalizing a joint distribution $P(X,Y)$ onto $X$ in a Bayesian network is summing out $Y$ in the factor corresponding to $P$.

Procedure of Variable Elimination $(\mathcal{F},X)$:

• Input: $\mathcal{F}$: a list of functions; $X$: a variable to be eliminated.
• Output: another list of factor functions ${\mathcal{F}}^{\prime }$:

1. Remove from the $\mathcal{F}$ all the functions, say $f_1,f_2,...,f_k$, that involve $X$.
2. Compute new function $g=\prod _{i=1}^k{f}_i$, e.g., $P(A)P(B\mid A)$ and $k=2$.
3. Compute new function $h=\sum _{X}g$, e.g., ${\psi }_1(B)$, which is a marginal probability distribution.
4. Add new function $h$ to $\mathcal{F}$ to replace $f_1,f_2,...,f_k$.
5. Return $\mathcal{F}$ as ${\mathcal{F}}^{\prime }$.

Sum-product inference task: Compute: $\sum _X\prod _{i=1}^k{f}_i$ This can be more effective than: $\sum _{X}P(X_1,X_2,...,X_n)!$

Variable Elimination Algorithm $VE(\mathcal{F},Q,E,e,\rho )$

• Inputs:

  • $\mathcal{F}$: the list of conditional probability tables in a BN; set of factors
  • $Q$: a list of query variables;
  • $E$: a list of observed variables;
  • $e$: observed values;
  • $\rho$: eliminating order of variables which are not in $Q\cup E$

• Output: $P(Q\mid E=e)$, the query answer

• While $\rho$ is not empty

  • eliminate the first variable $Z$ from $\rho$
  • call function $\text{eliminate}(\mathcal{F},Z)$ endwhile.

• Set $h$ to be the product of all the factors in $\mathcal{F}$

• Instantiate observed variables in $h$ to their observed values

• Re-normalization: $\frac{h(Q)}{\sum _{Q}h(Q)}$

• Return

Example

Conditional Probability Inference

digraph G {
    // Set global graph, node, and edge attributes
    graph [rankdir=TB];
    node [shape=circle, style=filled, color=lightblue, fontname="Helvetica", fontsize=12];
    edge [color=black];
    // Define nodes
    A [label="A"];
    B [label="B"];
    C [label="C"];
    D [label="D"];
    E [label="E"];
    F [label="F"];
    // Define edges
    A -> D;
    B -> D;
    B -> E;
    C -> E;
    D -> F;
    E -> F;
}

Query $P(A|F=0)$

This Bayesian network (BN) factorizes $P(A,B,C,D,E,F)$ into the following form:

$$P(A,B,C,D,E,F)=P(A)P(B)P(C)P(D\mid A,B)P(E\mid B,C)P(F\mid D,E)$$

So the initial factorization:

$$\mathcal{F}=\{P(A),P(B),P(C),P(D\mid A,B),P(E\mid B,C),P(F\mid D,E)\}$$

Elimination order for the non-query, non-evidence variables: $\rho :C,E,B,D$

Inference process:

• Step 1: Eliminate all non-query variables:

  • Eliminate C (furthest): So we have the new marginal function:

    $${\psi }_1(B,E)=\sum _{C}P(C)P(E\mid B,C)$$$$\mathcal{F}=\{P(A),P(B),P(D\mid A,B),P(F\mid D,E),{\psi }_1(B,E)\}$$

    Assuming all variables are binary, the cost of eliminating $C$ is $2^3$ (index 3 is the number of variables involved in this process).

  • Eliminate E: Only two factors contain $E$ in $\mathcal{F}$, while three factors contain $B$:

    $${\psi }_2(B,D,F)=\sum _{E}P(F\mid D,E){\psi }_1(B,E)$$$$\mathcal{F}=\{P(A),P(B),P(D\mid A,B),{\psi }_2(B,D,F)\}$$

    The cost of eliminating $E$ is $2^4$.

  • Eliminate B:

    $${\psi }_3(A,D,F)=\sum _{B}P(B)P(D\mid A,B){\psi }_2(B,D,F)$$$$\mathcal{F}=\{P(A),{\psi }_3(A,D,F)\}$$

  • Eliminate D:

    $${\psi }_4(A,F)=\sum _D{\psi }_3(A,D,F)$$$$\mathcal{F}=\{P(A),{\psi }_4(A,F)\}$$
• Step 2: Deal with the evidence variable:
  • $g(A,F)=P(A){\psi }_4(A,F)$
• Step 3: Instantiation for $F=0$:
  • $h(A)=g(A,F=0)$
  • This $h(A)$ is an un-normalized factor, because $\sum _{A}h(A)$ may not be 1.
• Step 4: Re-normalization and obtain the conditional probability:
  • $P(A\mid F=0)=\frac{h(A)}{\sum _{A}h(A)}$

Marginal Probability Inference

digraph BayesianNetwork {
    // Node attributes
    node [shape=ellipse, fontname="Helvetica", fontsize=12, style=solid];

    // Nodes
    Coherence;
    Difficulty;
    Intelligence;
    Grade;
    SAT;
    Letter;
    Job;
    Happy;

    // Edges
    Coherence -> Difficulty;
    Difficulty -> Grade;
    Intelligence -> Grade;
    Intelligence -> SAT;
    Grade -> Letter;
    SAT -> Job;
    Letter -> Job;
    Job -> Happy;
    Difficulty -> Happy;
}

(a) The chain rule for this Student BN asserts that

$$P(C,D,I,G,S,L,H)=P(C)P(D\mid C)P(I\mid D)P(G\mid I,D)P(S\mid I)P(L\mid G)P(J\mid L,S)P(H\mid G,J)$$$$={\varphi }_C(C){\varphi }_D(D,C){\varphi }_I(I\mid D){\varphi }_G(G,I,D){\varphi }_S(S,I){\varphi }_L(L,G){\varphi }_J(J,L,S){\varphi }_H(H,G,J)$$

So, we have the list of function factors:

$$F=\{{\varphi }_C(C),{\varphi }_D(D,C),{\varphi }_I(I),{\varphi }_G(G,I,D),{\varphi }_S(S,I),{\varphi }_L(L,G),{\varphi }_J(J,L,S),{\varphi }_H(H,G,J)\}$$

(b) Apply VE algorithm to compute $P(J)$

• p: $C,D,I,H,G,S,L$
• q: $J$

---

i. Eliminating $C$: Compute the factors with sum-production operation

$${\psi }_1(C,D)={\varphi }_C(C){\varphi }_D(D,C)$$$${\tau }_1(D)=\sum _C{\psi }_1(C,D)$$

In this case, ${\tau }_1(D)$ is simply the marginal distribution of $D$. (This is a trivial case; the others may NOT necessarily be the marginal distribution function). Now we have eliminated one factor that involves $D$, ${\varphi }_D(D,C)=P(D\mid C)$, and introduced the new factor ${\tau }_1(D)$ that involves $D$. Now the list of factors are:

$$F=\{{\tau }_1(D),{\varphi }_I(I),{\varphi }_G(G,I,D),{\varphi }_S(S,I),{\varphi }_L(L,G),{\varphi }_J(J,L,S),{\varphi }_H(H,G,J)\}$$

---

ii. Eliminating $D$:

$${\psi }_2(G,I,D)={\varphi }_G(G,I,D){\tau }_1(D)$$$${\tau }_2(G,I)=\sum _D{\psi }_2(G,I,D)$$

Now the list of factors are:

$$F=\{{\tau }_2(G,I),{\varphi }_I(I),{\varphi }_S(S,I),{\varphi }_L(L,G),{\varphi }_J(J,L,S),{\varphi }_H(H,G,J)\}$$

---

iii. Eliminating $I$:

There are three factors involving $I$: ${\tau }_2(G,I),{\varphi }_I(I),{\varphi }_S(S,I)$.

$${\psi }_3(G,I,S)={\varphi }_I(I){\varphi }_C(G,I,D){\varphi }_S(S,I)$$$${\tau }_3(G,S)=\sum _I{\psi }_3(G,I,S)$$

Now the list of factors are:

$$F=\{{\tau }_3(G,S),{\varphi }_L(L,G),{\varphi }_J(J,L,S),{\varphi }_H(H,G,J)\}$$

---

iv. Eliminating $H$:

There is only one factor involving $H$: ${\varphi }_H(H,G,J)$.

$${\psi }_4(G,J,H)={\varphi }_H(H,G,J)$$$${\tau }_4(G,J)=\sum _H{\psi }_4(G,J,H)$$

Note that:

$${\varphi }_H(H,G,J)=P(H\mid G,J)$$$${\tau }_4(G,J)=\sum _H{\psi }_4(G,J,H)=\sum _{H}P(H\mid G,J)=1$$

We generated this new factor, but it does not complicate the algorithm. Now the list of factors are:

$$F=\{{\tau }_3(G,S),{\tau }_4(G,J),{\varphi }_L(L,G),{\varphi }_J(J,L,S)\}$$

---

v. Eliminating $G$:

There are three factors related to $G$:

$${\psi }_5(G,J,L,S)={\tau }_3(G,S){\tau }_4(G,J){\varphi }_L(L,G)$$$${\tau }_5(J,L,S)=\sum _G{\psi }_5(G,J,L,S)$$

So now the list of factors are:

$$F=\{{\tau }_5(J,L,S),{\varphi }_J(J,L,S)\}$$

---

vi. Eliminating $S$:

$${\psi }_6(J,L,S)={\tau }_5(J,L,S){\varphi }_J(J,L,S)$$$${\tau }_6(J,L)=\sum _S{\psi }_6(J,L,S)$$

So now the list of factors are:

$$F=\{{\tau }_6(J,L)\}$$

---

vii. Eliminating $L$:

$${\tau }_7(J)=\sum _L{\tau }_6(J,L)$$

Then we renormalize ${\tau }_7$ to obtain $P(J)$.

---

• We can use any elimination ordering, but some are obviously better than the others.
• The optimal elimination ordering: the one with minimum cost.