\documentclass[12pt]{article}
\usepackage{fullpage,enumitem,amsmath,amssymb,graphicx,algorithm,algpseudocode}
%%
%% The tikz package is used for doing the actual drawing.
\usepackage{tikz}
\usepackage{color}
%%
%% In order to be able to put arrowheads in the middle of directed edges, we need an extra library.
\usetikzlibrary{decorations.markings}
%%
%% The next line says how the "vertex" style of nodes should look: drawn as small circles.
\tikzstyle{vertex}=[circle, draw, inner sep=0pt, minimum size=10pt]
%%
%% Next, we make a \vertex command as a shorthand in place of \node[vertex} to get that style.
\newcommand{\vertex}{\node[vertex]}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\newcommand{\deriv}{\frac{\partial d}{\partial d w_k}}

\DeclareMathOperator*{\argmax}{arg\,max}

\begin{document}

\begin{center}
{\Large CS228 Winter 2016 Homework 2}

\begin{tabular}{rl}
SUNet ID: & dguo1113 \\
Name: & Dan Guo \\
Collaborators: & Aran Nayebi \\
\end{tabular}
\end{center}

By turning in this assignment, I agree by the Stanford honor code and declare that all of this is my own work.

\section{Problem 1}
\begin{enumerate}[label=(\alph*)]
\item
\[\begin{tikzpicture}[x=1.3cm, y=1cm,
    every edge/.style={
        draw,
        postaction={decorate,
                    decoration={markings,mark=at position 1 with {\arrow{>}}}
                   }
        }
]
  \vertex (A) at (0,0) [label=left:$A$]{};
  \vertex (B) at (1,2) [label=left:$B$]{};
  \vertex (C) at (2,0) [label=left:$C$]{};
  \vertex (D) at (3,2) [label=left:$D$]{};

  \path
    (B) edge[bend left=0] (A)
    (B) edge[bend left=0] (C)
    (D) edge[bend left=0] (C)
  ;
\end{tikzpicture}\]
\item Yes there is one I-equivalent graph. The arrow between A-B flipped. 
\[\begin{tikzpicture}[x=1.3cm, y=1cm,
    every edge/.style={
        draw,
        postaction={decorate,
                    decoration={markings,mark=at position 1 with {\arrow{>}}}
                   }
        }
]
  \vertex (A) at (0,0) [label=left:$A$]{};
  \vertex (B) at (1,2) [label=left:$B$]{};
  \vertex (C) at (2,0) [label=left:$C$]{};
  \vertex (D) at (3,2) [label=left:$D$]{};

  \path
    (A) edge[bend left=0] (B)
    (B) edge[bend left=0] (C)
    (D) edge[bend left=0] (C)
  ;
\end{tikzpicture}\]

\item 
\[\begin{tikzpicture}[x=1.3cm, y=1cm,
    every edge/.style={
        draw}
]
  \vertex (A) at (0,0) [label=left:$A$]{};
  \vertex (B) at (1,2) [label=left:$B$]{};
  \vertex (C) at (2,0) [label=left:$C$]{};
  \vertex (D) at (3,2) [label=left:$D$]{};

  \path
    (B) edge[bend left=0] (A)
    (B) edge[bend left=0] (C)
    (D) edge[bend left=0] (C)
    (D) edge[bend left=0] (B)
  ;
\end{tikzpicture}\]

This is not a perfect map as $ B \perp D \in I(P)$, but $B \perp D \not\in I(G)$ where $G$ is the Markov Network above.

\end{enumerate}
\section{Problem 2}

\begin{enumerate}[label=(\alph*)]
\item 
Through marginalization of the full joint, we get that $P(C=0) = .5$, $P(D=0) = .5$, $P(B=1) = \frac{5}{8}$ \\

Similarly, through marginalization, we arrive that
$$ P(C=c, D=d) = .25, \forall c=0,1, d=0,1$$
$$ P(B=1, C=0) = \frac{3}{8}$$

Thus, it is clear that $(C \perp D) \in I(P), (C \perp B) \not\in I(P)$

