Maximum entropy modelling

Entropy is the measure of the uncertainty of some information. The bigger the entropy is, the more uncertainty it has, and therefore more bits are needed to encode such information with binary encoding, for example.

It’s worth noticing that entropy is also the measure of how uniform a distribution is. This is not contradicting the above conclusion. The less uniform a distribution is, the less uncertain it is. In the extreme condition, {0, 1} -> {0, 1} mapping always outputs 1. 0 bit is needed.

Maximum entropy models study the conditional probability distribution p(y|x). Given a set of training examples (xi, yi), where xi are observations and yi are outputs, it tries to find a distribution p behind, by supervised learning.

A unique property of maximum entropy modelling is the use of features. Instead of computing p(y|x) directly from the examples, it maps the training data into a set of features. Each feature indicates the occurracnce of a certain pattern in the data, and a feature from (x, y) can be written as f(x, y). The motivation of features is easy to understand - instead of naive Bayes counting, features are a means to explore deeper the factors behind the observed data. As a natural consequence, we assume that the frequency of features in the training data is the same as the feature frequence in the model. This is the constraint equation for maximum entropy models.

Given the constraint, the model finds the distribution p(y|x) that gives the highest conditional entropy to corpus. The math deductions including the lambda exponential form of p(y|x) can be found from (berger, 96)