On mutual information estimation for mixed-pair random variables
Aleksandr Beknazaryan Xin Dang Hailin Sang




On mutual information estimation for mixed-pair random variables
    Roberto Aloisio1,2roberto.aloisio@gssi.it
    
================================================================



Aleksandr Beknazaryan,
Xin Dang
and Hailin Sang
^1[1]
Corresponding author.

Department of Mathematics, The University of Mississippi,
University, MS 38677, USA. E-mail: abeknaza@olemiss.edu, xdang@olemiss.edu, sang@olemiss.edu







Abstract


We study the mutual information estimation for mixed-pair random variables. One random variable is discrete and the other one is continuous. We develop a kernel method to estimate the mutual information between the two random variables. The estimates enjoy a central limit theorem under some regular conditions on the distributions. The theoretical results are demonstrated by simulation study. 

Keywords: central limit theorem, entropy,  kernel estimation,
mixed-pair, mutual information.


MSC 2010 subject classification: 62G05, 62G20



§ INTRODUCTION


The entropy of a discrete random variable X∈ℝ^d with countable support {x_1,x_2,...} and p_i=ℙ(X=x_i) is defined to be

    H(X)=-∑_ip_ilog p_i,

and the (differential) entropy of a continuous random variable Y∈ℝ^d with probability density function f(y) is defined as 

    H(Y)=-∫_ℝ^df(y)log f(y)dy.






If d≥ 2, H(X) or H(Y) is also called the joint entropy of the components in X or Y. Entropy is a measure of distribution uncertainty and naturally it has application in the fields of information theory, statistical classification, pattern recognition and so on. 

 Let P_X, P_Y be probability measures on some arbitrary measure spaces 𝒳  and  𝒴 respectively. Let P_XY be the joint probability measure on the space 𝒳×𝒴.  If  P_XY is absolutely continuous with respect to the product measure P_X× P_Y, let dP_XY/d(P_X× P_Y) be the Radon-Nikodym derivative. Then the general definition of  the mutual information (e.g.,  <cit.>) is given by
 
    I(X,Y)=∫ _𝒳×𝒴dP_XYlogdP_XY/d(P_X× P_Y).

If two random variables X and Y are either both discrete or both continuous then the mutual information of X and Y can be  expressed in terms of entropies as 

    I(X,Y)=H(X)+H(Y)-H(X,Y).


However, in practice and application, we often need to work on a mixture of continuous and discrete random variables. There are several ways for the mixture. 1). One random variable X is discrete and the other random variable Y is continuous; 2). A random variable Z has both discrete and continuous components, i.e., Z=X with probability p and Z=Y with probability 1-p, where 0<p<1, X is a  discrete random variable and Y is a continuous random variable; 3). a random vector with each dimension component being discrete, continuous or mixture as in 2).  

In <cit.>, the authors extend the definition of the joint entropy for the first case mixture, i.e., for the pair of random variables, where the first random variable is discrete and the second one is continuous. 


Our goal is to study the mutual information for that case
and provide the estimation of the mutual information from a given i.i.d. sample {X_i,Y_i}_i=1^N. 

In <cit.>, the authors applied the k-nearest neighbor method to estimate the Radon-Nikodym derivative and, therefore, to estimate the mutual information for all three mixed cases. 
In the literature,  if the random variables X and Y are either both discrete or both continuous, the estimation of mutual information is usually performed by the estimation of the three entropies in (<ref>). The estimation of a differential entropy has been well studied. An incomplete list of the related research includes the nearest-neighbor estimator 

<cit.>,

<cit.>,

<cit.>;   the kernel estimator 

<cit.>,

<cit.>,

<cit.>,

<cit.> and  the orthogonal projection estimator 

<cit.>, <cit.>.
 Basharin <cit.> studied the plug-in entropy estimator for the finite value discrete case and obtained the mean, the variance and the central limit theorem of this estimator. Vu, Yu and Kass <cit.> studied the coverage-adjusted entropy estimator with unobserved values for the infinite value discrete case. 



§ MAIN RESULTS


 Consider a random vector Z = (X, Y). We call Z
