Concentration Bounds for Unigrams Language Model
Lists
Only you see this
Abstract
We show several PAC-style concentration bounds for learning unigrams language model. One interesting quantity is the probability of all words appearing exactly k times in a sample of size m. A standard estimator for this quantity is the Good-Turing estimator. The existing analysis on its error shows a PAC bound of approximately \(O(\frac{k}{\sqrt{m}})\). We improve its dependency on k to \(O(\frac{\sqrt[4]{k}}{\sqrt{m}}+\frac{k}{m})\). We also analyze the empirical frequencies estimator, showing that its PAC error bound is approximately \(O(\frac{1}{k}+\sqrt{k}{m})\). We derive a combined estimator, which has an error of approximately \(O(m-\frac{2}{5})\), for any k.
BibTeX
@inproceedings{drukh2004concentration,
author = {Evgeny Drukh and Yishay Mansour},
title = {{Concentration Bounds for Unigrams Language Model}},
booktitle = {Conference on Learning Theory},
year = {2004},
url = {https://openreview.net/forum?id=Pyc-sBsHsV},
}Loading related content...