The power of absolute discounting: all-dimensional distribution estimation
Moein Falahatgar, Mesrob I Ohannessian, Alon Orlitsky, Venkatadheeraj Pichapati
Abstract
Categorical models are a natural fit for many problems. When learning the distribution of categories from samples, high-dimensionality may dilute the data. Minimax optimality is too pessimistic to remedy this issue. A serendipitously discovered estimator, absolute discounting, corrects empirical frequencies by subtracting a constant from observed categories, which it then redistributes among the unobserved. It outperforms classical estimators empirically, and has been used extensively in natural language modeling. In this paper, we rigorously explain the prowess of this estimator using less pessimistic notions. We show that (1) absolute discounting recovers classical minimax KL-risk rates, (2) it is \emph{adaptive} to an effective dimension rather than the true dimension, (3) it is strongly related to the Good-Turing estimator and inherits its \emph{competitive} properties. We use power-law distributions as the cornerstone of these results. We validate the theory via synthetic data and an application to the Global Terrorism Database.
BibTeX
@inproceedings{NIPS2017_331316d4,
author = {Falahatgar, Moein and Ohannessian, Mesrob I and Orlitsky, Alon and Pichapati, Venkatadheeraj},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {The power of absolute discounting: all-dimensional distribution estimation},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/331316d4efb44682092a006307b9ae3a-Paper.pdf},
volume = {30},
year = {2017}
}