WittenBell

Witten-Bell smoothing is a simple statistical technique used to estimate probabilities for discrete events, particularly in language modeling and other n-gram based applications. It was introduced by Ian H. Witten and Toby Bell in the early 1990s to address the zero-frequency problem, where some events observed in a dataset have not appeared in a given context and would otherwise be assigned zero probability.

The method relies on the idea that the probability mass for unseen events can be allocated based on how many distinct events have been seen after a given history. For a given history h, let N(h) be the total number of occurrences of all events that follow h, and t(h) be the number of distinct events that have followed h (the number of seen types). For an observed event w with count c(h,w) > 0, the smoothed probability is proportional to its count: P(w|h) = c(h,w) / (N(h) + t(h)). The remaining probability mass, which accounts for unseen events (those with c(h,w) = 0), is distributed evenly among the unseen types: P(w|h) = t(h) / [(N(h) + t(h)) * (V − t(h))], where V is the vocabulary size (the total number of possible events). This yields a nonzero probability for unseen events without requiring any explicit zero-frequency adjustments.

Witten-Bell smoothing is valued for its simplicity and parameter-free nature, and it performs reasonably well for moderate to large vocabularies. Its limitations include sensitivity to vocabulary size and the assumption of equal distribution among unseen events, which may be suboptimal in some domains. It is one of several smoothing techniques used to improve language models, alongside Laplace, Good-Turing, and Kneser-Ney methods.