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)

Generative models and discriminative models - comparison

Given a set of samples (x1, y1) ... (xk, yk) , try to find a model behind them by supervised learning.

Both the generative and the discriminative models assume that there is an underlying probability distribution P(x, y) that generates the samples, however,

- The generative models try to find exactly the distribution P(x, y)
examples: Bayesian models
structural prediction: find a probabilistic model that simplifies P(x,y), usually by the chain rule / Bayes theorum / Independence assumption.

- The discriminative models find some distribution with low error rate on the training examples
examples: support vector machines
structural prediction: find a feature vector representation of the structures of Y.

Daume III (2006) gave an example where a generative model makes much worse error expection than a discriminative model (chap 3).