# Statistical tests for 3-gram collocations extraction

I'm trying to extract collocations from some text data, and I use statistical tests to tell if an n-gram is a good collocation candidate or not.

All the sources I came across so far (for example, Manning's book on Statistical NLP, chapter 5) only treat 2-gram candidates and do not go on to considering 3-grams and higher order compound terms.

For bigrams it works as following:

• Under $H_0$ we assume that words $w_1, w_2$ are "independent", i.e. do not form a collocation. That is, $P(w_1, w_2) = P(w_1) \, P(w_2)$.
• Then we estimate $P(w_1), P(w_2)$ and $P(w_1, w_2)$ from our data (e.g. by using Maximum Likelihood Estimator)
• Finally, we compare the observed value of $P(w_1, w_2)$ with the value expected under $H_0$.

How this can be extended to 3-grams and 4-grams? And how one would go about estimating probabilities for such n-grams under $H_0$?

Should $H_0$ for 3-grams look like $P(w_1, w_2, w_3) = P(w_1, w_2) \, P(w_3)$? Or rather $P(w_1, w_2, w_3) = P(w_1) \, P(w_2) \, P(w_3)$?

$H_0$ here is the hypothesis that these words appearing together as often as they do is simply due to chance. The most basic interpretation would be that all three words are independent, i.e. $P(w_1, w_2, w_3) = P(w_1)P(w_2)P(w_3)$.

Now you have to be careful with this. If your phrase is "New York resident," then these three words probably do occur together more frequently than expected by chance, since "New" and "York" form what we would think of as a collocation (whether or not that will be significant depends on your corpus).

Since "collocation" doesn't have a rigorous definition, it's not clear what the best way to avoid the above problem is mathematically. Some authors have considered $P(w_1,w_2,w_3)=P(w_1,w_2)P(w_3)+P(w_1)P(w_2,w_3)$ .

My recommendation would be the following: Since English is a primarily right-branching language, most collocations will have this form $((a,b),c)$ like "New York Yankees" or $(((a,b), c), d)$ like "New York Yankees manager". I think you'd be pretty safe making your null hypothesis $P(w_1,w_2,w_3)=P(w_1,w_2)P(w_3)$.

Sorry that's not a rigorous statistical answer, but I don't think you'll find such an answer for a loosely defined term like "collocation."

 Petrović S. et al. Comparison of collocation extraction measures for document indexing, 2006. [pdf]

• Thank you. I myself also lean towards $P(w_1,w_2,w_3)=P(w_1,w_2)P(w_3)$. You say that "some authors have considered..." - do you, by chance, remember the references? I would be interested to have a look. – Alexey Grigorev Oct 15 '15 at 15:23
• The paper I was remembering was this one, but it turns out the authors actually used this idea on pointwise mutual information (rather than the chi-square test), but I think it should apply equally well to statistical methods. – Ben Oct 15 '15 at 15:32