Santiago Cortijo

Christophe Gonzales

On Conditional Truncated Densities Bayesian Networks

Keywords: Bayesian network, continuous random variable, mixed probability distribution, inference

The majority of Bayesian networks learning and inference algorithms rely on the assumption that all random variables are discrete, which is not necessarily the case in real-world problems. In situations where some variables are continuous, a trade-off between the expressive power of the model and the computational complexity of inference has to be done: on one hand, conditional Gaussian models are computationally efficient but they lack expressive power; on the other hand, mixtures of exponentials (MTE), basis functions (MTBF) or polynomials (MOP) are expressive but this comes at the expense of tractability. In this paper, we introduce an alternative model called a ctdBN that lies in between. It is composed of a "discrete" Bayesian network (BN) combined with a set of univariate conditional truncated densities modeling the uncertainty over the continuous random variables given their discrete counterpart resulting from a discretization process. We prove that ctdBNs can approximate (arbitrarily well) any Lipschitz mixed probability distribution. They can therefore be exploited in many practical situations. An efficient inference algorithm is also provided and its computational complexity justifies theoretically why inference computation times in ctdBNs are very close to those in discrete BNs. Experiments confirm the tractability of the model and highlight its expressive power, notably by comparing it with BNs on classification problems and with MTEs and MOPs on marginal distributions estimations.

Introduction

For several decades, Bayesian networks (BN) [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] have been successfully exploited for dealing with uncertainties. Their popularity has stimulated the Preprint submitted to International Journal of Approximate Reasoning October 17, 2017 development of many efficient learning and inference algorithms [START_REF] Shafer | Probabilistic expert systems[END_REF][START_REF] Dechter | Bucket elimination: A unifying framework for reasoning[END_REF][START_REF] Madsen | LAZY propagation: A junction tree inference algorithm based on lazy inference[END_REF][START_REF] Bacchus | Algorithms and complexity results for #sat and Bayesian inference[END_REF][START_REF] Chavira | On probabilistic inference by weighted model counting[END_REF]. Whilst these algorithms are relatively well understood when they involve only discrete variables, their ability to cope with continuous variables is often unsatisfactory. Dealing with continuous random variables is much more complicated than dealing with discrete ones and one actually has to trade-off between the expressive power of the uncertainty model and the computational complexity of its learning and inference mechanisms. Conditional Gaussian models and their mixing with discrete variables [START_REF] Lauritzen | Graphical models for associations between variables, some of which are qualitative and some quantitative[END_REF][START_REF] Lauritzen | Propagation of probabilities, means and variances in mixed graphical association models[END_REF][START_REF] Lerner | Exact inference in networks with discrete children of continuous parents[END_REF] lie on one side of the spectrum. They compactly represent multivariate Gaussian distributions. Their inference mechanisms are computationally very efficient but their main drawback is that they lack expressive power. Indeed, although Conditional Linear Gaussian (CLG) models can easily encode conditional independences between random variables, the density functions of their continuous random variables are required to be Normal distributions whose parameters depend linearly on the values of their parents. They are therefore unable to represent models where dependences between the continuous random variables are nonlinear. In addition, they are not very well suited to represent models in which random variables are not distributed w.r.t. Normal distributions. On the other side of the spectrum, there are more expressive models like mixtures of exponentials (MTE) [START_REF] Moral | Mixtures of truncated exponentials in hybrid Bayesian networks[END_REF][START_REF] Cobb | Approximating probability density functions in hybrid Bayesian networks with mixtures of truncated exponentials[END_REF][START_REF] Rumí | Approximate probability propagation with mixtures of truncated exponentials[END_REF], mixtures of truncated basis functions (MTBF) [START_REF] Langseth | Mixtures of truncated basis functions[END_REF][START_REF] Langseth | Inference in hybrid Bayesian networks with mixtures of truncated basis functions[END_REF] and mixtures of polynomials (MOP) [START_REF] Shenoy | A re-definition of mixtures of polynomials for inference in hybrid Bayesian networks[END_REF][START_REF] Shenoy | Inference in hybrid Bayesian networks using mixtures of polynomials[END_REF][START_REF] Shenoy | Two issues in using mixtures of polynomials for inference in hybrid Bayesian networks[END_REF]. Those can approximate very well density functions but this comes at the expense of tractability: their exact inference computation times tend to grow exponentially with the number of continuous variables, which makes them unusable when they contain hundreds of random variables.

In this paper, we propose an alternative model that lies in between these two extremes. The key idea is to discretize the random variables, thereby mapping each (continuous) value of their domain into an interval within a finite set of intervals. Of course, whenever some discretization is performed, some information about the continuous random variables is lost. But this can be significantly alleviated by modeling the distribution of the continuous values within each discretization interval by a density function which may not necessarily be a uniform distribution (which is the implicit assumption when using a classical discretization). The set of density functions over all the intervals of a continuous variable constitutes its "conditional truncated density" given its discretized counterpart. Now, our uncertainty model is a (discrete) BN over the set of discrete and discretized random variables combined with the set of conditional truncated densities assigned to the continuous random variables that were discretized. This model model is therefore called "conditional truncated densities Bayesian network", or ctdBN for short. It represents compactly mixed probability distributions. The model is derived from the result of an algorithm for learning BNs from datasets containing both discrete and continuous random variables [START_REF] Mabrouk | Multivariate cluster-based discretization for Bayesian network structure learning[END_REF].

By assigning conditional truncated densities to continuous variables, our model gains expressive power over a BN in which all continuous variables are discretized. As we show in this paper, this assertion is justified theoretically by the fact that any Lipschitz mixed probability distribution can be (arbitrarily well) approximated by a ctdBN. For inference, the density functions need only be included in the BN as discrete evidence (computed by integrations) over the discretized variables and, then, only a classical inference over discrete variables is needed to complete the process. As, in our model, the density functions are univariate, integrations can be performed efficiently. So the inference times are very close to those of inferences in classical BNs, which makes inference tractable in ctdBNs. The theoretical computational complexity of our inference algorithm supports this assertion. In addition, the experiments performed in the paper also highlight this point as well as the expressive power of the model.

The paper is organized as follows. In the next section, we recall some related works on CLGs, MTEs, MTBFs and MOPs. Then, in Section 3, we present our model, we study theoretically its expressive power, i.e., its capacity to approximate mixed probability distributions, and we propose an inference algorithm as well as its computational complexity. Next, the efficiency and effectiveness of ctdBN's inferences are highlighted through a set of experiments. Finally, a conclusion and some perspectives are provided in the last section.

Related Works

In the rest of the paper, capital letters (possibly subscripted) refer to random variables and boldface capital letters to sets of variables. To distinguish continuous random variables from discrete ones, we denote by Xi a continuous variable and by X i a discrete one. Without loss of generality, for any Xi , variable X i represents its discretized counterpart. Throughout the paper, let X D = {X 1 , . . . , X d } and XC = { Xd+1 , . . . , Xn } denote the set of discrete and continuous random variables respectively. We denote by X = X D ∪ XC the set of all random variables. In addition, for any set of indices I = {i 1 , . . . , i k }, X I denotes the set of random variables {X i 1 , . . . , X i k }. Finally, for any variable X or set of random variables Y or Y, let Ω X (resp. Ω Y or Ω Y) denote the domain of X (resp. Y or Y).

As mentioned in the introduction, a Conditional Linear Gaussian (CLG) model represents a mixed probability distribution [START_REF] Lauritzen | Graphical models for associations between variables, some of which are qualitative and some quantitative[END_REF]. Like in a BN, in the CLG model, to each discrete variable X i in X D is assigned its conditional probability table (CPT) P (X i |Pa(X i )) given its parents (the latter are all discrete). In addition, to each continuous variable Xi ∈ XC is assigned the conditional distribution:

f (x i |X D i = x D i , XC i = xC i ) = N (x i |α(x D i ) + β(x D i ) T xC i , σ(x D i )),
where X D i and XC i are the set of discrete and continuous parents of Xi respectively. α(x D i ) and β(x D i ) are the coefficients of a linear regression model of Xi given its continuous parents. These coefficients depend on the values x D i of the discrete parents. The product of all the CPTs and the conditional distributions represent the joint mixed distribution over X . Our ctdBN model shares some similarities with CLGs: it represents mixed probability distributions using a DAG whose nodes represent random variables, the parents of the discrete ones being also necessarily discrete. The main difference between CLGs and ctdBNs lies in the conditional density functions assigned to the continuous random variables. Unlike CLGs, in ctdBNs, they are not limited to normal distributions and any conditional truncated density function can be used. In this sense, ctdBNs are more general than CLGs. The dependences between the continuous variables are also different: in CLGs, those are necessarily linear (the coefficients of the mean vector result from a linear regression) whereas, in ctdBNs, linearity is not required. Of course, nonlinearity can be approximated by piecewise linear functions and can therefore be taken into account in CLGs introducing latent variables and using deterministic relationships, like in [START_REF] Shenoy | Inference in hybrid Bayesian networks using mixtures of Gaussians[END_REF]. In ctdBNs, this is taken into account directly through the relationships between the discretized random variables. There is no need to introduce latent variables, which complexifies the learning of the model. Finally, in CLGs, the mean vector of the normal distribution assigned to Xi can vary with the values of XC i whereas, in ctdBNs, this interaction between Xi and XC i is limited to the interaction between the discretized counterpart of Xi and that of XC i .

The introduction into the ctdBN model of these discretized counterparts makes ctdBNs similar to mixture distributions, which explains their high expressive power. Mixture distributions have been studied in the literature, notably from the learning perspective, see e.g., [START_REF] Poland | Three approaches to probability model selection[END_REF]. However, unlike [START_REF] Poland | Three approaches to probability model selection[END_REF] in which the number of components of the mixture is implicitly assumed to be small, in ctdBNs, this number, which is equal to the product of the domain sizes of the discretized random variables, is potentially very high. Yet, the way ctdBNs are defined, they remain as tractable as fully discrete BNs. In terms of mixture models, the closest works related to our model are probably MTEs, MOPs and MTBFs. In MTE [START_REF] Moral | Mixtures of truncated exponentials in hybrid Bayesian networks[END_REF], the distribution over the set of all random variables X is specified by a density function f such that:

• x D ∈Ω X D Ω XC f (x D ,x C ) dx C = 1,
• f is an MTE potential over X , i.e.:

