{'fraction_non_alphanumeric': 0.04832659065833027, 'fraction_numerical': 0.011670957459850435, 'mean_word_length': 4.169328263624841, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Estimating Conditional Mutual Information for Discrete-Continuous Mixtures using Multi-Dimensional Adaptive Histograms

Estimating conditional mutual information (CMI) is an essential yet challenging step in many machine learning and data mining tasks. Estimating CMI from data that contains both discrete and continuous variables, or even discrete-continuous mixture variables, is a particularly hard problem. In this paper, we show that CMI for such mixture variables, defined based on the Radon-Nikodym derivate, can be written as a sum of entropies, just like CMI for purely discrete or continuous data. Further, we show that CMI can be consistently estimated for discrete-continuous mixture variables by learning an adaptive histogram model. In practice, we estimate such a model by iteratively discretizing the continuous data points in the mixture variables. To evaluate the performance of our estimator, we benchmark it against state-of-the-art CMI estimators as well as evaluate it in a causal discovery setting.


Introduction
In many research areas, such as classification [16], feature selection [34], and causal discovery [29], estimating the strength of a dependence plays a key role. A theoretically appealing way to measure dependencies is through mutual information (MI) since it has several important properties, such as the chain rule, the data processing inequality, and-last but not least-it is zero if (and only if) two random variables are independent of each other [4]. For structure identification, such as causal discovery, conditional mutual information (CMI) is even more interesting since it can help to distinguish between different graph structures. For instance, in a simple Markov chain X → Z → Y , X and Y may be dependent, but are rendered independent given Z. Vice versa, a collider structure such as X → Z ← Y may introduce a dependence between two marginally independent variables X and Y when conditioned on Z.
While estimating (conditional) mutual information for purely discrete or continuous data is a well-studied problem [4,5,8,10,22], many real-world settings concern a mix of discrete and continuous random variables, such as age (in years) and height, or even random variables that can individually consist of a mixture of discrete and continuous components. Although several discretization-based approaches that can estimate MI for a mix of discrete and continuous random variables have recently emerged [2,17,31], so far only methods based on k-nearest neighbour (kNN) estimation were shown to work on mixed variables, which may consist of discrete-continuous mixture variables [7,19,24].
Regardless of the success of kNN-based estimators, discretization-based approaches have attractive properties, e.g., with regard to global interpretation. That is, a natural and understandable way to discretize a continuous random variable is via creating a histogram model, where we cut the sample space of the continuous variable in multiple non-overlapping parts called bins [27], or (hyper)rectangles for multi-dimensional variables. Within a bin, we consider the distribution to be constant, which allows us to estimate the density function via Riemann integration by making the bins smaller and smaller [4]. This definition, however, is less straightforward when mixed variables are involved.
In this paper, we approach the problem as follows: we first extend the definition of entropy for a univariate discrete-continuous mixture variable given by Politis [23] to multivariate variables. Using this definition, we show that CMI for mixed random variables can be written as a sum of entropies that are well-defined through the Radon-Nikodym derivate (see Sec. 2). Exploiting this property, we propose a consistent CMI estimator for such data that is based on adaptive histogram models in Sec. 3. To efficiently learn adaptive histograms from data, in Sec. 4 we define a model selection criterion based on the minimum description length (MDL) principle [9]. Subsequently, we propose an iterative greedy algorithm that aims to obtain the histogram model that minimizes the proposed MDL score in Sec. 5. We discuss related work in Sec. 6 and in Sec. 7, we empirically show that our method performs favourably to state-of-the-art estimators for mixed data and can be used in a causal discovery setting.

Entropy for Mixed Random Variables
We consider multi-dimensional mixed random variables, of which any individual dimension can be discrete, continuous, or a discrete-continuous mixture. Further, we call a vector of such mixed random variables a mixed random vector. For a mixed random vector (X, Y ), where X and Y are possibly multivariate, we need to adopt the most general definition of mutual information (MI), i.e., the measure-theoretic definition: where dP XY /(dP X P Y ) is the Radon-Nikodym derivative, dP XY the joint measure, and P X P Y the product measure. It has been proven that P X P Y is absolutely continuous with respect to P XY [7], i.e., P XY = 0 whenever P X P Y = 0; and therefore, such a Radon-Nikodym derivative always exists and I(X, Y ) is welldefined. This measure-theoretic definition can be extended to CMI using the chain rule: It is common knowledge that for purely discrete or continuous random variables, CMI can be written as a sum of entropies, i.e., . What is not clear, however, is if this formula also holds when (X, Y, Z) contains discretecontinuous mixture random variables. We investigate this problem in two steps. We first define the measuretheoretic entropy for a (possibly multi-dimensional) discrete-continuous mixture random variable and prove it to be well-defined, though previous work claimed the opposite [7]. Second, using this definition, we prove that (conditional) MI for a mixed random vector can be written as the sum of measure-theoretic entropies, just like purely continuous or discrete random vectors.

A Generalized Definition of Entropy
The measure-theoretic entropy is defined only for onedimensional random variables [23]. Building upon this definition, we give an explicit proof that such a onedimensional measure-theoretic entropy is well-defined, and then extend this definition to the multi-dimensional case, which we prove is also well-defined.

Generalized One-Dimensional Entropy
We start off by reviewing the existing definition for the one-dimensional case [23]. Given a one-dimensional random variable X, entropy H is defined as where v(·) is a measure defined on all one-dimensional Borel sets [23]. If v(·) is the Lebesgue measure, which we denote as u(·), H(X) becomes the differential entropy. Alternatively, if v(·) is a counting measure, H(X) becomes the common (discrete) entropy. If, however, X is a discrete-continuous mixture variable, v is defined as follows. We split R into three disjoint subsets s.t. R = S d ∪ S c ∪ S o . First, S o is the subset of R on which X has zero probability measure, i.e., P X (S o ) = 0. Second, the set S d contains all discrete points, i.e., S d is countable and ∀x ∈ S d , P X (x) > 0. Third, S c covers the continuous points, hence P X (S c ) + P X (S d ) = 1 and for any Borel set A ⊆ S c satisfying u(A) = 0, we have P X (A) = 0. Based on these three subsets S d , S c , and S o , we can define v as where |A ∩ S d | is the cardinality of this intersection.
To show that the generalized one-dimensional entropy is well-defined, we need to prove that the Radon-Nikodym derivative dP X /dv always exists. This we show in the following lemma.
Lemma 2.1. Given a one-dimensional discretecontinuous random variable X with probability measure P X , P X is absolutely continuous w.r.t. v, i.e., P X = 0 whenever v = 0, and hence dP X /dv always exists.
We provide the proof of Lemma 2.1, as well as for Lemmas 2.2 and 2.3 in Supplementary Material S.1.

Generalized Multi-Dimensional Entropy
In the following, we extend the measure-theoretic entropy definition to a mixed k-dimensional random vector W = (W 1 , . . . , W k ). For each W i , we define S i d , S i c , S i o and measure v i as above, and also define the product measure v for the k-dimensional random vector as v = v 1 × . . . × v k . Then, define the entropy for W as To prove that such entropy is well-defined, we show that dP W /dv always exists.
Lemma 2.2. Given a mixed k-dimensional random vector W = (W 1 , . . . , W k ) with probability measure P W , dP W /dv always exists.
Last, based on Lemma 2.1 and 2.2, we can prove that just like for a purely continuous or discrete random vector, conditional mutual information for a mixed random vector can be written as a sum of entropies. As a direct implication of the above proof, it follows that mutual information can also be written as the sum of entropies, since it is a special case of CMI with Z = ∅. With this generalized definition, we can now show how to estimate CMI using adaptive histogram models.

Adaptive Histogram Models
Adaptive histogram models have been thoroughly studied for continuous random variables [27]; however, to the best of our knowledge, there exists no rigorous definition of histograms for mixed random variables. Thus, to use histogram models as a foundation to estimate the measure-theoretic (conditional) MI, we need to rigorously define histograms for mixed random variables. We start with the one-dimensional case.

One-Dimensional Histogram Models
A histogram model is typically defined based on a set of consecutive intervals called bins [27]. However, to deal with discrete-continuous mixture random variables, we define the set of bins, denoted as B, such that each bin is either an interval or a set containing only a single point. That is, B = B ∪ B , where B and B are sets of subsets of R, with B consisting of countable consecutive intervals and B consisting of countable single point sets. Last, we define the "width" of a bin using the measure v as defined in Eq. 2.1, i.e., for a bin As any B j ∈ B contains only a single discrete point, v(B j ) = 1 for all B j ∈ B .
Further, we define a histogram model M as a set of bins equipped with a parameter vector of length K, where K = |B| is the number of bins. That is, a histogram model M is a family of probability distributions P X,θ , parametrized by the vector θ = (θ 1 , . . . , θ K ). Each element of θ represents the Radon-Nikodym derivative (or density) of each bin. Note that this definition generalizes to purely continuous random variables when B = ∅ and also to discrete random variables if B = ∅. For the latter case, the histogram model degenerates to a multinomial model.

Multi-Dimensional Histograms
First, we define the set of multi-dimensional bins. For a mixed k-dimensional random vector W = (W 1 , . . . , W k ), we define the set of bins for each W i as in Sec. 3.1, denoted as B i . Consequently, we can define a set of kdimensional bins, denoted B, by the Cartesian product Since each B i is countable, B is also countable, and we can hence assume B is indexed by j. Then, we split B in a similar way as in the one-dimensional case, i.e., B = B ∪ B , where B contains only discrete values. That is, for any k-dimensional bin B j ∈ B , each dimension of B j is a set that contains a single onedimensional point. Note that, however, for any B j ∈ B , each dimension of B j can either be a one-dimensional interval or a one-dimensional single-point set. Further, we define the volume of a multi-dimensional bin B j ∈ B using the product measure v(B j ) (see Sec. 2.1.2).
Similar to one-dimensional histograms, a multidimensional histogram model M can be described by a probability distribution P W,θ parametrized by the vector θ = (θ 1 , . . . , θ K ), where K is the number of bins and θ i is the Radon-Nikodym derivative for each bin.

Maximum Likelihood Estimator
Given a possibly multi-dimensional histogram with K bins, we denote the Radon-Nikodym derivative dP W,θ /dv as f h θ and its maximum likelihood estimator as f ĥ θ . Observe that for any parameter θ j ∈ θ, the product θ j v(B j ) follows a multinomial distribution. Thus, given a dataset D = {D i } i=1,...,n , with D i representing a row, the maximum log-likelihood is denoted as and equal to where c j and v(B j ) are respectively the number of data points and the bin volumes of bin j ∈ {1 . . . K}. Notice that this maximum likelihood generalizes to the purely discrete case (i.e., multinomial distribution) where all v(B j ) = 1, and to the purely continuous case [27] where v becomes the Lebesgue measure.

Conditional Mutual Information Estimator
Combining all previous theoretical discussions, we can now estimate conditional mutual information for three (possibly multivariate) random variables X, Y and Z by in which f ĥ θ (x, y, z) is the maximum likelihood estimator given the data, while we obtain f ĥ θ (x, z), f ĥ θ (y, z), and f ĥ θ (z) via marginalization from f ĥ θ (x, y, z). Next, we will prove that I h is a strongly consistent estimator for conditional mutual information on mixed data.
almost surely, where n refers to the sample size and v refers to the maximum of the histogram volumes for bins in B (defined in Sec. 3.2).
The proof is provided in Supplementary Material S.1. Informally, our proof is based on the following key aspects: 1) All volume-related terms in I h cancel out, 2) discrete empirical entropy converges to the true entropy almost surely [1], and 3) in the limit, differential entropy can be obtained by discretizing a continuous random variable into "infinitely" small bins [4,Theorem 8.3.1]. Notably, the order of the double limit in Theorem 3.1 inherently indicates that n should grow faster than the number of bins [26], which is also required for histograms on purely continuous data to converge [27].

