mm-inference-alg.tex

\begin{algorithm} 
\dontprintsemicolon
\caption[max-sum inference]{Max-sum message passing to solve 
\begin{align*}
&\mmi =  \max_{y'} s(x,y') = \max_{y'} \sum_{i \in \cV} \phi_i + \sum_{ij \in \cE} \phi_{ij}, \\
&\text{subject to: } y_i' = y_i
\end{align*}
} 
\label{alg:mm-inference} 

\KwIn{ Factors $\{\phi_i\}, \{\phi_{ij}\}$. Tree graph $G = (\cV,\cE)$ with (arbitrary) root node index $r$ and topological ordering $\pi$, where $\pi_n = r$.
}
\KwOut{ $\mmi = \argmax_{y} s(x,y)$ }
\For{$i = \pi_1, \pi_2, \ldots, \pi_n $ }{
$\fwdmsg_i = \phi_i + \sum_{j \in \text{kids}(i)} m_{j \rightarrow i}$\;
\If{$i == r$}{ break\; }
$p = \text{parent}_\pi(i) $\;
$m_{i \rightarrow p} = \max_{y_i} \phi_{ip} + \fwdmsg_i$\;
}

\For{$i = \pi_{n},\pi_{n-1},\ldots,\pi_1$}{

\eIf{$i == r$}{
$\bwdmsg_i = \phi_i$\;
}{
$\bwdmsg_i = \phi_i + m_{\text{parent}_\pi(i) \rightarrow i}$\;
}

\For{$j \in \text{kids}(i)$}{
$m_{i \rightarrow j} = \max_{y_i} \phi_{ij} + \bwdmsg_i$ \;
}
$m^\star_i = \bwdmsg_i + \fwdmsg_i - \phi_i$\;
}
\BlankLine
$\mmi \defn m^\star_i[y_i],\; \forall y_i \in \cY_i$\;

\end{algorithm}