Definition 1 (MTE potential).

Let Y = {X r 1 , . . . , X rp } and Z = { Xs 1 , . . . , Xsq } be sets of discrete and continuous variables respectively. A function φ : Ω Y∪ Z → R + 0 is a MTE potential if one of the two following conditions holds:

1. φ can be written as:

φ(y,z) = a 0 + m i=1 a i exp    p j=1 b (j) i x r j + q k=1 b (p+k) i xs k    (1)
for all (x r 1 , . . . , x rp ) ∈ Y, (x s 1 , . . . , xsq ) ∈ Z, where a i , i = 0, . . . , m and b (j) i , i = 1, . . . , m, j = 1, . . . , p + q, are real numbers. 2. There exists a partition Ω 1 , . . . , Ω k of Ω Y∪ Z such that the domain of the continuous variables, Ω Z, is divided into hypercubes, the domain Ω Y of the discrete variables is divided into arbitrary sets, and such that φ is defined as:

φ(y,z) = φ i (y,z) if (y,z) ∈ Ω i ,
where each φ i , i = 1, . . . , k, can be written in the form of Equation (1), i.e., it is a MTE potential on Ω i .

MTEs present attractive features. First, they are expressive in the sense that they can approximate (w.r.t. the Kullback-Leibler distance) any continuous density function [START_REF] Cobb | Approximating probability density functions in hybrid Bayesian networks with mixtures of truncated exponentials[END_REF][START_REF] Cobb | Inference in hybrid Bayesian networks with mixtures of truncated exponentials[END_REF]. Second, they are easy to learn from datasets [START_REF] Moral | Estimating mixtures of truncated exponentials from data[END_REF][START_REF] Romero | Structural learning of Bayesian networks with mixtures of truncated exponentials[END_REF]. Finally, they satisfy Shafer-Shenoy's propagation axioms [START_REF] Shenoy | Axioms for probability and belief function propagation[END_REF] and inference can thus be performed using a junction tree-based algorithm [START_REF] Moral | Mixtures of truncated exponentials in hybrid Bayesian networks[END_REF][START_REF] Cobb | Inference in hybrid Bayesian networks with mixtures of truncated exponentials[END_REF]. This algorithm can be described as follows. An undirected graph called a Markov network is first created: its nodes correspond to the variables of X and its edges are such that, for every MTE potential φ i , all the nodes involved in φ i are linked together. This graph is then triangulated by eliminating sequentially all the nodes. A node elimination consists i) in adding edges to the Markov network in order to create a clique (a complete subgraph) containing the eliminated node and all its neighbors; and ii) in removing the eliminated node and its adjacent edges from the Markov network. The cliques created during this process constitute the nodes of the junction tree. They are linked in order to satisfy a "running intersection" property [START_REF] Madsen | LAZY propagation: A junction tree inference algorithm based on lazy inference[END_REF]. Finally, each MTE potential φ i is inserted into a clique containing all its variables.

A collect-distribute message-passing algorithm can then be performed in this junction tree, hence enabling to compute a posteriori marginal distributions of all the random variables. As usual, the message passed from one clique C i to a neighbor C j is the projection onto the variables in C i ∩ C j of the combination of the MTE potentials stored in C i with the messages received by C i from all its neighbors except C j . By Equation (1), combinations and projections are Algebraic operations over sums of exponentials. Unfortunately, these operations have a serious shortcoming: when propagating messages from one clique to another, the number of a i /exp terms in Equation ( 1) tends to grow exponentially, hence limiting the use of this exact inference mechanism to problems with only a small number of cliques.

To overcome this issue, approximate algorithms based on MCMC [START_REF] Moral | Mixtures of truncated exponentials in hybrid Bayesian networks[END_REF] or on the Penniless algorithm [START_REF] Rumí | Approximate probability propagation with mixtures of truncated exponentials[END_REF] are provided in the literature.

Mixtures of polynomials (MOP) are similar to MTE except that functions φ : Ω Y∪ Z → R + 0 of Equation (1) are substituted by polynomials over the variables in Y ∪ Z [START_REF] Shenoy | A re-definition of mixtures of polynomials for inference in hybrid Bayesian networks[END_REF][START_REF] Shenoy | Inference in hybrid Bayesian networks using mixtures of polynomials[END_REF]. MOPs have several advantages over MTEs: their parameters for approximating density functions are easier to determine than those of MTEs. They are also applicable to a larger class of deterministic functions in hybrid BNs. As MTE, the MOP model satisfies Shafer-Shenoy's propagation axioms and inference can thus be performed by message-passing in a junction tree. But, similarly to Equation (1), the number of terms these messages involve tends to grow exponentially with the number of cliques in the junction tree, thereby limiting the use the messagepassing algorithm to junction trees with a small number of cliques/random variables.

Finally, mixtures of truncated basis functions (MTBF) generalize both MTEs and MOPs [START_REF] Langseth | Mixtures of truncated basis functions[END_REF]. The definition of an MTBF is the same as Definition 1 except that Equation (1) is substituted by:

φ(y,z) = m i=0 q k=1 a (k) i,y ψ i (x s k ), (2)
where potentials ψ i : R → R are basis functions. MTBFs are defined so that the potentials are closed under combination and projection which, again, ensures that inference can be performed by message-passing in a junction tree. By exploiting cleverly factorizations of terms in Equation ( 2), inference in MTBFs can be more efficient than in MTEs [START_REF] Langseth | Inference in hybrid Bayesian networks with mixtures of truncated basis functions[END_REF]. But, like all the other aforementioned models, the sizes of the messages tend to grow with the number of cliques in the junction tree.

In the next section, we propose an alternative model that overcomes this issue while still being expressive.

Conditional Truncated Densities Bayesian Networks

In this section, we propose a new graphical model called "conditional truncated densities Bayesian network". This is a combination of a classical discrete Bayesian network with some conditional truncated densities. Before describing it in details, we therefore need to recall what are Bayesian networks and conditional densities.

Definition 2 (Bayesian network (BN)). A (discrete) BN B is a pair (G, θ) where G = (X, A) is a directed acyclic graph (DAG), X = {X 1 , ..., X n } represents a set of discrete and/or discretized random variables1 , A is a set of arcs, and θ = {P (X i |Pa(X i ))} n i=1 is the set of the conditional probability tables/distributions (CPT) of the variables X i in G given their parents Pa(X i ) in G. The BN encodes the joint probability over X as P (X) = n i=1 P (X i |Pa(X i )).

Our model is intended to be used in situations where uncertain variables are mixed discrete/continuous. BNs are unable to model such situations because, by their very definition, they assign CPTs to the nodes of their graphical structure, which requires all random variables to be discrete. A first idea to exploit BNs is therefore to discretize the continuous random variables, thereby creating new discrete variables, and to express the uncertainties as a BN over the set of discrete and discretized variables. In some sense, our model is a refinement of this process.

Definition 3 (Discretization). A discretization of a continuous variable

Xi is a function d Xi : Ω Xi → {0, . . . , g i } defined by an increasing sequence of g i cut points {t 1 , t 2 , ..., t g i } ⊂ Ω Xi such that:

d Xi (x i ) =    0 if xi < t 1 , k if t k ≤ xi < t k+1 , for all k ∈ {1, . . . , g i -1} g i if xi ≥ t g i
Thus the discretized variable X i corresponding to Xi has a finite domain of {0, . . . , g i }. Therefore, after discretizing all the continuous random variables, the uncertainty over all the discrete and discretized random variables X = {X 1 , ..., X n } can be represented by a classical BN in which very efficient exact message-passing inference mechanisms can be used, notably junction tree-based algorithms [START_REF] Shafer | Probabilistic expert systems[END_REF][START_REF] Shenoy | Binary join trees for computing marginals in the Shenoy-Shafer architecture[END_REF][START_REF] Dechter | Bucket elimination: A unifying framework for reasoning[END_REF][START_REF] Madsen | LAZY propagation: A junction tree inference algorithm based on lazy inference[END_REF] and weighted model counting methods [START_REF] Bacchus | Algorithms and complexity results for #sat and Bayesian inference[END_REF][START_REF] Chavira | On probabilistic inference by weighted model counting[END_REF]. In this paper, we will exploit the former.

However, discretizing continuous random variables raises two major issues: i) which discretization function shall be used to minimize the loss of information? and ii) will the loss of information affect significantly the results of inference? A possible answer to the first question consists of exploiting "conditional truncated densities" [START_REF] Mabrouk | Multivariate cluster-based discretization for Bayesian network structure learning[END_REF]. The answer to the second question of course strongly depends on the discretization performed but, as we shall see, conditional truncated densities can limit the discrepancy between the exact a posteriori marginal density functions of the continuous random variables and the approximation they provide.

Definition 4 (Conditional truncated density). Let Xi be a continuous random variable. Let d Xi be a discretization of Xi with set of cutpoints {t 1 , t 2 , ..., t g i }. Finally, let X i be a discrete random variable with domain

Ω X i = {0, . . . , g i }. A conditional truncated density is a function f ( Xi |X i ) : Ω Xi × Ω X i → R + 0 satisfying the following properties: 1. f (x i |x i ) = 0 for all x i ∈ Ω X i and xi ∈ [t x i , t x i +1
) with, by abuse of notation t 0 = inf Ω Xi and t g i +1 = sup Ω Xi ; 2. the following equation holds:

t x i +1 tx i f (x i |x i ) dx i = 1, for all x i ∈ Ω X i . (3)
In other words, f (x i |x i ) represents the truncated density function of random variable Xi over the interval of discretization [t x i , t x i +1 ).

Lemma 1. Let P (X i ) be any probability distribution over the discrete random variable X i of Definition 4. Then f ( Xi |X i )P (X i ) is a mixed probability distribution over Ω Xi × Ω X i , i.e., it is a non-negative function such that:

x i ∈Ω X i Ω Xi f (x i |x i )P (x i ) dx i = 1. ( 4
)
All the proofs are given in the appendix.

We can now introduce "Bayesian networks with conditional truncated densities", which are Bayesian networks defined over discrete and discretized random variables, in which to each discretized variable is assigned its corresponding continuous random variable and its conditional truncated density: Definition 5 (Conditional truncated densities Bayesian networks). (ctdBN) Let X D = {X 1 , . . . , X d } and XC = { Xd+1 , ..., Xn } be sets of discrete and continuous random variables respectively. Let X C = {X d+1 , ..., X n } be a set of discretized variables resulting from the discretization of the variables in XC . Then, a ctdBN is a pair (G, θ) where:

• G = (X, A) is a directed acyclic graph, • X = X D ∪ X C ∪ XC ,
• A is a set of arcs such that nodes Xi ∈ XC have no children and exactly one parent equal to X i . This condition is the key to guarantee that inference in a ctdBN is as fast as that in a classical BN.

• Finally, θ = θ D ∪θ C , where θ D = {P (X i |Pa(X i ))} n i=1
is the set of the conditional probability tables of the discrete and discretized variables X i in G given their parents Pa(X i ) in G, and

θ C = {f ( Xi |X i )} n
i=d+1 is the set of the conditional truncated densities of the continuous random variables of XC .

Note that θ C needs a very limited amount of memory compared to θ D since truncated densities are univariate (e.g., a truncated normal distribution f ( Xi |X i ) is specified by only 2|Ω X i | parameters). An example of ctdBN is given in Figure 1. The model contains 3 continuous variables, XC = { X1 , X3 , X5 } represented by blue dotted circles, which are discretized into X C = {X 1 , X 3 , X 5 }. Nodes in pink solid circles X C and X D form a classical BN. Finally, all the continuous nodes Xi ∈ XC are children of their discretized counterpart X i and none has any child. The key idea of ctdBNs is thus to extend BNs by specifying the uncertainties over continuous random variables Xi as 2-level functions: a "rough" probability distribution for discrete variable X i and a finer-grain conditional density f ( Xi |X i ) for Xi . This idea can be somewhat related to second order probabilities [START_REF] Baron | Second-order probabilities and belief functions[END_REF].

X 5 X 6 X5 X 4 X 3 X 2 X 1 X3 X1 P (X 1 ) P (X 3 |X 1 ) P (X 2 ) P (X 4 |X 1 , X 2 ) P (X 5 |X 3 , X 4 ) P (X 6 |X 5 ) f ( X1 |X 1 ) f ( X3 |X 3 ) f ( X5 |X 5 )
Proposition 1. In a ctdBN defined over X = X D ∪X C ∪ XC , where X D = {X 1 , . . . , X d }, X C = {X d+1 , . . . , X n } and XC = { Xd+1 , . . . , Xn }, function h : X → R + 0 defined as: h(X) = n i=1 P (X i |Pa(X i )) n i=d+1 f ( Xi |X i ) ( 5
)
is a mixed probability distribution over X.

The above proposition therefore shows that ctdBNs encode compactly mixed probability distributions.

Faithfulness with ctdBNs

It was shown in [START_REF] Cobb | Approximating probability density functions in hybrid Bayesian networks with mixtures of truncated exponentials[END_REF][START_REF] Cobb | Inference in hybrid Bayesian networks with mixtures of truncated exponentials[END_REF] that MTEs can approximate standard probability density functions (w.r.t. the Kullback-Leibler distance). One may wonder whether ctdBN are also faithful, i.e., whether they can provide good approximations of densities or mixed probability distributions. The propositions provided in this subsection show that the answer to this question is positive and that ctdBNs can actually approximate very general functions.

Proposition 2. Let XC = { X1 , ..., Xn } be a set of continuous real-valued random variables of respective domains Ω1 , ..., Ωn such that none of the Ωi is a singleton. Let ΩC = n i=1 Ωi be the domain of XC . Let f : ΩC → R be a probability density function. Assume that f is Lipschitz, i.e., there exists a constant M > 0 such that, for every pair

(x, ẙ) of elements of ΩC , |f (x) -f (ẙ)| ≤ M ||x -ẙ||, where ||x -ẙ|| represents the L2-norm of vector (x -ẙ).
Then, for every strictly positive real number < 1, there exists a ctdBN B = (G, θ) that approximates f up to , i.e.:

• the nodes of Graph G are X = X D ∪ XC , where X D = {X 1 , . . . , X n }
is a set of the discretized variables corresponding to XC ; in addition, let Ω D = n i=1 Ω i and Ω = Ω D × ΩC be the domains of X D and X respectively;

• B represents a mixed probability distribution g : Ω → R such that, for every x ∈ ΩC , |g(x, x) -f (x)| ≤ , where x corresponds to the discretized counterpart of x.

The above proposition shows that any Lipschitz multivariate probability density function can be (arbitrarily well) approximated by a ctdBN. Note that, to do so, the conditional truncated densities used by such ctdBN need not be "complex": in the proof of this proposition, only uniform and conditional truncated normal distributions were used. An obvious corollary of this proposition is that standard density functions can be approximated by ctdBNs:

Corollary 1. Standard distributions like, e.g., univariate and multivariate Normal distributions, Beta distributions B(x, α, β), with α, β ≥ 2, Gamma distribution Γ(x, α, β) with α > 2, as well as their combinations by mutually independent random variables, can be approximated up to < 1 by ctdBNs.

But ctdBNs represent compactly the uncertainties over both discrete and continuous random variables. So, they may also provide good approximations of mixed probability distributions and the following proposition justifies this intuition:

Proposition 3. Let X D = {X 1 , . . . , X d } be a set of discrete random vari- ables of respective domains {Ω 1 , . . . , Ω d } and let Ω D = d
i=1 Ω i be the domain of X D . Let XC = { Xd+1 , ..., Xn } be a set of continuous random variables of respective domains Ωd+1 , ..., Ωn such that none of the Ωi is a singleton. Let ΩC = n i=d+1 Ωi be the domain of XC . Finally, let X = X D ∪ XC and Ω = Ω D × ΩC .

Let f : Ω D × ΩC → R be a mixed probability distribution. Assume that f is Lipschitz w.r.t. the continuous variables of XC , i.e., there exists a constant M > 0 such that, for every pair (x, ẙ) of elements of Ω such that

x i = y i for all i ∈ {1, . . . , d}, |f (x) -f (ẙ)| ≤ M ||x -ẙ||, where ||x -ẙ|| represents the L2-norm of vector (x -ẙ).
Then, for every strictly positive real number < 1, there exists a ctdBN B = (G, θ) that approximates f up to , i.e.:

• the nodes of G are X = X D ∪ X C ∪ XC , where X C = {X d+1 , . . . , X n }
is a set of discretized variables corresponding to XC ; in addition, let CtdBNs also have some decomposability properties. For instance, the following proposition shows that, if the mixed probability distribution to be approximated is decomposable, then so is also the approximating ctdBN: Proposition 4. Let X D = {X 1 , . . . , X d } and XC = { Xd+1 , ..., Xn } be sets of discrete and continuous random variables respectively. Let f : Ω D × ΩC → R be a mixed probability distribution. Assume that sets of variables X D and XC can be partitioned into sets {X D 1 , . . . , X D k } and XC 1 , . . . , XC k respectively, and that there exist some non-negative functions f i :

Ω C = n i=d+1 Ω i and Ω = Ω D × Ω C × ΩC be
Ω D i × ΩC i → R, i = 1, . . . , k, such that f (x, x) = k i=1 f i (x D i , xC i ) for all (x, x) ∈ Ω D × ΩC . Then if f is Lipschitz w.r.t.
the continuous variables of XC , it can be approximated up to by a ctdBN which has the same decomposition, i.e., sets (X D i ∪ X C i ∪ XC i ), i = 1, . . . , k, where X C i are the discretized counterparts of XC i , form the connected components of the ctdBN's graphical structure.

All these theoretical results will be confirmed in practice in the experimental section of the paper. Now, we will focus on inferences with ctdBNs, in particular on the efficiency of junction tree-based algorithms.

Inference in ctdBNs

The terms in Equation ( 5) satisfy Shafer-Shenoy's propagation axioms [START_REF] Shenoy | Axioms for probability and belief function propagation[END_REF], so we can rely on a message-passing algorithm in a junction tree to perform inference. The latter is constructed by node eliminations from the Markov network, as described in the preceding section. It was proved that first eliminating all simplicial nodes, i.e., nodes that, together with their neighbors in the Markov network, constitute a clique (a complete maximal subgraph), cannot prevent obtaining a junction tree that is optimal w.r.t. inference [START_REF] Van Den Eijkhof | Safe reduction rules for weighted treewidth[END_REF]. By the definition of ctdBNs, all the continuous nodes Xi ∈ XC constitute a clique with their parent X i (for instance, in Figure 1, {X 3 , X3 } is a complete maximal subgraph and is thus a clique). As a consequence, the junction tree of a ctdBN is simply the junction tree of its discrete BN part defined over X C ∪ X D to which cliques {X i , Xi }, for Xi ∈ XC , have been added (linked to a clique containing X i in order to satisfy the running intersection property). Figure 2 shows a junction tree related to the ctdBN of Figure 1. All the CPTs P (X i |Pa(X i )), i = 1, . . . , n, are inserted into cliques not containing any continuous node of XC . Of course, conditional truncated densities are inserted into cliques {X i , Xi }, Xi ∈ XC . The inference process can now be performed by message passing within the junction tree, for instance using a usual collect-distribute algorithm in a Shafer-Shenoy-like architecture [START_REF] Shafer | Probabilistic expert systems[END_REF], sending messages in both directions on all the edges of the junction tree.

There remains to show how to compute the messages sent on the separators in the Shafer-Shenoy collect-distribute algorithm and how to encode and insert evidence into junction tree T . First, let us address the second problem. Of course evidence on discrete random variables X i are handled in a usual manner by multiplying the joint mixed probability distribution g(X, X) represented by the ctdBN with discrete beliefs of the type P (e X i |X i ). This corresponds to adding probability table P (e X i |X i ) into a clique of T containing X i . For continuous random variables, two cases can occur: first, it may be the case that the available evidence on continuous random variable Xi can be encoded as an evidence on its discretized random variable, then we do so. For instance, if {t 1 , . . . , t g i } are the cutpoints of the discretization function applied to Xi , then evidence " Xi is known to belong [t j , t k ]" can be encoded as a vector P (e X i |X i ) whose values are 1 for the indices in {j, . . . , k -1}, else 0. Second, it may be impossible to enter evidence e Xi on Xi into X i . In this case, e Xi can be of the type " Xi belongs to some interval [a, b]", with a, b ∈ {t 1 , . . . , t g i }. Such an evidence can be represented by function