Learning Adaptive Histograms from Data
To efficiently estimate a histogram model that inherits the consistency guarantees from Theorem 3.1 we need to consider the following requirements. First of all, we need to ensure that we learn a joint histogram model over (X, Y, Z). This is due to the fact that we obtain the lower-dimensional entropies such as H h (X, Z) by marginalization over the likelihood estimator f ĥ θ (x, y, z). If we would not learn a joint model, the volume-related terms in H h (X, Y, Z), H h (X, Z), H h (Y, Z), and H h (Z) would not cancel out. In addition, we need to make sure that the number of bins is in o(n) and increases if we were to increase the number of samples n, while at the same time the size of the bins decreases.
One way to achieve those properties would be to fix the bin width or the number of bins depending on the number of samples. However, such an approach is not very flexible and does not allow for variable bin widths. To allow for a more flexible model, we formally consider the problem of constructing an adaptive multi-dimensional histogram as a model selection problem and employ a selection criterion based on the minimum description length (MDL) principle [25]. MDLbased model selection has been successfully used for learning one-dimensional [13] and two-dimensional histograms [11,36], demonstrating adaptivity to both local density changes and sample size.
We now briefly introduce the MDL principle and define the MDL-optimal histogram model. Specifically, while previous work [11,13,36] only considers purely continuous data (or more precisely, data with arbitrarily small precision), we apply the MDL principle to mixedtype data, based on our rigorous definition of histogram models for mixed random variables. On top of that, we empirically show that our score fulfils the desired properties-i.e. the number of bins grows as o(n).