a mixed-pair if X∈ℝ is a discrete random variable with countable support 𝒳={x_1,x_2,...} while Y∈ℝ^d is a continuous random variable. Observe that Z = (X, Y) induces measures {μ_1, μ_2, ⋯} that are absolutely continuous with respect to
the Lebesgue measure, where μ_i(A) = ℙ(X = x_i, Y ∈ A), for every Borel set A in ℝ^d. 
There  exists a non-negative function g(x, y) with h(x):=∫_ℝ^dg(x,y)dy be the probability mass function on 𝒳 and f(y):=∑_i g_i(y) be the marginal density function of Y. Here,  g_i(y)=g(x_i,y), i∈ℕ. In particular, denote p_i=h(x_i), i∈ℕ. We have that 
    f_i(y)=1/p_ig_i(y)
 is the probability density function of Y conditioned on X = x_i. In <cit.>, the authors gave the following regulation of mixed-pair and then defined the joint entropy of a mixed-pair. 

 (Good mixed-pair). A mixed-pair random variables Z = (X, Y ) is called good if the following
condition is satisfied: 
    ∫_𝒳×ℝ^d|g(x, y)log g(x,y)|dxdy=∑_i∫_ℝ^d|g_i(y)log g_i(y)|dy<∞.
 


Essentially, we have a good mixed-pair random variables when restricted to any of the X values, the conditional differential entropy of Y is well-defined.

 (Entropy of a mixed-pair). The entropy of a good mixed-pair random variable is defined by

    H(Z)=-∫_𝒳×ℝ^dg(x, y)log g(x, y)dxdy=-∑_i∫_ℝ^dg_i(y)log g_i(y)dy.



As g_i(y)=p_if_i(y) then we have that 


    H(Z)= -∑_i∫_ℝ^dg_i(y)log g_i(y)dy 
       =-∑_i∫_ℝ^dp_if_i(y)log p_if_i(y)dy
       = -∑_ip_ilog p_i∫_ℝ^df_i(y)dy-∑_ip_i∫_ℝ^df_i(y)log f_i(y)dy 
       = -∑_ip_ilog p_i-∑_ip_i∫_ℝ^df_i(y)log f_i(y)dy
       =H(X)+∑_ip_iH(Y|X=x_i).

 
We take the convention log 0=0 and log 0/0=0. From the general formula of the mutual information (<ref>),  we get that

    I(X,Y)=∫_𝒳×ℝ^dg(x, y)logg(x, y)dxdy/h(x)f(y)dxdydxdy 
       =∑_i∫_ℝ^dg_i(y)logg_i(y)/p_if(y)dy 
       =∑_i∫_ℝ^d g_i(y)log g_i(y)dy-∑_i∫_ℝ^d g_i(y)log p_idy-∑_i∫_ℝ^d g_i(y)log f(y)dy
       =∑_i∫_ℝ^d p_if_i(y)log [p_if_i(y)]dy-∑_ip_ilog p_i∫_ℝ^d f_i(y)dy-∫_ℝ^d f(y)log f(y)dy
       =∑_ip_ilog p_i∫_ℝ^d f_i(y)dy+∑_ip_i∫_ℝ^d f_i(y)log f_i(y)dy-∑_ip_ilog p_i-∫_ℝ^d f(y)log f(y)dy
       =-H(Z)+H(X)+H(Y)=H(Y)-∑_ip_iH(Y|X=x_i):=H(Y)-∑_i I_i.
 

Let (X,Y), (X_1,Y_1),...,(X_N,Y_N) be a random sample drawn from a mixed distribution with discrete component having support {0,1, ⋯, m}, and let p_i=ℙ(X=i), 0≤ i≤ m with 0<p_i<1, ∑ p_i=1. Also suppose that the continuous component has pdf f(y). Denote p̂_i=∑_k=1^N𝕀(X_k=i)/N, 0≤ i≤ m, and let   

    I̅_i = -p̂_i[Np̂_i]^-1∑_k=1^N𝕀(X_k=i)log f_i(Y_k) 
       = -N^-1∑_k=1^N𝕀(X_k=i)log f_i(Y_k)

and 

    H̅(Y) = - N^-1∑_k=1^Nlog f(Y_k)

be  the estimators of I_i=p_iH(Y|X=i), 0≤ i≤ m, and H(Y) respectively, where f_i(y) is the probability density function of Y conditioned on X = i, 0≤ i≤ m. Denote a=(1,-1,⋯, -1)^⊺. Let  Σ 
be the covariance matrix of (log f(Y), 𝕀(X=0)log f_0(Y), ⋯,𝕀(X=m)log f_m(Y))^⊺.

a^⊺Σ a>0 if and only if X and Y are dependent. 
For the estimator 

    I̅(X,Y)=H̅-∑_i=0^mI̅_i

