Bayesian Networks

Bayes Burritos

Bayes’ Burrito Bowls is a food truck that serves burrito bowls (obviously). You can choose:

a type of rice, which can be; white, brown
a type of bean, which can be; black, pinto, lima, or kidney
any of the following toppings; guacamole, corn, salsa, sour cream, onion, lettuce, or cheese

We model each type of burrito as a triple (R, B, T), where R and B are the types of rice and bean, and T is any subset of the toppings. The type of burrito a customer picks depends on his/her preferences. We can model such preferences using a probability distribution over (R, B, T ).

How many different types of burrito bowls are there?
Eshan builds a burrito bowl as follows: He first chooses the type of rice and bean independently of each other. Based on both these choices, he chooses the toppings (the toppings are not chosen independently of each other). Provide an appropriate factorization of $P_{Eshan} (R, B, T)$ and the number of values that must be known to compute it for any R, B, T.
Zafeer builds a burrito as follows: He first chooses type of rice. Based on this choice, he chooses a type of bean. He chooses the toppings independently of the other choices (toppings are not chosen independently of each other). Provide an appropriate factorization of $P_{Zafeer} (R, B, T)$ and the number of values that must be known to compute it for any R, B, T

We'll first count the number of different burritos, we already know that there are $2 \cdot 4 = 8$ rice-bean combinations, therefore we just have to figure out how many different topping choices there are, clearly we want to count the number of different subsets of the collection of toppings, by putting each topping in a tuple, and then using a binary tuple of the same length to produce a subset, then there $2^{7}$ topping choices, this leads there to be $2 \cdot 4 \cdot 2^{7} = 2^{10}$ different burritos.

Eshan chooses rice and beans independently of each other, this means that $P (B | R) = P (B)$ . Thus we can start by using the product rule and then obtaining $P (R, B, T) = P (R) P (B | R) P (T | R, B) = P (R) \cdot P (B) P (T | R, B)$ Therefore we need to know $2 + 4 + 2^{7} \cdot 2 \cdot 4$ values to compute it for any $R, B, T$

In Zafeer's case, we know that $P (T | R, B) = P (T)$ , therefore using the same initial factorization as above and simplifying respectively we obtain that $P (R, B, T) = P (R) P (B | R) P (T)$ and therefore we only have to know $2 + 2 \cdot 4 + 2^{7}$ values, to compute it for any $R, B, T$ which is an improvement on our original size.

Bayesian Network Independence

Consider the following bayesian network:

Which variables are independent of $I$
Which variables are conditionally independent of $A$ given $K$
Which variables are conditionally independent of $B$ given $E$

Before we start recall when variables are conditionally indedpent using d-separation. Let's recall what an active path is and an inactive path, which are defined in terms of active and in-active triples.

Let's first see what variables are independent of $I$ , to do this we verify which nodes have no active paths from them to $I$ since $J, G$ have direct dependence, then they cannot be independent of $I$ , $K$ has the active path $J - G - K$ so it is not independent and the same for $H$ . Looking at $F$ we see that it is blocked by $G$ , similarly this is true for $E$ , moreover since there is only one active path from $G$ to $I$ as it is the bottleneck, then every path from the variables $A, B, E, D, F$ is blocked by the inactive triple $I - G - E$ therefore there is no active path from any of these variables to $I$ and thus ${A, B, E, D, F}$ are independent of $I$ .

Suppose we are given $K$ and we want to find which variables are conditionally independent of $A$ given $K$ observe that we obtain active paths from $B, E, F, G, H$ so they are all not indepedent with respect to $A$ , by the "common effect", we obtain that $D, F, I$ are not independent, similarly we obtain that $J$ is not independent, therefore none of the variables are conditionally independent of $A$ given $K$ .

We repeat the process this time for the situation where we are given $E$ and we want to find what variables are conditionally independent of $B$ . By "the common effect rule", we deduce that $D$ is not independent, on the other hand, any path which has B-E-G as a subpath will be an in-active path, given any variable $V \in {F, G, H, I, J, K}$ any path from $B$ to $V$ will always have B-E-G as a subpath, and therefore there are no active paths, so that only the variables $F, G, H, I, J, K$ are independent of $B$ given $E$ .

