Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Reading this PDF, I encountered a very simple simplification that I can't obtain. Basically, it asks what is the probability of the occurrence of a word $w_{n}$ given that we know another word $w_{n-1}$ already appeared before. Usually, this is calculated using the Maximum Likelihood Estimate which gives the probability:

$$P(w_{n}|w_{n-1}) = \displaystyle \frac{C(w_{n-1}w_{n})}{C(w_{n-1})}$$

where $C(w_{n})$ is the frequency of the word $w_{n}$

However, using an alternative probability called Laplace's law or Expected Likelihood Estimation we have as probability of $w_{n-1}w_{n}$

$$P(w_{n-1}w_{n}) = \frac{C(w_{n-1}w_{n})+1}{N + B} \tag{*}$$

where N is the number of tokens considered in our sample and B is the number of types which in this case would be B = V (V = vocabulary size) for unigrams and B = $V^{2}$ for bigrams.

The PDF says that $P(w_{n}|w_{n-1}) = \displaystyle \frac{C(w_{n-1}w_{n})+1}{C(w_{n-1}+V)}$ however I can't prove that. I expected to get that answer by using Bayes rule like this:

$$P(w_{n}|w_{n-1})=\displaystyle \frac{P(w_{n-1}w_{n})}{P(w_{n-1})}$$

and using (*) but I don't get anything similar.

Some help would be appreciated.

By the way, the part I'm referring to is contained in a slide titled "Laplace Add-One Smoothing"


share|cite|improve this question
up vote 2 down vote accepted

Laplace smoothing is a result of maximum aposteriori (MAP) estimation of the conditional probability $P(w_n|w_{n-1})$ under a Dirichlet prior.

Specifically, we want to estimate the $|V|$-valued multinomial distribution $p_k = P(w_n=k|w_{n-1})$, where $V$ is the vocabulary. Let us impose a Dirichlet prior on this multinomial distribution. That is, let $(p_1,\ldots,p_{|V|})$ be drawn from $Dir(\alpha,\ldots,\alpha)$, where $\alpha \geq 0$ is the concentration parameter of the Dirichlet distribution.

The MAP estimate of $p_k$ can be found out as under:

$\hat{p}_k = \arg \max_{p_k} \sum_{k_1=1}^{|V|} C(w_{n-1}, k_1)\log p_{k_1} + \log{\Gamma(\alpha|V|)} - |V|\log{\Gamma(\alpha)} + \sum_{k_1}^K(\alpha-1)\log p_{k_1}$

subject to $\sum_{k_1=1}^K p_{k_1} = 1$

($\Gamma(x)$ is the Gamma function)

The first term in the objective term is due to the multinomial likelihood function, while the remaining are due to the Dirichlet prior. We can now use Lagrange multipliers to solve the above constrained convex optimization problem. The solution is the Laplace smoothed bigram probability estimate:

$\hat{p}_k = \frac{C(w_{n-1}, k) + \alpha - 1}{C(w_{n-1}) + |V|(\alpha - 1)}$

Setting $\alpha = 2$ will result in the add one smoothing formula.

share|cite|improve this answer
Thanks for your answer. Then this formula can't be derived from Bayes' rule? I never read anything suggesting that it required to solve an optimization problem. – Robert Smith Aug 19 '12 at 15:36
Actually, we are using Bayes rule to formulate the MAP optimization problem. The posterior density of the parameter (say $\theta$) is being decomposed as: $P(\theta|x) \propto P(x|\theta) P(\theta)$. $P(x|\theta)$ is the likelihood of data $x$ and $P(\theta)$ is the prior on the parameter. – Kartik Audhkhasi Aug 19 '12 at 16:58
I see. It's only that as I haven't read about MAP problems, I'm a bit lost understanding this as opposed to other smoothing procedures. But thanks. – Robert Smith Aug 19 '12 at 17:53
I have read now about this distribution but I can't find a reason to use the Dirichlet distribution in this case. Do you something about it? – Robert Smith Aug 19 '12 at 19:45
Dirichlet distribution is the conjugate prior of the multinomial/categorical distribution. This is especially attractive in Bayesian statistics, since the parameter posterior will again be a Dirichlet distribution. As an important consequence, the MAP estimate of the parameters will have a "nice" form. So it is really a matter of convenience. You can read further on conjugate priors on the Wikipedia page: – Kartik Audhkhasi Aug 19 '12 at 20:44

In Kartik Audhkhasi's answer, he concluded that Laplace's smoothing can be achieved using MAP on the Dirichlet posterior, with $\alpha=2$. However I guess this is not a practical solution. As for infrequent bigrams, $C(w_{n-1}w_n)$ could be $0$ or $1$, and using a "pseudocount" (intuitively speaking) of "2" gives too much prior information. Another flaw is, when $\alpha < 1$, the MAP estimate doesn't have a solution in the simplex of $\sum_k p_k = 1,\text{and } \forall k, p_k \ge 0$.

Actually, it's widely accepted that Laplace's smoothing is equivalent to taking the mean of the Dirichlet posterior -- as opposed to MAP. The mean of the Dirichlet has a closed form, which can be easily verified to be identical to Laplace's smoothing, when $\alpha=1$. This is better than $\alpha=2$, but still often imposes excessive prior information. That's why Laplace's smoothing is described as a "horrible choice" in Bill MacCartney's NLP slides.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.