f i (e Xi | Xi ) : Ω Xi → [0, 1] equal to 1 when Xi ∈ [a, b]
and 0 otherwise. As function f i is defined only over Xi , it can be entered into the clique C i = {X i , Xi } of junction tree T . More generally, beliefs about Xi can be entered as any [0, 1]-valued function f i (e Xi | Xi ) into clique C i . It is easy to see that the product of the evidence functions f i (e Xi | Xi ) and P (e X i |X i ) with g(X, X) defines, up to a proportional constant equal to the probability of all the evidence, a new mixed probability distribution. Now, there remains to show how to compute the messages sent from one clique, say C i , to one of its neighbor C j . Two cases can occur. First, assume that C i contains a continuous random variable Xi . Then, by construction of ctdBNs, C i = {X i , Xi }, with X i the discretized variable corresponding to Xi . By construction, clique C i has only one neighbor clique, say C j , and the separator between C i and C j is necessarily S ij = {X i }. Clique C i contains only conditional truncated density g i ( Xi |X i ) and, potentially, some evidence belief f i (e Xi | Xi ). So, in order to remove variable Xi from the equations, it must be marginalized out as:

M C i →C j (x i ) = Ω Xi g i (x i |x i )f i (e Xi |x i ) dx i , for all x i ∈ Ω X i . (6)
Assume that {t 1 , . . . , t g i } are the cutpoints of the discretization function applied to Xi . Then message M C i →C j is a real-valued vector of size g i + 1. So, messages sent from cliques containing continuous random variables to their neighbor are necessarily vectors of finite size. In addition, whether Xi received evidence or not, note that message M C i →C j is computed by integrating a univariate function, which, in practice, is not time consuming (it can be done either exactly in closed-form formula or approximately using a MCMC algorithm or well-known tables like for normal distributions).

The second case for computing messages concerns situations in which clique C i contain only discrete random variables. Then, by construction, the separator S ij = C i ∩ C j contains only discrete random variables. Message M C i →C j can therefore be computed as usual by first multiplying all the messages sent to C i by all C i 's neighbors except C j with the product of the CPTs stored into C i , and then by marginalizing out all the variables in C i \C j . Proposition 5. Let e represent all the evidence entered into junction tree T . Assume that Shafer-Shenoy's message-passing algorithm has been performed, with messages computed as described above.

Let C k be any clique containing only discrete variables and let C i 1 , . . . , C ir be the neighbors of C k . Then the CPT resulting from the normalization of the product of all the messages M C i j →C k , j = 1, . . . , r, with the CPTs stored into C k is equal to the joint posterior distribution of the variables of C k given evidence e. The posterior of any variable in C k can be obtained by marginalizing out the other variables from this CPT.

Let C k be any clique containing a continuous random variable, say Xk . Let g k +1 be the domain size of the corresponding discretized random variable X k . Finally, let C j be the neighbor clique of C k . Then:

g k (x k |e) ∝ g x k =0 M C j →C k (x k )g k (x k |x k )f k (e Xk |x k ) (7)
is the posterior density of variable Xk .

As shown above, ctdBNs allow for the computation of the marginal a posteriori distributions of the continuous and discrete random variables. In addition, as shown in the next proposition, the algorithm proposed in this paper is very efficient for performing these computations. Notably, when the integrals of Equation ( 6) can be computed in O(1), the complexity of inference in ctdBN is exactly the same as that in classical discrete BNs. As a consequence, when tables for these integrals are available, like, e.g., when the ctdBN's conditional truncated densities are truncated normal distributions, inference in ctdBNs is as fast as that in discrete BNs. Proposition 6. Let w be the treewidth of T and let k denote the maximum domain size of the discrete and discretized random variables. Finally, let n be the number of random variables in the ctdBN and let I be the average complexity of computing one integral of Equation (6) (i.e., an integral for a given value of x i ) and J the average complexity of computing the product in Equation [START_REF] Lauritzen | Graphical models for associations between variables, some of which are qualitative and some quantitative[END_REF]. Then the complexity of computing all the marginal posterior distributions of all the random variables is in O(nk(k w + I + J)).

Overall, inference in ctdBNs is fast because i) by construction, most of the inference's complexity lies in computations performed on discrete variables; and ii) whenever computations concern densities, either they correspond to compute a mixture of univariate conditional truncated densities (like in Equation ( 7)) or to compute the integral of a univariate function (like in Equation ( 6)).

Experiments

In this section, we provide two sets of experiments. The first one is intended to show the gain brought by ctdBNs over classical BNs. For this purpose, we illustrate the discrepancies between both models on classification problems derived from UCI datasets [START_REF] Lichman | UCI machine learning repository[END_REF]. The second set of experiments is devoted to the comparison between ctdBNs and MTBFs in order to highlight the inference scalability of ctdBNs compared to that of MTBFs.

Comparisons with discrete BNs

In order to compare BNs and ctdBNs on real-world problems, we base our experiments on the real-world datasets of the UCI repository [START_REF] Lichman | UCI machine learning repository[END_REF] reported in Table 1. In these datasets, all records with missing values are discarded. In each resulting dataset, there exists a discrete random variable, call it X 0 , representing a classification variable. The other random variables can be either discrete (variables X D = {X 1 , . . . , X d }) or continuous ( XC = { Xd+1 , . . . , Xn }). Our classification problem consists of estimating the most probable value of X 0 given some observation on the values of variables in X D ∪ XC . To address such a problem with Bayesian networks, we must first discretize all the continuous random variables. To do so, we exploit Friedman's discretization algorithm [START_REF] Friedman | Discretizing continuous attributes while learning Bayesian networks[END_REF]. After performing these discretizations, variables in XC = { Xd+1 , . . . , Xn } are mapped into discretized variables in X C = {X d+1 , . . . , X n } and the mixed discrete/continuous dataset D of the UCI dataset is mapped into a fully discrete dataset D. A BN B over (X 0 , X 1 , . . . , X n ) is then learnt from D using a hill climbing algorithm with an MDL score. To do so, we use the aGrUM library (http://www.agrum.org). This BN is then exploited for a classification task as follows: given some observation e Xi (resp. e X i ) on each continuous random variable Xi (resp. discrete variable X i ), we enter belief P (e Xi |X i ) (resp. P (e X i |X i )) into B, so that the latter represents: P (X 0 , . . . , X n , e X 1 , . . . , e X d , e Xd+1 , . . . , e Xn ) = P (X 0 |Pa(X 0 ))

n i=1 P (X i |Pa(X i )) d i=1 P (e X i |X i ) n i=d+1 P (e Xi |X i ).
From this distribution, by means of a Shafer-Shenoy (exact) inference, we compute the posterior distribution P (X 0 |e X 1 , . . . , e X d , e Xd+1 , . . . , e Xn ) so that the most probable value for class variable X 0 is determined as:

x * 0 = Argmax X 0 P (X 0 |e X 1 , . . . , e X d , e Xd+1 , . . . , e Xn ).

To highlight the gain brought by ctdBNs over simple BNs, for each dataset, we construct our ctdBN as follows: we start from BN B computed in the preceding paragraphs and we add to it its respective conditional truncated densities g i ( Xi |X i ), i = d + 1, . . . , n, defined as follows: let Ωobs i = {x i,1 , xi,2 , . . . , xi,N } be the set of distinct observed values of Xi in the dataset, sorted by increasing order. The midpoints of Ωobs i are defined as:

m i,j =      xi,1 -xi,2 -x i,1 2 if j = 0, xi,j +x i,j+1 2 if 1 ≤ j < N , xi,N + xi,N -x i,N -1 2 if j = N .
Let h i : Ω Xi → R be the histogram of Xi whose bins correspond to intervals [m i,j , m i,j+1 ). Assume that Xi has been discretized into X i using cutpoints {t 1 i , . . . , t g i i }. Then we define conditional truncated densities g i ( Xi |X i = j), j = 0, . . . , g i , as the normalized histogram of h i over [t j i , t j+1 i ), i.e.,

g i (x i |X i = j) =      h i (x i ) t j+1 i t j i h i (x)dx if xi ∈ [t j i , t j+1 i ), 0 otherwise.
The ctdBN therefore represents the following mixed probability distribution:

g(X 0 , . . . , X n , Xd+1 , . . . , Xn ) = P (X 0 |Pa(X 0 ))

n i=1 P (X i |Pa(X i )) n i=d+1 g i ( Xi |X i ).
The same evidence e X i and e Xi as those of the BN are entered into the ctdBN. However, the latter are included into the ctdBN as beliefs f i (e Xi | Xi ) as ctdBNs can cope with more precise evidence than mere beliefs P (e Xi |X i ) about discretized random variables X i . Therefore, after entering evidence, the ctdBN represents:

g(X 0 , . . . , X n , Xd+1 , . . . , Xn , e X 1 , . . . , e X d , e Xd+1 , . . . , e Xn ) = P (X 0 |Pa(X 0 ))

n i=1 P (X i |Pa(X i )) d i=1 P (e X i |X i ) n i=d+1 g i ( Xi |X i )f i (e Xi | Xi ).
From this distribution, using the algorithm provided in Section 3, we compute g(X 0 |e X 1 , . . . , e X d , e Xd+1 , . . . , e Xn ) and the most probable value for class variable X 0 is x * 0 = Argmax X 0 g(X 0 |e X 1 , . . . , e X d , e Xd+1 , . . . , e Xn ). Finally, to perform our experiments, each dataset of Table 1 is randomly shuffled 100 times. Each resulting dataset is splitted into a learning set (70%) and a test set (30%). So, overall, for each UCI dataset, 100 different learning sets and their respective 100 test sets are created. From each learning set, we learn a BN and a ctdBN and, then, for each record of the corresponding test set, we estimate the most probable values of class variable X 0 given observations on X 1 , . . . , X d , Xd+1 , . . . , Xn according to these two models. These estimations are then compared with the true values of X 0 observed in the test set and the accuracy of the model (BN,ctdBN) is defined as the proportion of correct estimations performed. The latter depend on the kind of observations available, so we shall now describe those used in the experiments.