Bayesian Construction

Draw a Bayesian Network over the varaibles

W, X, Y, Z

such that

$X$ and $Y$ are independent given $Z$
$Z$ and $W$ are independent given $X$ and $Y$

Consider the network

W \to X \to Z \to Y

We can see that $W$ and $Y$ re independent given $Z$ as their path is blocked by the inactive triple $X \to Z \to Y$ . We also see that $Z$ and $W$ are independent given $X$ and $Y$ because they are blocked by $X$ in a similar manner.

Bayesian Network Computation

Compute $P (F = yes | N = n, M = m)$

m \in M, n \in N

Recall that

P (F = yes | N = n, M = m) = \frac{P (F = yes, N = n, M = m)}{P (M = m, N = n)}

By the law of total probability we have that

\frac{P (F = yes, N = n, M = m)}{P (M = m, N = n)} = \frac{\sum_{t \in T, s \in S} P (M = m, N = n, T = t, S = s, F = yes)}{\sum_{T, S, F} P (M = m, N = n, T = t, S = s, F = f)}

For easy of notation, let's denote

X = x

simply by

x

and

\sum_{x \in X} P (X = x)

\sum_{X} P (X)

we can re-write our value of interest as

\frac{\sum_{T, S} P (m, n, T, S, f)}{\sum_{T, S, F} P (m, n, T, S, F)}

Observe that by ordering our variables like $M, N, T, S, F$ anything to the left of a given variable is an ancestor node to it. Recall that throught the chain rule we obtain that $P (m, n, T, S, f) = P (m) P (m | n) P (T | m, n) P (S | T, m, n) P (F | S, T, m, n)$

But we are doing a summation over, this observe that we can nest the summation inside with a particular order $\sum_{T, S} P (m, n, T, S, F) = P (m) P (n) (\sum_{S} P (S | n) (\sum_{T} P (F | T, S) P (T | m, n)))$

Let us define the inner most sum as a function $g_{1} (S, F)$ so that $g_{1} (S, F) = P (F | T = e, S) P (T = e | M = m, N = n) + P (F | T = l, S) \cdot P (T = l | M = m, N = n)$ where we've iterated over the possible values of $T$ so that our summation has become $P (m) P (n) (\sum_{S} P (S | n) g_{1} (S, F))$

Let's take a closer look at this new summation and define a function $g_{2} (F)$ as $P (S = f | n) g_{1} (S = f, F) + P (S = s | n) g_{1} (S = s, F)$ so that the original summation is really just $P (m) P (n) g_{2} (F)$

The question wants us to find $P (F = yes | N = n, M = m)$ for each choice of $n, m$ so let's do that. Suppose that $M = train$ and $n = 0$ , then $\begin{matrix} g_{1} (S, F) & = P (F | T = e, S) P (T = e | M = train, N = 0) + P (F | T = l, S) \cdot P (T = l | M = train, N = 0) \\ = P (F | T = e, S) 0.9 + P (F | T = l, S) 0.1 \end{matrix}$ We now have to compute $g_{2}$ we have: $\begin{matrix} g_{2} (F) & = P (S = f | N = 0) g_{1} (S = f, F) + P (S = s | N = 0) g_{1} (S = s, F) \\ = 0.9 \cdot g_{1} (S = f, F) + 0.1 \cdot g_{1} (S = s, F) \end{matrix}$ Therefore the numerator of $α$ is given by $\begin{matrix} g_{2} (F = y) + g_{2} (F = n) & = (0.9 \cdot g_{1} (S = f, F = y)) + (0.1 \cdot g_{1} (S = s, F = n)) \\ = . . . \end{matrix}$ At this point we realize that this problem will require many computations, so as we are programmers, we write a program which encodes everything we've done up until this point and then use it to determine $P (F = y | M, N)$ for all $M, N$ . After observing the output of this program we deduce that you should take the train with no bags to maximize your changes of making the flight.