The problem of f-divergence estimation is important in the fields of machine learning, information theory, and statistics. While several nonparametric divergence estimators exist, relatively few have known convergence properties. In particular, even for those estimators whose MSE convergence rates are known, the asymptotic distributions are unknown. We establish the asymptotic normality of a recently proposed ensemble estimator of f-divergence between two distributions from a finite number of samples. This estimator has MSE convergence rate of O(1 T), is simple to implement, and performs well in high dimensions. This theory enables us to perform divergence-based inference tasks such as testing equality of pairs of distributions based on empirical samples. We experimentally validate our theoretical results and, as an illustration, use them to empirically bound the best achievable classification error.
Estimators for some @math -divergences already exist. For example, P ' o czos & Schneider @cite_1 and @cite_16 provided consistent @math -nn estimators for R ' e nyi- @math and the KL divergences, respectively. Consistency has been proven for other mutual information and divergence estimators based on plug-in histogram schemes @cite_10 @cite_32 @cite_17 @cite_9 . @cite_28 provided an estimator for R ' e nyi- @math divergence but assumed that one of the densities was known. However none of these works study the convergence rates of their estimators nor do they derive the asymptotic distributions.
@cite_28 @cite_9 @cite_1 @cite_32 @cite_16 @cite_10 @cite_17
2060677448 1974829031 121168560 2149268774 2150879893 2127234432 2171585891
This article presents applications of entropic spanning graphs to imaging and feature clustering applications. Entropic spanning graphs span a set of feature vectors in such a way that the normalized spanning length of the graph converges to the entropy of the feature distribution as the number of random feature vectors increases. This property makes these graphs naturally suited to applications where entropy and information divergence are used as discriminants: texture classification, feature clustering, image indexing, and image registration. Among other areas, these problems arise in geographical information systems, digital libraries, medical information processing, video indexing, multisensor fusion, and content-based retrieval. Abstract The Darbellay–Vajda partition scheme is a well known method to estimate the information dependency. This estimator belongs to a class of data-dependent partition estimators. We would like to prove that with some simple conditions, the Darbellay–Vajda partition estimator is a strong consistency for the information dependency estimation of a bivariate random vector. This result is an extension of Silva and Narayanan, 2010a , Silva and Narayanan, 2010b work which gives some simple conditions to confirm that the Gessaman's partition estimator and the tree-quantization partition estimator, other estimators in the class of data-dependent partition estimators, are strongly consistent. We propose new nonparametric, consistent Renyi-α and Tsallis-α divergence estimators for continuous distributions. Given two independent and identically distributed samples, a “naive” approach would be to simply estimate the underlying densities and plug the estimated densities into the corresponding formulas. Our proposed estimators, in contrast, avoid density estimation completely, estimating the divergences directly using only simple k-nearest-neighbor statistics. We are nonetheless able to prove that the estimators are consistent under certain conditions. We also describe how to apply these estimators to mutual information and demonstrate their efficiency via numerical experiments. We present a universal estimator of the divergence D(P spl par Q) for two arbitrary continuous distributions P and Q satisfying certain regularity conditions. This algorithm, which observes independent and identically distributed (i.i.d.) samples from both P and Q, is based on the estimation of the Radon-Nikodym derivative dP dQ via a data-dependent partition of the observation space. Strong convergence of this estimator is proved with an empirically equivalent segmentation of the space. This basic estimator is further improved by adaptive partitioning schemes and by bias correction. The application of the algorithms to data with memory is also investigated. In the simulations, we compare our estimators with the direct plug-in estimator and estimators based on other partitioning approaches. Experimental results show that our methods achieve the best convergence performance in most of the tested cases. A new universal estimator of divergence is presented for multidimensional continuous densities based on k-nearest-neighbor (k-NN) distances. Assuming independent and identically distributed (i.i.d.) samples, the new estimator is proved to be asymptotically unbiased and mean-square consistent. In experiments with high-dimensional data, the k-NN approach generally exhibits faster convergence than previous algorithms. It is also shown that the speed of convergence of the k-NN method can be further improved by an adaptive choice of k. We demonstrate that it is possible to approximate the mutual information arbitrarily closely in probability by calculating the relative frequencies on appropriate partitions and achieving conditional independence on the rectangles of which the partitions are made. Empirical results, including a comparison with maximum-likelihood estimators, are presented. This work studies the problem of information divergence estimation based on data-dependent partitions. A histogrambased data-dependent estimate is proposed adopting a version of Barron-type histogram-based estimate. The main result is the stipulation of su cient conditions on the partition scheme to make the estimate strongly consistent. Furthermore, when the distributions are equipped with density functions in ( d ;B( d )), we obtain su cient conditions that guarantee a density-free strongly consistent information divergence estimate. In this context, the result is presented for two emblematic partition schemes: the statistically equivalent blocks (Gessaman’s data-driven partition) and data-dependent tree-structured vector quantization (TSVQ).