First, all observations over discrete variables are supposed to be precise. Now, assume that observation e Xi over continuous variable Xi is also precise, i.e., it is equal to the observed value of Xi in the record. Then, for the ctdBN, f i (e Xi | Xi ) is a Dirac function, which means that message M C i →C j , as defined in Eq. ( 6), is a zero filled vector, bringing no information. In addition, the BN is unable to handle such precise information. What can be handled by the BN is the (less precise) observation that "the discretized value of the observed value of Xi is equal to j". Such information is exactly equivalent to " Xi belongs to interval [t j i , t j+1 i )", where [t j i , t j+1 i ) is the discretization interval containing the observed value of Xi . In this case, P (e Xi |X i ), is a vector filled with zeros except for a 1 in the cell corresponding to the discretized value of Xi . If we enter the same information into the ctdBN, Message M C i →C j is exactly proportional to P (e Xi |X i ) and, therefore, the BN and the ctdBN provide the same estimation for X 0 .

The advantage of ctdBNs over standard BNs becomes visible when observations are imprecise. So, in our experiments, all the continuous variables Xi are imprecisely observed and the belief f i (e Xi | Xi ) is always expressed as a normal distribution centered on the observed value of Xi . For the BN, vector P (e Xi |X i ) can then simply be computed as:

P (e Xi |X i = j) = t j+1 i t j i f i (e Xi |x i ) dx i for all j. (8)
When the standard deviations of the normal distributions are sufficiently small, in the BN, P (e Xi |X i ) is approximately equal to a vector filled with zeros except for one cell equal to 1 and, in the ctdBN, Message M C i →C j of Eq. ( 6) is approximately proportional to P (e Xi |X i ). So, both models are equivalent. However, when standard deviations are higher, i.e., when observations are less precise, P (e Xi |X i ) can contain several non-zero cells and, from Eq. ( 6 that M C i →C j ∝ P (e Xi |X i ), except for the few variables mentioned in Table 2 in which the standard deviations displayed introduce discrepancies between M C i →C j and P (e Xi |X i ). Note that these standard deviations are often much smaller than the range of the random variable. With the observations as described above, the average accuracies for the different UCI datasets over the 100 corresponding test sets, as well as their standard deviations, are reported in Table 3. From this table, it is clear that ctdBNs outperform BNs for classification tasks. The way we constructed the ctdBNs from the BNs, this improvement is necessarily due to the conditional truncated densities contained in the ctdBNs.

Comparisons with MTBFs

In this subsection, we highlight the faithfulness of ctdBNs by comparing them with MTBFs, more precisely with MOPs [START_REF] Shenoy | A re-definition of mixtures of polynomials for inference in hybrid Bayesian networks[END_REF] and MTEs [START_REF] Moral | Mixtures of truncated exponentials in hybrid Bayesian networks[END_REF]. We show that ctdBNs can approximate effectively these MTBFs while being more efficient in terms of inference. For this purpose, we generate MTBFs Φ( X1 , . . . , Xn ) as products of bivariate MTBF potentials:

Φ( X1 , . . . , Xn ) = Φ 1 ( X1 , X2 ) × Φ 2 ( X2 , X3 ) × • • • × Φ n-1 ( Xn-1 , Xn ).
This decomposition has been chosen in order to make inference in MTBFs as fast as possible. Indeed, the corresponding junction tree contains only cliques of size two, having at most two neighbors, which limits the combinatorics of the algebraic operations performed during inference. All these MTBF potentials are defined over some continuous variables Xi whose domain is Ω Xi = [0, 10]. To make MTEs as efficient as possible for inference, we express MTE potentials Φ M T E i ( Xi , Xi+1 ) by only one exponential term:

Φ M T E i ( Xi , Xi+1 ) = a i,0 + a i,1 exp (b i,0 Xi + b i,1 Xi+1 ), with a i,0 , a i,1 ∈ [0, 1] and b i,0 , b i,1 ∈ [0.5, 1] chosen randomly.
In order to make the shape of MOP potentials not easily captured by affine distributions2 (which we use in our ctdBNs) while guaranteeing that inferences in MOPs are as fast as possible, we define MOP potentials as polynomials of degree 6, more precisely as polynomials of degree 3 in each of their variables, i.e.,:

Φ M OP i ( Xi , Xi+1 ) = 3 j=0 3 k=0 c i,j,k Xj i Xk i+1 , with c i,j,k chosen randomly in interval [0, 1].
Our goal is to approximate these MTBFs by ctdBNs B encoding a mixed probability distribution g(X 1 , . . . , X n , X1 , . . . , Xn ). To construct B, we first discretize every continuous variable Xi in 50 equally-sized intervals, hence resulting in discretized random variables X i . Then, we construct a discrete BN B d over X 1 , . . . , X n whose independence structure corresponds to that of the MTBF, i.e., to the structure shown in Figure 3. Finally, ctdBN B is defined as B d to which are added conditional truncated densities g i ( Xi |X i ). Therefore, the ctdBN encodes the following mixed distribution: As a result, the junction tree used for inferences with ctdBN B always contains only cliques of size two, exactly like that of the MTBF. Since inference complexity with junction trees is exponential in the treewidth, imposing As a consequence, the following equation holds for all xi ∈ Ω Xi :

g(X 1 , . . . , X n , X1 , . . . , Xn ) = P B d (X 1 ) n i=2 P B d (X i |X i-1 ) n i=1 g i ( Xi |X i ). X 1 X 2 . . . X n-1 Xn
g i (x i |X i = j) = α i,j xi - t j i + t j+1 i 2 + 1 t j+1 i -t j i .
Using the projection over Xi of the 500 000-record sample of Φ( Xi-1 , Xi ) previously used for estimating P B d (X i |X i-1 ), we can now estimate α i,j by maximum likelihood under the constraint that g i (•) is non-negative on [t j i , t j+1 i ). As there is no closed-form formula for the optimal value of α i,j , we solve this constrained optimization problem by the Newton-Raphson method.

The experiments are conducted as follows: we generate MTBFs (both MTEs and MOPs) with n = 4, 8, 16, 32, 64, 128 and 256 variables. For each number of variables, 25 MTEs and 25 MOPs are generated. Exact inferences are performed in all these models using Variable Elimination [START_REF] Dechter | Bucket elimination: A unifying framework for reasoning[END_REF] in order to determine the distribution Φ( Xn ) of the last random variable. For each MOP and each MTE, we also learn a ctdBN as described above and execute the inference algorithm described in Section 3 to determine the distribution g( Xn ) of Xn .

The inference times are reported in Tables 4 and5. They highlight the scalability of ctdBNs. The ratios of the average inference time by the number of variables, i.e., the last two columns of the tables, are displayed in Figures 4 and5. It is clear that the MTBFs' inference times increase exponentially with the number of variables, even though the largest clique always remains of size 2. This results from the multiplications of the algebraic functions performed during the inferences that tend to produce new functions with an ever increasing number of parameters. Even marginalizations cannot restrain this increase. Unlike in MTBFs, in ctdBNs, the number of operations performed on each clique remains always the same during inference. This explains the linear increase in computation times when the number of vari- ables increase. This also corroborates the inference complexity provided in Proposition 4.

Of course, better inference times are attractive only if the estimations by ctdBNs approximate pretty well those of MTBFs. As a first hint that this is the case, Table 6 displays the average Jensen-Shannon Divergence (JSD) between the distributions Φ( Xn ) and g( Xn ) computed previously. The low JSD values show that ctdBNs approximate effectively MTBFs. To precise these results, we add some small noise to distributions Φ( Xn ) computed previously, hence resulting in new distributions Ψ( Xn ). Comparing the JSDs between Φ( Xn ) and Ψ( Xn ) on one hand and between Φ( Xn ) and g( Xn ) on the other, we show that ctdBNs provide better approximations than the slightly perturbed distributions, hence highlighting the ctdBN's faithfulness, while enabling much faster inferences than MTBFs, as shown above.

For the MTEs, the marginal distribution inferred for Xn is of the form Φ M T E ( Xn ) = a 0 + b 0 exp(b 1 Xn ). We perturb its parameters by , for different values of , as follows:

Ψ M T E ( Xn ) ∝ (1 + )a 0 + (1 -)b 0 exp (1 + )b 1 Xn .
Note that Ψ M T E ( Xn ) is not strictly equal to the right hand side of the above equation, but only proportional to it, so that the integral of Ψ M T E over Ω Xn is equal to one, hence ensuring that Ψ M T E is a probability density function.

For MOPs, the marginal distribution of Xn is of the form Φ M OP ( Xn ) =

c 0 + c 1 Xn + c 2 X2 n + c 3 X3 n .
We perturb it up to as follows:

Ψ M OP ( Xn ) ∝ (1 + )c 0 + (1 -)c 1 X1+ n + (1 + )c 2 X2(1-) n + (1 -)c 3 X3(1+ ) n .
As for Ψ M T E , function Ψ M OP is normalized so that its integral over Ω Xn is equal to one. The average JSDs between distributions Φ( Xn ) and Ψ ( Xn ) for = 0.1, 0.05 and 0.01 are provided in Tables 7 and8 for MTEs and MOPs respectively. As can be observed, for = 0.05, both for MTEs and MOPs, and whatever the number of random variables, the JSDs between the true distribution Φ( Xn ) and the distribution g( Xn ) inferred by ctdBN are smaller than those between Φ( Xn ) and -perturbed distributions Ψ ( Xn ). This supports the fact that ctdBNs approximate very well MTBFs. Indeed, in real-world applications, the parameters of MTEs and MOPs are learnt from datasets and perturbed probability density functions Ψ ( Xn ) can be seen as the result of the imprecision on the values of these parameters due to this learning. We can therefore conclude that ctdBNs outperform MTBFs in terms of scalability of inference. As shown above, the cost of this speed increase is 2.90 × 10 -4 ± 5.12 × 10 -5 1.20 × 10 -5 ± 2.27 × 10 -6 32 1.08 × 10 -3 ± 5.32 × 10 -5

n JSD[Φ M T E ( Xn); g( Xn)] JSD[Φ M OP (
2.83 × 10 -4 ± 1.50 × 10 -5 1.17 × 10 -5 ± 6.58 × 10 -7 64 1.08 × 10 -3 ± 4.58 × 10 -5

2.83 × 10 -4 ± 1.30 × 10 -5 1.17 × 10 -5 ± 5.77 × 10 -7 128 1.06 × 10 -3 ± 4.89 × 10 -5

2.77 × 10 -4 ± 1.37 × 10 -5 1.15 × 10 -5 ± 6.04 × 10 -7 256 1.12 × 10 -3 ± 1.40 × 10 -4

2.93 × 10 -4 ± 3.87 × 10 -5 1.21 × 10 -5 ± 1.67 × 10 -6 a slight imprecision in the results of the inferences. All experiments have been performed using the C++ aGrUM library (http://www.agrum.org) on a Linux box with an Intel Xeon at 2.40GHz and 128GB of RAM.

Conclusion

In this paper, ctdBNs, a new graphical model for handling uncertainty over sets of continuous and discrete variables, have been introduced. We have proved that ctdBNs can approximate (arbitrarily well) any Lipschitz mixed probability distribution. So, theoretically, most of the mixed probability distributions used in real-world situations can be approximated by ctdBNs. Experiments highlight that this result is not only theoretic: in practice, ctdBNs are very expressive and can be exploited efficiently for diagnosis and classification tasks. A junction tree-based inference algorithm has also been provided. Its theoretical computational complexity has been given and it shows that inference in ctdBNs is essentially similar to that in classical discrete BNs. Here again, the experiments provided in the paper highlight the tractability of inference in practical situations.

For future works, we plan to enrich ctdBNs by allowing the conditional truncated densities assigned to the continuous nodes to depend not only on their discretized counterpart but also on other nodes, in particular their parents. This shall increase the expressive power of the model. In addition, if only parents are added, the conditional truncated densities are defined over the same discrete nodes as the CPTs of the discretized nodes. This shall ensure tractability of inference since the computational complexity of inference shall remain of the same order of that in a classical BN. But the expressive power shall be increased. In some sense, a ctdBN learning algorithm has already been provided in [START_REF] Mabrouk | Multivariate cluster-based discretization for Bayesian network structure learning[END_REF]. This algorithm raises some issues, notably the fact that computing discretizations conditionally to the nodes in the Markov blankets of each discretized node limits the ctdBNs that can be learnt. For instance, a discretized node with no parent and many children has a large Markov blanket, which may prevent discretization to be possible due to too high a memory requirement. Therefore, new algorithms are needed for learning ctdBNs from data. This is especially necessary if the set of parents of the continuous nodes Xi is no more limited to the discretized counterpart X i .

Acknowledgments

This work was supported by European project H2020-ICT-2014-1 #644425 Scissor.

Appendix: proofs

Proof of Lemma 1 By definition, f ( Xi |X i ) and P (X i ) are non-negative real-valued functions, hence f ( Xi |X i )P (X i ) is also a non-negative real-valued function. So, to prove that it is a mixed probability distribution, it is sufficient to show that:

x i ∈Ω X i Ω Xi f (x i |x i )P (x i ) dx i = 1.
By Property 1., f ( Xi = xi |X i = x i )P (X i = x i ) = 0 for all x i ∈ Ω X i and xi ∈ [t x i , t x i +1 ). So, the above equation is equivalent to:

x i ∈Ω X i t x i +1 tx i f (x i |x i )P (x i ) dx i = 1,
which, by the fact that x i is a constant inside the integral and by Equation [START_REF] Dechter | Bucket elimination: A unifying framework for reasoning[END_REF], is also equivalent to:

x i ∈Ω X i P (x i ) t x i +1 tx i f (x i |x i ) dx i = x i ∈Ω X i P (x i ) = 1.
As a consequence, f ( Xi |X i )P (X i ) is a mixed probability distribution.

Proof of Proposition 1 First, note that all the terms in the product are non-negative real-valued functions, hence h is also a non-negative real-valued function. Let

α = x 1 ∈X 1 • • • xn∈Xn Xd+1 • • • Xn n i=1 P (x i |Pa(x i )) n i=d+1 f (x i |x i )d xn • • • d xd+1 = x 1 ∈X 1 • • • xn∈Xn n i=1 P (x i |Pa(x i ))× Xd+1 f (x d+1 |x d+1 )d xd+1 • • • Xn f (x n |x n )d xn .
By Property 2 of Definition 4, each integral of a conditional truncated density is equal to 1, hence:

α = x 1 ∈X 1 • • • xn∈Xn n i=1 P (x i |Pa(x i )).
This formula is also equal to 1 since its terms constitute a discrete BN. Therefore, h(X) is a mixed probability distribution.

Proof of

{x∈ ΩC :||x||≥||å||} f (x)dx ≥ x∈B( b, 4M ) f (x)dx + {x∈ ΩC :||x||≥|| b||+ 4M } f (x)dx
and since f is Lipschitz, for every x inside Ball B b, 4M , we have that

|f (x) -f ( b)| ≤ M ||x -ẙ|| ≤ 2M 4M = 2 .
As f ( b) > , we can deduce that f (x) > /2 for every x ∈ B b, 4M and, therefore, that the middle term in the above equation is greater than 2 x∈B( b, 4M ) 1dx. This last integral corresponds to the volume of the intersection of the n-dimensional hyperball of radius 4M centered on b = ( b1 , . . . , bn ) with ΩC . As ≤ min{|Ω i |}, for each random variable Xi , at least one interval among ( bi -4M , bi ) and ( bi , bi + 4M ) belongs to Ω i . So the integral is greater than or equal to 1/2 n of the volume of an n-dimensional hyperball of radius r, which is equal to α = π n/2 r n /Γ( n 2 + 1). Consequently,

ΩC f (x)dx > B(0,||å||) f (x)dx + α 2 n+1 + {x∈ ΩC :||x||≥|| b||+ 4M } f (x)dx.
By our contradiction hypothesis, the same process can be applied to the last term and, by induction, it is possible to construct an infinite sequence

{ b(i)} i≥0 such that b(0) = b and, for all i ≥ 1, || b(i)|| ≥ || b(i -1)|| + 4M and f ( b(i)) > . Thus, for all k > 0, ΩC f (x)dx > x:||x||<||å|| f (x)dx+k α 2 n+1 + {x∈ ΩC :||x||≥|| b(k-1)||+ 4M } f (x)dx.
So ΩC f (x)dx tends toward +∞, which is impossible since f is a probability density function (hence its integral over ΩC is equal to 1). Therefore, there necessarily exists å ∈ ΩC such that, for every x ∈ ΩC , we have f (x) ≤ whenever ||x|| ≥ ||å||.

β n . So, if N ∞ = |L -∞ | + |L +∞ |, then: P (x) n i=1 h(x i |x i )| ≤ β nN∞ × √ nM n-N∞ . As N ∞ ≥ 1, nN ∞ ≥ n ≥ n -N ∞ + 1. Hence, as β = max{1, √ nM } and /β ≤ < 1, P (x) n i=1 h(x i |x i )| ≤ × β n-N∞ × √ nM n-N∞ ≤ .
If, on the contrary, L +∞ ∪ L -∞ = ∅, then all the Ω i|x i are bounded and their sizes are all equal to /( √ nM ), so Ω|x is also bounded. Let f -= min x∈ Ω|x f (x) and f + = max x∈ Ω|x f (x). Then:

Ω i|x i f -dx = √ nM n f -≤ P (x) ≤ √ nM n f + = Ω i|x i f + dx. As all the h(x i |x i )'s are equal to √ nM/ , we have f -≤ P (x) n i=1 h(x i |x i ) ≤ f + . Now, for any pair of elements (ẙ, z) of Ω|x , ||ẙ -z|| < n( / √ nM ) 2 = M . So, as f is Lipschitz, |f (ẙ) -f ( z)| ≤ M M = . As a consequence, f + -f (x) ≤ and f (x) -f -≤ . Hence, |f (x) -P (x) n i=1 h(x i |x i )| ≤ .
To complete the proof, note that any joint distribution P (X 1 , . . . , X n ) can be rewritten as P (X 1 , . . . , X n ) = P (X 1 ) n i=2 P (X i |X 1 , . . . , X i-1 ). Using this decomposition, we obtain a ctdBN whose discrete and continuous nodes are {X 1 , . . . , X n } and { X1 , . . . , Xn } respectively, and in which the parents of discretized node X i are the set {X 1 , . . . , X i-1 }, the conditional probability P (X i |X 1 , . . . , X i-1 ) resulting from the joint probability P (X 1 , . . . , X n ) are defined in the above paragraphs. Finally, to each X i is assigned as a child a continuous node Xi whose conditional truncated density is h( Xi |X i ) as defined in the above paragraph. As shown above, this ctdBN approximates f up to .

Proof of Corollary 1

The absolute value of the derivative of the density function of a univariate normal distribution is highest at its inflection point, which corresponds to x = µ±σ. At that point, the derivative is equal to M = exp(-0.5)/( √ 2πσ 2 ). So the univariate normal distribution is Lipschitz. By Proposition 2, it can be approximated up to by a ctdBN.

The density function of a multivariate normal distribution is equal to:

f (x) = 1 (2π) n |Σ| exp - 1 2 (x -µ) T Σ -1 (x -µ) .
Σ -1 being invertible, it is diagonalizable and its eigenvalues are all different from 0. By expressing x in the basis of the eigenvectors, f (x) becomes a product of univariate normal distributions and the preceding paragraph implies that f is Lipschitz and can be approximated up to by a ctdBN. The density of the Beta distribution is f

(x) = xα-1 (1 -x) β-1 /B(α, β), with B(α, β) = Γ(α)Γ(β)/Γ(α + β). The derivative is therefore equal to f (x) = [(α-1)(1-x)-(β -1)x](α-1)x α-2 (1-x) β-2 /B(α, β) If 2 = α < β, then |f (x)
| is maximal when x = 0 and it is equal to (α -1)/B(α, β). If 2 = β < α, then |f (x)| is maximal when x = 1 and it is equal to (β -1)/B(α, β). Finally, if 2 < α and 2 < β, it is known that the Beta distribution is bellshaped with two inflection points at x = (α -1 ± (α-1)(β-1) α+β-3 )/(α + β -1). So the derivative is bounded and f is Lipschitz.

When α > 2, the Gamma distribution is bell-shaped and its inflection points are β(α -1 ± √ α -1). Hence, the distribution is Lipschitz. To complete the proof, consider a set XC of sets of random variables XC = { X1 , . . . , Xn } such that all the Xi 's are mutually independent. Let f i , i = 1, . . . , n, be the respective density functions of the Xi 's and assume that all the f i 's belong to the probability density functions defined in the above paragraphs. Then, every f i can be approximated up to 0 = /2 n by some ctdBN B i defining a mixed probability distribution g i , i.e., for any xi ∈ Xi , |f i (x i ) -g i (x i , xi )| ≤ 0 , where x i correspond to the discretized value of xi . Now, the joint density function f : XC → R is defined as f (x) = n i=1 f i (x i ), for all x = (x 1 , . . . , x n ) since the Xi 's are mutually independent. Let B be the ctdBN resulting from the union of all the B i 's, i.e., its graphical structure is the union of all the graphical structures of the B i 's and B represents mixed probability g(x, x) = n i=1 g i (x i , xi ). So, we have that g(x, x) ≤ n i=1 (f i (x i ) + 0 ). Let S k be the set of k-subsets of {1, . . . , n}. Then:

n i=1 (f i (x i ) + 0 ) = n i=1 f i (x i ) + n-1 k=0 S∈S k   n-k 0 j∈S f j (x j )   . (9)
As the f j 's are probability density functions, j∈S f j (x j ) ≤ 1. In addition, for every n, k, we have that n-k

0 ≤ 0 since 0 < 1. Finally, n-1 k=0 S∈S k 1 <
2 n since this corresponds to the size minus 1 of the power set of {1, . . . , n}. So, the right hand side of Equation ( 9) is less than or equal to n i=1 f i (x i ) + 2 n 0 = f (x) + . We can show similarly, that g(x, x) ≥ f (x) -. So ctdBN B approximates up to probability density function f . Proof of Proposition 3 If X D = ∅, then Proposition 3 exactly corresponds to Proposition 2. So, assume that X D = ∅.

For every y = (y 1 , . . . , y d ) ∈ Ω D , let π(y) = x∈ XC f (y, x)dx. As y corresponds to the discrete part of f , π(y) corresponds to the probability of y w.r.t. f . So k y : ΩC → R defined as k y (x) = f (y, x)/π(y) for all x ∈ ΩC is a probability density function. In addition, by the hypotheses of Proposition 3, it is Lipschitz. Hence the proof of Proposition 2 can be applied on it. Let us call åy the vector å of this proof applied on k y (•). In addition, let å denote a vector of {å y : y ∈ Ω D } with the highest L2-norm. Then, for every y ∈ Ω D and any x ∈ ΩC , we have k y (x) ≤ whenever ||x|| ≥ ||å||. Applying the proof of Proposition 2, with this value of å, we can therefore perform the same discretization of x into x and construct the same conditional truncated density functions h(x|x) for all the values of y. The proof of Proposition 2 also shows that, by setting P y (x) = Ω|x k y (x)dx, then we have that: k y (x) -P y (x) n i=d+1 h(x i |x i ) ≤ , for all x ∈ ΩC and all y ∈ Ω D , (10) and

x P y (x) = 1 for every y. In other words, P y (x) corresponds to a conditional distribution of x given y. Define P (y, x) = P y (x) × π(y). Then, P (y, x) corresponds to the joint distribution of x and y (i.e., x,y P (y, x) = 1). So, as k y (x) = f (y, x)/π(y) and π(y) ≤ 1 (since it is a probability), Equation [START_REF] Moral | Mixtures of truncated exponentials in hybrid Bayesian networks[END_REF] implies that: f (y, x) -P (y, x) n i=d+1 h(x i |x i ) ≤ π(y) ≤ , for all (y, x) ∈ Ω D × ΩC .

The completion of the proof is now the same as that of Proposition 2: joint distribution P (y, x) can be decomposed as P (y 1 ) × d i=2 P (y i |y 1 , . . . , y i-1 ) × P (x d+1 |y 1 , . . . , y d ) n j=d+2 ×P (x j |y 1 , . . . , y d , x d+1 , . . . , x j-1 ) and the resulting ctdBN follows.

Proof of Proposition 4 According to the proof of Proposition 3, since f is Lipschitz, the continuous variables Xi of XC can be discretized into discrete variables X i of X C = {X d+1 , . . . , X n } and, for all (y, x) ∈ Ω D × ΩC , f (y, x) can be approximated up to by P (y, x) n i=d+1 h(x i |x i ), where x is the discretized counterpart of x and P (y, x) is the joint probability distribution defined as:

P (y, x) = Ω|x f (y, x)dx. ( 11
)
Let us show that this joint distribution can be decomposed w.r.t. sets C i = X D i ∪X C i ∪ XC i , i = 1, . . . , k. Proof by induction on i: let i = 1 and let X E 1 = X D \ X C 1 and XE 1 = XC \ XC 1 . Function f can be decomposed as f (y, x) = f 1 (y C 1 , xC 1 )×h 1 (y E 1 , xE 1 ), with h 1 (y E 1 , xE 1 ) = k j=2 f j (y C j , xC j ). Note that f 1 and h 1 share no variable in common. Then Equation ( 11) is equal to:

P (y, x) = Ω|x C 1 Ω|x E 1 f 1 (y C 1 , xC 1 ) × h 1 (y E 1 , xE 1 )dx E 1 dx C 1 = Ω|x C 1 f 1 (y C 1 , xC 1 )dx C 1 Ω|x E 1 h 1 (y E 1 , xE 1 )dx E 1
Now, we also have that:

P (y C 1 , x C 1 ) = y E 1 x E 1 P (y, x) = Ω|x C 1 f 1 (y C 1 , xC 1 )dx C 1 y E 1 x E 1 Ω|x E 1 h 1 (y E 1 , xE 1 )dx E 1 = Ω|x C 1 f 1 (y C 1 , xC 1 )dx C 1 y E 1 ΩE 1 h 1 (y E 1 , xE 1 )dx E 1
Note that, by definition, h 1 (y E 1 , xE 1 ) = k j=2 f j (y C j , xC j ) is a mixed probability distribution over Ω E 1 × ΩE 1 . Consequently, we have that: ). So, P can be decomposed similarly to f as concerns clique C 1 . By induction, we can repeat the same process with mixed probability h 1 rather than f and the result follows.

y E 1 ΩE 1 h 1 (y E 1 ,
Proof of Proposition 5 By definition, the product of all the functions stored into junction tree T is a mixed probability distribution P (x, x, e). So it satisfies the Shafer-Shenoy axioms [START_REF] Shenoy | Axioms for probability and belief function propagation[END_REF][START_REF] Shafer | Probabilistic expert systems[END_REF]. As a consequence, the messagepassing algorithm is sound and, for each clique, the function resulting from the multiplication of the functions stored in any clique by the messages sent to this clique is the joint (mixed) probability of the variables of the clique and evidence e. So, if the clique contains only discrete variables, after normalizing this resulting function, we necessarily get a joint posterior distribution of the variables of the clique. On the other hand, if the clique contains a continuous variable Xk , then the resulting function is necessarily the posterior mixed distribution of X k and Xk given evidence e and, by marginalizing out X k , we get the posterior density function of Xk .

Proof of Proposition 6 There are at most n continuous random variables. Computing each message they send to their neighbor corresponds to perform |Ω X i | ≤ k integrals. Hence the overall complexity of computing all these messages is in O(nkI). As there are n random variables, there are at most n cliques containing only discrete variables. The complexity of computing their messages in both directions is therefore in O(nk w+1 ). For the same reason, the complexity of sending messages from the cliques with only discrete variables to the cliques containing continuous variables is also O(nk w+1 ). To compute the posterior of any discrete or discretized variable, it is sufficient to select one clique that contains it, to multiply the tables stored into this clique by all the messages sent to the clique and, then to marginalize out all the other variables. When performing the distribution phase, the tables stored into the clique are already multiplied by all the messages sent to the clique except one. So, to compute the posterior of the discrete variable, we just need to perform the last product required, with a complexity in O(k w+1 ) and the summation (marginalizing-out) has the same complexity. Finally, there are n continuous variables. To compute the posterior density of a continuous variable, we must perform the operations of Equation [START_REF] Lauritzen | Graphical models for associations between variables, some of which are qualitative and some quantitative[END_REF]. There are at most k products to perform and each product has an average complexity of J, hence the overall complexity of computing all the posterior densities is in O(nkJ). Overall, we get the complexity stated in the proposition.

Figure 1 :

 1 Figure 1: A BN with conditional truncated densities.

  the domains of X C and X respectively;• B represents a mixed probability density function g : Ω → R such that, for every (y, x) ∈ Ω D × ΩC , |g(y, x, x) -f (y, x)| ≤ , where x corresponds to the discretized counterpart of x.

Figure 2 :

 2 Figure 2: A junction tree for the ctdBN of Figure 1.

Figure 3 :

 3 Figure 3: The BN structure used for approximating MTBFs.

Figure 4 :

 4 Figure 4: The ratio of inference times in MTEs and ctdBNs by the number of variables.

Figure 5 :

 5 Figure 5: The ratio of inference times in MOPs and ctdBNs by the number of variables.

Table 1 :

 1 UCI datasets used for BN/ctdBN comparisons in classification tasks.

	dataset	#attributes #classes #instances #continuous attr.
	australian	14	2	690	6
	cleve	14	2	296	13
	crx	16	2	653	6
	glass2	10	2	163	9
	iris	5	3	150	4
	pima	9	2	768	8
	shuttle small	10	7	3866	9
	vehicle	19	4	846	18

Table 2 :

 2 The standard deviations for the beliefs on the observations of the Xi's. The domain sizes of the Xi's are given inside parentheses. In each dataset, the first variable/column is called X1 or X1, the second one X2 or X2, etc. Class variable X0 is always located in the last column of the dataset.

Table 3 :

 3 Comparisons between BNs and ctdBNs for classification tasks. The first two columns present the average accuracies and the accuracies' standard deviations over the 100 datasets constructed from each UCI dataset. The third column displays the gain in accuracy of using ctdBNs instead of BNs (the subtraction of the first column from the second one). Assuming that accuracies are distributed w.r.t. normal distributions of parameters the average BN accuracy and the variance of the BN accuracy, the last column shows the p-value obtained by the ctdBN accuracy.

Table 4 :

 4 Average inference times (plus standard deviations) for MTEs and ctdBNs. These averages are computed over the 25 different networks defined for each number n of variables.

	n	T mte (ms)	T ctdBN (ms)	T mte /n T ctdBN /n
	4	0.30 ± 0.03	1.59 ± 0.16	0.07	0.40
	8	0.57 ± 0.08	3.53 ± 0.31	0.07	0.44
	16	1.67 ± 1.10	7.14 ± 0.41	0.10	0.45
	32	5.79 ± 0.87	13.99 ± 1.35	0.18	0.44
	64	23.68 ± 2.01	29.22 ± 1.92	0.37	0.46
	128 122.37 ± 10.99 50.87 ± 6.88	0.96	0.40
	256 708.11 ± 37.12 96.02 ± 13.79	2.77	0.38

Table 5 :

 5 Average inference times (plus standard deviations) for MOPs and ctdBNs. These averages are computed over the 25 different networks defined for each number n of variables.

  Xn); g( Xn)] 4 2.47 × 10 -4 ± 7.19 × 10 -5 8.07 × 10 -5 ± 7.40 × 10 -6 8 2.33 × 10 -4 ± 8.28 × 10 -5 8.33 × 10 -5 ± 4.24 × 10 -6 16 2.32 × 10 -4 ± 7.56 × 10 -5 8.24 × 10 -5 ± 6.13 × 10 -6 32 2.56 × 10 -4 ± 8.15 × 10 -5 8.30 × 10 -5 ± 5.48 × 10 -6 64 2.58 × 10 -4 ± 9.05 × 10 -5 8.10 × 10 -5 ± 7.11 × 10 -6 128 2.07 × 10 -4 ± 6.72 × 10 -5 7.85 × 10 -5 ± 7.83 × 10 -6 256 2.39 × 10 -4 ± 7.87 × 10 -5 8.18 × 10 -5 ± 5.11 × 10 -6

Table 6 :

 6 Average Jensen-Shannon Divergences between Φ( Xn) and g( Xn) for different numbers of variables. 10 -3 ± 4.02 × 10 -52.84 × 10 -4 ± 1.14 × 10 -5 1.18 × 10 -5 ± 5.06 × 10 -7 81.08 × 10 -3 ± 5.39 × 10 -5 2.81 × 10 -4 ± 1.51 × 10 -5 1.16 × 10 -5 ± 6.64 × 10 -7 16 1.11 × 10 -3 ± 1.80 × 10 -4

			JSD[Φ M T E ( Xn); Ψ M T E ( Xn)]
	n	= 0.1	= 0.05	= 0.01
	4	1.09 ×

Table 7 :

 7 Average Jensen-Shannon Divergences between Φ M T E ( Xn) inferred by MTE and its perturbed distributions. 10 -4 ± 7.32 × 10 -5 2.13 × 10 -4 ± 1.92 × 10 -5 8.80 × 10 -6 ± 7.93 × 10 -7 16 8.43 × 10 -4 ± 8.58 × 10 -5 2.19 × 10 -4 ± 2.16 × 10 -5 9.04 × 10 -6 ± 8.65 × 10 -7 32 8.33 × 10 -4 ± 7.70 × 10 -5 2.17 × 10 -4 ± 1.98 × 10 -5 8.96 × 10 -6 ± 8.10 × 10 -7 64 8.94 × 10 -4 ± 1.17 × 10 -4 2.33 × 10 -4 ± 3.04 × 10 -5 9.61 × 10 -6 ± 1.25 × 10 -6 128 9.24 × 10 -4 ± 1.54 × 10 -4 2.40 × 10 -4 ± 3.91 × 10 -5 9.88 × 10 -6 ± 1.57 × 10 -6 256 8.59 × 10 -4 ± 1.06 × 10 -4 2.24 × 10 -4 ± 2.76 × 10 -5 9.25 × 10 -6 ± 1.14 × 10 -6

	n	= 0.1	= 0.05	= 0.01
	4	8.86 × 10 -4 ± 1.37 × 10 -4	2.31 × 10 -4 ± 3.58 × 10 -5	9.54 × 10 -6 ± 1.48 × 10 -6
	8	8.17 ×

JSD[Φ M OP ( Xn); Ψ M OP ( Xn)]

Table 8 :

 8 Jensen-Shannon Divergences for marginalized distributions of Xn in MOPs w.r.t. the marginals obtained using perturbed MOPs.

  Proposition 2 Without loss of generality, we will assume in the sequel that ≤ min{|Ω i | : i ∈ {1, . . . , n}}, where |Ω i | denotes the size of domain Ω i . In addition, let us denote by B(x, r) the intersection of the hyperball of radius r centered on x with ΩC . First, let us show that there exists å ∈ ΩC such that, for every x ∈ ΩC , we have f (x) ≤ whenever ||x|| ≥ ||å||. Proof by contradiction: assume that, for every å ∈ ΩC , there exists x ∈ ΩC such that ||x|| ≥ ||å|| and f (x) > . Then: By hypothesis, there exists b ∈ ΩC such that || b|| ≥ ||å|| + 4M and f ( b) > . So, since f is a probability density function, i.e., it is a positive function, the last term of the above equation is such that:

	f (x)dx =	f (x)dx +	f (x)dx.
	ΩC	B(0,||å||)	{x∈ ΩC :||x||≥||å||}

  xE 1 )dx E 1 = 1,and, therefore, that P (yC 1 , x C 1 ) = Ω|x C 1 f 1 (y C 1 , xC 1 )dx C 1 .We can prove in a similar way that P (yE 1 , x E 1 ) = Ω|x E 1 h 1 (y E 1 , xE 1 )dx E 1 . Consequently, P (y, x) = P (y C 1 , x C 1 )P (y E 1 , x E 1

By abuse of notation, we use interchangeably Xi ∈ X to denote a node in the BN and its corresponding random variable.

X 1 X 2 X 4 X 1 X 1 X1 X 1 X 4 X 1 X 3 X 4 X 3 X 3 X3 X 3 X 4 X 3 X 4 X 5 X 5 X 5 X5 X 5 X 5 X 6

The conditional truncated densities we use in our ctdBNs are in fact Beta rectangular distributions with parameters α = 2 and β = 1.

the structure of Figure 3 allows to perform a fair comparison of how well ctdBNs' and MTBFs' inferences scale with increasing numbers of random variables.

As the structure of B is imposed, only B's parameters (CPTs P B d (X i |X i-1 ) and functions g i ( Xi |X i )) need be learnt. This learning is performed iteratively, i.e., in a first step, functions P B d (X 1 ), P B d (X 2 |X 1 ), g i ( X1 |X 1 ) and g i ( X2 |X 2 ) are determined. Then, assuming that ctdBN B has been constructed for variables X 1 , X1 up to X i-1 , Xi-1 , we learn P B d (X i |X i-1 ) and g i ( Xi |X i ). More precisely, to learn the parameters related to X i , Xi , we first perform an inference in the MTBF in order to compute:

We also compute Φ( Xi ) =

Xi-1 Φ( Xi-1 , Xi ). Then we sample 500 000 times the potentials Φ( Xi-1 , Xi ) and Φ( Xi ) using the Metropolis-Hastings algorithm [START_REF] Hastings | Monte carlo sampling methods using markov chains and their applications[END_REF] and the Inverse Transform Sampling's method, respectively. Discretizing these samples using the discretizations of Xi-1 and Xi defined above results in new discrete samples from which we determine by maximum likelihood some probability distributions P (X i-1 |X i ) and P (X i ) respectively. Note that, due to the finite size of the samples, the estimated distributions P (X i-1 |X i ) and P (X i ) are not necessarily equal to P B d (X i-1 |X i ) and P B d (X i ). From these two distributions, we compute

The goal of constructing joint distribution P (X i-1 , X i ) in this two-step process rather than directly from the sample of Φ( Xi-1 , Xi ) is to ensure that, in this joint, the marginal distribution P (X i ) is as close as possible to distribution Φ( Xi ), which may not be the case when sampling with Metropolis-Hastings uniquely on pairs ( Xi-1 , Xi ), due to the finite size of the samples. Finally, we define P B d (X 1 ) = P (X 1 ) and, for every i > 1,

is computed by inference in the ctdBN constructed so far.

In our experiments, for every j, conditional density g i ( Xi

) and is equal to 0 everywhere else. Therefore, it is of the form g i (x i |X i = j) = α i,j xi + β i,j on this interval and, since this is a probability density function, we have that:

Now, for any continuous variable Xi of XC , let t - i = max{inf Xi , -||å||} and t + i = min{sup Xi , ||å||}. Define a discretization function d i of Xi by its set of cutpoints {t k i }:

Applying discretization function d i to Xi , we obtain a discretized random variable X i of domain Ω i . Let X D be the set of all these discretized variables and let Ω D = n i=1 Ω i . Finally, for any value x i of discretized variable X i , denote by Ωi|x i the subdomain of variable Xi compatible with x i , i.e., Ωi|x i = [t

i=1 Ωi|x i . We can now construct a joint probability distribution over Ω D and conditional truncated densities as follows: for every x = (x 1 , . . . , x n ) ∈ Ω D , partition the set of indices {1, . . . , n} into L = {i : Ωi|x i is bounded}, L -∞ = {i : inf Ωi|x i = -∞} and L +∞ = {i : sup Ωi|x i = +∞}. Fix the joint probability value of x = (x 1 , . . . , x n ) to P (x) = Ω|x f (x)dx and define for all xi ∈ Ω|x i the truncated conditional density function h(x i |x i ) as:

where β = max{1, √ nM }. Then, it is easy to see that P (•) is non-negative and that x∈Ω D P (x) = ΩC f (x)dx = 1. In addition, Ω|x i h(x i |x i )dx i = 1 for all x i since the formulas for i ∈ L -∞ ∪ L +∞ are nothing else than twice the density function of a Normal distribution of variance 2 π β n

. So for all x i , since h(x i |x i ) ≥ 0, h is a truncated conditional density function. Consequently P (x) n i=1 h(x i |x i ) defines a mixed probability distribution. Now, let us show that, for all x ∈ ΩC , |f (x) -P (x) n i=1 h(x i |x i )| ≤ , where x is the discretized value of x. Consider any element x ∈ ΩC . First, assume that L +∞ ∪ L -∞ = ∅, then ||x|| ≥ ||å|| and, consequently, f (x) ≤ . By definition, P (x) ≤ 1. In addition, for all i ∈ L +∞ ∪ L -∞ , h(x i |x i ) ≤