Source-linked AI summary
Measures of Entropy from Data Using Infinitely Divisible Kernels
Luis G. Sanchez Giraldo, Murali Rao, Jose C. Principe
TL;DR
The paper tackles the difficulty of estimating information-theoretic quantities from empirical data without relying on restrictive distribution models or plug-in density estimators. It defines entropy-like functionals on kernel Gram matrices, using infinitely divisible kernels and RKHS operators, and reports favorable independence-test comparisons with the state of the art.
Problem
Estimating entropy from finite samples is difficult because plug-in approaches depend on estimating an unknown distribution, with risks from model choice, tuning, computation, and overfitting.
Method
The paper defines entropy-like functionals on normalized positive definite Gram matrices generated by infinitely divisible kernels and extends them to kernel-based conditional entropy and mutual information.
Results
The proposed estimators have asymptotic behavior supported by operator-spectrum concentration results, and independence-test experiments compare favorably with state-of-the-art methods.
Takeaways & Limitations
Entropy and related information quantities can be estimated directly from data through kernel operators without estimating the underlying probability distribution.
Takeaways & Limitations
Estimation bounds can require more data as α increases, although they may be lower when dominant eigenvalues fall below α−1.
Abstract
from arXiv · showhide
Information theory provides principled ways to analyze different inference and learning problems such as hypothesis testing, clustering, dimensionality reduction, classification, among others. However, the use of information theoretic quantities as test statistics, that is, as quantities obtained from empirical data, poses a challenging estimation problem that often leads to strong simplifications such as Gaussian models, or the use of plug in density estimators that are restricted to certain representation of the data. In this paper, a framework to non-parametrically obtain measures of entropy directly from data using operators in reproducing kernel Hilbert spaces defined by infinitely divisible kernels is presented. The entropy functionals, which bear resemblance with quantum entropies, are defined on positive definite matrices and satisfy similar axioms to those of Renyi's definition of entropy. Convergence of the proposed estimators follows from concentration results on the difference between the ordered spectrum of the Gram matrices and the integral operators associated to the population quantities. In this way, capitalizing on both the axiomatic definition of entropy and on the representation power of positive definite kernels, the proposed measure of entropy avoids the estimation of the probability distribution underlying the data. Moreover, estimators of kernel-based conditional entropy and mutual information are also defined. Numerical experiments on independence tests compare favourably with state of the art.
1 Introduction
The paper addresses the difficulty of estimating entropy from finite data without first estimating an underlying probability distribution. It proposes kernel-based entropy functionals on normalized positive definite matrices, with infinitely divisible kernels enabling direct, nonparametric measures of entropy and related information quantities.
- Motivation: Entropy estimation from finite samples normally requires estimating the data-generating probability distribution.Plug-in methods fit a distribution model and then substitute it into the information-theoretic quantity.
- Motivation: Distribution estimation introduces difficulties including meaningless empirical densities, model-selection trade-offs, hyperparameter tuning, computational cost, and overfitting.These issues motivate alternatives that avoid explicit distribution estimation.
- Related approaches: Existing graph-based estimators obtain entropy directly from samples but are often limited to α ∈ (0, 1) or are not differentiable for conventional gradient optimization.The cited approaches include entropic graphs, k-nearest-neighbour distances, and k-nearest-neighbour graphs.
- Proposed framework: The proposed method defines entropy-like functionals on normalized positive definite matrices without assuming known or estimated event probabilities.The matrices are formed by evaluating a positive definite kernel on every pair of data points, implicitly mapping data into an RKHS.
- Proposed framework: The resulting data-driven entropy measures uncertainty or structure in a sample represented by a Gram matrix.The paper emphasizes that kernel choice is central, with infinitely divisible kernels particularly suited to direct entropy measurement.
- Extensions: The framework extends beyond entropy by introducing joint entropy through Hadamard products and related conditional-entropy and mutual-information quantities.The construction is analyzed in relation to positive definite matrices and RKHS representations.
2 Hilbert Space Representation of Data
The section develops Hilbert-space representations of data through feature families and positive definite kernels, then connects information potentials and entropy estimators to Gram matrices.
- Hilbert-space representations: Reproducing kernel Hilbert spaces represent data through feature families that can handle non-vectorial objects and support generic kernel methods.The representation uses bounded measurable features indexed by a measure space and is useful for structured data such as text, trees, point processes, and functional data.
- Hilbert-space representations: Positive definite functions define Hilbert-space representations whose completed function spaces are reproducing kernel Hilbert spaces with the original kernel.The construction uses finite linear combinations of kernel sections and the positive-definiteness condition on their Gram matrices.
- Kernel geometry: A kernel-induced distance between representations is given by d^2(x,y)=G(x,x)+G(y,y)−2G(x,y), linking Gram matrices to geometry.The resulting function is a semimetric, and the Gram matrix becomes central to connecting information-theoretic concepts with kernel methods.
- Cross-information potential: For Parzen-type kernels, the cross-information potential defines an RKHS on mixtures of densities and links density-based and sample-based representations.The associated empirical estimator uses a Gram matrix whose entries are kernel evaluations on data pairs.
- Cross-information potential: The information potential estimator is related to the Frobenius norm of the Gram matrix, motivating extensions based on other spectral norms.A normalization term ensures that the Parzen window integrates to one, while the kernel choice determines the induced representation.
3 Renyi’s Entropy Axioms on Positive Definite Matrices
The paper extends Rényi-style entropy axioms from nonnegative numbers to normalized positive definite matrices using spectral matrix functionals. Its entropy depends on the eigenvalue spectrum and differs from quantum entropy because the matrices are kernel Gram matrices derived from data.
- Axiomatic matrix entropy: The matrix entropy framework applies Rényi-like axioms to nonnegative definite matrices, generalizing scalar nonnegative quantities.The admissible matrices have trace at most one and are closed under finite convex combinations.
- Spectral construction: Matrix functions are defined spectrally by applying continuous scalar functions to the eigenvalues of a positive definite matrix.The construction uses the spectral theorem and corresponding eigenvectors to define f(A).
- Entropy properties: The entropy satisfies a maximum value of log2 n for the identity matrix and assigns zero entropy to rank-one matrices.The rank-one result identifies concentrated spectral structure as an entropy-zero case.
- Relation to quantum entropy: The matrix functional resembles quantum-information entropies, but here the density-like object is a kernel Gram matrix formed from pairwise evaluations on a finite sample.Consequently, the analysis depends on both the entropy functional and the positive definite kernel used to construct the matrix.
- Kernel dependence: The kernel-induced mapping’s implicit dimensionality affects entropy because normalized rank-one Gram matrices have zero entropy.This makes the choice of positive definite kernel part of the information-theoretic analysis rather than merely a representation choice.
4 A Definition of Joint Entropy using Hadamard Products
The section defines joint, conditional, and mutual information quantities from normalized positive definite matrices using Hadamard products. Majorization inequalities provide compatibility and nonnegativity properties under explicit matrix conditions.
- Joint entropy: A Hadamard product of kernel matrices represents paired observations through a product kernel and defines their joint entropy.For paired samples, A and B are formed from separate kernels on X and Y, while A◦B represents the pair (X,Y).
- Majorization: Majorization orders eigenvalue sequences and supports Schur-concavity arguments for comparing matrix-based entropy quantities.The section introduces majorization before deriving inequalities that relate joint entropy to the entropies of its components.
- Joint entropy: The joint-entropy inequalities require positive definite matrices with unit trace, nonnegative entries, and diagonal entries equal to 1/n.These conditions enable the spectral inequalities used in the Hadamard-product construction.
- Conditional entropy: Conditional entropy is defined from the matrix-based joint and marginal quantities and is nonnegative and bounded above by the entropy of the conditioned variable.The bounds follow from the Hadamard-product inequalities under the stated positive semidefinite and normalization conditions.
- Mutual information: The matrix mutual-information quantity is nonnegative under the same normalization constraints and differs from Rényi mutual information based on α-order divergence.Its construction follows the matrix joint-entropy inequalities rather than a divergence between joint and product distributions.
- Infinitely divisible structure: Fractional Hadamard powers preserve positive definiteness only for infinitely divisible matrices, motivating their use in joint representations.The entrywise product A◦r◦B◦(1−r) preserves normalization for normalized diagonal matrices but requires this special matrix class for positive definiteness.
5 Information Theoretic Functionals based on Infinitely Divisible Matrices
Infinitely divisible matrices connect fractional Hadamard products, negative definite functions, and Hilbert-space embeddings. This framework supplies normalized Gram matrices for the proposed information-theoretic functionals.
- Infinite divisibility: An infinitely divisible matrix is positive semidefinite with nonnegative entries whose Hadamard powers remain positive semidefinite for every nonnegative exponent.Integer Hadamard powers are always positive semidefinite, whereas fractional powers require infinite divisibility.
- Negative definiteness: Infinite divisibility is linked to negative definiteness through the entrywise transformation B_ij=−log A_ij.This relation provides the logarithmic route from matrix kernels to negative definite functions.
- Hilbert-space embeddings: Negative definite matrices support isometric embeddings into Hilbert spaces, connecting infinitely divisible matrices with geometric representations.The construction uses a Hilbert space and a mapping derived from the transformed matrix.
- Matrix transformations: Positive definite matrices can be transformed through exponentiation into infinitely divisible matrices, providing a converse construction route.The paper states that if A is positive definite, then −A is negative definite and exp A_ij is infinitely divisible.
- Normalization: The normalization in the theorem yields the maximum-entropy matrix among matrices whose Hilbert-space embeddings are isometrically isomorphic.The theorem also establishes infinitely divisible normalized matrices associated with two semimetrics and their isometrically isomorphic embeddings.
- Framework overview: The framework offers two routes to the Gram matrix used by the entropy functional: direct normalization of an infinitely divisible kernel or a negative-definite-function route using log and exp.Figure 1 depicts the links among the kernel, negative-definite, and Hilbert-space representations.
6 Gram Matrices and Operator Embeddings of Probability Measures
This section embeds probability measures as operators in RKHSs and connects their population spectra to empirical Gram-matrix spectra. Under bounded, normalized positive definite kernels, these spectral relationships support convergence guarantees for matrix-based entropy estimators.
- Population operator: The operator G represents the population second-order structure induced by a kernel, with G(f,g)=E_X[f(X)g(X)] in the associated RKHS.The operator is trace class, Hilbert–Schmidt, and compact under the stated conditions.
- Empirical spectrum: The empirical operator bGN is constructed from the empirical distribution and has a spectrum determined by the positive eigenvalues of the Gram matrix K.The Gram matrix is formed from pairwise kernel evaluations, with normalization imposed on the infinitely divisible kernel.
- Empirical spectrum: The spectrum of bGN contains at most N positive eigenvalues, which correspond to the relevant Gram-matrix eigenvalues.This finite-dimensional spectral correspondence enables matrix calculations to estimate operator quantities.
- Convergence: Trace-power functionals of the Gram matrix estimate tr(G^α) through spectral convergence between empirical and population operators.The analysis uses variational eigenvalue results, concentration inequalities, and continuity of tr(A^α).
- Convergence: For α>1, the estimator’s deviation from the population trace is probabilistically bounded under bounded-kernel assumptions.The bound’s constant depends on α because Gram-matrix eigenvalues are raised to the power α; it can be reduced when dominant eigenvalues are below α^-1.
- Conditional entropy: The same RKHS construction extends to conditional entropy using tensor-product kernels and an operator Q on HX⊗HY.The finite counterpart is defined analogously from the paired sample and product Gram structure.
7 Experiments
The experiments evaluate an independence test based on the entropy gap between tensor and Hadamard Gram-matrix products. Across simulated dimensions, sample sizes, and angles, the proposed method is competitive with kernel and graph-based alternatives, while performance depends on dimensionality and angle.
- Experimental setup: The independence benchmark mixes pairs of standardized ICA densities with rotations, added Gaussian noise, and further random rotations to create dependent vectors.Experiments vary rotation angle, sample size, and dimensionality.
- Test procedure: The proposed test compares an entropy gap from tensor and Hadamard Gram products against a permutation-based threshold for the independence null hypothesis.The threshold uses 100 shuffled surrogates, and H0 is rejected when the observed gap exceeds the estimated 1−τ quantile.
- Results: In one dimension, type II error is low even for small samples, whereas increasing dimensionality makes dependence harder to detect and requires larger N.The reported acceptance-rate plots compare the proposed test with kernel-based and minimum-spanning-graph statistics.
- Results: The three methods perform relatively similarly for large angles, while the proposed method works better when the angle is close to 0.The comparison covers the kernel statistic and the entropic graph estimator.
- Parameter effects: Figure 3 varies kernel size σ and entropy order α at fixed sample size 1024 and rotation angle θ=π to examine parameter effects on test power.The figure’s stated setup fixes the sample size and rotation angle while changing the kernel and entropy parameters.
8 Conclusions
The paper presents entropy-like quantities from infinitely divisible matrices and establishes their RKHS-based operator behavior. Experiments show that the approach is useful for independence testing and competitive with state-of-the-art methods.
- Framework: The framework defines entropy-like functionals on positive definite matrices using the axiomatic characterization of Rényi entropy.The functionals resemble quantum-information entropies, but the analysis also depends on the kernel used to construct them.
- Derived quantities: Hadamard products support matrix-based quantities analogous to conditional entropy and mutual information, with infinitely divisible kernels providing the relevant conditions.The paper also analyzes asymptotic behavior through RKHS operators associated with data distributions.
- Theory: The convergence of Gram-matrix eigenvalues to integral-operator eigenvalues is independent of input dimensionality.This is identified as an important theoretical result of the framework.
- Experiments: Numerical experiments demonstrate usefulness for independence testing, with results that compete with the state of the art.The conclusion summarizes the empirical evidence without specifying a single benchmark value.
A.1 Hilbert Space representation of Data
This appendix establishes that the kernel-induced function d(x,y) is a semimetric. The argument uses symmetry from the positive definite function and Cauchy–Schwarz-based inequalities.
- Semimetric proof: The proof obtains symmetry of d(x,y) directly from the symmetry of G(x,y).The remaining semimetric properties are handled through Cauchy–Schwarz-based inequalities.
- Semimetric proof: The distance expression expands into kernel terms involving G(x,x), G(y,y), G(z,z), G(x,z), and G(y,z).This expansion is used in the inequality argument for the semimetric property.
A.2 Functional Calculus on Hermitian Matrices
The section extends scalar functions to Hermitian matrices through spectral decomposition, then develops generalized probability distributions and entropy axioms alongside kernel constructions that mirror sequence operations.
- Functional calculus: Continuous scalar functions extend to normal matrices by applying the function to eigenvalues in a unitary spectral decomposition.For A = UΛU* with diagonal eigenvalue matrix Λ, the resulting primary matrix function is continuous.
- Entropy functionals: Rényi entropy satisfies the stated axioms for α > 0 and α ≠ 1 and is monotone under the refinement ordering of σ-algebras.Refinement is defined by inclusion between sub-σ-algebras.
- Kernel constructions: Direct-sum kernels add positive definite kernels and induce an RKHS of sums, with its norm obtained by minimizing over decompositions into component functions.The construction accounts for overlapping component spaces through a quotient-style orthogonal decomposition.
- Kernel constructions: Tensor-product kernels multiply component kernels, remain positive definite, and generate tensor-product RKHSs whose diagonal restrictions have a reproducing kernel given by pointwise multiplication.The diagonal restriction uses the minimum tensor-space norm among extensions agreeing on the diagonal.
C.2.1 Negative Definite Functions and Hilbertian Metrics
Negative definiteness characterizes Hilbert-space embeddability of a separable metric space and yields positive definite Gaussian-type kernels, forming a bridge to infinitely divisible kernels.
- Hilbertian metrics: A separable metric space is embeddable in a Hilbert space exactly when its distance function satisfies the negative-definiteness inequality for finite coefficient sets summing to zero.The condition is stated for any n + 1 points in the metric space.
- Infinitely divisible kernels: Negative definiteness implies that exp(−r d^2(x_i, x_j)) is positive definite for every r > 0, and the resulting matrices are infinitely divisible.This implication connects metric-derived functions with the kernel class used in the paper.