MDL and Stochastic Complexity
The minimum description length principle is arguably one of the best off-the-shelf model selection criteria [9], which has been successfully applied to many machine learning and data mining tasks. The general idea is to assign a code length to data D compressed by a model M , e.g., a histogram model. Given a collection of candidate models, denoted as M, MDL selects the model M * that minimizes the joint code length of the model and the data. Formally, our goal is to find where L(D|M ) denotes the code length 1 of the data given the model, while L(M ) denotes the code length needed to encode the model.
The optimal way of encoding data D given M , in the sense that it will result in minimax regret, is to use the normalized maximum likelihood (NML) code [9]. Accordingly, the code length of the data is called stochastic complexity (SC), which is defined as the sum of the negative log-likelihood −l M (D), defined in Eq. 3.3, and the parametric complexity (also called regret) log R(n, K) [9]. The parametric complexity of a histogram model with K bins is given by [13,36] and can be computed in sub-linear time [20].

Code
Length of the Model Given a dataset D with n rows and k individual columns D j , we now define the model class M. First, we create fixed bins according to B (as defined in Sec. 3.2) per discrete value that occurs in D j . Next, we enumerate all possible bins for B with fixed precision . To this end, denote the remaining non-discrete data points in D j as D c j . If D c j is empty D j corresponds to a discrete variable and we can stop here. Otherwise, we create all possible cut points for D c j as C 0 j = {min(D c j ), min(D c j ) + , . . . , max(D c j )}. By selecting a subset of cut points C j ⊆ C 0 j , we get a valid solution for B . We can enumerate all possible segmentations by enumerating each C j ⊆ C 0 j . By repeating this process for each dimension, we obtain our model class M. Further, we get the code length for a model M ∈ M by encoding all combinations of cut points for each dimension [13], i.e., This completes the definition of our final optimization score L(D|M ) + L(M ).
To proof consistency for this score, we need to show that the number of selected bins grows at rate o(n).
Since the theoretical analysis is rather difficult, we instead empirically demonstrate this property for Gaussian distributed data in Supplementary Material S.3. In the next section, we present an iterative greedy algorithm that optimizes our MDL score.

