Estimating Mutual Information for Discrete-Continuous Mixtures
Estimation of mutual information from observed samples is a basic primitive in machine learning, useful in several learning tasks including correlation mining, information bottleneck, Chow-Liu tree, and conditional independence testing in (causal) graphical models. While mutual information is a quantity well-defined for general probability spaces, estimators have been developed only in the special case of discrete or continuous pairs of random variables. Most of these estimators operate using the 3H-principle, i.e., by calculating the three (differential) entropies of X, Y and the pair (X, Y ). However, in general mixture spaces, such individual entropies are not well defined, even though mutual information is. In this paper, we develop a novel estimator for estimating mutual information in discrete-continuous mixtures. We prove the consistency of this estimator theoretically as well as demonstrate its excellent empirical performance. This problem is relevant in a wide-array of applications, where some variables are discrete, some continuous, and others are a mixture between continuous and discrete components.
1 Introduction mutual information estimators, on both the theoretical as well as practical fronts [46,31,44,45,22,19,7,15,14,17,16].
The previous estimators focus on either of two cases -the data is either purely discrete or purely continuous. In these special cases, the mutual information can be calculated based on the three (differential) entropies of X, Y and (X, Y ). We term estimators based on this principle as 3H-estimators (since they estimate three entropy terms), and a majority of previous estimators fall under this category [19,16,46].
In practical downstream applications, we often have to deal with a mixture of continuous and discrete random variables. Random variables can be mixed in several ways. First, one random variable can be discrete whereas the other is continuous. For example, we want to measure the strength of relationship between children's age and height, here age X is discrete and height Y is continuous. Secondly, a single scalar random variable itself can be a mixture of discrete and continuous components. For example, consider X taking a zero-inflated-Gaussian distribution, which takes value 0 with probability 0.1 and is a Poisson distribution with mean 10 with probability 0.9. This distribution has both a discrete component as well as a component with density, and is a well-known model for gene expression readouts [24,37]. Finally, X and / or Y can be high dimensional vector, each of whose components may be discrete, continuous or mixed.
In all of the aforementioned mixed cases, mutual information is well-defined through the RadonNikodym derivative (see Section 2) but cannot be expressed as a function of the entropies or differential entropies of the random variables. Crucially, entropy is not well defined when a single scalar random variable comprises of both discrete and continuous components, in which case, 3H estimators (the vast majority of prior art) cannot be directly employed. In this paper, we address this challenge by proposing an estimator that can handle all these cases of mixture distributions. The estimator directly estimates the Radon-Nikodym derivative using the k-nearest neighbor distances from the samples; we prove 2 consistency of the estimator and demonstrate its excellent practical performance through a variety of experiments on both synthetic and real dataset. Most relevantly, it strongly outperforms natural baselines of discretizing the mixed random variables (by quantization) or making it continuous by adding a small Gaussian noise.
The rest of the paper is organized as follows. In Section 2, we review the general definition of mutual information for Radon-Nikodym derivative and show that it is well-defined for all the cases of mixtures. In Section 3, we propose our estimator of mutual information for mixed random variables. In Section 4, we prove that our estimator is 2 consistent under certain technical assumptions and verify that the assumptions are satisfied for most practical cases. Section 5 contains the results of our detailed synthetic and real-world experiments testing the efficacy of the proposed estimator.
Summary: This paper proposes an estimator for the mutual information of a pair (X,Y) of random variables given N joint samples. While most previous work has focused separately on the purely discrete and purely continuous methods (with significantly different methods used in each setting), the novel focus here on the case of combinations or mixtures or discrete and random variables; in this case, the mutual information is well-defined but cannot always be expressed in terms of entropy, making most previous estimators unusable. The proposed estimator generalizes the classic KSG estimator by defining the behavior at samples points with k-NN distance 0. The L_2 consistency of the estimator is proven, under a sort of continuity condition on the density ratio that allows the existence of atoms, and suitable scaling of k with N. Finally, experimental results on synthetic and real data compare the proposed estimator to some baseline estimators based on perturbing the data to make it purely discrete or continuous.
Main Comments:
This paper addresses a significant hole that remains in the nonparametric dependence estimation literature despite significant recent progress in this area; many current estimators are difficult or impossible to use with many data sets due to a combination or mixture of discrete and continuous components. While the proposed estimator seems like a fairly simple correction of the KSG estimator, and the consistency result is thus likely straightforward given the results of [16], the empirical section is strong and I think the work is of sufficient practical importance to merit acceptance. The paper is fairly well-written and easy to read.
Minor Comments/questions:
1) As far as I understand 3H estimators can work as long as each individual dimension of the variables is fully discrete or full continuous, but fail if any variable is a mixture of the two (i.e., if an otherwise continuous distribution has any atoms). It might be good to clarify this, and also to compare to some 3H estimators (e.g., in experiment II).
2) Lines 39-42: Perhaps there is a typo or I am misreading something, but it isn't clear to my why the given definition of X isn't entirely discrete (it appears to be supported on {0,1,2,...}).
3) Lines 129-130: could be probably clearer "the average of Radon-Nikodym derivative" should be "the average of the logarithm Radon-Nikodym derivative of the joint distribution P_{XY} with respect to the product distribution P_XP_Y."
4) As discussed in Appendix A, a key observation of the paper is that, to be well-defined, mutual information requires only the trivial condition of absolute continuity of the joint distribution w.r.t. the marginal distribution (rather than w.r.t. another base measure, as for entropy). I think it would be worth explicitly mentioning this in the main paper, rather than just in the Appendix.
5) Although this paper doesn't study convergence rates, could the authors conjecture about how to quantify parameters that determine the convergence rate for mixed discrete/continuous variables? For continuous distributions, the smoothness of the density is usually relevant, while, for discrete distributions, the size of the support is usually relevant. However, mixture distributions are discontinuous and have infinite support.
6) Theorem 1 assumes that k -> infinity as N -> infinity. Can the authors conjecture whether the proposed estimator is consistent for fixed values of k? I ask because of recent work [4,16,43] showing that the KL and KSG estimators are consistent even for fixed k.
7) For some reason, the PDF is encoded such that I cannot search, highlight, or copy text. Perhaps it was converted from a postscript? Anyhow, this made the paper significantly more difficult to review.
#### AFTER READING AUTHOR REBUTTAL ####
"H(X,Y) is not well-defined as either discrete entropy or continuous entropy" - I think