Timezone: »

 
Poster
The power of absolute discounting: all-dimensional distribution estimation
Moein Falahatgar · Mesrob Ohannessian · Alon Orlitsky · Venkatadheeraj Pichapati

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #59
in Posters Tue »

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.

Keywords: Information Theory · Learning Theory · Density Estimation · Natural Language Processing · Competitive Analysis
[ Paper] 

Author Information

Moein Falahatgar (UCSD)
Mesrob Ohannessian (Toyota Technological Institute at Chicago)
Alon Orlitsky (University of California, San Diego)
Venkatadheeraj Pichapati (UCSD)

More from the Same Authors