{'fraction_non_alphanumeric': 0.03850456031664085, 'fraction_numerical': 0.0172517638960592, 'mean_word_length': 4.266198459447214, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Inference in Hybrid Bayesian Networks Using Mixtures of Gaussians

The main goal of this paper is to describe a method for exact inference in general hybrid Bayesian networks (BNs) (with a mixture of discrete and continuous chance variables). Our method consists of approximating general hybrid Bayesian networks by a mixture of Gaussians (MoG) BNs. There exists a fast algorithm by Lauritzen-Jensen (LJ) for making exact inferences in MoG Bayesian networks, and there exists a commercial implementation of this algorithm. However, this algorithm can only be used for MoG BNs. Some limitations of such networks are as follows. All continuous chance variables must have conditional linear Gaussian distributions, and discrete chance nodes cannot have continuous parents. The methods described in this paper will enable us to use the LJ algorithm for a bigger class of hybrid Bayesian networks. This includes networks with continuous chance nodes with non-Gaussian distributions, networks with no restrictions on the topology of discrete and continuous variables, networks with conditionally deterministic variables that are a nonlinear function of their continuous parents, and networks with continuous chance variables whose variances are functions of their parents.


INTRODUCTION
This paper is about making exact inferences in hybrid Bayesian networks, i.e., Bayesian networks with a mix of discrete, continuous, and conditionally deterministic variables. One of the earliest algorithms for this class of problems was proposed by Lauritzen [1992], and later revised by Lauritzen and Jensen [2001]. We refer to this algorithm as the LJ algorithm. The LJ algorithm applies only to Bayesian networks where the continuous variables have the so-called conditional linear Gaussian distributions, and to networks such that discrete variables do not have continuous parents. In this case, for every instantiation of the discrete variables, the joint distribution of the continuous variables is multivariate Gaussian.
Thus, we will refer to such Bayesian networks as mixtures of Gaussians (MoG) Bayesian networks. The LJ algorithm is implemented in Hugin, a commercially available software.
One approach to exact inference in hybrid Bayesian networks is suggested by Murphy [1999] and . This approach is only applicable to so-called "augmented CLG networks," which are hybrid Bayesian networks with conditional linear Gaussian distributions for continuous variables, and which allow discrete variables with continuous parents. The main idea of this approach is to approximate the product of a Gaussian and a logistic distribution (for discrete variables with continuous parents) by a variational approximation [Murphy 1999] or by mixture of Gaussians using numerical integration ]. This idea is then embedded within the general framework of the LJ algorithm.
Another approach to exact inference in hybrid Bayesian networks is based on the idea by Moral et al. [2001] of using mixtures of truncated exponentials to approximate arbitrary probability density functions (PDFs). This idea was further explored by Cobb and Shenoy [2006a], and they describe how mixtures of truncated exponentials can be estimated to approximate any PDF using an optimization procedure [Cobb et al. 2004], and applied to hybrid Bayesian networks with linear deterministic variables [Cobb and Shenoy 2005a] and also to hybrid Bayesian networks with non-linear deterministic variables [Cobb and Shenoy 2005b].
In this paper, we explore an alternative strategy for exact inference in hybrid Bayesian networks. It is well known that mixtures of Gaussians can approximate any probability distribution [Titterington et al. 1985]. Thus, in principle, it should be possible to solve any hybrid Bayesian networks by first approximating such a network by a MoG Bayesian network, and then using the LJ algorithm to solve the MoG Bayesian network exactly. In this paper, we describe how this can be done. First we describe how non-Gaussian distributions can be approximated by a MoG distribution using an optimization method similar to that used by Cobb et al. [2004]. Second, we describe how to transform a network in which a discrete variable has continuous parents to a network where discrete variables do not have continuous parents using a series of arc reversals. Arc reversals were initially proposed by Olmsted [1983] and Shachter [1986] in the context of solving influence diagrams. Third, we show how a Bayesian network with conditionally deterministic nodes that are a nonlinear function of their parents can be approximated by a MoG Bayesian network. We approximate a nonlinear function by a piecewise linear function. Finally, we show how a BN with a conditional Gaussian distribution whose variance is a function of its parents can be approximated by a MoG BN.
An outline of the remainder of this paper is as follows. In section 2, we describe how a mixture of Gaussians can approximate a non-Gaussian distribution. In section 3, we describe how a Bayesian network in which some discrete variables have continuous variables can be converted to a MoG Bayesian network. In section 4, we describe how a Bayesian network with conditionally deterministic nodes that are a nonlinear function of their parents can be approximated by a MoG Bayesian network. In section 5, we describe how a Bayesian network with a conditional Gaussian distribution whose variance is a function of its parents can be approximated by a MoG Bayesian network. In section 6, we solve a small example to illustrate our technique. Finally in section 7, we conclude with a summary and some issues for future research.

