\begin{problem}{Variable Elimination Nation}

Suppose you are given a Bayes net with the same variables and structure as the alarm Bayes net from lecture, with the conditional probability tables given below.\\ 
\begin{center}
\begin{tabular}{|c|c|}\hline
$B$ & $P(B)$\\ \hline
$+b$ & 0.25 \\
$-b$ & 0.75 \\ \hline
\end{tabular}\hfill \begin{tabular}{|c|c|}\hline
$E$ & $P(E)$\\ \hline
$+e$ & 0.15\\
$-e$ & 0.85\\ \hline
\end{tabular}\hfill \begin{tabular}{|c c c|c|}\hline
$A$ & $B$ & $E$ & $P(A \mid B, E)$ \\ \hline
$+a$ & $+b$ & $+e$ & $0.8$\\ 
$-a$ & $+b$ & $+e$ & $0.2$\\ 
$+a$ & $+b$ & $-e$ & $0.6$\\ 
$-a$ & $+b$ & $-e$ & $0.4$\\ 
$+a$ & $-b$ & $+e$ & $0.6$\\ 
$-a$ & $-b$ & $+e$ & $0.4$\\ 
$+a$ & $-b$ & $-e$ & $0.1$\\
$-a$ & $-b$ & $-e$ & $0.9$\\ \hline
\end{tabular}\hfill \begin{tabular}{|c c|c|}\hline
$J$ & $A$ & $P(J \mid A)$\\ \hline
$+j$ & $+a$ & $0.8$\\ 
$-j$ & $+a$ & $0.2$\\ 
$+j$ & $-a$ & $0.1$\\
$-j$ & $-a$ & $0.9$\\ \hline
\end{tabular}\hfill \begin{tabular}{|c c|c|}\hline
$M$ & $A$ & $P(M \mid A)$\\ \hline
$+m$ & $+a$ & $0.65$\\
$-m$ & $+a$ & $0.35$\\
$+m$ & $-a$ & $0.4$\\
$-m$ & $-a$ & $0.6$\\ \hline
\end{tabular}\\
\end{center}
Apply the variable elimination algorithm to the query $P(B \mid +j,\ +m)$. You will have to eliminate the variables $E$ and $A$, in that order. For each variable, write:
\begin{enumerate}[label=(\roman*)]
\item The variables involved in the resulting factor (e.g., after eliminating $X$ the resulting factor might be $f_1(Y, Z)$, so the variables involved are $Y, Z$). You do not have to include constant values (ie. the given evidence).
\item The summation to calculate the factor (e.g., $f_1(Y, Z) = \sum_x P(Y)P(x \mid Y)P(Z \mid x)$)
\item The numeric values in the factor table
\end{enumerate}

\begin{question}[8]
Eliminating $E$:
\begin{center}
\solutionspace{1.75cm}{4cm}{(i) Variables:}{\FourAi}
\solutionspace{1.75cm}{11.5cm}{(ii) Summation:}{\FourAii}
\solutionspace{4.5cm}{15.85cm}{(iii) Factor table:}{\FourAiii}
\end{center}
\end{question}

\newpage
 
\begin{question}[8]
Eliminating $A$:
\begin{center}
\solutionspace{1.75cm}{4cm}{(i) Variables:}{\FourBi}
\solutionspace{1.75cm}{11.5cm}{(ii) Summation:}{\FourBii}
\solutionspace{4.5cm}{15.85cm}{(iii) Factor table:}{\FourBiii}
\end{center}
\end{question}

\begin{question}[8]
After eliminating E and A above, you must multiply the remaining factors to produce yet another factor table. Specify the variables associated with the resulting factor, and fill out the values in the corresponding factor table.
\begin{center}
\solutionspace{3.5cm}{5cm}{(i) Variables:}{\FourCi} \quad
\solutionspace{3.5cm}{10.5cm}{(ii) Factor table:}{\FourCii}
\end{center}
Now, find the normalizing constant to make this factor the probability distribution we want, $P(B \mid +j, +m)$. Write out the values of this normalized probability table.
\begin{center}
\solutionspace{3.5cm}{5cm}{(iii) Constant ($\alpha$ or $Z$):}{\FourCiii} \quad
\solutionspace{3.5cm}{10.5cm}{(iv) Probability table:}{\FourCiv}
\end{center}
\end{question}

\newpage

Now consider the Bayes net below. Suppose we are trying to compute the query $P(X \mid e_1, e_2)$. Assume all variables are binary.
\begin{center}
\includegraphics[height=0.3\textwidth]{figures/q4_bn.png}
\end{center}

\begin{question}[2]
Suppose we choose to eliminate variables in the order $A, C, B, D, F$.\\
Of the factors resulting from summing out over each of these variables, which factor has the most entries in its corresponding table? How many entries are in its table? Assume that we have separate entries for pairs of numbers even if we know sum to one (e.g., we would store both $P(X=+x)$ and $P(X=-x)$).

\solutionspace{2.25cm}{9cm}{(i) Factor:}{\FourDi} \quad
\solutionspace{2.25cm}{2.5cm}{(ii) \# entries:}{\FourDii}
\end{question}

\begin{question}[5]
An optimal variable elimination ordering is one which minimizes the sum of the sizes of factors generated.

Fill in the table below with an optimal variable elimination ordering. For each variable, include the resulting factor and the number of entries in its table, again assuming that we separately store pairs of numbers which sum to one.

\begin{center}
\solution{
\begin{tabular}{|p{2cm}|p{2cm}|p{2cm}|}
\hline
Variable & Factor & \# Entries  \\ [4mm]
\hline
& & \\ [4mm]
\hline
& & \\ [4mm]
\hline
& & \\ [4mm]
\hline
& & \\ [4mm]
\hline
& & \\ [4mm]
\hline
\end{tabular}
}{\FourE}
\end{center}

\end{question}

\end{problem}