PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimating Mutual Information for Discrete-Continuous Mixtures

Weihao Gao, Sreeram Kannan, Sewoong Oh, Pramod Viswanath

arXiv:1709.06212v3cs.ITcs.LG

TL;DR

Existing mutual-information estimators mainly handle purely discrete or purely continuous variables because entropy-based 3H methods are not directly applicable to mixtures. The paper proposes a k-nearest-neighbor estimator that directly targets the Radon-Nikodym derivative, proves consistency under stated assumptions, and reports better performance than noise-based and quantization baselines in experiments.

  • Problem

    Mutual-information estimation is limited for mixed distributions because entropy-based 3H estimators are not directly applicable when discrete and continuous components coexist.

  • Method

    The paper estimates the Radon-Nikodym derivative using k-nearest-neighbor distances and local neighbor counts, adapting the effective neighbor count for zero distances.

  • Results

    The estimator is consistent under stated assumptions and strongly outperforms quantization and small-noise baselines in the reported experiments.

  • Takeaways & Limitations

    The estimator extends mutual-information estimation to discrete-continuous mixtures and other mixed distributions covered by the paper’s assumptions.

  • Takeaways & Limitations

    Consistency is established under assumptions on k and for distributions including discrete, continuous, mixed-dimensional, and finite-mixture cases.

Abstract

from arXiv · show

Estimating mutual information from observed samples is a basic primitive, useful in several machine learning tasks including correlation mining, information bottleneck clustering, learning a Chow-Liu tree, and conditional independence testing in (causal) graphical models. While mutual information is a well-defined quantity in general probability spaces, existing estimators can only handle two special cases of purely discrete or purely continuous pairs of random variables. The main challenge is that these methods first estimate the (differential) entropies of X, Y and the pair (X;Y) and add them up with appropriate signs to get an estimate of the mutual information. These 3H-estimators cannot be applied in general mixture spaces, where entropy is not well-defined. In this paper, we design a novel estimator for mutual information of discrete-continuous mixtures. We prove that the proposed estimator is consistent. We provide numerical experiments suggesting superiority of the proposed estimator compared to other heuristics of adding small continuous noise to all the samples and applying standard estimators tailored for purely continuous variables, and quantizing the samples and applying standard estimators tailored for purely discrete variables. This significantly widens the applicability of mutual information estimation in real-world applications, where some variables are discrete, some continuous, and others are a mixture between continuous and discrete components.

1 Introduction

Mutual information is widely useful in machine learning, but estimating it from samples remains challenging when variables combine discrete and continuous structure. Existing entropy-based estimators target purely discrete or purely continuous data, whereas mixed variables require a broader approach.

  • Mutual information measures shared information and supports tasks including classification, clustering, feature selection, and graphical-model inference.
  • Estimating mutual information effectively from samples remains an active theoretical and practical research problem.
  • Most existing estimators use three entropy terms and focus on either purely discrete or purely continuous data.
  • Mixed settings include discrete-continuous pairs, scalar variables with discrete and continuous components, and high-dimensional vectors with mixed components.
  • The paper addresses these mixed cases with an estimator based on k-nearest-neighbor distances and proves its consistency.

2 Problem Formation

The paper defines mutual information for general distributions using the Radon-Nikodym derivative between the joint distribution and the product of its marginals. This formulation covers discrete, continuous, and mixed distributions beyond the scope of entropy-based definitions.

  • For a joint measure PXY and marginal product measure PXPY, mutual information is defined through the Radon-Nikodym derivative when PXY is absolutely continuous with respect to PXPY.
  • The general definition covers discrete-continuous pairs, variables with mixed components, and joint distributions mixing discrete and continuous parts.

3 Estimators of Mutual Information

