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 Maximum Entropy principles, in order to combine evidence from multiple sources (for example: trigrams and long distance triggers).

The Problem

State of the art language model was a trigram model - perplexity of 772 (prob of a word, based on the two word preceeding it). ==> Static model, not able to adapt to style and topic of the document

Adaptive model ==> changes estimates as a result of "seeing" some of the text

• process a large heterogeneous data source
• trained on data from one domain, can be used in another domain

Use trigger pairs: if a word sequence A is significantly correlated with another word sequence B (A->B) this is considered a trigger pair.

Given the document that was processed so far (h) and a word considered for the next position (w), there are many different estimates P(w|h), derived from the various triggers. How to combine them?

The Solution

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.

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 the exponential family defined by 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.

Trigger pairs are formulated as the empirical expectation of a 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}}$

Its associated constrain comes directly from the previous equation

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

To incorporate the previous static model the authors formulated constraint functions to fit the ML/ME paradigm as 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. This was done as a trigger pair $A\rightarrow A$.

Results

Trained on 5 million words of data:Wall Street Journal text, using a vocabulary comprised of the DARPA's 20k words. They tested the baseline trigram model, against their solutions. The formulations they came up to test were the ML/ME with the best 3 triggers for each word, and the ML/ME with the best 6 triggers for each word. For each of the latter methods they incorporated the static trigram model as a different experiment. The results can be seen in the following table:

ME is simple, intuitive and general. It can accomodate new factors, just reformulating them as constraints, and reutilize information from previous used models (as the static one).

The Generalized Iterative Scaling allows incremental adaptation, adding new constraints at any time, and guarantees to converge to a unique ME solution. 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 enconded self triggers do not take into account the number of times the word had previously occurred, which is significant for the problem. They leave as future work modeling the frequency of occurrences and distance of occurrence.