NON-GAUSSIAN DISTRIBUTIONS
In this section, we will describe a methodology for approximating any non-Gaussian distribution by a MoG distribution. Poland and Shachter [1993] describe a method based on the EM algorithm [Dempster et al. 1977] for approximating continuous distributions by mixtures of Gaussians. Here we will describe an alternative method based on minimizing some measure of distance between two distributions to find a good approximation of a non-Gaussian distribution by a MoG distribution. We will illustrate our method for the uniform distribution over the unit interval [0, 1].
Let A denote a chance variable that has the uniform distribution over the unit interval, denoted by U[0, 1], and let f A denote its probability density function (PDF). Thus In approximating the PDF f A by a mixture of Gaussians, we first need to decide on the number of Gaussian components needed for an acceptable approximation. In this particular problem, more the components used, better will be the approximation. However, more components will lead to a bigger computational load in making inferences. We will measure the goodness of an approximation by estimating the Kullback-Liebler [1951] divergence measure between the target distribution and the corresponding MoG distribution.
Suppose we decide to use five components. Then we will approximate f A by the mixture PDF g A = p 1 μ 1 , 1 +… + p 5 μ 5 , 5 , where μ i , i denote the PDF of a uni-variate Gaussian distribution with mean μ i and standard deviation i > 0, p 1 , …, p 5 0, and p 1 +…+ p 5 = 1. To estimate the mixture PDF, we need to estimate fourteen free parameters, e.g., p 1 , …, p 4 , μ 1 , …, μ 5 , 1 , …, 5 . Based on the symmetry of f A around a = 0.5, we can reduce the number of free parameters to 7 by assuming that p 1 = p 5 , p 2 = p 4, μ 3 = 0.5, μ 4 = 1-μ 2 , μ 5 = 1-μ 1 , 1 = 5, and 2 = 4 . To find the values of the 7 free parameters, we solve a non-linear optimization problem as follows: Find p 1 , p 2, μ 1 , μ 2, 1 , 2 , 3 so as to minimize (f A , g A ) subject to: p 1 0, p 2 0, 2p 1 +2p 2 1, 1 0, 2 0, 3 0, where (f A , g A ) denotes a distance measure between two PDFs. A commonly used distance measure that is easy to optimize is the sum of squared errors SSE defined as follows: In practice, we solve a discrete version of the non-linear optimization problem by discretizing both f A and g A using a large number of bins. To discretize g A , we assume that the domain of μ i , i extends only from μ i -3 i to μ i +3 i . To match the domain of the U[0, 1] distribution, we constrain the values μ i -3 i 0, and μ i +3 i 1 for i = 1, …, 5. Suppose we divide the domain [0, 1] into n equally sized bins. Let f i and g i denote the probability masses for the i th bin corresponding to PDFs f A and g A , respectively Then the discrete version of the non-linear programming problem can be stated as follows: i=1 n subject to: p 1 0, p 2 0, 2p 1 +2p 2 1, 1 0, 2 0, 3 0, μ 1 -3 1 0, μ 2 -3 2 0, 0.5 -3 3 0.
One can use the solver in Excel to solve such optimization problems taking care to avoid local optimal solutions. An optimal solution computed in Excel with n = 100 (shown rounded to 3 digits) is as follows: p 1 = p 5 = 0.169, p 2 = p 4 = 0.070, p 3 = 0.522, μ 1 = 0.069, μ 2 = 0.197, μ 3 = 0.5, 1 = positive, i.e., [0,1]. The KL divergence is approximately 0.042. We can also compare moments. The mean and variance of the U[0, 1] distribution are 0.5 and 0.083. The mean and variance of the MoG approximation are 0.5 and 0.073. We can also compare the cumulative distribution functions (CDF). A graph of the two CDFs overlaid over each other is shown in Figure 2.  In a Bayesian network, chance node A with the U[0, 1] distribution is approximated by a Bayes net component that has a discrete variable S with five states and a continuous variable A whose conditional distributions are conditional linear Gaussians as shown in Figure 3. Borrowing the convention from Hugin, discrete nodes are depicted by single border ovals and continuous variables are denoted by double border ovals. The marginal distribution of A is approximately uniform over the unit interval. The selector variable S has no significance. It is just a synthetic variable whose only role is to provide weights for the mixture distribution.
If we wish to model a uniform distribution over the range [a, b], denoted by U [a, b], then one easy way is to introduce a conditionally deterministic variable C, which is a linear function of A as follows: a, b]. Alternatively, we can find a mixture of Gaussians approximation of U [a, b] directly, by having the selector variable S with the same distribution as before, and changing the conditional linear Gaussian distributions of A as follows:

