Lau et al HLT 1993

Citation

Raymond Lau, Ronald Rosenfeld and Salim Roukos. Adaptive Language Modeling Using the Maximum Entropy Principle. In Proceedings of the ARPA Human Language Technology Workshop, published as Human Language Technology, pages 108–113. Morgan Kaufmann, March 1993.

Online version

ACL WEB

Summary

In this paper the authors focus on the development of Language Models using the Maximum Entropy Principle, in order to combine evidence from multiple sources (for example: trigrams and long distance triggers).

The state-of-the-art language model, by the writing time of the paper, was a "static" trigram model, where the probability of the next word is decided by looking merely at the two words that precedes it. By definition, this model, after trained, always derives the same word for the same sequence of two words, not being able to "adapt" to different texts and contexts. In the present paper the authors developed an Adaptive Model, i.e., a model that changes estimates as a result of "seeing" some of the text. This new interpretation allows one to process large heterogeneous data sources (different writing styles and/or topics) and does not require to be trained in the same domain that it will be used for.

The way this domain variation is capture in the model is through the concept of "Trigger Pairs". If a word sequence $A$ is significantly correlated with another word sequence $B$, one can say that $A\rightarrow B$ this is considered a trigger pair. This phenomenon can be seen in the figure below, where the probability of the word "WINTER" is shown as a function of the number of previous occurrences of the word "SUMMER".

The adaptive model that was developed in this paper is a solution to combine several estimates $P(w|h)$ derived from several triggers, where $h$ is the section of the document processed so far and $w$ is the next word to predict. They used a Maximum Likelihood/Maximum Entropy Model (ML/ME), and reformulated triggers as constraints. Three types of constraints were considered: trigger pairs, ngrams, and self-triggers (where the trigger and the triggered word are the same, i.e., $A\rightarrow A$).

The authors compared the existent state-of-the-art static model with their new approach and obtained improvements of 27%. The author claim that, since they are using ME, their solution is simple, intuitive and general. It can accomodate new factors, just by reformulating them as constraints, and reutilize information from previous used models (as the static one). Additionally, the method used to solve the constraints, Generalized Iterative Scaling, which guarantees to converge to a unique ME solution, allows incremental adaptation, adding new constraints at any time. Although is very expensive and requires that the constraints to be consistent (which may not apply if the constraints are derived from other data than the training, or are externally imposed).

The way the authors encoded the previously mentioned self triggers do not take into account the number of times the word has previously occurred, which is significant for the problem, as one can see in the figure above. They leave as future work modeling the frequency of occurrences and distance of occurrence.

Brief Description of the Method

The Maximum Entropy Principle is a common technique used to combine several different knowledge sources in a combined estimate. This method reformulates the different estimates as constraints on the expectation of various functions to be satisfied by the combined estimante, ending up choosing, among the probability distributions that satisfy these constraints, the one with the highest entropy.

Formally, given a general event space $\{x\}$ , to derive a combined probability function $P(x)$, each constraint $i$ is associated with a constraint function $f_{i}(x)$ and a desired expectation $c_{i}$. The constraint is then written as:

$E_{p}f_{i}{\overset {\underset {\mathrm {def} }{}}{=}}\sum _{X}P(x)f_{i}(x)=c_{i}$

Given consistent constraints, a unique ME solution is guaranteed to exist, and to be of the form:

$P(x)=\prod _{i}\mu _{i}^{f_{i}(x)}$

where the $\mu _{i}$’s are some unknown constants, to be found. To search this exponential family for the $\mu _{i}$’s that will make $P(x)$ satisfy all the constraints, the authors used an iterative algorithm, Generalized Iterative Scaling, which is guaranteed to converge to the solution.

In the specific case of Language Modeling, the desired probability estimate is given by $P(h,w)$, being ${\hat {P}}(h,w)$ the empirical distribution of the training data. Taking the general equation for a contraint, and adapting it to this problem, one ends up with:

$\sum _{h}{\hat {P}}(h).\sum _{w}P(w|h).f_{i}(h,w)=c_{i}$

where $f_{i}(h,w)$ is any constraint function and $c_{i}$ its desired expectation. The only missing piece is the constraint functions for the three types of triggers. So, for a general trigger pair $A\rightarrow B$, the authors define the constraint function $f_{A\rightarrow B}$ as:

$f_{A\rightarrow B}(h,w)={\begin{cases}1,&{\mbox{if }}A\in h,w=B\\0,&{\mbox{otherwise}}\end{cases}}$

To incorporate the previous static model, the authors formulated unigram, bigram and trigram constraint functions to fit the ML/ME paradigm. For instance, for bigrams:

$f_{w_{1},w_{2}}(h,w)={\begin{cases}1,&{\mbox{if }}h{\mbox{ ends in }}w_{1}{\mbox{ and }}w=w_{2}\\0,&{\mbox{otherwise}}\end{cases}}$

Similarly, the authors integrated the "bursty" nature of language, i.e., the fact that once an infrequent word occurs in a document, the probability of reoccurrence is significantly elevated, simply as a trigger pair $A\rightarrow A$.

Experimental Results

The baseline static trigram model was tested against the authors' adaptive solutions. Four formulations were used: the ML/ME with the best 3 triggers for each word (with and without the incorporation of the trigram model), and the ML/ME with the best 6 triggers for each word (also with and without the incorporation of the trigram model). For each of the latter methods they incorporated the static trigram model as a different experiment. Each model was trained on 5 million words of Wall Street Journal text, using a vocabulary comprised of the DARPA's 20k words. The results can be seen in the following table:

As one can see there are improvements when the number of triggers considered for each word is increased. There are also improvements when the adaptive model incorporates the static trigram model. Although, the authors do not discuss significance of these results and, since there is no data for more triggers considered for each word, one cannot predict how does this variation affect the results.

Related Papers

The authors show the importance of self triggers, stating that they are responsible for a large part of the reduction in perplexity, and proved to be robust (maintain the correlations for different domains) in Rosenfield and Huang, 1992.