Estimation of Nonlinear Functionals of Densities With Confidence

Kumar Sricharan, Raviv Raich, Alfred O. Hero Iii

Abstract

This paper introduces a class of <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\rm k}$</tex></formula> -nearest neighbor ( <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$k$</tex></formula> -NN) estimators called bipartite plug-in (BPI) estimators for estimating integrals of nonlinear functions of a probability density, such as Shannon entropy and Rényi entropy. The density is assumed to be smooth, have bounded support, and be uniformly bounded from below on this set. Unlike previous <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$k$</tex></formula> -NN estimators of nonlinear density functionals, the proposed estimator uses data-splitting and boundary correction to achieve lower mean square error. Specifically, we assume that <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$T$</tex></formula> i.i.d. samples <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$ {\bf X}_{i} \in \BBR ^{d}$</tex></formula> from the density are split into two pieces of cardinality <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$M$</tex></formula> and <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$N$</tex> </formula> , respectively, with <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$M$</tex></formula> samples used for computing a <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$k$</tex></formula> -NN density estimate and the remaining <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$N$</tex></formula> samples used for empirical estimation of the integral of the density functional. By studying the statistical properties of <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$k$</tex></formula> -NN balls, explicit rates for the bias and variance of the BPI estimator are derived in terms of the sample size, the dimension of the samples, and the underlying probability distribution. Based on these results, it is possible to specify optimal choice of tuning parameters <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$M/T$</tex></formula> , <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$k$</tex></formula> for maximizing the rate of decrease of the mean square error. The resultant optimized BPI estimator converges faster and achieves lower mean squared error than previous <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$k$</tex></formula> -NN entropy estimators. In addition, a central limit theorem is established for the BPI estimator that allows us to specify tight asymptotic confidence intervals.
BibTeX
@article{sricharan2012estimation,
  author = {Kumar Sricharan and Raviv Raich and Alfred O. Hero III},
  title = {{Estimation of Nonlinear Functionals of Densities With Confidence}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  doi = {10.1109/tit.2012.2195549},
}
Figure