of I(X,Y) we have that 

    √(N)(I̅(X,Y)-I(X,Y))→ N(0,a^⊺Σ a)

given that X and Y are dependent.
Furthermore, the variance a^⊺Σ a can be calculated by 

    a^⊺Σ a= var(log f(Y))+∑_i=0^m p_i E_i[log f_i(Y)]^2-∑_i=0^m p_i^2(E_i[log f_i(Y)])^2
       -2 ∑_i=0^m p_i[E_ilog f_i(Y)log f(Y)-E_ilog f_i(Y) Elog f(Y)]
       -2∑_0≤ i<j≤ mp_ip_j[E_ilog f_i(Y)][E_jlog f_j(Y)],

where E_i is the conditional expectation of Y given X=i, 0≤ i≤ m.


First of all, a^⊺Σ a≥ 0 since Σ is the variance covariance matrix. If a^⊺Σ a=0 then 

    var(log f(Y)-∑_i=0^m 𝕀(X=i)log f_i(Y))=a^⊺Σ a=0

and  log f(Y)-∑_i=0^m 𝕀(X=i)log f_i(Y)≡ C  for some constant C.  But 

    log f(Y)-∑_i=0^m 𝕀(X=i)log f_i(Y)
    =∑_i=0^m 𝕀(X=i)logf(Y)/f_i(Y).

Hence logf(Y)/f_i(Y)≡ C. Then  f_i(y)=cf(y) for some constant c>0 and for all 0≤ i≤ m. But 
f(y)=∑_i=0^m p_if_i(y)=cf(y)∑_i=0^m p_i=cf(y). Hence, c≡ 1 and  f_i(y)=f(y) for all 0≤ i≤ m. Then X and Y are independent.
On the other hand, if X and Y are independent, then f_i(y)=f(y)  for all 0≤ i≤ m. Therefore, log f(Y)-∑_i=0^m 𝕀(X=i)log f_i(Y)=0 and a^⊺Σ a=0. Hence, a^⊺Σ a=0 if and only if X and Y are independent.


Notice that the vector (H̅(Y), I̅_0,⋯, I̅_m)^⊺ is the sample mean of a sequence of i.i.d. random vectors 
    {(log f(Y_k), 𝕀(X_k=0)log f_0(Y_k), ⋯, 𝕀(X_k=m)log f_m(Y_k))^⊺}_k=1^N
 with mean (H(Y), I_0,⋯, I_m)^⊺. Then, by central limit theorem,  we have 

    √(N) ([   H̅; I̅_0;    ⋮; I̅_m ]-[   H; I_0;   ⋮; I_m ] )→ N( 0̅,Σ ),

and, given a^⊺Σ a>0, we have (<ref>). 
By the formula for variance decomposition, we have 

    var(𝕀(X=i)log f_i(Y))
       = E{var[𝕀(X=i)log f_i(Y)|X]}+var{E[𝕀(X=i)log f_i(Y)|X]}
       = E{𝕀(X=i) var[log f_i(Y)|X]}+var{𝕀(X=i)E[log f_i(Y)|X]}
       = E{𝕀(X=i) ∑_j=0^m var_j(log f_j(Y))𝕀(X=j)}
           +var{𝕀(X=i)∑_j=0^m E_j(log f_j(Y))𝕀(X=j)}
       = var_i[log f_i(Y)] E{𝕀(X=i) }+(E_i[log f_i(Y)])^2var{𝕀(X=i)}
       = p_i var_i[log f_i(Y)]+(p_i-p_i^2)(E_i[log f_i(Y)])^2
       =p_i E_i[log f_i(Y)]^2-p_i^2(E_i[log f_i(Y)])^2,

0≤ i≤ m. Here var_i is the conditional variance of Y when X=i, 0≤ i≤ m.
By similar calculation,

    Cov(𝕀(X=i)log f_i(Y),𝕀(X=j)log f_j(Y))
       =-p_ip_j[E_ilog f_i(Y)][E_jlog f_j(Y)],

for all 0≤ i<j≤ m, and 

    Cov(𝕀(X=i)log f_i(Y),log f(Y))
       =p_i[E_ilog f_i(Y)log f(Y)-E_ilog f_i(Y) Elog f(Y)].

Thus, the covariance matrix Σ 
of (log f(Y), 𝕀(X=0)log f_0(Y), ⋯,𝕀(X=m)log f_m(Y))^⊺ and therefore a^⊺Σ a can be calculated by the above calculation (<ref>)-(<ref>). We then have (<ref>). 



We consider the case when the random variables X and Y are dependent. Note that in this case a^⊺Σ a>0 and we have (<ref>). 
However, I̅(X,Y) is not a practical estimator since the density functions involved are not known. 

Now let K(·) be a kernel function in ℝ^d and let h be the bandwidth. Then

    f̂_ik(y)={(Np̂_i-1)h^d}^-1∑_j≠ k𝕀(X_j=i)K{(y-Y_j)/h}

are the “leave-one-out" estimators of the functions f_i, 0≤ i≤ m, and  

    Î_i=- N^-1∑_k=1^N𝕀(X_k=i)logf̂_ik(Y_k)

are estimators of I_i=p_iH(Y|X=i), 0≤ i≤ m. Also 

    Ĥ=- N^-1∑_k=1^Nlogf̂_k(Y_k)

is an estimator of H(Y), where

    f̂_k(y)={(N-1)h^d}^-1∑_j≠ kK{(y-Y_j)/h}
       ={(N-1)h^d}^-1∑_j≠ k[∑_i=0^m𝕀(X_k=i)]K{(y-Y_j)/h}
       = ∑_i=0^mNp̂_i-1/N-1f̂_ik(y).


Assume that the tails of f_0, ⋯, f_m are decreasing like |x|^-α_0, ⋯, |x|^-α_m , respectively, as |x|→∞. 
Also assume that the kernel function has appropriately heavy tails  as in  <cit.>. If h=o(N^-1/8) and α_0⋯, α_m are all greater than 7/3 in the case d=1, greater than 6 in the case d=2 and greater than 15 in the case d=3, then for the estimator 

    Î(X,Y)=Ĥ-∑_i=0^mÎ_i,

we have

    √(N)(Î(X,Y)-I(X,Y))→ N(0,a^⊺Σ a).



Under the conditions in the theorem,  applying the formula (3.1) or (3.2) from <cit.>, we have
 
    Ĥ=H̅+o(N^-1/2),   Î_0=I̅_0+o(N^-1/2), ⋯,   Î_m=I̅_m+o(N^-1/2).

Together with Theorem <ref>, we have (<ref>). 


We may take the probability density function of Student-t distribution with proper degree of freedom instead of the normal density function as the kernel function. On the other hand, 
if X and Y are independent then I(X,Y)=I̅(X,Y)=0 and we have that Î(X,Y)=o(N^-1/2).



§ SIMULATION STUDY

In this section we conduct a simulation study with m=1, i.e., the random variable X takes two possible values 0 and 1, to confirm the main results stated in (<ref>) for the kernel mutual information estimation of good mixed-pairs. First we study some one dimensional examples. Let t(ν, μ, σ) be the Student t distribution with degree of freedom ν, location parameter μ and scale parameter σ and let pareto(x_m, α) be the Pareto distribution with density function f(x)=α x_m^α x^-(α+1)𝕀(x≥ x_m).  We study the mixture for the following four cases: 1). t(3, 0, 1) and t(12, 0, 1);   2).  t(3, 0, 1) and t(3, 2, 1);  3). t(3, 0, 1) and t(3, 0, 3); 4). pareto(1,2) and pareto(1,10). For each case, p_0=0.3 for the first distribution and p_1=0.7 for the second distribution.  

The second row of Table <ref>  lists the mathematica calculation of the mutual information (MI) as stated in (<ref>)  for each case. The third row of Table <ref> gives the average of 400 estimates based on formula (<ref>). For each estimate, we use the probability density function of the Student t distribution with degree of freedom 3, i.e. t(3, 0, 1), as the kernel function. We also have simulation study with kernel functions satisfying the conditions in the main results and obtained similar results. We take h=N^-1/5 as the bandwidth for the first three cases and h=N^-1/5/24 for the last case. The data size for each estimate is N=50,000 in each case. The Pareto distributions pareto(1,2) and pareto(1,10) have very dense area on the right of 1. This is the reason that we take a relatively small bandwidth for this case. To apply the kernel method in estimation, one should select an optimal bandwidth based on some criteria, for example, to minimize the mean squared error.  It is interesting to investigate the bandwidth selection problem from both theoretical and application viewpoints. However, it seems that the study in this direction is very difficult. We leave it as an open question for future study. It is clear that the average of the estimates matches the true value of mutual information. 

