Calculating Laplace's law for bigrams

Question

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"

Regards

Answer 1

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.

Answer 2

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.

Answer 3

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

is supposed to be understood intuitively using the "probability estimate as relative frequency" argument.

The unsmoothed bigram probabilities are computed by normalizing bigram count by unigram count (the unigram that the bigram begins with):

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

After "adding one" smoothing, the bigram count increases by 1, and the unigram count increase by $V$, since you add 1 to the count of every bigram of the form $w_{n-1}w, w\in vocabulary$, giving you $V$ more counts in total. Then divide to get relative frequency

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

[Page 99 of Jurafsky's Speech and Language Processing, 2ed]

I think the problem with the Bayes' rule calculation $P(w_{n}|w_{n-1})=\displaystyle \frac{P(w_{n-1}w_{n})}{P(w_{n-1})}$ is the interpretation of the denominator $P(w_{n-1})$. Here it should be thought of as the "probability of $w_{n-1}$ being the prefix of any bigram", rather than the usual "probability of occurrence of the unigram $w_{n-1}$".

Extended to n-grams, $P(w_{n}|w_{1}^{n-1})=\displaystyle \frac{P(w_{1}^{n})}{P(w_{1}^{n-1})}$ says "the probability of word $w_n$ being preceded by word sequence $w_{1}...w_{n-1}$ is the probability of $w_{1}...w_{n}$ occurring divided by the probability of $w_{1}...w_{n-1}$ being a prefix of any n-gram".

Here the ML estimate of $P(w_{1}^{n-1})$ asks the question -- "out of all the bigrams, what portion have $w_{1}...w_{n-1}$ as their prefixes?" Therefore in our bigram case, Laplace smoothing gives the estimate $$P(w_{n-1}) = \frac{C(w_{n-1})+V}{N+V^2}$$ and following the usual interpretation of $P(w_{n-1}w_{n})$, Laplace smoothing gives

$$P(w_{n-1}w_{n}) = \frac{C(w_{n-1}w_{n})+1}{N + V^2} $$