\item 
\[\begin{tikzpicture}[x=1.3cm, y=1cm,
    every edge/.style={
        draw,
        postaction={decorate,
                    decoration={markings,mark=at position 1 with {\arrow{>}}}
                   }
        }
]
  \vertex (C) at (2,4) [label=left:$C$]{};
  \vertex (D) at (0,4) [label=left:$D$]{};
  \vertex (A) at (2,2) [label=left:$A$]{};
  \vertex (B) at (2,0) [label=left:$B$]{};

  \path
    (C) edge[bend left=0] (A)
    (A) edge[bend left=0] (B)
    (D) edge[bend left=0] (A)
    (D) edge[bend left=0] (B)
  ;
\end{tikzpicture}\]

Yes this solution is unique. Because we know the structure of the BN already, it suffices to assign edges until we assign the whole graph, or we reach a state of contradiction. Specifically, if any assignment creates an active path between $C,D$ or $C,B$ then it is not a valid I-map of $P$, and hence cannot be its perfect map. Or, if any assignment introduces a cycle, this cannot be a BN. \\

Here are all possible assignments, with a 1 in edge signifying directed from 1st node to second, i.e. for an edge $(u,v), u \rightarrow v$:


\begin{center}
\begin{tabular}{ |c|c|c|c|c| } 
 \hline
 $(A,C)$ & $(A,B)$ & $(A,D)$ & $(B,D)$ & Valid? \\ 
 \hline
 0 & 0 & 0 & 0 & No, no active path from $C,B$ \\
 0 & 0 & 0 & 1 & No, no active path from $C,B$ \\
 0 & 0 & 1 & 0 & No, active path $C - A - D$\\
 0 & 0 & 1 & 1 & No, active path $C - A - D$\\
 0 & 1 & 0 & 0 & Yes\\
 0 & 1 & 0 & 1 & No, active path $C - A - B - D$\\
 0 & 1 & 1 & 0 & No, active path $C - A - D$\\
 0 & 1 & 1 & 1 & No, active path $C - A - D$\\
 1 & 0 & 0 & 0 & No, active path $C - A - D$\\
 1 & 0 & 0 & 1 & No, active path $C - A - D$\\
 1 & 0 & 1 & 0 & No, active path $C - A - D$\\
 1 & 0 & 1 & 1 & No, active path $C - A - D$\\
 1 & 1 & 0 & 0 & No, active path $C - A - D$\\
 1 & 1 & 0 & 1 & No, active path $C - A - D$\\
 1 & 1 & 1 & 0 & No, active path $C - A - D$\\
 1 & 1 & 1 & 1 & No, active path $C - A - D$\\
 \hline
\end{tabular}
\end{center}

Note another explanation for why the network is not valid is that some of the networks have arrows that will introduce a cycle. The network must be a DAG.

\item CPDs for each node

\begin{center}
\begin{tabular}{ |c|c| } 
 \hline
 $C$ & $P(C)$ \\ 
 \hline
 0 & .5 \\
 1 & .5 \\
 \hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ |c|c| } 
 \hline
 $D$ & $P(D)$ \\ 
 \hline
 0 & .5 \\
 1 & .5 \\
 \hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ |c|c|c|c| } 
 \hline
 $A$ & $C$ & $D$ & $P(A|C,D)$ \\ 
 \hline
 0 & 0 & 0 & 1/2 \\
 0 & 0 & 1 & 1 \\
 0 & 1 & 0 & 0 \\
 0 & 1 & 1 & 0 \\
 1 & 0 & 0 & 1/2 \\
 1 & 0 & 1 & 0 \\
 1 & 1 & 0 & 1 \\
 1 & 1 & 1 & 1 \\
 \hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ |c|c|c|c| } 
 \hline
 $A$ & $B$ & $D$ & $P(B|A,D)$ \\ 
 \hline
 0 & 0 & 0 & 1 \\
 0 & 0 & 1 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 1 & 1 & 1 \\
 1 & 0 & 0 & 0 \\
 1 & 0 & 1 & 1 \\
 1 & 1 & 0 & 1 \\
 1 & 1 & 1 & 0 \\
 \hline
\end{tabular}
\end{center}

\end{enumerate}


\section{Problem 3}

