A Maximum Entropy Approach to Natural Language Processing

Feature selection (determining a set of statistics that capture the behavior of a random process) and model selection (corralling those facts into an accurate predictive model). Maximum entropy gives a unified approach to both.

The uniform model: each phrase gets 1/5. Models like p(dans) = 1 assume more than we know.

Spread probability as evenly as the constraints allow: p(dans) = p(en) = 3/20, and p(à) = p(au cours de) = p(pendant) = 7/30. Adding a third fact (dans or à half the time) makes the most uniform model no longer obvious, which motivates a precise measure of uniformity.

Model all that is known and assume nothing about what is unknown: among models consistent with all the facts, choose the most uniform one.

Laplace’s Principle of Insufficient Reason: with no information to distinguish two events, treat them as equally likely. Jaynes: the maximum-entropy distribution agrees with everything known but carefully avoids assuming anything not known.

A binary-valued (indicator) function of a context \(x\) and output \(y\), e.g. \(f(x, y) = 1\) if \(y = \text{en}\) and April follows in, else 0. Any statistic of the sample can be expressed as the expected value of such a function.

An equation requiring the model’s expected value of a feature to equal its empirical expected value: \(p(f) = \tilde{p}(f)\), i.e. \(\sum_{x,y} \tilde{p}(x)\, p(y \mid x)\, f(x, y) = \sum_{x,y} \tilde{p}(x, y)\, f(x, y)\). (Berger et al. insist on not confusing features with constraints.)

By its conditional entropy \(H(p) = -\sum_{x,y} \tilde{p}(x)\, p(y \mid x) \log p(y \mid x)\), between 0 (no uncertainty) and \(\log |\mathcal{Y}|\) (uniform over outputs).

Given the set \(\mathcal{C}\) of models satisfying the constraints, choose \(p_* = \arg\max_{p \in \mathcal{C}} H(p)\). This model always exists and is unique.

No constraint: any model allowed. One constraint: a line (hyperplane) of models. Two consistent constraints may pin down a single model, or be inconsistent. Constraints from a training sample are consistent by construction, and in practice leave an infinite set of models, from which maximum entropy picks one.

An exponential (log-linear) model with one parameter per feature: \(p_\lambda(y \mid x) = \frac{1}{Z_\lambda(x)} \exp\big(\sum_i \lambda_i f_i(x, y)\big)\), with \(Z_\lambda(x) = \sum_y \exp\big(\sum_i \lambda_i f_i(x, y)\big)\).

Introduce a multiplier \(\lambda_i\) per constraint; maximizing the Lagrangian over \(p\) for fixed \(\lambda\) gives the exponential form \(p_\lambda\) and a dual function \(\Psi(\lambda)\). By the Kuhn–Tucker theorem the maximum entropy model is \(p_{\lambda^*}\) with \(\lambda^* = \arg\max_\lambda \Psi(\lambda)\).

The dual function \(\Psi(\lambda)\) is exactly the log-likelihood \(L_{\tilde{p}}(p_\lambda) = \sum_{x,y} \tilde{p}(x, y) \log p_\lambda(y \mid x)\) of the training data. So the maximum entropy model subject to the constraints is the exponential model that maximizes the likelihood of the training sample.

primal	maximum entropy: \(\arg\max_{p \in \mathcal{C}} H(p)\), constrained search over models
dual	maximum likelihood: \(\arg\max_\lambda \Psi(\lambda)\), unconstrained search over \(\lambda\)

Even if choosing the most uniform model isn’t compelling in itself, the same model is the one in its parametric family that best accounts for the training sample.

It is smooth and concave in \(\lambda\), so standard numerical methods work: coordinate-wise ascent (the Brown algorithm), gradient methods, or iterative scaling designed for maximum entropy.