We apply mathematica to calculate the covariance matrix Σ
of 

    (log f(Y), 𝕀(X=0)log f_0(Y),𝕀(X=1)log f_1(Y))^⊺

 and, therefore, the value of a^⊺Σ a for each case by formulae  (<ref>)-(<ref>) or (<ref>). The values of a^⊺Σ a are 0.02189236, 0.3092179, 0.1540501 and 0.2748102 respectively for the four cases. 
The fourth row of Table <ref> lists the values of (a^⊺Σ a/N)^1/2 which serves as the asymptotic approximation of the standard deviation of the estimator Î(X,Y) in the central limit theorem (<ref>). The last row gives the sample standard deviation from M=400 estimates. These two values also have good match.
 







 Figure <ref> and <ref> show the histograms with kernel density fits and normal Q-Q plots of 400 estimates for each case. It is clear that the values of Î(X,Y) follow a normal distribution. 

We study two examples in the two dimensional case. Let t_ν(μ,Σ_0) be the two dimensional Student t distribution with degree of freedom ν, mean μ and shape matrix Σ_0. We study the mixture in two cases: 1). t_5(0, I) and t_25(0, I);   2).  t_5(0, I) and t_5(0, 3I). Here I is the identity matrix. For each case, p_0=0.3 for the first distribution and p_1=0.7 for the second distribution. Table <ref> summarizes 200 estimates of the mutual information with h=N^-1/5 and sample size N=50,000 for each estimate.  We take t_3(0,I) as the kernel function. Same as the one dimensional case, we apply mathematica to calculate the true value of MI and (a^⊺Σ a/N)^1/2 which is given in formula (<ref>).  Figure <ref> shows the histograms with kernel density fits and normal Q-Q plots of 200 estimates for each example. It is clear that the values of Î(X,Y) also follow a normal distribution in the two dimensional case. In summary, the simulation study confirms the central limit theorem as stated in (<ref>). 

 



Acknowledgement


The authors thank the editor and the referees for carefully reading the manuscript and for the suggestions that improved the presentation. This research is supported by the College of Liberal Arts
Faculty Grants for Research and Creative Achievement at the University of Mississippi. The research of Hailin Sang is also supported by the Simons Foundation Grant 586789.
99

AL
Ahmad, I. A. and Lin, P. E. 1976. A nonparametric estimation of the entropy for absolutely continuous distributions. IEEE Trans. Information Theory. 22, 372-375. 
 
Basharin
Basharin, G. P. 1959. On a statistical estimate for the entropy of a sequence of independent random variables. Theory of Probability and Its Applications. 4, 333-336.

Gao Gao, W., Kannan, S., Oh, S. and Viswanath, P.  2017. Estimating mutual
information for discrete-continuous mixtures. Advances in Neural Information Processing Systems.  5988-5999. 

Hall1 Hall, P.  1987. On Kullback-Leibler Loss and Density Estimation. Ann. Statist. 15, no. 4, 1491-1519. 

Hall
Hall, P. and Morton, S. 1993. On the estimation of entropy. Ann. Inst. Statist. Math. 45, 69-88.

Joe
Joe, H. 1989. On the estimation of entropy and other functionals of a multivariate density. Ann. Inst. Statist. Math. 41, 683-697. 







KL
Kozachenko, L. F. and Leonenko, N. N. 1987. Sample estimate of entropy of a random vector. Problems of Information Transmission, 23, 95-101.

L1
Laurent, B. 1996. Efficient estimation of integral functionals of a density. Ann. Statist. 24,  659-681.

L2
Laurent, B. 1997. Estimation of integral functionals of a density and its derivatives. Bernoulli  3, 181-211.

LPS
Leonenko, N., Pronzato, L. and Savani, V.  2008.   A class of Rényi information estimators for multidimensional densities. Ann. Statist. 36, 2153–2182. Corrections, Ann. Statist. 38  (2010), 3837-3838.





Nair
Nair, C., Prabhakar, B. and Shah, D. On entropy for mixtures of discrete and continuous variables. arXiv:cs/0607075

Tv
Tsybakov, A. B. and van der Meulen, E. C.  1994. Root-n consistent estimators of entropy for densities with unbounded support. Scand. J. Statist., 23, 75-83.

VYK
Vu, V. Q., Yu, B. and Kass, R. E. 2007. Coverage-adjusted entropy estimation. Statist. Med., 26, 4039-4060. 