\begin{align*} 
P(\mathbf{Y} = m| \mathbf{X}) &= \frac{1}{Z(\mathbf{X})} \hat{P}(\mathbf{Y},\mathbf{X}) \\
&= \frac{\prod_{i=0}^{k}{\phi_i (\mathbf{D}_i)} }{\sum_{j=1}^{M} {\hat{P}(j, \mathbf{X})}} \\
&= \frac{ \exp(w_0^m) \prod_{i=1}^{k}{\exp(w_i^m \mathbf{X}_i)} } {\sum_{j=1}^{M} \exp(w_0^j) \prod_{i=1}^{k} {\exp(w_i^j \mathbf{X}_i)}} \\
&= \frac{ \exp(\sum_{i=1}^{k} {w_i^m \mathbf{X}_i } + w_0^m) }{\sum_{j=1}^{M} \exp(\sum_{i=1}^{k} {w_i^j \mathbf{X}_i } + w_0^j) } \\
&= \frac{\exp(\theta_m^T x + b_m)}{\sum_{j=1}^{M}\exp(\theta_j^T x + b_j)}
\end{align*}

where for the last set, we define column vector $\theta_j = [w_1^j,...,w_k^j]$, column vector $\theta_m = [w_1^m,...,w_k^m]$, $b_m = w_0^m$, $b_j = w_0^j$.


\section{Problem 4}

\begin{enumerate}[label=(\alph*)]

\item

\begin{align*}
P(X_i) &= \frac{\sum_{X_{i+1}} {P(X_i, X_{i+1})} }{1} \\
&= \frac{\sum_{X_{i+1}} {P(X_i, X_{i+1})} }{ \sum_{X_i, X_{i+1}} {P(X_i, X_{i+1})}} \\
&= \frac{\sum_{X_{i+1}} {k \beta( C_i)} }{ \sum_{X_i, X_{i+1}} {k \beta( C_i)}} \\
&= \frac{\sum_{X_{i+1}} {\beta( C_i)} }{ \sum_{X_i, X_{i+1}} {\beta( C_i)}} \\
\end{align*}

Thus to calculate $P(X_i)$, we simply need to calculate the numerator and denominator. For example, we can sum over $X_{i+1}$ of the belief of clique $i$, $\beta(C_i)$, to arrive at the numerator and sum over $X_{i}, X_{i+1}$ to arrive at the denominator.

The numerator is summing over all values of $X_i$, with the belief being a table lookup, hence $O(d)$. The denominator is summing over all pairs of $X_i, X_{i+1}$, with the summand being a lookup, hence $O(d^2)$. In total, for a given $X_i$, we arrive at $O(d^2)$.

The result does not depend on which clique we use to extract the marginal form as the clique tree is calibrated. We can extract the probability $P(X_i)$ from either clique $C_i, C_{i-1}$ that are dependent on $X_i$ as shown here.

\begin{align*}
\frac{\sum_{X_{i-1}} {\beta( C_{i-1})} }{ \sum_{X_{i-1}, X_{i}} {\beta( C_{i-1})}} &=\frac{\sum_{X_{i-1}} {l \beta( C_{i-1})} }{ \sum_{X_{i-1}, X_{i}} {l \beta( C_{i-1})}} \\
&= \frac{\sum_{X_{i-1}} {P(X_{i-1}, X_{i})} }{ \sum_{X_{i-1}, X_{i}} {P(X_{i-1}, X_{i})}} \\
&= P(X_i) \\
&= \frac{\sum_{X_{i+1}} {P(X_i, X_{i+1})} }{ \sum_{X_i, X_{i+1}} {P(X_i, X_{i+1})}} \\
&= \frac{\sum_{X_{i+1}} {k \beta( C_i)} }{ \sum_{X_i, X_{i+1}} {k \beta( C_i)}} \\
&= \frac{\sum_{X_{i+1}} {\beta( C_i)} }{ \sum_{X_i, X_{i+1}} {\beta( C_i)}} \\
\end{align*}

\item
The runtime complexity is $O(n^3d^3)$.

We derived in lecture that the runtime complexity of Sum-Product-VE is $O(mv^{N_{max}})$. In our case the number of factors $m = O(n)$. The number of possible assignments of a given random variable is $d$, hence $v = d$. The maximum scope of any factor generated is $N_{max} = 3$ because when we sum out a particular variable it involves at most two other variables, its adjacent ones in the Markov Chain. This is $O(nd^3)$. The other operations, creating a subtree and looping to update factors, in Algorithm 1 are also $O(nd^3)$.\\
 
Because this is only one run of Algorithm 1, and we need to run $O(n^2)$ times for all marginal pairs, we arrive at our desired runtime.

