Non-Parametric Entropy Estimation via Nearest Neighbors

136 concepts112 papers2 proposals

When analyzing complex systems—whether tracking information flow in the human brain, mapping gene regulatory networks, or optimizing representations in deep neural networks—we fundamentally need to quantify how variables depend on one another.

Traditional statistical metrics like the Pearson correlation coefficient are widely used because they are simple to compute. However, they suffer from a fatal flaw: they assume relationships are linear and data distributions are Gaussian. If two variables share a complex, non-linear relationship (such as a periodic or sinusoidal coupling), linear metrics will often report a correlation of zero.

Information theory provides a universal alternative. Shannon entropy ($H$) measures the absolute uncertainty of a random variable, while Mutual Information ($I$) quantifies the shared information between two variables, capturing any statistical dependency regardless of its shape or form. As explained in a foundational overview by Robin A. A. Ince et al. in Summary of Information Theoretic Quantities, these metrics provide a standardized, model-free currency for comparing relationships across entirely different systems.

Because of this flexibility, mutual information has become essential across diverse domains:

But computing these information-theoretic quantities in practice introduces a massive challenge: How do you calculate entropy when you don't know the underlying probability distribution of your data?


The Pitfalls of Explicit Density Estimation

To calculate the Shannon entropy of a continuous variable $X$, we evaluate the integral:

$$H(X) = -\int p(x) \log p(x) \, dx$$

To compute this, we need the probability density function $p(x)$. In practice, we only have a finite set of data points sampled from $p(x)$.

The naive solution is to first estimate $p(x)$ explicitly and then compute the integral. One could assume a parametric form (like a Gaussian distribution), but if the assumption is wrong, the entropy estimate will be highly inaccurate. Alternatively, one could use non-parametric density estimation, such as splitting the space into fixed bins (histograms) or using Parzen window kernel density estimators, as explored by Jarkko Ylipaavalniemi et al. in Functional elements and networks in fMRI.

However, explicit density estimation suffers from severe limitations:

  1. The Curse of Dimensionality: As the number of dimensions grows, the amount of data needed to fill fixed bins grows exponentially. Most bins quickly become empty.
  2. Grid-Resolution Sensitivity: As noted by Yang Hu et al. in Maximal information-based nonparametric exploration of condition monitoring data, the results of grid-based estimators are highly sensitive to the choice of bin size or kernel width, making them unstable for complex data distributions.

To solve this, we need a way to bypass explicit density estimation entirely. We need to estimate entropy directly from the spatial distribution of the data points.


The Core Intuition: Distance as a Proxy for Density

The breakthrough insight behind non-parametric entropy estimation—originally formalized by Kozachenko and Leonenko—is that the distance between a data point and its nearest neighbors is an implicit reflection of the local probability density.

Imagine you are standing on a data point in a high-dimensional space. You expand a hyperspherical bubble outward from your position until it swallows exactly $k$ neighboring data points.

  • If the local probability density $p(x)$ around you is high (the data is tightly packed), your bubble will hit $k$ neighbors very quickly. The radius of the bubble will be small.
  • If the local probability density $p(x)$ around you is low (the data is sparse), you will have to expand your bubble significantly before it encapsulates $k$ neighbors. The radius of the bubble will be large.
High Density (Low Entropy)          Low Density (High Entropy)
     .  .   .                            .       .
   .  ( k ) .                                 (     k     )
     .  .   .                            .       .
  Small Radius (R)                            Large Radius (R)

Mathematically, the probability mass contained within a hypersphere of radius $R$ around a point $x_i$ can be approximated as the local density multiplied by the volume of the hypersphere:

$$\text{Mass} \approx p(x_i) \cdot V_d(R^3)$$

where $V_d(R^3)$ is the volume of a $d$-dimensional ball of radius $R$. Since we chose $R$ specifically to encompass exactly $k$ out of $N$ total sample points, the empirical probability mass inside the bubble is simply $k/N$. Setting these equal gives us a direct proxy for the local density:

$$\frac{k}{N} \approx p(x_i) \cdot V_d(R^3) \implies p(x_i) \approx \frac{k}{N \cdot V_d(R^3)}$$

If we substitute this local density approximation back into the Shannon entropy formula and average over all $N$ data points, the explicit density terms cancel out. We are left with an estimator that calculates entropy based purely on the logarithm of the distances to the $k$-th nearest neighbors plus a few analytic correction constants (like the Digamma function) to account for systematic biases.