DISCRETE NODES WITH CONTINUOUS PARENTS
MoG Bayesian networks do not allow discrete nodes with continuous parents. Often in the process of modeling situations, we are faced with a network in which some discrete nodes have continuous parents. In this section, we describe a method for approximating such Bayesian networks by MoG Bayesian networks.
Since MoG Bayesian networks do not allow discrete nodes with continuous parents, we change the topology of the network using arc reversals. Given a Bayesian network, we perform a series of arc reversals so that all discrete nodes precede continuous variables in any ordering that is compatible with the arcs in the Bayesian network (in the sense that if we have an arc from X to Y, then X precedes Y in the ordering). After we have completed the arc reversals, we then proceed to approximate the conditional distributions of continuous nodes by mixtures of Gaussians using the technique described in the previous section. We will illustrate our proposed method using a simple example.
Consider a Bayesian network with two chance variables A and B, and an arc from A to B. A is a continuous variable with the standard normal N(0, 1) distribution, and B is a binary discrete chance variable with states b and nb, whose conditional distribution is given by the logistic function: A graph of the logistic function is shown in Figure 4. Notice that the logistic function is symmetric about the axis a = 0 in the sense that P(b | a) = 1 -P(b | -a) for a > 0. Also, P(nb | a) = 1 -P(b | a) = P(b | -a).
Since the joint distribution of A and B is mixed (with probability masses and densities), we will describe it using the notation of mixed potentials introduced in Cobb and Shenoy [2005a]. The values of a mixed potential have two parts, mass and density. When we have only probability masses for discrete variables, we will use the symbol in the density part to denote an absence of density (or vacuous density), and it has the property that it is an identity for the semigroup of density potentials with the pointwise multiplication operation. Thus the potential for A is given by (a) = (1, 0,1 (a)), where 0,1 (a) is the PDF of the standard normal distribution. The 1 in the mass part can be interpreted as a weight for the density value in the density part. The potential for {A, B} representing the conditional distribution of B given A is given by  To reverse the arc from A to B, we perform the usual operations. First, we combine the mixed potentials associated with A and B using pointwise multiplication of the corresponding mass and density parts. The combination is denoted by . Thus, is a potential for {A, B} given by Next, we find the marginal for B by marginalizing A out of the joint potential . Since A is a continuous variable, it is marginalized out by integrating the product of the mass and density parts over the domain of A. We denote the marginal by ( ) B or ( ) A , depending on whether we wish to emphasize the variables that remain, or the variables that are marginalized out. Thus In general, we may have to do a numerical integration to do this operation if the integrals are not easily done in closed form. In our case, since both the logistic and density function are symmetric about the axis a = 0, the results can be deduced.
Next, to compute the conditional distributions for A given B, we divide the joint potential by the marginal ( ) B using pointwise division. We denote the division by ( ) ( ) B . Thus, Finally, we need to approximate the conditional density functions (2/(1+e 2a )) 0,1 (a) and (2e 2a /(1+e 2a )) 0,1 (a) by mixtures of Gaussians. To do this, we use the technique described in the previous section. We used only two components to approximate these density functions, and an approximation is given as follows (computed in Excel using n = 600, parameters rounded to 3 decimal places): (2/(1+e 2a )) 0,1 (a) 0.   We have completed approximating the mixed Bayesian network by a mixture of Gaussians (MoG) Bayesian network. The original Bayesian network and its MoG approximation are shown in Figure 6.
To verify the quality of the approximation, we implemented the MoG approximation in Hugin and computed the following quantities. The marginal distribution of A has mean 0 and variance 0.96 (compared to the exact mean 0 and variance 1). An observation, e.g., of A = 1 yields marginal probability P(B = b | A = 1) = 0.876 (compared to 0.881 given by the exact model).