\item 

We show that $P(X_i, X_j) = \sum_{X_{j-1}} {P(X_i, X_{j-1}), P(X_j| X_{j-1})}, i < j-1$


\begin{align*}
P(X_i, X_j) &= \sum_{X_{j-1}} {P(X_i, X_{j-1}, X_{j})}  \\
&= \sum_{X_{j-1}} {P(X_i, X_{j}) P(X_j | X_{i}, X_{j-1})} \\
&= \sum_{X_{j-1}} {P(X_i, X_{j}) P(X_j | X_{j-1})} \\
\end{align*}

where the second equality uses that there is no clique involving $X_j, X_k$, where $k < j-1$. Thus, conditioning on $X_{j-1}$, $X_j$ independent on all such $X_k$. In particular, $X_j \perp X_{i} | X_{j-1}$

\item 
First note the following:
$$P(X_j | X_{j-1}) = P(X_j, X_{j-1}) / P(X_{j-1}) = \frac{k \beta(C_{j-1})}{\sum_{X_j}{k \beta(C_{j-1})} } = \frac{\beta(C_{j-1})}{\sum_{X_j}{\beta(C_{j-1})} }$$

and,

$$P(X_i) = \frac{\sum_{X_{i+1}} {\beta( C_i)} }{ \sum_{X_i, X_{i+1}} {\beta( C_i)}} $$, from part (a).

Let us define the recurrence as follows:
\[
 P_(X_i,X_j) =
  \begin{cases} 
      \hfill P(X_j | X_{j-1}) P(X_{j-1})   \hfill & \text{ if $i = j-1$} \\
      \hfill \sum_{X_{j-1}} {P(X_i, X_{j-1}), P(X_j| X_{j-1})}  \hfill & \text{ if $i < j-1$} \\
  \end{cases}
\]


Let the algorithm be as follows:
First compute all $P(X_i)$ marginal probabilities as in part (a). Specifically $P(X_i) = \frac{\sum_{X_{i+1}} {\beta( C_i)} }{ \sum_{X_i, X_{i+1}} {\beta( C_i)}} $

Next we compute all $P(X_j | X_{j-1})$ conditional probabilities, by the formula above.

Finally we calculate all pairwise marginal probabilities $P(X_i, X_j)$. The order we calculate is for every $X_i$, starting from $P(X_i, X_{i+1}), P(X_i, X_{i+2}),..., P(X_i, X_{n})$ \\



Here is the runtime analysis: 
For calculating $P(X_i)$, from part (a), for a given $X_i$ is $O(d^2)$ time. Calculating for all values of $X_i$, and over all $i$, we get total time of $O(nd^3)$. 

For calculating $P(X_j | X_{j-1})$, the costliest operation is summing in the denominator over $d$ values, hence $O(d)$ operation. For all such $X_j, X_{j-1}$ pairings, it costs $O(nd)$.

For the inductive step, for a particular pairing $X_i, X_j$, the calculation has two cases. If $i=j-1$, we require two lookups and a product, hence $O(1)$. Note that by the order of our algorithm, we have already calculated the conditional and single marginal probabilities. If $i<j-1$, the calculation is simply summing over $d$ values of $X_{j-1}$ and the summand is two lookups, as $P(X_i, X_{j-1})$ term has been calculated already and $P(X_j| X_{j-1})$ term has been calculated before hand. Thus regardless of case, the calculation is $O(d)$ time. But note that we must calculate $P(X_i, X_j)$ for all possible assignments of $X_i, X_j$ and between all pairings of random variables. For a particular pair of random variables, there are $O(d^2)$ assignments. Finally, there are $O(n^2)$ pairings of random variables. Hence this inductive step is $O(n^2d^3)$.

The computation is $O(n^2d^3)$.


\end{enumerate}

\section{Problem 5}

Let us define a Bayesian Network with the following structure:

and conditional probability distributions:

\begin{center}
\begin{tabular}{ |c|c| } 
 \hline
 $A$ & $P(A)$ \\ 
 \hline
 0 & .4 \\
 1 & .6 \\
 \hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}{ |c|c|c| } 
 \hline
 $A$ & $B$ & $P(B|A)$ \\ 
 \hline
 0 & 0 & .1 \\
 0 & 1 & .9 \\
 1 & 0 & .5 \\
 1 & 1 & .5 \\
 \hline
