Estimation of KL divergence between large-alphabet distributions
Lists
Only you see this
Abstract
The problem of estimating the KL divergence between two unknown distributions is studied. The alphabet size k of the distributions can scale to infinity. The estimation is based on m and n independent samples respectively drawn from the two distributions. It is first shown that there does not exist any consistent estimator to guarantee asymptotic small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions with bounded ratio f(k) is further considered. An augmented plug-in estimator is proposed, and is shown to be consistent if and only if m = ω(k ⋁ log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> (f(k)) and n = ω(k f(k)). Furthermore, if f(k) ≥ log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> k and log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> (f(k)) = o(k), it is shown that any consistent estimator must satisfy the necessary conditions: m = ω( k/log k ⋁ log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> (f(k)) and n = ω( k f(k)/log k).
BibTeX
@inproceedings{bu2016estimation,
author = {Yuheng Bu and Shaofeng Zou and Yingbin Liang and Venugopal V. Veeravalli},
title = {{Estimation of KL divergence between large-alphabet distributions}},
booktitle = {ISIT},
year = {2016},
doi = {10.1109/isit.2016.7541473},
}Loading related content...