Always Good Turing: Asymptotically Optimal Probability Estimation

by: Alon Orlitsky, Narayana P Santhanam, Junan Zhang

Science, Vol. 302, No. 5644. (17 October 2003), pp. 427-431.

View FullText article

DOI, HighWire, Pubmed, Hubmed

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

davidr

Find related articles with these CiteULike tags

good-turing, language-modeling, smoothing, statistics

Abstract

While deciphering the Enigma code, Good and Turing derived an unintuitive, yet effective, formula for estimating a probability distribution from a sample of data. We define the attenuation of a probability estimator as the largest possible ratio between the per-symbol probability assigned to an arbitrarily long sequence by any distribution, and the corresponding probability assigned by the estimator. We show that some common estimators have infinite attenuation and that the attenuation of the Good-Turing estimator is low, yet greater than 1. We then derive an estimator whose attenuation is 1; that is, asymptotically it does not underestimate the probability of any sequence. 10.1126/science.1088284

@article{citeulike:582392, abstract = {While deciphering the Enigma code, Good and Turing derived an unintuitive, yet effective, formula for estimating a probability distribution from a sample of data. We define the attenuation of a probability estimator as the largest possible ratio between the per-symbol probability assigned to an arbitrarily long sequence by any distribution, and the corresponding probability assigned by the estimator. We show that some common estimators have infinite attenuation and that the attenuation of the Good-Turing estimator is low, yet greater than 1. We then derive an estimator whose attenuation is 1; that is, asymptotically it does not underestimate the probability of any sequence. 10.1126/science.1088284}, author = {Orlitsky, Alon and Santhanam, Narayana P. and Zhang, Junan }, citeulike-article-id = {582392}, doi = {10.1126/science.1088284}, journal = {Science}, keywords = {good-turing, language-modeling, smoothing, statistics}, month = {October}, number = {5644}, pages = {427--431}, posted-at = {2006-04-11 23:52:09}, priority = {2}, title = {Always Good Turing: Asymptotically Optimal Probability Estimation}, url = {http://dx.doi.org/10.1126/science.1088284}, volume = {302}, year = {2003} }

RIS record

TY - JOUR ID - citeulike:582392 L3 - citeulike-article-id:582392 TI - Always Good Turing: Asymptotically Optimal Probability Estimation JF - Science VL - 302 IS - 5644 SP - 427 EP - 431 N2 - While deciphering the Enigma code, Good and Turing derived an unintuitive, yet effective, formula for estimating a probability distribution from a sample of data. We define the attenuation of a probability estimator as the largest possible ratio between the per-symbol probability assigned to an arbitrarily long sequence by any distribution, and the corresponding probability assigned by the estimator. We show that some common estimators have infinite attenuation and that the attenuation of the Good-Turing estimator is low, yet greater than 1. We then derive an estimator whose attenuation is 1; that is, asymptotically it does not underestimate the probability of any sequence. 10.1126/science.1088284 KW - good-turing KW - language-modeling KW - smoothing KW - statistics AU - Orlitsky, Alon AU - Santhanam, Narayana AU - Zhang, Junan PY - 2003/10/17/ UR - http://dx.doi.org/10.1126/science.1088284 ER -

RIS BibTeX