\end{tabular}
\end{center}







Note calculating MAP on variable $A$ is as follows:

$$ \text{MAP}(A) = \argmax_{a} P(A=a) = 1$$

Note the probabilities for all possible assignments of $A,B$ are as follows. This is computed using the joint specified by the structure, that $P(A,B) = P(A) P(B|A)$.

\begin{center}
\begin{tabular}{ |c|c|c| } 
 \hline
 $A$ & $B$ & $P(A,B)$ \\ 
 \hline
 0 & 0 & .04 \\
 0 & 1 & .36 \\
 1 & 0 & .3 \\
 1 & 1 & .3 \\
 \hline
\end{tabular}
\end{center}

This shows that the MPE assignment is $A= 0, B=1$. However the MAP assignment for $A = 1$. Thus the assignments do not match.



\section{Problem 6}
\begin{enumerate}[label=(\alph*)]
\item Implemented factors. Used Variable Elimination. The source code is in Section 7, but for full experience refer to submitted code.

\item -15.801923869942652

\begin{center}
\begin{tabular}{ |c|c|c|c|c|c| } 
 \hline
FromNode & ToNode & A & C & G & T \\ 
 \hline
1 & 3 &  0.032   &  0.816  & 0.028  &  0.076 \\
2 & 3 &  0.052   &  0.11   & 0.042  & 0.842 \\
3 & 5 &  0.00768265  & 0.08039275  & 0.00635416  & 0.06082532 \\
4 & 5 &  0.032   &  0.816  & 0.028  & 0.076 \\
6 & 8 &  0.085   &  0.028  & 0.808  & 0.029 \\
7  & 8 &  0.032   &  0.816  & 0.028  & 0.076 \\
8 & 10 &  0.0050291   & 0.019645    & 0.01934434  & 0.00439247 \\
9 & 10 &  0.831   &  0.046  & 0.122  & 0.053 \\
5 & 11 &  0.00255902  & 0.05405479  & 0.00220472  & 0.00889616 \\
10 & 11 &  0.00371453  & 0.00102133  & 0.00245183  & 0.00055463 \\
12 & 14 &  0.831   &  0.046  & 0.122  & 0.053 \\
13  & 14 &  0.831   &  0.046  & 0.122  & 0.053 \\
11 & 15 &   1.03817927e-05   & 4.61807163e-05   & 7.28043697e-06   & 9.01085538e-06 \\
14 & 15 &  0.57533511 & 0.0342182   & 0.09645194 &  0.03955736 \\
15 & 17 &   5.09236150e-06   & 1.62308990e-06   & 1.35531163e-06   & 7.57157749e-07 \\
16  & 17 &  0.085   &  0.028  & 0.808  & 0.029 \\
17 & 19 &   4.55377840e-07   & 9.00733950e-08   & 9.39836682e-07   & 7.66409639e-08 \\
18 & 19 &  0.831   &  0.046  & 0.122  & 0.053 \\
 \hline
\end{tabular}
\end{center}

\item Table and Tree

\begin{center}
\begin{tabular}{ |c|c|c|c|c|c| } 
 \hline
 NodeIndex & A & C & G & T & MaxAssignment \\ 
 \hline
3 & 0.01097032 &  0.80709913 &  0.002892 &    0.17903854 & C\\
5 & 0.05363426 &  0.84801463 &  0.01202623 &  0.08632488 & C \\
8 & 0.31047568 &  0.25534941 &  0.40861052 &  0.02556439 & G \\
10 & 0.68168057 &  0.15212077 &  0.14858574 &  0.01761291 & A\\
11 & 0.6494745 &   0.19702325 &  0.12504436 &  0.0284579  & A\\
14 & 0.97700779 &  0.00136516 &  0.0205555 &   0.00107156 & A\\
15 & 0.82186714 &  0.02269878 &  0.14744669 &  0.00798738 & A\\
17 & 0.65637297 &  0.00577348 &  0.33337198 &  0.00448156 & A\\
19 & 0.81373552 &  0.00619151 &  0.17133829 &  0.00873468 & A\\
 \hline
\end{tabular}
\end{center}

Tree in part (d)

\item

The maximal assignment achieves log probability of -17.70357925.