NON-LINEAR CONDITIONALLY DETERMINISTIC NODES
In this section, we examine the problem of representing a Bayesian network with a non-linear conditionally deterministic variable as a MoG Bayesian network.
Consider a Bayesian network with two continuous variables A and B such that A ~ N(0, 1), and B|a ~ N(a 2 , 0). Since the conditional distribution of B is not linear Gaussian, this is not a MoG Bayesian network. The chance variable B is a deterministic function of A, B|a = a 2 with probability 1. We say B is "conditionally deterministic," and we depict conditionally deterministic variables with triple-bordered circles. A BN graph for this example is shown in Figure 8.
To approximate this Bayesian network by a MoG Bayesian network, we employ the same idea as in Cobb and Shenoy [2005b]. We approximate the non-linear deterministic function B|a = a 2 by a piecewise linear function. Suppose, e.g., we approximate the deterministic function B|a = a 2 by a six-segment piecewise linear approximation as follows: B|a = -5a -6 for -a < -2 = -3a -2 for -2 a < -1 = -a for -1 a < 0 = a for 0 a < 1 = 3a -2 for 1 a < 2 = 5a -6 for 2 a A graph of the piecewise linear approximation appears overlaid on the actual function in Figure 7. Next, we approximate the Bayesian network with the network shown in Figure  8. In this Bayesian network, S is a discrete indicator variable with six states corresponding to the six regions of the piecewise linear approximation. The conditional probability distribution for S is as follows. If a is in region i, then P(S = s i | a) = 1, P(S = s j | a) = 0 for j i. The conditional probability distribution of B given a and s i is given by the linear approximation of a 2 in the region s i .   The Bayesian network shown in the right-hand side of Figure 8 is not a MoG since S, which is discrete, has a continuous parent. We can approximate this BN by a MoG BN using the technique described in the previous section. The resulting MoG BN is shown in Figure 9. To verify the quality of the approximation this MoG BN was entered in Hugin. The mean of B is reported as 1.12 and the variance is reported as 1.64. Since B has a chi-square distribution with 1 degree of freedom, its true mean is 1 and its variance is 2.

NON-CONSTANT VARIANCE
In CLG distributions, the variance of the conditional Gaussian distribution is a constant. In this section, we examine the case where a continuous node has a Gaussian distribution with a variance that is a function of its parents. A and B, such that A ~ N(3, 1) and B|a ~ N(a, a 2 ). Notice that although the conditional distributions of B are Gaussian, the marginal distribution of B is not Gaussian. A graph of the probability density function of B is shown in Figure 10. To approximate the joint distribution of A and B with a MoG distribution, we divide the domain of A into many small segments, and in each segment, we approximate the conditional distribution of B by a CLG distribution. We introduce a discrete variable S with state space {s 1 , …, s 6 }. The variable S indicates which segment A lies in. Suppose we partition the domain of A into six segments as follows (-, 1), [1, 2), …, [5, ). Thus, the conditional probability distribution for S is as follows. If a is in segment i, then P(S = s i | a) = 1, P(S = s j | a) = 0 for j i. Next, we approximate the conditional distribution of B (with A and S as its parents) with a CLG distribution as follows: B|a, s 1 ~ N(a, 0.5 2 ), B|a, s 2 ~ N(a, 1.5 2 ), B|a, s 3 ~ N(a, 2.5 2 ), B|a, s 4 ~ N(a, 3.5 2 ), B|a, s 5 ~ N(a, 4.5 2 ), B|a, s 6 ~ N(a, 5.5 2 ). The resulting BN, shown in Figure 11, is not a MoG since discrete variable S has continuous variable A as its parent. We reverse the arc A S as we did in the previous section resulting in the MoG BN shown in Figure 12.

