15 Bayes Nets Inference

Review: D Separation

Query: Is \(X_i\) independent of \(X_j\) given \(\{X_{k1}, \dots, X_{kn}\}\)?

• check all undirected paths between \(X_i\) and \(X_j\)
• if one or more are active then independence is not guaranteed

• if all paths are inactive, independence is guaranteed

• at least 1 active path = no independence

• all inactive paths = independence

caveat: on the same path you may have multiple triplets — if one is inactive then the entire path becomes inactive

L -> R
R -> D
R -> T
B -> T
T -> T'

• \(L \perp T' \mid T\)? Yes
• \(L \perp B\)? Yes
• \(L \perp B \mid T\)? No
• \(L \perp B \mid T'\)? No
• \(L \perp B \mid T, R\)? Yes

other example

R -> T
R -> D
T -> S
D -> S

now there are two paths, so there should be a problem — there are two separate paths each with their own triplet

in this case: - \(T \perp D\)? No - \(T \perp D \mid R\)? Yes - \(T \perp D \mid R, S\)? No

• the arrows use assumptions about conditional dependence
• the fewer assumptions we make, the more arrows we use, the larger our bayes net is

• the conditional assumption is that

• Given some graph topology \(G\), only certain joint distributions can be encoded

• The graph structure guarantees certain conditional independencies
• There might be more independences
• Adding arcs increases the set of distributions but has several costs
• Full conditioning can encode any distribution

the more arrows you have encoding the specific structure is interesting

CONNECTION TO RL

• bayes nets are just a way of encoding the conditional probability tables more efficiently
• if we think back to RL, when we were writing the transition model and reward model, those were essentially just CPTs and can be modified by using bayes nets
• model based RL

INFERENCE

• inference: calculating some useful quantity from a joint probability distribution
• \(P(Q | E_1 = e_1, E_2 = e_2, \dots, E_k = e_k)\)
• most likely explanation:
• \(\arg\max_q P(Q = q | E_1 = e_1, E_2 = e_2, \dots, E_k = e_k)\)

inference by enumeration

• general case:
• evidence variables \(E_1, E_2, \dots, E_k\)
• query variable: \(Q\)

• hidden variables \(H_1, H_2, \dots, H_r\)

• step 1: select the rows we want that are consistent with the evidence

• sum out \(H\) to get the joint of query and evidence
• normalize (times \(\frac{1}{Z}\)) — works fine with multiple query variables too

in this model we don't need to look at the whole joint distribution

inference by enumeration in bayes net

• given infinite time, inference in BNs is easy
• reminder of inference by enumeration by example

Alarm Example

B -> A
E -> A
A -> J
A -> M

just by the definition of conditional:

\(P(B | +j, +m) \propto P(B, +j, +m)\)

we want to sum over hidden variables:

\(= \sum_{e,a} P(B, e, a, +j, +m)\) \(= \sum_{e,a} P(B)P(e)P(a|B, e)P(+j|a)P(+m|a)\)

Inference by enumeration? Variable elimination

what is going on and why are we doing it?

Example: just 6 vars, \(\{U, V, W, X, Y, Z\}\), consider 16 triplets of three distinct vars - 16 multiplies, 7 adds

rewrite as: \((U + V)(W + X)(Y + Z)\) - 2 multiplies, 3 adds

move summations inwards as far as possible

\(P(B|j, m) = \alpha \sum_{e,a} P(B)P(B)P(a|B, e)P(j|a)P(m|a)\)

do the calculation from the inside first - i.e. sum over \(a\) first, then sum over \(e\) - Note: \(P(a|B, e)\) is a table

why is inference by enumeration so slow? - we did that first step of looking at the rows that have the evidence, and we summed out the rows that we did care about

idea: interleave joining and marginalizing, so we sum out all the variables we don't care about. getting this really big unwieldy thing is hard to deal with — we want to remove things until it only contains what we care about. I'm gonna show you some examples.

lets do our first bayes net

• joint distribution: \(P(\text{Temp}, \text{Weather})\)
• entries sum to 1

T	W
hot	cold
hot	sunny

single conditional: - entries \(\{P(y | x)\}\) for fixed \(x\), all sum to one

family of conditional distributions - multiple conditionals - entries \(P(y | x)\)

specified family: - there are going to be pieces of the puzzle to actually get to what I want to get to

traffic example again

R -> T -> L

\(P(R)\) - \(+r = 0.1\) - \(-r = 0.9\)

\(P(T|R)\)

R	T	P
+r	+t	0.8
+r	-t	0.2
-r	+t	0.1
-r	-t	0.9

\(P(L|T)\)

L	T	P
+l	+t	0.3
+l	-t	0.7
-l	+t	0.1
-l	-t	0.9

\(P(L) = ?\)

\(= \sum_{r,t} P(L|t)P(t|r)P(r)\)

# P(R)
r_pos = 0.1
r_neg = 0.9
# eliminate R: P(T) = sum_R P(T|R) P(R)
t_pos = 0.8 * r_pos + 0.1 * r_neg =>
t_neg = 0.2 * r_pos + 0.9 * r_neg =>
# eliminate T: P(L) = sum_T P(L|T) P(T)
l_pos = 0.3 * t_pos + 0.7 * t_neg =>
l_neg = 0.1 * t_pos + 0.9 * t_neg =>

• track objects called factors
• initial factors are called local CPTs!
• any known values are selected: if we know \(L = +l\)
• if we looked at all the rows where \(L\) meant the distribution

although it's just two rows, you think it won't do too much, then I'm speeding up and being more efficient with our resources. remember we said that instead of computing the full joint, we can apply a couple of them together. this is what is called joining. it's like doing a database join. what does it actually mean to multiply two distributions to the store? the resulting tables would be \(P_r\), would be \(+r, -r\). so this is our process for joining these.

we would just have to multiply each entry in each distribution

we do that to get our final joint between the two

if we want to join on \(R\)

OPTION 2: eliminate, summing out

• second basic operation: marginalization
• take a factor and sum out a variable
• shrinks a factor to a smaller one
• a projection operation
• example

\(P(R, T)\)

R	T	P
+r	+t	0.08
+r	-t	0.02
-r	+t	0.09
-r	-t	0.81

\(P(T)\)

# P(T) = sum_R P(R, T)
t_pos = 0.08 + 0.09 =>
t_neg = 0.02 + 0.81 =>

Thus far: multiple joins, multiple eliminates = inference by enumeration.

\(P(L)\)? on \(R \to T \to L\)

\(= \sum_t \sum_r P(L|\dots)\)

Let's do it in our example 1. sum \(R\), we are going to do the pointwise to calculate 2. sum out \(R\) to get \(P(T)\)

• if evidence

Join on all hidden variables \(H\) and keep doing that for each of the \(H\) hidden variables, and at the end we normalize, and we get the distribution we wanted!

what is the sequence of processing these variables? - the order definitely matters

it's always iterative, so join \(H_1\), elim \(H_2\), join, etc...

what if I join \(H_2\) first?

What if I did the join-eliminate process in a different order? - it would affect the efficiency of this algorithm. Its

alarm Example again

\(P(B|j, m) \propto P(B, j, m)\)

\(P(B) P(E) P(A|B, E) P(j|A) P(m|A)\)

Choose \(A\): - \(P(A|B, E)\) - \(P(j|A)\) - \(P(m|A)\)

if we had tables we would have knocked out all rows that aren't \(j\) or \(m\). we select all the factors that have \(A\) in it (the three above) and multiply them together:

\(P(j, m, A|B, E)\)

when we eliminate \(A\), all the rows correspond to \(j\) and \(m\), given \(B\) and \(E\):

\(P(j, m|B, E)\)

so now we are at:

\(P(B) P(E) P(j, m|B, E)\)

now we want to look at everything \(E\): - \(P(E)\) - \(P(j, m|B, E)\)

join them, pointwise multiplication table:

\(P(j, m, E|B)\)

sum over \(E\) to eliminate:

\(P(j, m|B)\)

now all we have is \(P(B)\) and \(P(j, m|B)\)

now we can do one more join to get

\(P(j, m, B)\)

and then normalize

\(P(j, m|B)\)