Estimating mutual information from i.i.d. samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is one proposed by Kraskov and St "ogbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its @math nearest neighboring sample, where @math is a fixed small integer. Despite its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the bias as a function of number of samples. We argue that the superior performance benefits of the KSG estimator stems from a curious "correlation boosting" effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a byproduct of our investigations, we obtain nearly tight rates of convergence of the @math error of the well known fixed @math nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.
In this paper we have considered the smoothness of the class of pdfs studied via bounded Hessians. In nonparametric estimation, a standard feature is to consider whole families of smooth pdfs as defined by how the differences of derivatives relate to the differences of the samples @cite_27 . Of specific interest is the H " o lder family: @math , i.e., for any tuple @math , define @math . Then for any @math such that @math , where @math is the largest integer smaller than @math , we have: for any @math . The rate of convergence of various nonparametric estimators depends on the parameter @math of the H " o lder family under consideration, cf. @cite_63 @cite_0 for recent work on convergence rate characterization of information theoretic quantities via KDE and resubstitution estimators as a function of the smoothness parameter @math . It is natural to ask if such smoothness considerations could lead to a refined understanding of the rates of convergence of the fixed @math -NN KL and KSG estimators studied here.
@cite_0 @cite_27 @cite_63
2188155116 202188608 1673728053
We study the density estimation problem with observations generated by certain dynamical systems that admit a unique underlying invariant Lebesgue density. Observations drawn from dynamical systems are not independent and moreover, usual mixing concepts may not be appropriate for measuring the dependence among these observations. By employing the @math -mixing concept to measure the dependence, we conduct statistical analysis on the consistency and convergence of the kernel density estimator. Our main results are as follows: First, we show that with properly chosen bandwidth, the kernel density estimator is universally consistent under @math -norm; Second, we establish convergence rates for the estimator with respect to several classes of dynamical systems under @math -norm. In the analysis, the density function @math is only assumed to be H " o lder continuous which is a weak assumption in the literature of nonparametric density estimation and also more realistic in the dynamical system context. Last but not least, we prove that the same convergence rates of the estimator under @math -norm and @math -norm can be achieved when the density function is H " o lder continuous, compactly supported and bounded. The bandwidth selection problem of the kernel density estimator for dynamical system is also discussed in our study via numerical simulations. We study trend filtering, a recently proposed tool of [SIAM Rev. 51 (2009) 339-360] for nonparametric regression. The trend filtering estimate is defined as the minimizer of a penalized least squares criterion, in which the penalty term sums the absolute @math th order discrete derivatives over the input points. Perhaps not surprisingly, trend filtering estimates appear to have the structure of @math th degree spline functions, with adaptively chosen knot points (we say appear'' here as trend filtering estimates are not really functions over continuous domains, and are only defined over the discrete set of inputs). This brings to mind comparisons to other nonparametric regression tools that also produce adaptive splines; in particular, we compare trend filtering to smoothing splines, which penalize the sum of squared derivatives across input points, and to locally adaptive regression splines [Ann. Statist. 25 (1997) 387-413], which penalize the total variation of the @math th derivative. Empirically, we discover that trend filtering estimates adapt to the local level of smoothness much better than smoothing splines, and further, they exhibit a remarkable similarity to locally adaptive regression splines. We also provide theoretical support for these empirical findings; most notably, we prove that (with the right choice of tuning parameter) the trend filtering estimate converges to the true underlying function at the minimax rate for functions whose @math th derivative is of bounded variation. This is done via an asymptotic pairing of trend filtering and locally adaptive regression splines, which have already been shown to converge at the minimax rate [Ann. Statist. 25 (1997) 387-413]. At the core of this argument is a new result tying together the fitted values of two lasso problems that share the same outcome vector, but have different predictor matrices. Estimating divergences in a consistent way is of great importance in many machine learning tasks. Although this is a fundamental problem in nonparametric statistics, to the best of our knowledge there has been no finite sample exponential inequality convergence bound derived for any divergence estimators. The main contribution of our work is to provide such a bound for an estimator of R 'enyi- @math divergence for a smooth H "older class of densities on the @math -dimensional unit cube @math . We also illustrate our theoretical results with a numerical experiment. We derive the mean squared error convergence rates of kernel density-based plug-in estimators of mutual information measures between two multidimensional random variables @math and @math for two cases: 1) @math and @math are both continuous; 2) @math is continuous and @math is discrete. Using the derived rates, we propose an ensemble estimator of these information measures for the second case by taking a weighted sum of the plug-in estimators with varied bandwidths. The resulting ensemble estimator achieves the @math parametric convergence rate when the conditional densities of the continuous variables are sufficiently smooth. To the best of our knowledge, this is the first nonparametric mutual information estimator known to achieve the parametric convergence rate for this case, which frequently arises in applications (e.g. variable selection in classification). The estimator is simple to implement as it uses the solution to an offline convex optimization problem and simple plug-in estimators. A central limit theorem is also derived for the ensemble estimator. Ensemble estimators that achieve the parametric rate are also derived for the first case ( @math and @math are both continuous) and another case 3) @math and @math may have any mixture of discrete and continuous components.