Implementation
In this section, we describe our algorithm to estimate the joint entropy H(X 1 , . . . , X k ) for a k-dimensional discrete-continuous mixture random vector.

Algorithm
To discretize a one-dimensional random variable X, we first create bins for the discrete values of X and then discretize the continuous values. We detect discrete data points by checking if a single value x in the domain X of X occurs multiple times. If a user-defined threshold t, e.g., 5 is reached, we create a bin for this point. To discretize the remaining continuous values, we start by splitting X into K init equiwidth bins, which we can safely choose from the complexity class o( √ n) (see Supplementary Material S.3). Using dynamic programming, we compute the variablewidth histogram model M that minimizes L(D, M ) in quadratic time w.r.t. K init [13].
Since the runtime complexity to compute the optimal variable-width histogram over a multi-dimensional random variable would grow exponentially w.r.t. k, we opt for an iterative greedy algorithm (we provide the pseudocode in Supplementary Material S.2). We start by initializing the optimization: for every dimension, we fix bins for the discrete values and put the remaining continuous values into a single bin. Then, in each iteration, we compute a candidate discretization for each dimension and keep the discretization of that dimension that provides the highest gain in compression. To compute a candidate discretization for a dimension X j , we extend the one-dimensional algorithm described above. That is, we determine those cut points for X j that provide the highest gain in L(D, M ), while keeping the bins for the remaining dimensions fixed. We repeat this until the maximum number of iterations i max is reached or we cannot further decrease L(D, M ).

Complexity
The complexity of discretizing a univariate random variable is in O(K max · (K init ) 2 ) and depends on the number of initial bins K init and the maximum number of bins K max , which we typically chose as a fraction of K init (both in o( √ n)). In a multidimensional setting we have to multiply this complexity by the current domain size of the remaining variables, since we have to update each bin conditioned on those. In the worst case, this number is equal to (K max ) k−1 . Overall, we apply this procedure-if all variables are continuous-i max · k times.

Related Work
We discuss related methods for adaptive histograms and (conditional) mutual information estimation.
Both theoretical properties and practical issues of density estimation using histograms have been studied for decades [27]. Various algorithms have been proposed for the challenging task of constructing an adaptive onedimensional histogram, among which the MDL-based histogram [13] is considered to be the state-of-the-art, as it is self-adaptive to both local density structure and sample size and does not have any hyperparameters. Learning adaptive multivariate histograms is even harder due to the combinatorial explosion of the search space. One approach is to resort to the dyadic CART algorithm [12]; various methods designed for specific tasks also exist [11,35]. Our algorithm is similar to that of Kameya [11], but they only consider the twodimensional case.
For discrete data, (conditional) mutual information estimation is a well-studied problem [4,10,18,21,33] and it has been shown that mutual information can be estimated using the 3H principle [10]. An important observation is that for discrete data, the empirical estimator for entropy is sub-optimal [21], which encouraged the design of more efficient entropy estimators with sub-linear sample complexity [10,33].
For estimating (conditional) mutual information on continuous data or a mix of discrete and continuous data, three classes of approaches exist. The first class concerns kernel density estimation (KDE) methods [8,22], which perform well on continuous data; however, no KDE-based MI and CMI estimation methods exist that are designed for discrete-continuous mixture random variables. Moreover, bandwidth tuning for KDE can be computationally expensive, which becomes even worse for mixed data, as different bandwidths may be needed for discrete random variables. The second class of methods relies on k-nearest neighbour (kNN) estimates [6,14,15], which have been established as the state of the art [7,24]. kNN approaches can be applied not only to a mix of discrete and continuous variables, but can also be used as consistent MI [7] and CMI [19,24] estimators for discretecontinuous mixtures. The third class of methods first discretizes the continuous random variables and then calculates mutual information from the discretized variables [4,5,31]. Two recent approaches based on adaptive partitioning for mixed random variables have been proposed [2,17]. While Mandros et al. [17] focus on mutual information and its application to functional dependency discovery, Cabeli et al. [2], similar to us, build upon an MDL-based score to estimate MI and CMI, to which we compare in Sec. 7. The key difference is that Cabeli et al. [2] compute I(X; Y |Z) as (I(X; {Y, Z})−I(X; Z)+I(Y ; {X, Z})−I(Y ; Z))/2 and maximize each of the four terms (with penalty terms) directly, while we first learn a joint histogram.
To the best of knowledge, we are the first to propose a CMI estimator for discrete-continuous mixture variables based on discretization or histogram density estimation. Our method can consistently estimate CMI on mixed random variables containing discrete-continuous mixtures. We focus on histogram-based models instead of kNN estimation, since histograms are more interpretable [27] and do not require tuning of the parameter k, which can have a large impact on the outcome.

Experiments
In this section, we empirically evaluate the performance of our approach. First, we will benchmark our estimator against state-of-the-art CMI estimators on different data types. After that, we evaluate how well our estimator is suited to test for conditional independence in a causal discovery setup. For reproducibility, we make our code available online. 2

Mutual Information Estimation
On the mutual information estimation task, we compare our approach to the state-of-the-art MI estimators. In particular, we compare against FP [6], RAVK [24] and MS [19], which all rely on kNN estimates, and MIIC [2], which is a discretization-based method. All of those can be applied to our setup, but only the authors of RAVK and MS specifically consider discrete-continuous mixture variables. We apply MIIC using the default param-2 https://github.com/ylincen/CMI-adaptive-hist.git eters and use k = 10 for all kNN-based approaches. 3 For our algorithm, we set the maximum number of iterations and the threshold to detect discrete points in a mixture variable to 5, set K init = 20 log n and K max = 5 log n. To comply with the literature, we compute all entropies in this section using the natural logarithm.
7.1.1 Experiment I-IV As a sanity check, we start with an experiment on purely continuous data. That is, for Experiment I, let X and Y be Gaussian distributed random variables with mean 0, variance 1, and covariance 0.6. Consequently, the correlation ρ between X and Y is 0.6 and true MI can be calculated as I(X; Y ) = − 1 2 log(1 − ρ 2 ). In Experiment II, X is discrete and drawn from Unif(0, m − 1), with m = 5 and Y is continuous with Y ∼ Unif(x, x + 2) for X = x. Therefore, I(X; Y ) = log(m) − (m−1) log 2 m [7]. Next, for Experiment III, X is exponentially distributed with rate 1 and Y is a zero-inflated Poissonization of X-i.e., Y = 0 with probability p = 0.15 and Y ∼ Pois(x) for X = x with probability 1 − p. The ground truth is [7]. Last, in Experiment IV, we generate the data according to the Markov chain X → Z → Y (see Mesner and Shalizi [19]). In particular, X is exponentially distributed with rate 1 2 , Z ∼ Pois(x) for X = x and Y is binomial distributed with size n = z for Z = z and probability p = 1 2 . Due to the Markov chain structure, the ground truth I(X; Y | Z) = 0.
For each of the above experiments, we sample data with sample size n ∈ {100, 200, . . . , 1 000} and generate 100 data sets per sample size. We run each of the estimators on the generated data and show the mean squared error (MSE) of each estimator in Fig. 1. Overall, our estimator performs best or very close to the best throughout the experiments and reaches an MSE lower than 0.001 with at most 1 000 samples. The best competitors are MS and MIIC; however, both are biased when we consider discrete-continuous mixture variables, as we show in Experiment V. 7.1.2 Experiment V Next, we generate data according to a discrete-continuous mixture [7]. Half of the data points are continuous, with X and Y being standard Gaussian with correlation ρ = 0.8, while the other half follows a discrete distribution with P (1, 1) = P (−1, −1) = 0.4 and P (1, −1) = P (−1, 1) = 0.1. In addition, we generate Z independently with Z ∼

Binomial(3, 0.2). Hence the ground truth is equal to
In Fig. 2 (top) we show the mean and MSE for this experiment. We see that our estimator starts by overestimating the true value, but its average quickly converges to the true value, while the competing estimators seem to have a slightly positive or negative bias. Especially FP and MIIC, which were not designed for this setup, have a clear bias even for 1 000 data points. The same trend can be observed for MSE.

Experiment VI
Last, we test how sensitive our method is to dimensionality. We generate X and Y as in Experiment II, but fix n to 2 000 and add k independent random variables, Z k ∼ Binomial(3, 0.5). Fig. 2 (bottom) shows the mean and MSE. Our estimator recovers the true CMI up to a negligible error up to k = 2. After that, it starts to slowly underestimate the true CMI. This can be explained by the fact that the model costs increase linearly with the domain size and hence, we will fit fewer bins to the continuous variable for large k. We validated this conjecture by repeating the experiment for n = 10 000. On this larger sample size, the MSE for our estimator remained below 0.001 even for k = 4. While MIIC is slightly more stable for k ≥ 3, the competing kNN-based estimators deviate quite a bit from the true estimate for higher dimensions.
Overall, we are on par with or outperform the best competitor throughout Experiments I-VI. Especially on mixture data, which is our main focus, our method is the only one that converges to the true estimate.

Independence Testing
In theory, two random variables X and Y are conditionally independent given a set of random variables Z, denoted as X ⊥ ⊥ Y | Z, if I(X; Y | Z) = 0. Vice versa, X and Y are dependent given Z, if I(X; Y | Z) > 0. In practice, we cannot simply rely on our estimator to conclude independence: due to the monotonicity of mutual information, i.e., I(X; Y ) ≤ I(X; Y ∪ Z), estimates will rarely be exactly zero in the limited sample regime, but only close to zero [18,34]. To address this problem, we use our algorithm to discretize X, Y and Z, and compute where C n is a correction term calculated from the discretized variables, which is negative. In the following, we evaluate our estimator with two different correction criteria. The first one is a correction for mutual information based on the Chi-squared distribution, with C n equal to −X α,l /2n [34], where X α,l refers to the critical value of the Chi-squared distribution with significance level α and degrees of freedom l. We can compute the degrees of freedom l from the domain sizes of the discretized variables for the conditional case as l = (|X | − 1)(|Y| − 1)|Z| [32], and for the unconditional case as l = (|X | − 1)(|Y| − 1). For the second correction, we replace each empirical entropy in I n (X d ; Y d |Z d )  Figure 4: Precision (left) and recall (right) on undirected graphs inferred using the PC-stable algorithm equipped with the corresponding independence test. The data is generated from the graph shown in Fig. 3.
with its corresponding stochastic complexity term as defined in Sec. 4.1. If we subtract the regret terms for H n (X d , Y d , Z d ) and H n (Z d ) from those for H n (X d , Z d ) and H n (Y d , Z d ), we are guaranteed to get a negative value, thus a valid regret term [18]. In the following, we refer to the test using the Chi-squared correction as I X 2 and to the one based on stochastic complexity as I SC .
To test how well I X 2 and I SC perform on mixedtype and continuous data, we benchmark both against state-of-the-art kernel-based tests RCIT and RCoT [30], as well as JIC [31], and MIIC [2], which are both discretization-based methods using a correction based on stochastic complexity. 4 To apply RCIT and RCoT on mixed data, we treat the discrete data points as integers. In the following, we evaluate the performance of each test in a causal discovery setup. In addition, we provide a more detailed description of the data generation and experiments on individual collider and non-collider structures in Supplementary Material S.3.