\begin{center}
\begin{tabular}{ |c|c| } 
 \hline
 NodeIndex &  MaxAssignment \\ 
 \hline
3 & C\\
5 & C \\
8 & A \\
10 & A\\
11 &  A\\
14 & A\\
15 & A\\
17 & A\\
19 & A\\
 \hline
\end{tabular}
\end{center}

\[\begin{tikzpicture}[x=1.3cm, y=1cm,
    every edge/.style={
        draw,
        }
]
  \vertex (19) at (0,-1) [label=above:$19: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (18) at (6,-0) [label=above:$18: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (17) at (1,-3) [label=above:$17: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (16) at (6,-2) [label=above:$16: \color{blue}G\text{,}\color{red}G$]{};
  \vertex (15) at (2,-7) [label=above:$15: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (14) at (5,-5) [label=above:$14: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (13) at (6,-4) [label=above:$13: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (12) at (6,-6) [label=above:$12: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (11) at (3,-13) [label=above:$11: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (10) at (4,-9) [label=above:$10: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (9) at (6,-8) [label=above:$9: \color{blue}A\text{,}\color{red}A$]{};
  \vertex (8) at (5,-11) [label=above:$8: \color{blue}G\text{,}\color{red}A$]{};
  \vertex (7) at (6,-10) [label=above:$7: \color{blue}C\text{,}\color{red}C$]{};
  \vertex (6) at (6,-12) [label=above:$6: \color{blue}G\text{,}\color{red}G$]{};
  \vertex (5) at (4,-15) [label=above:$5: \color{blue}C\text{,}\color{red}C$]{};
  \vertex (4) at (6,-14) [label=above:$4: \color{blue}C\text{,}\color{red}C$]{};
  \vertex (3) at (5,-17) [label=above:$3: \color{blue}C\text{,}\color{red}C$]{};
  \vertex (2) at (6,-16) [label=above:$2: \color{blue}T\text{,}\color{red}T$]{};
  \vertex (1) at (6,-18) [label=above:$1: \color{blue}C\text{,}\color{red}C$]{};

[(1, C), (2,T), (4, C), (6, G), (7, C), 
(9, A), (12, A), (13, A), (16, G), (18, A)]

  \path
    (18) edge[bend left=0] (19)
    (17) edge[bend left=0] (19)

    (15) edge[bend left=0] (17)
    (16) edge[bend left=0] (17)

    (14) edge[bend left=0] (15)
    (11) edge[bend left=0] (15)

    (12) edge[bend left=0] (14)
    (13) edge[bend left=0] (14)

    (5) edge[bend left=0] (11)
    (10) edge[bend left=0] (11)
    
    (8) edge[bend left=0] (10)
    (9) edge[bend left=0] (10)

    (6) edge[bend left=0] (8)
    (7) edge[bend left=0] (8)


    (4) edge[bend left=0] (5)
    (3) edge[bend left=0] (5)

    (1) edge[bend left=0] (3)
    (2) edge[bend left=0] (3)
  ;
\end{tikzpicture}\]

c assignments in {\color{blue} blue}, d assignments in {\color{red} red}. \\

The assignments do differ in parts (c) and (d) on assignment of node 8. In part (c), we are calculating with sum product variable elimination the marginal, thereby sum marginalizing over nodes not leaf or $x_v$. In part (d), we are actually not summing but max marginalizing over nodes not leaf or $x_v$. In this case, we are calculating the assignment of $x_v$ in the maximal assignment of the joint $p(leaves, ancestors)$. Specifically, the part c is the MAP of each ancestor variable while d is MPE. We showed in problem 5 that these two assignments need not agree.

\item -9379.70771125. python problemSolutions.py e; see Section 7 Source Code.
\item -9474.43836219. The tree from part(e) is a better fit as it affords a higher probability of the assignments in modern species.
\item We could theoretically enumerate all possible phylogeny trees that can possibly exist amongst the species that are currently alive. Next for each such tree, we calculate the log likelihood of the bases at a particular spot for all species, across multiple gene locations (as in parts e,f). This will give a log likelihood of how likely it is we have the current species. The most likely phylogeny would be the tree that outputs the highest probability for base assignments in modern species. A problem is having to enumerate many trees and computing log likelihoods of each, which will be expensive.
\end{enumerate}






\end{document}










