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}}$

To incorporate the previous static model the authors formulated constraint functions to fit the ML/ME paradigm as: