In natural language processing, Witten-Bell discounting is a method that can address the sparse data and zero-frequency issues in N-gram algorithms. It was first proposed by Ian Witten and Tim Bell in 1991. A word that hasn't been encountered before is considered unseen, thus zero-frequency N-gram refers to an occurrence that has yet to take place; when it does, it will mark the initial instance we observe this new N-gram. Thus, the likelihood of encountering a zero-frequency N-gram can be represented by the likelihood of encountering an N-gram for the initial time. The idea behind Witten-Bell is the application of the number of items we have encountered once to assist in estimating the number of items never encountered. Utilizing this method, we can remove obtaining zero probability values for transition probability and maximum likelihood estimation for a series of words (N-gram) that is encountered for the first time in our algorithm.
Example Three models are linearly interpolated, where e1, e2, and e3 are the maximum likelihood estimates of the three backoff models: P = λ1 e1 + (1 - λ1) (λ2 e2 + (1-λ2) e3) The values of λ1 and λ2 are set to implement Witten-Bell discounting.
References