4.9.2 Class-based N-grams

The class-based N-gram or cluster N-gram is a variant of the N-gram that uses information about word classes or clusters. Class-based N-grams can be useful for dealing with sparsity in the training data. Suppose for a flight reservation system we want to compute the probability of the bigram to Shanghai, but this bigram never occurs in the training set. Instead, our training data has to London, to Beijing, and to Denver. If we knew that these were all cities, and assuming Shanghai does appear in the training set in other contexts, we could predict the likelihood of a city following from.

There are many variants of cluster N-grams. The simplest one is sometimes known as IBM clustering, after its originators (Brown et al., 1992b). IBM clustering is a kind of hard clustering, in which each word can belong to only one class. The model estimates the conditional probability of a word $ w_i $ by multiplying two factors: the probability of the word's class $ c_i $ given the preceding classes (based on an N-gram of classes), and the probability of $ w_i $ given $ c_i $. Here is the IBM model in bigram form:

$$ P(w_{i}|w_{i-1})\approx P(c_{i}|,c_{i-1})\times P(w_{i}|c_{i}) $$

If we had a training corpus in which we knew the class for each word, the maximum likelihood estimate (MLE) of the probability of the word given the class and the probability of the class given the previous class could be computed as follows:

$$ P(w|c)~=~\frac{C(w)}{C(c)} $$

$$ P(c_{i}|c_{i-1})~=~\frac{C(c_{i-1}c_{i})}{\sum_{c}C(c_{i-1}c)} $$

Cluster N-grams are generally used in two ways. In dialog systems (Ch. 24), we often hand-design domain-specific word classes. Thus for an airline information system, we might use classes like CITYNAME, AIRLINE, DAYOFWEEK, or MONTH. In other cases, we can automatically induce the classes by clustering words in a corpus (Brown

et al., 1992b). Syntactic categories like part-of-speech tags don't seem to work well as classes (Niesler et al., 1998).

Whether automatically induced or hand-designed, cluster N-grams are generally mixed with regular word-based N-grams.