The section reviews entropy-based and direct mutual-information estimators, showing why standard approaches fail or become biased for mixed variables. It then introduces a k-nearest-neighbor estimator that adapts to discrete and continuous local structure and recovers established estimators in canonical cases.

  • Review of Previous Works: The 3H principle estimates three entropy terms, but it applies only to purely discrete or purely continuous data.
  • Review of Previous Works: For mixed variables, entropy may be undefined; quantization enables discrete estimation but has complicated choices and can be problematic in mixed settings.
  • Mixed Regime: KSG avoids divergence for discrete-continuous pairs but has non-trivial bias and is inconsistent when discrete points occur in mixed cases.
  • Proposed Estimator: The proposed estimator directly estimates the Radon-Nikodym derivative using local neighbor counts and adjusts the effective neighbor number when the k-nearest-neighbor distance is zero.
  • Proposed Estimator: In purely discrete, purely continuous, and discrete-versus-one-dimensional-continuous settings, the estimator recovers corresponding plug-in, KSG, and discrete-continuous estimators.

4 Proof of Consistency

The paper establishes ℓ2 consistency for the proposed mutual-information estimator under technical assumptions, covering common discrete, continuous, and mixed distributions. The proof combines bias and variance control, treating discrete and continuous regions separately.

  • Under technical conditions on the joint probability measure, the proposed estimator is consistent.
  • The proof defines local joint and marginal probability masses within radius-r neighborhoods around observations.
  • The assumptions include a growth condition on k, finitely many discrete points, and coverage of discrete, continuous, coordinate-mixed, and finite-mixture distributions.
  • The analysis partitions the domain into regions with discrete mass and regions treated as continuous, using separate nearest-neighbor arguments.
  • The estimator’s variance is bounded by applying the Efron-Stein inequality and controlling the effect of removing one sample across three cases.
  • Combining the bias and variance results yields ℓ2 consistency of the proposed estimator.

5 Simulations

The simulations evaluate the proposed estimator on synthetic mixtures, higher-dimensional settings, zero-inflated data, feature selection, and gene regulatory network inference. Across these experiments, it is generally best or comparable to the best method and avoids several weaknesses of competing estimators.

  • Experimental setup: The experiments compare the proposed estimator with partitioning, adaptive partitioning, KSG, and noisy KSG using synthetic and real-world tasks.Synthetic comparisons report mean squared error over 250 independent trials.
  • Synthetic experiments: In Experiment I, only the proposed estimator has error decreasing with sample size, while KSG is misled by discrete samples and quantization introduces extra error.Adding noise improves KSG but causes degradation as noise increases.
  • Synthetic experiments: In Experiment II, the proposed estimator outperforms the other methods for a discrete X and continuous Y.The experiment uses m = 5 and a known mutual-information ground truth.
  • Synthetic experiments: In Experiment IV, the proposed estimator is comparable to adaptive partitioning without zero-inflation and outperforms the alternatives at 15% zero-inflation.The setting uses a zero-inflated Poisson observation model with p = 0 and p = 15%.
  • Synthetic experiments: Across four synthetic experiments, the proposed estimator is consistent and has mean squared error that is always best or comparable to the best.Other estimators are either inconsistent or have large mean squared error in at least one experiment.
  • Real-world tasks: For feature selection with noisy mixed observations, the proposed estimator outperforms partitioning, noisy KSG, and KSG according to the ROC comparison.The experiment models zero-inflated Poisson observations and evaluates selection using mutual-information rankings.

A Proof of Theorem 1

The proof establishes the estimator’s asymptotic behavior by expressing the Radon–Nikodym derivative through local probabilities and analyzing the k-nearest-neighbor statistic across mixture-support regions. Binomial count bounds, order-statistic calculations, and vanishing error terms control the estimator’s bias.

  • Proof strategy: The proof represents the Radon–Nikodym derivative dPXY/dPXPY using the limiting ratio of joint and marginal neighborhood probabilities.This representation supplies the target quantity for the estimator’s local analysis.
  • Proof strategy: The support is divided into regions with zero or positive probability at radius zero, and the proof treats each region separately.The regions include Ω2, where PXY(x,y,0) > 0, and Ω3, where PXY(x,y,0) = 0.
  • Ω2 analysis: On Ω2, repeated-point counts are modeled with binomial variables, enabling bounds for the marginal and joint count terms in the estimator.The k-nearest-neighbor radius is zero with high probability under the relevant conditioning.
  • Convergence: The resulting error terms vanish as N grows because k → ∞, k/N → 0, and the relevant integrability and finite-measure assumptions hold.The proof also uses uniform convergence outside a small exceptional set and bounds the exceptional-set contribution.
  • Ω3 analysis: The k-nearest-neighbor distance distribution is analyzed through its derivative with respect to PXY(x,y,r), yielding the order-statistic density used in the integrations.The resulting expression is a beta-type density involving N, k, and PXY(x,y,r).
  • Ω3 analysis: For positive-radius cases, the proof uses the conditional count distributions and a binomial logarithm bound to control marginal-count errors.The conditional counts nx,1 − k and ny,1 − k follow binomial distributions, and Lemma A.4 bounds expected logarithmic deviations.

A.1 Proof of Lemma A.1

The proof of Lemma A.1 applies the Lebesgue–Besicovitch differentiation theorem to the Radon–Nikodym derivative with respect to the product measure. The theorem’s conditions hold because the product measure is Radon and the derivative is integrable.

  • Measure-theoretic setup: The proof sets f = dPXY/dPXPY and μ = PXPY before applying the Lebesgue–Besicovitch differentiation theorem.The theorem identifies the limiting local ratio of joint to product-measure probabilities.
  • Assumptions: The product measure is a Radon measure because it is a probability measure on Euclidean space.This verifies the theorem’s measure assumption.
  • Assumptions: The derivative is globally integrable because the integral of its absolute value with respect to PXPY equals 1.Global integrability implies the local integrability required by the theorem.

A.2 Proof of Lemma A.2

Lemma A.2 bounds the conditional logarithmic deviation of a binomial count from its mean. The proof combines concentration, Jensen’s inequality, and a Taylor expansion around Np to obtain the required bound.

  • Lemma objective: The lemma controls logarithmic errors involving a binomial random variable conditioned on the event X ≥ k.These bounds are used to analyze count terms in the estimator’s bias proof.
  • Upper bound: The upper bound uses Hoeffding’s inequality and Jensen’s inequality to control E[log(X + m) | X ≥ k].Jensen’s inequality replaces the expected logarithm with a logarithm of a conditional expectation.
  • Lower bound: The reverse deviation is bounded by applying Taylor’s theorem around x0 = Np and lower-bounding the intermediate derivative denominator.The proof then takes conditional expectations and uses E[X | X ≥ k] ≥ Np.
  • Conclusion: Elementary inequalities for the resulting series complete the bound and yield the lemma’s desired result.The proof invokes 2i^2 ≥ (i + 1)(i + 2) for i ≥ 4 and (N + 2)p ≥ 4p for N ≥ 2.

A.3 Proof of Lemma A.3

The proof conditions on the k-nearest-neighbor distance, partitions the remaining samples by relative distance, and derives binomial distributions for coordinate-wise neighbor counts.

  • Distance ordering: Samples are ordered by their max-coordinate distance to (x, y), with auxiliary uniform variables breaking distance ties.The comparison orders samples by d_i = max{∥X_i − x∥, ∥Y_i − y∥}, then uses Z_i when distances coincide.
  • Partitioning: The indices excluding the reference sample are partitioned into S, the k−1 closer samples, j, the kth neighbor, and T, the N−k−1 remaining samples.Each partition has identical probability, and the number of partitions is (N−1)!/[(N−k−1)!(k−1)!].
  • Conditional counts: Conditioned on the partition, nx,1 ≤ k + m means at most m samples in T have X-distance no greater than r.The indicators U_l record whether each T-sample lies within the X-radius r.
  • Conditional counts: The relevant indicators are conditionally i.i.d. Bernoulli variables because samples outside T can be dropped under independence.This conditional independence gives the coordinate-wise count distributions used in the proof.
  • Distributional conclusion: The X- and Y-coordinate counts have binomial distributions with N−k−1 trials and probabilities PX(x,r)−PXY(x,y,r) and PY(x,r)−PXY(x,y,r), respectively.The proof also establishes that nx,1−k has the corresponding distributional representation.

