Maximum Entropy & SVMs in NLP (1996) › Maximum Entropy: A Principled Framework

Maximum Entropy models, also known as log-linear models or conditional exponential models, provided precisely this framework. The approach drew on information-theoretic principles: among all probability distributions that satisfy observed constraints, choose the one with maximum entropy, the one that makes the fewest assumptions beyond what the data requires. This principle, formalized by E. T. Jaynes in the 1950s, became a powerful tool for building probabilistic models from features and data.

The key insight was to express constraints through feature functions. A feature function $f_i(x, y)$ maps an input $x$ and output $y$ to a real number, typically 0 or 1, indicating whether some property holds. For part-of-speech tagging, features might include: $f_1(x, y)$ indicating whether the current word is "the" and the tag is determiner; $f_2(x, y)$ indicating whether the previous tag is noun and current tag is verb; $f_3(x, y)$ indicating whether the word ends in "-ing" and the tag is gerund; $f_4(x, y)$ indicating whether the word is capitalized and the tag is proper noun. By defining many such features, researchers could encode rich linguistic knowledge about what patterns indicated which tags.

Maximum Entropy models learned weights for these features, producing a conditional probability distribution:

where $\lambda_i$ are feature weights learned from data, $Z(x)$ is a normalization constant ensuring probabilities sum to one, and the exponential form ensures probabilities are non-negative. Features with positive weights increase the probability of outcomes where they're active; features with negative weights decrease it. The model automatically learned which features mattered and how much they mattered from training data.

Training Maximum Entropy models required solving an optimization problem: find feature weights that maximize the likelihood of the training data while satisfying the maximum entropy principle. This optimization, though computationally intensive, was tractable using algorithms like Improved Iterative Scaling or later, Limited-Memory BFGS. The learned weights reflected the importance of different features for the task. A feature like "current word is 'the' and tag is determiner" would receive a very high positive weight, since "the" is almost always a determiner. A feature like "word ends in '-ly' and tag is adverb" would also receive a positive weight, though smaller, since "-ly" words are often but not always adverbs.

The Maximum Entropy framework's power came from its flexibility. Researchers could define arbitrary features capturing any information they believed relevant, including lexical, morphological, syntactic, semantic, positional, and contextual information. The model didn't require independence assumptions or generative decompositions. Features could interact in complex ways through their combined effects on the probability distribution. This flexibility made Maximum Entropy models particularly attractive for NLP, where linguistic knowledge could be encoded naturally through feature design.

Adwait Ratnaparkhi's Maximum Entropy tagger, described in his 1996 thesis work, demonstrated the approach's effectiveness for part-of-speech tagging. The model used features capturing the current word, previous words, following words, word shapes, morphological properties, and tag context. It achieved tagging accuracy around 97%, competitive with or exceeding HMM-based taggers while offering greater flexibility and interpretability. The feature weights were interpretable. Researchers could examine which features received high weights and understand what patterns the model learned. This interpretability facilitated debugging and improvement, as researchers could identify which features helped and design new features addressing remaining errors.