Start with all \(\lambda_i = 0\). Repeatedly, for each feature, find the increment \(\Delta\lambda_i\) solving \(\sum_{x,y} \tilde{p}(x)\, p(y \mid x)\, f_i(x, y)\, e^{\Delta\lambda_i f^\#(x, y)} = \tilde{p}(f_i)\), where \(f^\#(x, y) = \sum_i f_i(x, y)\) is the number of active features, and update \(\lambda_i \leftarrow \lambda_i + \Delta\lambda_i\) until convergence.

\(\Delta\lambda_i = \frac{1}{M} \log \frac{\tilde{p}(f_i)}{p_\lambda(f_i)}\); otherwise the increment is found numerically (e.g. Newton’s method). Darroch and Ratcliff’s original Generalized Iterative Scaling additionally requires features to sum to 1.

The principle only combines constraints; it doesn’t say which facts matter. Candidate features can number in the millions, and with a finite sample many empirical expectations \(\tilde{p}(f)\) are unreliable, so only a subset of “active” features should be used.

Start with no features (the uniform model). At each step, for every candidate feature compute the gain in training log-likelihood from adding it, \(\Delta L(\mathcal{S}, f) = L(p_{\mathcal{S} \cup f}) - L(p_{\mathcal{S}})\), add the feature with the largest gain, re-fit, and repeat until a stopping criterion. Each added feature shrinks the set of allowed models.

It needs a full maximum entropy fit for every candidate at every step. Instead, assume adding \(f\) changes only its own new parameter \(\alpha\), keeping the other \(\lambda\)s fixed: the approximate gain is a one-dimensional optimization over \(\alpha\) (a line search, e.g. Newton’s method), at the cost of probably underestimating gains.

Cross-validation: grow the model on part of the data and monitor log-likelihood on held-out data. Training likelihood keeps rising, but when held-out likelihood stops increasing the model has begun fitting noise (overtraining), so stop.

IBM’s French-to-English statistical MT system: choose \(\hat{E} = \arg\max_E p(E)\, p(F \mid E)\) with a language model and a translation model (word fertilities, word translation probabilities and a distortion model) trained by EM on the Canadian Hansards.

It ignores English context when translating a word: it always gives in the same probabilities for dans, pendant… regardless of whether “a month’s time” or “the fiscal year 1992” follows, leading to errors like supérieures → “superior” instead of “greater” before “50%”.

From Hansard sentence pairs: compute the Viterbi alignment, and for each occurrence of in take the context \(x\) = the six surrounding English words and the output \(y\) = the aligned French word.

template	f(x, y) = 1 iff …
1	y = ◇ (no context)
2	y = ◇ and the next word is □
3	y = ◇ and the previous word is □
4	y = ◇ and □ is among the 3 previous words
5	y = ◇ and □ is among the 3 next words

◇ is a French translation, □ an English word. Template 1 alone reproduces the context-free distribution.

First a template-1 constraint for each translation seen, then context features chosen by approximate gain, e.g. that dans is more likely when speech is among the next three words; the run model showed a distinct “Hansard flavor” of parliamentary language.

Candide’s processing time was exponential in input length, so long French sentences had to be split. A rift is a position \(j\) where all French words to the left align to English words left of \(y_j\)’s English word and all to the right align to the right; splitting only at rifts means no English word must account for French words in two segments.

A maximum entropy model scored \(p(\text{rift} \mid x)\) at each position from a six-word window, POS tags and word classes; dynamic programming then chose segment boundaries with no segment longer than 10 words. Segments needn’t be semantically coherent, only translatable left to right.

To predict whether the English translation swaps the nouns and drops de (taux d’intérêt → interest rate) or translates word for word (conflit d’intérêt → conflict of interest), using features on the left noun, the right noun, or both; it beat a baseline that never swaps.

Some decisions depend on the pair: phrases ending in intérêt can go either way (conflit d’intérêt vs taux d’intérêt), and some, like taux d’inflation, can translate either way (inflation rate or rate of inflation).