%latex
\documentstyle[fleqn,epsf]{article}
%\documentstyle[psfig]{article}

%latex2e
%\documentclass{article}
%\usepackage{epsfig,alltt,fancybox}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parindent}{0in} % block style
\setlength{\parskip}{0.3cm}

\date{4/9/99}
\author{Kevin Murphy}
\title{Multiplexer nodes in Pearl's algorithm}

\begin{document}
\maketitle

In this section, we derive the equations that a multiplexer node needs
to use to implement Pearl's algorithm \cite{Pearl88}. (A multiplexer node is a
deterministic node with conditional distribution
$P(X|M_1, \ldots, M_n, S=i) = 1.0$ is $X=M_i$ and is 0.0 otherwise,
where $S \in \{1, \ldots, n\}$ is the switch node and $M_i \in \{1, \ldots, k\}$,
is the $i$'th multiplexer input.)
The derivation is similar in spirit to the one on Pearl p189 for
noisy-or nodes. The key point is to avoid summing over all possible
$O(k^n)$ parent values. Note that the marginals on the
parents will be computed correctly, even though we do not add any moral edges
to reflect their correlation (which would generate a clique of size $n+2$).

\newcommand{\ra}{\rightarrow}
\newcommand{\lambdamsg}[2]{\mbox{$\lambda_{#1 \rightarrow #2}$}} % from to
\newcommand{\pimsg}[2]{\mbox{$\Pi_{#1 \rightarrow #2}$}} % from to
\newcommand{\hatpimsg}[2]{\mbox{$\hat{\Pi}_{#1 \rightarrow #2}$}} % from to
\newcommand{\myvec}{\mbox{vec}}
\newcommand{\defeq}{\stackrel{\rm def}{=}}

We first restate the results from Pearl p183 for the case of a general
discrete node $X$ with parents $U_i$ and children $Y_j$.
Since the graph is singly connected, each edge $X \ra Y$ partitions
the evidence $e$ into an upstream $e^+_{X \ra Y}$ and downstream
$e^-_{X \ra Y}$ component.
In addition, we define $e^+_X$ to be the evidence upstream of node $X$
(i.e., all the evidence separated from $X$ if its incoming arcs were
deleted), and $e^-_X$ to be the remaining evidence (including evidence
in $X$ itself, if any).
(Following Peot and Shachter \cite{Peot91}, we include the evidence by letting a
node $X$ send a message to itself, $\lambdamsg{X}{X}(x)$. However, we
scale the messages as in Pearl, to simplify the derivation, and to
prevent underflow.)

\begin{eqnarray*}
{\rm bel}_X(x) &\defeq& \Pr(X=x | e)
 = \alpha \lambda_X(x) \pi_X(x) \\
\lambda_X(x) &\defeq& P(e^-_X|X=x) 
 = \lambdamsg{X}{X}(x) \times \prod_j \lambdamsg{Y_j}{X}(x) \\
\pi_X(x) &\defeq& \Pr(X=x|e^+_X)
  = \sum_{u}  P(X=x|u) \prod_i \pimsg{U_i}{X}(u_i) \\
\lambdamsg{X}{U_i}(u_i) &\defeq& \Pr(e^-_{U_i \ra X}|U_i=u)
 = \beta \sum_x \lambda_X(x)
     \left[ \sum_{u_k: k \neq i}  P(X=x|u) \prod_{k \neq i}  \pimsg{U_k}{X}(u_k) \right] \\
\pimsg{X}{Y_j}(x) &\defeq& \Pr(X=x|e^+_{X \ra Y_j})
  = \alpha \pi_X(x) \lambdamsg{X}{X}(x) 
   \prod_{k \neq j} \lambdamsg{Y_k}{X}(x)  
\end{eqnarray*}
where $\alpha$ is a normalizing constant and $\beta$ is an arbitrary
constant.

In the special case where the graph is a tree, so each node has a
unique parent, these equations can be simplified as follows.
\begin{eqnarray*}
\lambda_X(x) &=& \lambdamsg{X}{X}(x) \prod_{c \in {\rm children}(X)} \lambdamsg{Y_c}{X}(x) \\
%\lambda_X(x) &=& \lambdamsg{X}{X}(x) \prod_{c \in {\rm children}(X)} \sum_y P(Y_c=y | X=x) \\
\pi_X(x) &=& \sum_u P(X=x|u) \pi_U(u) \prod_{s \in {\rm siblings}(X)} \lambdamsg{X_s}{U}(u)
\end{eqnarray*}
where
\[
\lambdamsg{Y_c}{X}(x) = \beta \sum_y P(Y_c=y | X=x)  \lambda_{Y_c}(y)
\]


\section{Multiplexer node}

We now derive the equations for $\pi_X(x)$ and $\lambdamsg{X}{U_i}$
in such a way as to avoid explicitely summing over all parent values.

Let us divide the parents into $U=(S,M_1,\ldots,M_n)$, and fix $n=2$
for notational simplicity. We first derive $\pi_X(x)$ as follows.

\begin{eqnarray*}
\pi_X(x)
&=& \sum_s \sum_{m_1, m_2} P(x|m_1,m_2,s) \pimsg{S}{X}(s) \pimsg{M_1}{X}(m_1) \pimsg{M_2}{X}(m_2) \\
 &=& \sum_{m_1, m_2}   \pimsg{S}{X}(1) \delta(x,m_1) \pimsg{M_1}{X}(m_1) \pimsg{M_2}{X}(m_2)  \\
  && \; + \; \sum_{m_1, m_2} \pimsg{S}{X}(2) \delta(x,m_2) \pimsg{M_1}{X}(m_1) \pimsg{M_2}{X}(m_2)  \\
 &=&    \pimsg{S}{X}(1) \pimsg{M_1}{X}(x) \sum_{m_2} \pimsg{M_2}{X}(m_2)  
      + \pimsg{S}{X}(2) \sum_{m_1} \pimsg{M_1}{X}(m_1) \pimsg{M_2}{X}(x)  \\
 &=&
 \pimsg{S}{X}(1) \pimsg{M_1}{X}(x) + \pimsg{S}{X}(2) \pimsg{M_2}{X}(x) \\
\end{eqnarray*}
where we have used the fact that
\[
\sum_{u_i} \pimsg{U_i}{X}(u_i) = \sum_{u_i} P(u_i | e^+_{U_i X}) = 1
\]
In general we have
\[
\pi_X(x) = \sum_{i=1}^n \pimsg{S}{X}(i) \pimsg{M_i}{X}(x)
\]
Now let us define the vector
\begin{eqnarray*}
\pimsg{S}{X} & = &
  \pmatrix{\pimsg{S}{X}(1), \ldots, \pimsg{S}{X}(n)}^T
\end{eqnarray*}
and the matrix
\[
\pimsg{M}{X} =
\pmatrix{
\pimsg{M_1}{X}(1) & \ldots & \pimsg{M_n}{X}(1) \cr
\vdots            & \ddots & \vdots \cr
\pimsg{M_1}{X}(k) & \ldots & \pimsg{M_n}{X}(k) \cr
}
\]

Then we can restate the above result more concisely as
\[
\pi_X = \pimsg{M}{X} \pimsg{S}{X}
\]

To compute an expression for the lambda messages, we consider the term
\[
W_i(x, u_i) = \sum_{u_k: k \neq i}  P(x|u) \prod_{k \neq i} \pimsg{U_k}{X}(u_k)
\]

We first consider the case where we avoid summing over a multiplexer input,
say $U_i = M_j$. This is just like computing $\pi(x)$, except we don't
sum over $m_j$ and exclude the term $\pimsg{M_j}{X}$.
For concreteness, consider the case $j=1$.
\begin{eqnarray*}
W_1(x,m)  &=& 
  \sum_{m_2} \pimsg{S}{X}(1) \delta(x,m_1) \pimsg{M_2}{X}(m_2) +
  \sum_{m_2} \pimsg{S}{X}(2) \delta(x,m_2) \pimsg{M_2}{X}(m_2) \\
&=&
  \pimsg{S}{X}(1) \delta(x,m_1) +
  \pimsg{S}{X}(2) \pimsg{M_2}{X}(x) 
\end{eqnarray*}
In general, we have
%\begin{eqnarray*}
%W_j(x,m)  &=&
% \pimsg{S}{X}(j) \delta(x,m) +
%  \sum_{i \neq j} \pimsg{S}{X}(i) \pimsg{M_i}{X}(x)
%\end{eqnarray*}
\begin{eqnarray*}
W_j(x,m) &=& \pimsg{S}{X} \cdot \pimsg{M}{X}^{j,x,m}
\end{eqnarray*}
where $u \cdot v$ is the inner product between vectors $u$ and $v$,
and $\pimsg{M}{X}^{j,x,m} = \pimsg{M}{X}(x,:)$ with the $j$'th element
replaced by $\delta(x,m)$.

Then we have
\begin{eqnarray*}
\lambdamsg{X}{M_j}(m) &=& \beta \sum_x \lambda_X(x) W_j(x,m)
\end{eqnarray*}
or
\begin{eqnarray*}
\lambdamsg{X}{M_j} &=& \beta W_j^T \lambda_X
\end{eqnarray*}

Finally, we consider the case where we avoid summing over the
switching gate, $U_i = S$.
\begin{eqnarray*}
W_S(x,s) &=&
 \sum_{m_1, m_2} P(x|m_1,m_2,s) \pimsg{M_1}{X}(m_1) \pimsg{M_2}{X}(m_2) \\
& = & \pimsg{M_s}{X}(x)
\end{eqnarray*}
Hence
%\begin{eqnarray*}
%\lambdamsg{X}{S}(s) &=&
%  \beta \sum_x \lambda_X(x) \pimsg{M_s}{X}(x,s)
%\end{eqnarray*}
%or
\[
\lambdamsg{X}{S} = \beta \pimsg{M}{X}^T \lambda_X
\]


\section{Two-dimensional multiplexer node}

Now consider a node which has an $R \times C$ array of inputs and two
gates, $R$ and $C$, to select which element gets passed to $X$.

Let us make the following definitions.
\[
\pimsg{M}{X}(x) =
\pmatrix{
\pimsg{M_{1,1}}{X}(x) & \ldots & \pimsg{M_{1,c}}{X}(x) \cr
\vdots            & \ddots & \vdots \cr
\pimsg{M_{R,1}}{X}(x) & \ldots & \pimsg{M_{R,C}}{X}(x) \cr
}
\]

\[
\hatpimsg{M}{X} =
\pmatrix{
\myvec(\pimsg{M}{X}(1))^T & \ldots & \myvec(\pimsg{M}{X}(1))^T \cr
\vdots            & \ddots & \vdots \cr
\myvec(\pimsg{M}{X}(k))^T & \ldots & \myvec(\pimsg{M}{X}(k))^T \cr
}
\]
where
$\myvec A = (A_{1,1}, \ldots, A_{R,1}, A_{1,2}, \ldots, A_{R,C})^T$
is the columns of $A$ concatenated into a column
vector with $n=R \times C$ elements.

\[
\pimsg{R}{X} \pimsg{C}{X}^T =
\pmatrix{
\pimsg{R}{X}(1) \pimsg{C}{X}(1) & \ldots & \pimsg{R}{X}(1) \pimsg{C}{X}(C) \cr
\vdots            & \ddots & \vdots \cr
\pimsg{R}{X}(R) \pimsg{C}{X}(1) & \ldots & \pimsg{R}{X}(R) \pimsg{C}{X}(C) \cr
}
\]

\[
\hatpimsg{RC}{X} = \myvec( \pimsg{R}{X} \pimsg{C}{X}^T)
\]

Hence we have
\[
\pi_X = \hatpimsg{M}{X} \hatpimsg{RC}{X}
\]

Now we consider how to compute the lambda messages.
If we don't sum out over $M_{r,c}$, we get
\[
W_{r,c}(x,m) = \hatpimsg{RC}{X} \cdot
  \myvec(\pimsg{M}{X}(x)^{r,c,x,m})
\]
where $\pimsg{M}{X}(x)^{r,c,x,m}$ = $\pimsg{M}{X}(x)$ with element
$(r,c)$ replaced by $\delta(x,m)$.

Now suppose we don't sum out over $R$.
For purposes of illustration, let $r=1$ and $R=C=2$.
\begin{eqnarray*}
W_{R}(x,1) &=&  \sum_{c=1}^2
%\sum_{m_1,m_2,m_3,m_4}  P(x|m_1,m_2,m_3,m_4,R=1,C=c) \pimsg{C}{X}(c) \\
%\sum_{m}  P(x|m,R=1,C=c) \pimsg{C}{X}(c) \\
\sum_{m_{1,1}} \sum_{m_{1,2}} \sum_{m_{2,1}} \sum{m_{2,2}}
  P(x|m_{1,1},m_{1,2},m_{2,1},m_{2,2},R=1,C=c) \pimsg{C}{X}(c) \\
 && \times \pimsg{M_{1,1}}{X}(m_{1,1})   \pimsg{M_{1,2}}{X}(m_{1,2})
   \pimsg{M_{2,1}}{X}(m_{2,1})   \pimsg{M_{2,2}}{X}(m_{2,2}) \\
 &=& \sum_{m_{1,1}} \delta(x, m_{1,1}) \pimsg{M_{1,1}}{X}(m_{1,1}) \pimsg{C}{X}(1) 
  + \sum_{m_{1,2}} \delta(x, m_{1,2})  \pimsg{M_{1,2}}{X}(m_{1,2}) \pimsg{C}{X}(2) \\
 &=& \pimsg{M_{1,1}}{X}(x) \pimsg{C}{X}(1) 
  + \pimsg{M_{1,2}}{X}(x) \pimsg{C}{X}(2) 
\end{eqnarray*}
In general,
\[
W_R(x,r) = \pimsg{C}{X} \cdot \pimsg{M_{r,\cdot}}{X}
\]
Hence
\[
\lambdamsg{X}{R}(r) = \beta \sum_x \lambda_X(x) W_R(x,r)
\]
becomes
\[
\lambdamsg{X}{R} = \beta W_R^T \lambda_X
\]
Similarly,
\[
W_C(x,c) = \pimsg{R}{X} \cdot \pimsg{M_{\cdot,c}}{X}
\]
and
\[
\lambdamsg{X}{C} = \beta W_C^T \lambda_X
\]


\bibliography{../../dna}
\bibliographystyle{alpha}


\end{document}



\section{Noisy-or nodes}

We can rephrase the results in Pearl p189 for the noisyor distribution
using our notation as follows.
Let $q$ be the inhibition vector for $X$, and $c=1-q$, and assume
$\pimsg{U_i}{X}(0) + \pimsg{U_i}{X}(1) = 1$.
Then Eqn 4.60 becomes
\begin{eqnarray*}
t(x=0,u_i=0) &=& \Pi'_i \\
t(x=1,u_i=0) &=& 1-\Pi'_i \\
t(x=0,u_i=1) &=& q_i \Pi'_i \\
t(x=1,u_i=1) &=& 1- q_i\Pi'_i \\
\end{eqnarray*}
where (Eqn 4.61)
\[
\Pi'_i = \prod_{k \neq i} (1 - c_k \pimsg{U_k}{X}(1))
\]
Finally, Eqn 4.57 becomes
\begin{eqnarray*}
\pi(x) &=& \prod_{k} (1 - c_k \pimsg{U_k}{X}(1)) 
  \mbox{ if $x = 0$ } \\
\pi(x) &=& 1 - \prod_{k} (1 - c_k \pimsg{U_k}{X}(1)) 
  \mbox{ if $x = 1$ } 
\end{eqnarray*}

