inference-alg.tex

\begin{algorithm} 
\dontprintsemicolon
\caption[max-sum inference]{Max-sum message passing to solve 
$$\argmax_{y \in 
\cY} s(x,y) = \argmax_{y \in \cY} \sum_{i \in \cV} \phi_i + \sum_{ij \in \cE} 
\phi_{ij}$$} \label{alg:max-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{$y^\star = \argmax_{y} s(x,y)$}

\BlankLine
\For{$i = \pi_1, \pi_2, \ldots, \pi_n $ }{
$m_i = \phi_i + \sum_{j \in \text{kids}(i)} m_{j \rightarrow i}$\;
\If{$i == r$}{
break\;
}
$p = \texttt{parent}_\pi(i) $ \;
$m_{i \rightarrow p} = \max_{y_i} \phi_{ip} + m_i$ \;
$a_i = \argmax_{y_i} \phi_{ip} + m_i$ \;
}
$y^\star_r = \argmax m_r$\;
\For{$i = \pi_{n-1},\pi_{n-2},\ldots,1$}{
$y^\star_i = a_i\left[y^\star_{\texttt{parent}_\pi(i)}\right]$
}

\end{algorithm}