17
$\begingroup$

In two popular language identification libraries, Compact Language Detector 2 for C++ and language detector for java, both of them used (character based) n-grams to extract text features. Why is a bag-of-words (single word/dictionary) not used, and what is the advantage and disadvantage of bag-of-words and n-grams?

Also, what are some other uses of n-grams model in text classification?

Oh oops. Seems like there is a similar question here: Regarding using bigram (N-gram) model to build feature vector for text document

But can someone give a more comprehensive answer? Which is better in the case of language identification?

(Hopefully I got the meaning of n-grams and bag-of-words correct, haha, if not please help me with that.)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
25
$\begingroup$

I think the most detailed answers can be found in Mehryar Mohri's extensive work on the topic. Here's a link to one of his lecture slides on the topic: https://web.archive.org/web/20151125061427/http://www.cims.nyu.edu/~mohri/amls/lecture_3.pdf

The problem of language detection is that human language (words) have structure. For example, in English, it's very common for the letter 'u' to follow the letter 'q,' while this is not the case in transliterated Arabic. n-grams work by capturing this structure. Thus, certain combinations of letters are more likely in some languages than others. This is the basis of n-gram classification.

Bag-of-words, on the other hand, depends on searching through a large dictionary and essentially doing template matching. There are two main drawbacks here: 1) each language would have to have an extensive dictionary of words on file, which would take a relatively long time to search through, and 2) bag-of-words will fail if none of the words in the training set are included in the testing set.

Assuming that you are using bigrams (n=2) and there are 26 letters in your alphabet, then there are only 26^2 = 676 possible bigrams for that alphabet, many of which will never occur. Therefore, the "profile" (to use language detector's words) for each language needs a very small database. A bag-of-words classifier, on-the-other-hand would need a full dictionary for EACH language in order to guarantee that a language could be detected based on whichever sentence it was given.

So in short - each language profile can be quickly generated with a relatively small feature space. Interestingly, n-grams only work because letters are not drawn iid in a language - this is explicitly leverage.

Note: the general equation for the number of n-grams for words is l^n where l is the number of letters in the alphabet.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I guess that for some close languages, using lists of words in addition to n-grams would help . I have seen, sometimes, norwegian text claasified as danish. I doubt n-grams is a good way to distinguish those two languages. $\endgroup$
    – kjetil b halvorsen ♦
    Apr 5, 2015 at 12:37
  • $\begingroup$ Thank you for your detailed answer. However I have a few questions regarding this, firstly could you explain 'bag-of-words will fail if none of the words in the training set are included in the testing set'? and secondly, why is CLD2 using 4-grams, which will result in 456976 entries for the English language, when using a dictionary method may bring about half the size of the profile ( oxforddictionaries.com/words/… )? $\endgroup$
    – dennis97519
    Apr 5, 2015 at 13:12
  • 1
    $\begingroup$ @dennis97519 re: "bag-of-words..." Suppose your dictionary only consists of the words {"dog","cat","turtle","animal"} for English and {"perro","gato","tortuga","animal"} for Spanish. Your dictionary would not be able to classify the following sentence: "A donkey is an animal" because the word "animal" appears in both dictionaries, but none of the other words exist. This is an extreme example. Re 4-grams: 1) Remember that you need a dictionary for each language, 2) n-grams tend to be sparse (faster search), and 3) as Dougal said, they can be represented in just a few bytes. $\endgroup$
    – justanotherbrain
    Apr 6, 2015 at 3:22
  • 1
    $\begingroup$ @loretoparisi - There are two trade-offs: The first is between model complexity (large N = more complex) and generalization error (how well you do on some test set) - you don't want to overfit. The second trade-off is computational complexity. The memory complexity grows exponentially with N. Training is typically linear with the number of words in the text, so having a very long text isn't usually a problem. That said, large text often means more words in your dictionary D. So again, memory complexity is O(D^N). In practice, it's usually best to use as large an N as computationally possible. $\endgroup$
    – justanotherbrain
    Nov 29, 2016 at 14:43
  • 1
    $\begingroup$ @loretoparisi - Following up on that, as mentioned before, N-grams tend to be sparse, but this isn't always true. If it is sparse for your particular text, then cross validating with different N is best approach to find optimal N (again, with computational constraints). $\endgroup$
    – justanotherbrain
    Nov 29, 2016 at 14:46
4
$\begingroup$

Letter N-grams are used instead of words for several reasons:

1) The list of words needed for a given language is quite large, perhaps 100,000 if you consider fast, faster, fastest, fasted, fasts, fasting, ... as all different words. For 80 languages, you need about 80x as many words,taking up a lot of space -- 50+ megabytes.

2) The number of letter trigrams for a 26-letter alphabet is 26**3 or about 17,000 and for quadgrams (N=4) about 450,000 covering ALL languages using that alphabet. Similar but somewhat larger numbers for N-grams in larger alphabets of 30-100 characters. For the CJK languages with 4000+ letters in the Han script, unigrams (N=1) are sufficient. For some Unicode scripts, there is just one language per script (Greek, Armenian), so no letter combinations are needed (so-called nil-grams N=0)

3) With words, you have no information at all when given a word not in the dictionary, while with letter N-grams you often have at least a few useful letter combinations within that word.

CLD2 uses quadgrams for most Unicode scripts (alphabets) including Latin, Cyrillic, and Arabic, unigrams for the CJK scripts, nilgrams for other scripts, and also includes a limited number of quite-distinctive and fairly common complete words and pairs of words for distinguishing within difficult groups of statistically-similar languages, such as Indonesian and Malay. Letter bigrams and trigrams are perhaps useful for distinguishing among a tiny number of languages (about eight, see https://docs.google.com/document/d/1NtErs467Ub4yklEfK0C9AYef06G_1_9NHL5dPuKIH7k/edit), but are useless for distinguishing dozens of languages. Thus, CLD2 uses quadgrams, associating with each letter combination the top three most likely languages using that combination. This allows covering 80 languages with about 1.5 MB of tables and 160 languages in more detail with about 5MB of tables.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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