Causal Discovery
To evaluate our test in a causal discovery setting, we generate data according to a small synthetic network-shown in Fig. 3-that consists of a mixture of generating mechanisms that we used in experiments I-IV and includes continuous and discrete (ordinal) random variables and one mixture variable, which is partially Gaussian and partially Poisson distributed (for details see Supplementary Material S.3). To evaluate how well the ground truth graph can be recovered, we apply the PC-stable algorithm [3,29] equipped with the different independence tests, where we use α = 0.01 for I X 2 , RCIT and RCoT. Fig 4 shows recovery precision and recall for the undirected graph, averaged over 20 draws per sample size n ∈ {100, 500, 1 000, 2 000, 5 000, 10 000}.
We see that overall I X 2 performs best and is the only method that reaches both a perfect accuracy and recall. While JIC also reaches a perfect recall, it finds too many edges leading to a precision of only 80%. Although also MIIC, RCIT and RCoT have a perfect precision, their recall is worse than for I X 2 . Neither of the kernel-based tests manages to recall all the edges even for 10 000 samples. After a closer inspection, this is due to the edge E → G that involves the discretecontinuous variable G. If we compare I X 2 to I SC , we clearly see that the latter is too conservative, which leads to a bad recall.

Conclusion
We proposed a novel approach for the estimation of conditional mutual information from data that may contain discrete, continuous, and mixture variables. To be able to deal with discrete-continuous mixture variables, we defined a class of generalized adaptive histogram models. Based on our observation that CMI for mixture-variables can be written as a sum of entropies, we presented a CMI estimator based on such histograms, for which we proved that it is consistent.
Further, we used the minimum description length principle to formally define optimal histograms, and proposed a greedy algorithm to practically learn good histograms from data. Finally, we demonstrated that our algorithm outperforms state-of-the-art (conditional) mutual information estimation methods, and that it can be successfully used as a conditional independence test in causal graph structure learning. Notably, for both setups, we observe that our approach performs especially well when mixture variables are present.