This approach is incredibly powerful because it adapts dynamically to the local geometry of the data. It has been leveraged by Mirco Mutti et al. in Task-Agnostic Exploration via Policy Gradient of a Non-Parametric State Entropy Estimate to allow reinforcement learning agents to explore continuous state spaces without explicit density modeling. Similarly, Amur Ghose et al. in Batch norm with entropic regularization turns deterministic autoencoders into generative models used $k$-nearest neighbor distances within a minibatch to regularize the latent space of deterministic autoencoders without forcing them into rigid parametric distributions.


From Entropy to Mutual Information: The Scale-Matching Problem

Mutual Information ($I$) can be expressed as a combination of individual and joint entropies:

$$I(X;Y) = H(X) + H(Y) - H(X,Y)$$

A naive approach to calculating Mutual Information would be to use the Kozachenko-Leonenko method to estimate $H(X)$, $H(Y)$, and $H(X,Y)$ independently using $k$-nearest neighbors, and then subtract them.

However, this fails spectacularly in practice. The spatial scales of the marginal spaces ($X$ and $Y$) are often completely different from the spatial scale of the joint space $(X,Y)$. If you choose a fixed $k$ (e.g., $k=3$) to find the nearest neighbors in the joint space, the corresponding distance might cover a completely different number of neighbors when projected down into the individual $X$ or $Y$ spaces. The systematic biases of the individual entropy estimates will not cancel out, leading to highly inaccurate, sometimes negative mutual information values.

To fix this, the seminal Kraskov-Stögbauer-Grassberger (KSG) estimator introduces a clever scale-matching trick:

  1. First, look at the joint space $(X,Y)$. For each data point $i$, find the distance $\epsilon_i$ to its $k$-th nearest neighbor using a maximum norm (which forms a bounding box rather than a sphere).
  2. Project this exact bounding box down into the marginal spaces $X$ and $Y$.
  3. Instead of looking for the $k$-th nearest neighbor in the marginal spaces, simply count how many points ($n_x$ and $n_y$) fall inside that exact distance $\epsilon_i$ in the $X$ and $Y$ spaces independently.
       Joint Space (X, Y)                     Marginal Projections

          +-------+-------+                      +-------+-------+
          |       |   .   |                      |       |       |
          |   .   |       |                      |   n_x |       |
    Y  ---+-------o-------+---             X  ---+-------o-------+---
          |       |       |                      |       |       |
          |   .   |       |                      |       |       |
          +-------+-------+                      +-------+-------+
                  X                                      
    Find k-NN distance (epsilon)           Count points within epsilon

By fixing the distance scale $\epsilon_i$ across both joint and marginal spaces and letting the number of neighbors ($n_x, n_y$) vary, the systematic errors introduced by the local data geometry match perfectly. When we compute $H(X) + H(Y) - H(X,Y)$, the biases cancel out mathematically, yielding a highly accurate, low-variance estimate of Mutual Information.


Robustness and Modern Extensions

The non-parametric nearest-neighbor approach has proven remarkably resilient to real-world data anomalies. For instance, when data lies on low-dimensional manifolds embedded within high-dimensional spaces, standard estimators can collapse. The authors of Mutual information and the speech signal demonstrated that adding controlled noise to "thicken" these manifolds allows distance-based estimators to remain stable and accurate.

Furthermore, the framework has been extended to handle complex data structures. Weihao Gao et al. in Estimating Mutual Information for Discrete-Continuous Mixtures adapted the $k$-NN approach to calculate mutual information for datasets containing a mix of discrete labels and continuous variables, bypassing the traditional requirement that data must be purely one or the other. In time-series analysis, the authors of Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information. combined nearest-neighbor conditional mutual information (CMI) with local permutations to create robust, non-parametric conditional independence tests that can isolate true directed dependencies without assuming a functional form.

By shifting the problem from modeling global probability densities to measuring local geometric distances, non-parametric nearest-neighbor estimation provides a mathematically rigorous, computationally scalable, and highly intuitive framework for uncovering the hidden, non-linear structures of our world.

Key Foundational Work

Comparison of Clustering Metrics and Unsupervised Learning Algorithms on Genome-Wide Gene Expression Level Data (1999) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 110 papers
  2. Version 1 · 2026-10-04 · 151 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_parametric_entropy_estimation_278f09a6,
  title = {non-parametric entropy estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-parametric-entropy-estimation/rdr_278f09a66a474aa9a01f0ea58eb50cae},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_non_parametric_entropy_estimation_278f09a6_v2,
  title = {non-parametric entropy estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-parametric-entropy-estimation/rdr_278f09a66a474aa9a01f0ea58eb50cae/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake