I have a corpus {text1, text2, text3, text4, ..., etc.}. I have no prior knowledge about the text. Lets say we extract all the n-grams (unigrams, bigrams, trigrams, 4-gram, 5-gram, ...) along with their frequency from the text.

My question is how can we merge the best N n-grams form the unigrams, bigrams, trigrams, 4-gram, 5-gram to one variable n-gram dictionary (that contains different n-gram lengths) with a simple "statistical" action?

  • $\begingroup$ Do you mean How do I program it? If so this is off-topic here so perhaps you can clarify. $\endgroup$ – mdewey May 22 '17 at 11:34
  • $\begingroup$ No I didn't mean how I program it. how to program I know excellent. I ask from the conceptual side. How I merge N different ngrams to one dictionary and take only the top K . (merge by frequency) $\endgroup$ – MAK May 22 '17 at 14:18

What you are looking for is statistical means for identifying collocations (that is, non-compositional phrases). Have a look at Foundations of Statistical Natural Language Processing, Manning & Schütze 1999, Chapter 5. A collocation is an expression consisting of two or more words that correspond to some conventional way of saying things. Collocations are non-compositional phrases because their meaning cannot be understood [viz., composed] from its parts. E.g., strong tea, weapons of mass destruction, to make up, the rich and powerful, stiff breeze, broad daylight, white wine, ...

While a whole bunch of collocation detection strategies exist, from "normal" t-tests to calculating your n-grams' point-wise mutual information (PMI, see Church & Hanks (1990)) or via the Dice (1945) coefficient (see Smadja & McKeown (1994)), I prefer the likelihood ratio test by Dunning (1993) and as applied to non-compositional phrases by Lin (1993), because it is fairly robust for both excluding frequently co-occurring words and including infrequent collocations that are hard to detect. E.g., for bi-grams of a two word sequence $[1, 2]$ with counts $c$ for either word or the bi-gram, and a total number of words $N$ in your corpus, you get:

$$ \lambda = {-2}\ log \frac{B(c_{12}, c_1, p_2) B(c_2-c_{12},N-c_1,p_2)}{B(c_{12},c_1,p_{2|1})B(c_2-c_{12},N-c_1,p_{2|\neg1})} $$

Where $B(k, n, p) = \binom{n}{k} p^k (1-p)^{n -k}$ (note that the binomial term $n$ over $k$ can be dropped), $p_2 = \frac{c_2}{N}$, $p_{2|1} = \frac{c_{12}}{c_1}$, and $p_{2|\neg1} = \frac{c_2-c_{12}}{N-c_1}$. The $-2$ multiplier is in there to make $\lambda$ asymptotically $\chi^2$ distributed. As cutoff, I'd recommend $\lambda > 10.83$, which is the critical value for $\chi^2$ with 99.9% confidence at 1 d.f., but you might use lower cutoffs for better recall, depending on what you want to do with those collocations.

To extend this to higher n-grams, just re-run the test on the merged bi-grams to get tri-grams, a.s.f. (see Mikolov et. al. (2013), where they applied this strategy to a discounted PMI collocation detection approach). For more details, and an in-depth discussion, please refer to Manning & Schütze's excellent book chapter.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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