Supplementary Material
The supplementary material is structured as follows. First, we provide proofs for all lemmas and theorems. After that, we provide the pseudocode for our algorithm. Last, we provide additional experiments and details for the data generation for the causal discovery experiment.  Next, denote v as the product measure defined based on (X, Z), where v = v 1 ×. . .×v k XZ , and k XZ is the number of dimensions of X plus that of Z; then by Lemma 2.2, we also have P XZ v. Then, we show that P X P Z v.
where P i is the marginalization of the product measure P X P Z to the ith dimension and P i (A i ) = 0 is because v i (A i ) = 0 by the definition of v.
Finally, by the chain rule of the Radon-Nikodym derivative we have that The proof for I(X; {Y, Z}) is equivalent. If Z = ∅, CMI reduces to I(X; Y ), for which we can prove the statement in the same manner.
with probability estimateŝ where | · | represents the cardinality of a set, and q j is Lemma S.2. Given a random vector (X, Y, Z) that contains discrete-continuous mixture random variables, with bins B = B ∪ B and the resulting discretized random vector (X d , Y d , Z d ), where B contains discrete data points (of which every dimension has a discrete value) and B = B \ B , we have where v = max Bj ∈B (v(B j )).
Proof. Firstly, it is well-known that this result holds if (X, Y, Z) is a continuous random vector [4]; then, if (X, Y, Z) contains mixture variables, which concludes the proof.
Definition S.2. Given a random vector (X, Y, Z) that contains mixture variables, and an adaptive grid B, we define the discretized random variable X d , Y d , Z d , with probability measure (probability mass function) where B j denotes the jth bin of B.
Lemma S.3. Given a k-dimensional random vector (X, Y, Z) that contains mixture variables with an unknown probability measure P XY Z , a dataset D = (x i , y i , z i ) i∈{1,...,n} generated by P XY Z , a histogram model M , and corresponding discretized random vector That is, the terms corresponding to volumes in I h cancel out and our histogram model results a valid discretization.
Proof. Denote the adaptive grid of histogram model M as B XY Z , which is the Cartesian product of bins defined on X, Y, Z-i.e. B XY Z = B X × B Y × B Z , and denote the corresponding MLE of histogram density function as f ĥ θ XY Z . Further, define a function v X , such that for each By the definition I h (X, Y |Z) is equal to where c j is the number of data points in B j and v XZ ( The remaining entropies can be calculated similarly. Hence, as the sum of the volume related terms is equal to zero.
To proof Theorem 3.1, we link the above results: =I(X; Y | Z) .

S.2 Implementation Details
As discussed in Section 5, our goal is to find that discretization that minimizes the joint entropy over a set of k random variables via an iterative greedy algorithm. We provide the pseudocode in Algorithm 1. As input, we are given a dataset D = {D 1 , . . . , D k } consisting of n rows and k columns, representing a sample of size n from a k-dimensional random vector X, and a user-specified parameter i max specifying the maximum number of iterations. First, we initialize the discretization X d (line 1) by creating single bin histograms for the continuous points in D j and Algorithm 1: a bin with bin-width 1 per discrete point. To detect the latter, we check if there exist |{x ∈ X j | D j = x}| ≥ t, where t is a user-defined threshold. After that, we iteratively update the discretization for that X j providing the highest gain in stochastic complexity, until either the score cannot be improved or the maximum number of iterations has been reached (lines 2-8). To update the discretization of a variable X j we call the function refine (line 5), which receives as input the data D j and the discretization after iteration i. It then re-discretizes X j using an extension of the dynamic programming algorithm by Kontkanen et al. [13]. In essence, instead of simply discretizing X j independently of the remaining variables, we keep the discretizations for all X i = X j fixed and find the optimal histogram model M * over X j s.t. the overall score L(D, M ) is minimized.
S.3 Data Generation and Additional Experiments In the following, we first provide an empirical analysis on how the number of bins depends on the number of samples, then we give the details of the data generation for the experiments carried out on the synthetic causal network and last we provide additional experiments to evaluate I X 2 and I SC .
S.3.1 Sample Size and Number of Bins As discussed in Section 3, an important requirement to ensure consistency is that the number of bins grows as a sub-linear function w.r.t. the number of samples. We demonstrate that MDL-optimal histograms have this desirable property when learned on one-dimensional Gaussian distributions in Figure 5: the number of bins K grows with n, but slower than √ n. In addition, for multi-dimensional data, for which we can only approximate the histogram model that minimizes L(D, M ), we observe that if the number of dimensions increases, the a v e r a g e k #dimensions Figure 5: Left: Average number of bins k to discretize X ∼ N (0, 1) for increasing sample sizes (20 repetitions). Right: Per dimension of a multivariate Gaussian distribution with X i ⊥ ⊥ X j and X i ∼ N (0, 1), we show the average number of bins (n = 2 000, 20 repetitions).
average number of bins per dimension decreases if we keep n fixed.

S.3.2 Synthetic Network
Here, we describe the data generation for the synthetic network shown in Fig. 3. The source nodes of the network are A and B. A is generated as A ∼ Exp(1) and B ∼ Unif(0, 4) (discrete). To get B → C we generate C as C ∼ Binom(b, 0.5) for B = b, for B → D we sample D as D ∼ N (b − 2, 1) for B = b and E is sampled is exponentially distributed with rate 1 c+1 for C = c. F is generated as a function of C and D. First, we generate C by rounding the values of C and then we write F as F = D C 2 + N (0, 1). Last, we generate G as the zero inflated Poissonization of A. Let E = sign(E−1)+1 2 , which ensures that E is either zero or one dependent on the value of E. Then G ∼ N (a, 1) if E = 0 and A = a, and G ∼ Poisson(a) for A = a if G = 1.

S.3.3 Detecting Collider and Non-Collider
Structures To evaluate how well I X 2 and I SC can identify conditional (in)dependencies, we evaluate both variants on various generating mechanisms that involve collider and non-collider structures. Those structures are at the core of causal discovery, since collider structures can be inferred by detecting conditional dependencies, while non-collider structures impose conditional independencies. As in the causal discovery experiment, we set α = 0.01 for I X 2 , RCIT and RCoT.
Collider Structures We generate data according to a collider structure, which can be represented by a directed acyclic graph as, e.g., X → Z ← Y . According to this structure, we model X and Y by some distribution and write Z as a non-deterministic function of X and Y . We generate data for different generating mechanisms, including two continuous and four mixed settings.