A.4 Proof of Lemma A.4

The proof bounds the deviation between log(Np + m) and E[log X] for a shifted binomial variable by treating the cases Np ≥ m and Np < m separately.

  • Reduction: Jensen’s inequality reduces the task to upper-bounding log(Np + m) − E[log X].The proof uses E[log X] ≤ log E[X] = log(Np + m).
  • Case analysis: When Np ≥ m, Taylor expansion around x0 = Np + m and bounds on the remainder control the logarithmic deviation.The case uses the relation 1/(2Np) ≤ 1/(Np + m).
  • Bound: For m ≥ 1 and N ≥ 4, the resulting bound is −E[log X] + log(Np + m) ≤ 1/(Np) + Np(1 − p).The proof obtains this expression after substituting bounds into the case-specific inequality.
  • Bound: The deviation is further bounded by 5/[2(Np + m)], and combining the two cases completes the lemma.The final simplification uses the preceding case bounds.
  • Case analysis: When Np < m, Taylor’s theorem around x0 = Np + m again supplies a bound using ζ ≥ m ≥ (Np + m)/2.This lower bound controls the Taylor remainder in the small-Np regime.

B Proof of Theorem 2

The proof establishes consistency by applying Efron–Stein to bound estimator variance, analyzing the change caused by removing one sample across several geometric cases, and using an asymptotic growth assumption.

  • Variance control: Efron–Stein inequality is used to bound the estimator’s variance by controlling changes after one sample is removed.The proof compares the original estimate with leave-one-out and replaced-sample versions.
  • Case analysis: The leave-one-out change is divided into the case i = j and cases where the removed sample has zero or positive joint nearest-neighbor distance.The proof then subdivides the latter cases according to coordinate coincidences and neighborhood membership.
  • Zero-distance cases: When joint distance is zero, coordinate coincidences determine how ˜k_i, nx,i, and ny,i change, yielding bounded contribution terms.For the case Zi = Zj, the proof gives |ξ_i(Z) − ξ_i(Z\j)| ≤ 8 for ˜k_j ≥ k ≥ 2.
  • Positive-distance cases: When joint distance is positive, four geometric subcases track whether the removed point lies in joint, X-only, Y-only, or neither neighborhood.The joint-neighbor case uses a cone-covering lemma to bound how many i can be affected.
  • Asymptotic conclusion: Under the assumption that d_x + d_y is constant and (kN log N)^2/N → 0, the variance bound vanishes as N → ∞.The proof inserts the aggregate difference bound into Efron–Stein inequality.

B.1 Proof of Lemma B.1

Lemma B.1 bounds how often a point can appear among nearest neighbors, first for a fixed neighbor rank and then for varying ranks.

  • Fixed rank: The lemma is proved using a prior result that bounds the number of points for which a fixed point is among the k-nearest neighbors.The cited result supplies the first part of the argument.
  • Varying ranks: The proof reorders indices by their neighbor ranks k_i and rewrites the relevant sum using indicators for each rank.This converts the varying-rank statement into a sum over fixed-rank contributions.
  • Varying ranks: The rank-specific contribution S_k counts indices satisfying k_i = k and the point’s inclusion in the k-nearest-neighbor set.The proof sums over k from 1 to N because no k_i exceeds N.
  • Final bound: The target inequality is Σ_{k=1}^N S_k/k ≤ γ_d log N, obtained by applying the fixed-rank bound.The second part follows from the first after reorganizing the indicators.
  • Final bound: The lemma’s proof is completed after establishing the fixed-rank and varying-rank bounds.The argument concludes once the reordered summation satisfies the logarithmic bound.
Loading 1709.06212v3…