AN EXAMPLE
In this section, we describe a slightly more complicated example with a mix of discrete, continuous, and conditionally deterministic variables. To approximate the non-MoG Bayesian network with a MoG Bayesian network, we need to do a series of arc reversals and approximate the resulting non-Gaussian PDFs with MoGs.
Consider a hybrid Bayesian network consisting of four variables as shown in Figure 13. This BN has two discrete and two continuous variables. One of the continuous variables is conditionally deterministic given its parent.
Although the distributions of the continuous variables are conditional linear Gaussian, the BN is not MoG since the discrete variable D has a continuous parent. This BN is an example of an augmented CLG model studied by Murphy [1999] and .

ARC REVERSALS
A few words about arc reversals. First, a necessary condition for an arc to be reversible is that the two variables defining the arc have to be "adjacent." Two variables are said to be adjacent if there is a sequence of variables compatible with the arcs in a Bayes net (in the sense described earlier) such that the two variables are adjacent. Thus in the Bayes net in Figure 13, the following pairs of variables are adjacent: {A, B}, {B, C}, {C, D}. Second, an arc with a continuous conditionally deterministic variable at its tail cannot be reversed. This is because one of the operations involved in arc reversal is the computation of the conditional joint distribution (conditional on the union of the parents of the two variables) of the two variables defining the arc. This operation cannot be performed when we have only an equation defining the conditional distribution for the deterministic variable. Thus, in our example, the arc (C, D) cannot be reversed. An arc between two adjacent variables such that the variable at the head of the arc is deterministic can be reversed. The mechanics for reversing such arcs are slightly different from the usual operations for arc reversal [Cobb and Shenoy 2006b]. Consider the arc (B, C) in which B is a continuous variable and C is a continuous conditionally deterministic variable. The conditional joint density for {B, C} (given A) does not exist. However the conditional marginal density for C (given A) does exist. Also, the conditional distribution for B given C (and A) is not a density function, but a deterministic function given by the inverse of the original deterministic function defining C.
In our example, after arc reversal, the distributions of B and C are as shown in Figure 13. Notice that after the arc reversal, C is a continuous variable and B is a continuous conditionally deterministic variable.
In the new BN, C and D are still adjacent and the arc (C, D) can be reversed. After reversing this arc, we get a BN as shown in Figure 14. Notice that the resulting BN has discrete variables that do not have continuous parents. Thus, this BN is almost MoG, except for the conditional distribution of variable C, which is not CLG. Of course, we can approximate the four conditional distributions by MoG as discussed in Section 2. We skip the details.  Our strategy of approximating non-MoG hybrid BNs by MoG BNs is based on the existence of a fast exact algorithm for making inferences in MoG BNs. However, the problem of making exact (or approximate) inferences in hybrid Bayes nets has been shown to be NP hard [Lerner and Parr 2001]. So there are no guarantees that our strategy will always work (i.e., while we may be successful in converting a hybrid BN to a MoG BN, the LJ algorithm may fail to compute marginals). But we are hopeful that our strategy will work for a broad class of problems. We expect the process of approximation to be done off line. And there exists a commercial implementation of the LJ algorithm that makes the use of our strategy practical.

SUMMARY AND CONCLUSIONS
The process of approximating a non-MoG BN by a MoG BN is not without costs. First, we add some dummy discrete variables that are not present in the original non-MoG BN. This, of course, adds to the computational load of making inferences in the resulting MoG BN. Second, in the process of reversing arcs, we increase the domains of potentials. This again increases the computational burden of making inferences in the MoG approximation. Finally, although the inference is exact, the quality of the approximation depends on how many components are used to approximate non-MoG BNs by MoG BNs. Further research is needed to quantify the quality of the approximation as a function of components used.