# Gaussian Mixture Reduction for Time-Constrained Approximate Inference in Hybrid Bayesian Networks +
## 2 Preliminaries
### Hybrid Message Passing Inference
#### 2.1.2 Message Passing Inference for Discrete BN  
Message passing inference for a discrete BN was introduced in Reference [1]. A discrete BN contains only discrete nodes (i.e., Type 1 in Figure 1). The objective of inference is to compute the function  
\[BEL(B)=P(B|e) \tag{2}\]  
for each node \(B\) in the Bayesian network. Here, \(B\) denotes a node with its associated RV, \(e\) is a set of evidence events consisting of state assignments for nodes in the network and BEL(\(B\)) is the conditional distribution of \(B\) given the values of the evidence RVs. If the BN is a polytree (has no undirected cycles), the evidence \(e\) can be split into two components, \(e_{B}^{+}\) and \(e_{B}^{-}\), where \(e_{B}^{+}\) relates only to non-descendants of \(B\) and \(e_{B}^{-}\) relates only to descendants of \(B\). Equation (2) can be decomposed as follows:  
\[P(B|e) =\alpha P(B|e_{B}^{+},e_{B}^{-})\] \[=\alpha P(B|e_{B}^{+})P(B|e_{B}^{-})\] \[=\alpha\pi(B)\lambda(B),\]  
where \(\alpha\) denotes a normalizing constant. The second line is valid because in a polytree, \(e_{B}^{+}\) and \(e_{B}^{-}\) are independent given \(B\). The factors relating to non-descendants and descendants are denoted \(\pi(B)\) and \(\lambda(B)\), as shown in the third line of the equation. These factors are called the Pi and Lambda functions, respectively.  
The Pi function \(\pi(B)\) and Lambda function \(\lambda(B)\) can be written as follows:  
\[\pi(B)=\sum_{\mathbf{A}}P(B|\mathbf{A})\prod_{i}\pi_{B}(A_{i}) \tag{3}\]  
and  
\[\lambda(B)=\prod_{j}\lambda_{C_{j}}(B), \tag{4}\]  
where \(\pi_{B}(A_{i})\) and \(\lambda_{C_{j}}(B)\) denote a Pi message from the parent \(A_{i}\) to \(B\) and Lambda message from the child \(C_{j}\) to \(B\), respectively. These messages can be written as follows:  
\[\pi_{C_{j}}(B)=\alpha\left[\prod_{k\
eq j}\lambda_{C_{k}}(B)\right]\pi(B) \tag{5}\]  
Figure 1: Possible Node Types for a Conditional Gaussian Hybrid BN (rectangle denotes discrete node; circle denotes continuous node).  
\[\lambda_{B}(A_{i})=\sum_{B}\lambda(B)\sum_{A_{k}:k\
eq i}P(B|\mathbf{A})\prod_{k \
eq i}\pi_{B}(A_{k}) \tag{6}\]  
Note that the Lambda function \(\lambda(B)\) is similar to the Pi message \(\pi_{C_{j}}(B)\) except that the Pi message includes a factor of \(\pi(B)\), includes Lambda messages for all children of the parent except the target child node \(j\) and includes a normalizing constant \(\alpha\). A similar relationship exists between the Pi function \(\pi(B)\) and the Lambda message \(\lambda_{B}(A_{i})\). The Lambda message multiplies by \(\lambda(B)\) and includes Pi messages only from parent nodes other than the target parent node \(i\).  
The MP algorithm is given as follows.  
1. _Initialization_: For any evidence node \(B=b\), set \(\pi(B)=\lambda(B)\) to 1 for \(B=b\) and 0 for \(B\
eq b\). For any non-evidence node with no parents, set \(\pi(B)\) to the prior distribution for \(B\). For any non-evidence node \(B\) with no children, set \(\lambda(B)\) uniformly equal to 1.
2. _Iterate_ until no change occurs: * For each node \(B\), if \(B\) has received Pi messages from all its parents, then calculate \(\pi(B)\). * For each node \(B\), if \(B\) has received Lambda messages from all its parents, then calculate \(\lambda(B)\). * For each node \(B\), if \(\pi(B)\) has been calculated and \(B\) has received Lambda messages from all its children except \(C\), calculate and send the Pi message from \(B\) to \(C\). * For each node \(B\), if \(\lambda(B)\) has been calculated and \(B\) has received Pi messages from all its parents except \(A\), calculate and send the Lambda message from \(B\) to \(A\).
3. _Calculate_\(P(B\,|\,e)=\alpha\pi(B)\lambda(B)\) for each node B.  
This algorithm finds exact values of all \(\pi(B)\) if the network is a polytree. The algorithm can also be applied to BNs containing undirected cycles. It is not guaranteed to converge but when it converges, it often results in a good approximation to the correct posterior probabilities [30].