6.7.1 Why do we call it Maximum Entropy?

Why do we refer to multinomial logistic regression models as MaxEnt or Maximum Entropy models? Let's give the intuition of this interpretation in the context of part-of-speech tagging. Suppose we want to assign a tag to the word zzfish (a word we made up for this example). What is the probabilistic tagging model (the distribution of part-of-speech tags across words) that makes the fewest assumptions, imposing no constraints at all? Intuitively it would be the equiprobable distribution:

| NN | JJ | NNS | VB | NNP | IN | MD | UH | SYM | VBG | POS | PRP | CC | CD | ... |

| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |

| $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | $ \frac{1}{45} $ | ... |

Now suppose we had some training data labeled with part-of-speech tags, and from this data we learned only one fact: the set of possible tags for zzfish are NN, JJ, NNS, and VB (so zzfish is a word something like fish, but which can also be an adjective). What is the tagging model which relies on this constraint, but makes no further assumptions at all? Since one of these must be the correct tag, we know that

$$ P(NN)+P(JJ)+P(NNS)+P(VB)=1 $$

Since we have no further information, a model which makes no further assumptions beyond what we know would simply assign equal probability to each of these words:

| NN | JJ | NNS | VB | NNP | IN | MD | UH | SYM | VBG | POS | PRP | CC | CD | ... |

| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |

| $ \frac{1}{4} $ | $ \frac{1}{4} $ | $ \frac{1}{4} $ | $ \frac{1}{4} $ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ... |

In the first example, where we wanted an uninformed distribution over 45 parts-of-speech, and in this case, where we wanted an uninformed distribution over 4 parts-of-speech, it turns out that of all possible distributions, the equiprobable distribution has the \textit{maximum entropy}. Recall from Sec. \ref{sec:دعا} that the entropy of the distribution of a random variable x is computed as:

$$ H(x)=-\sum_{x}P(x)\log_{2}P(x) $$

An equiprobable distribution in which all values of the random variable have the same probability has a higher entropy than one in which there is more information. Thus of all distributions over four variables the distribution $ \{\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\} $ has the maximum entropy. (To have an intuition for this, use Eq. 6.93 to compute the entropy for a few other distributions such as the distribution $ \{\frac{1}{4},\frac{1}{2},\frac{1}{8},\frac{1}{8}\} $, and make sure they are all lower than the equiprobable distribution.)

The intuition of MaxEnt modeling is that the probabilistic model we are building should follow whatever constraints we impose on it, but beyond these constraints it should follow Occam's Razor, i.e., make the fewest possible assumptions.

Let's add some more constraints into our tagging example. Suppose we looked at our tagged training data and noticed that 8 times out of 10, zzfish was tagged as some sort of common noun, either NN or NNS. We can think of this as specifying the feature 'word is zzfish' and $ t_i = NN $ or $ t_i = NNS' $. We might now want to modify our distribution so that we give $ \frac{8}{10} $ of our probability mass to nouns, i.e. now we have 2 constraints

$$ P(NN)+P(JJ)+P(NNS)+P(VB)=1 $$

$$ P(\mathrm{word}\mathrm{is}\mathrm{zzfish}\mathrm{and}t_{i}=\mathrm{NN}\mathrm{or}t_{i}=\mathrm{NNS})=\frac{8}{10} $$

but make no further assumptions (keep JJ and VB equiprobable, and NN and NNS equiprobable).

| NN | JJ | NNS | VB | NNP | ... |

| --- | --- | --- | --- | --- | --- |

| $ \frac{4}{10} $ | $ \frac{1}{10} $ | $ \frac{4}{10} $ | $ \frac{1}{10} $ | 0 | ... |

Now suppose we don't have any more information about zzfish. But we notice in the training data that for all English words (not just zzfish) verbs (VB) occur as 1 word in 20. We can now add this constraint (corresponding to the feature $ t_i = VB $):

$$ P(NN)+P(JJ)+P(NNS)+P(VB)=1 $$

$$ P(\mathrm{word}\text{is}\mathrm{zzfish}\text{and}t_{i}=\mathrm{NN}\text{or}t_{i}=\mathrm{NNS})=\frac{8}{10} $$

$$ P(VB)=\frac{1}{20} $$

The resulting maximum entropy distribution is now as follows:

| NN | JJ | NNS | VB |

| --- | --- | --- | --- |

| $ \frac{4}{10} $ | $ \frac{3}{20} $ | $ \frac{4}{10} $ | $ \frac{1}{20} $ |

In summary, the intuition of maximum entropy is to build a distribution by continuously adding features. Each feature is an indicator function, which picks out a subset of the training observations. For each feature we add a constraint on our total distribution, specifying that our distribution for this subset should match the empirical distribution we saw in our training data. We then choose the maximum entropy distribution which otherwise accords with these constraints. Berger et al. (1996) pose the optimization problem of finding this distribution as follows:

“To select a model from a set $C$ of allowed probability distributions, choose the model $p^* \in C$ with maximum entropy $H(p)$”:

$$ p^{*}=\underset{p\in C}{\operatorname{argmax}}H(p) $$

Now we come to the important conclusion. Berger et al. (1996) show that the solution to this optimization problem turns out to be exactly the probability distribution of a multinomial logistic regression model whose weights W maximize the likelihood of the training data! Thus the exponential model for multinomial logistic regression, when trained according to the maximum likelihood criterion, also finds the maximum entropy distribution subject to the constraints from the feature functions.

6.8 MAXIMUM ENTROPY MARKOV MODELS

We began our discussion of MaxEnt by pointing out that the basic MaxEnt model is not in itself a classifier for sequences. Instead, it is used to classify a single observation into one of a set of discrete classes, as in text classification (choosing between possible authors of an anonymous text, or classifying an email as spam), or tasks like deciding whether a period marks the end of a sentence.

We turn in this section to the Maximum Entropy Markov Model or MEMM, which is an augmentation of the basic MaxEnt classifier so that it can be applied to assign a class to each element in a sequence, just as we do with HMMs. Why would we want a sequence classifier built on MaxEnt? How might such a classifier be better than an HMM?

Consider the HMM approach to part-of-speech tagging. The HMM tagging model is based on probabilities of the form $ P(\text{tag}|\text{tag}) $ and $ P(\text{word}|\text{tag}) $. That means that if we want to include some source of knowledge into the tagging process, we must find a way to encode the knowledge into one of these two probabilities. But many knowledge sources are hard to fit into these models. For example, we saw in Sec. ?? that for tagging unknown words, useful features include capitalization, the presence of hyphens, word endings, and so on. There is no easy way to fit probabilities like $ P(\text{capitalization}|\text{tag}) $, $ P(\text{hyphen}|\text{tag}) $, $ P(\text{suffix}|\text{tag}) $, and so on into an HMM-style model.

We gave the initial part of this intuition in the previous section, when we discussed applying MaxEnt to part-of-speech tagging. Part-of-speech tagging is definitely a sequence labeling task, but we only discussed assigning a part-of-speech tag to a single word.

How can we take this single local classifier and turn it into a general sequence classifier? When classifying each word we can rely on features from the current word, features from surrounding words, as well as the output of the classifier from previous words. For example the simplest method is to run our local classifier left-to-right, first making a hard classification of the first word in the sentence, then the second word, and so on. When classifying each word, we can rely on the output of the classifier from the previous word as a feature. For example, we saw in tagging the word race that a useful feature was the tag of the previous word; a previous TO is a good indication that race is a VB, whereas a previous DT is a good indication that race is a NN. Such a strict left-to-right sliding window approach has been shown to yield surprisingly good results across a wide range of applications.

While it is possible to perform part-of-speech tagging in this way, this simple left-to-right classifier has an important flaw: it makes a hard decision on each word before moving on to the next word. This means that the classifier is unable to use information from later words to inform its decision early on. Recall that in Hidden Markov Models, by contrast, we didn't have to make a hard decision at each word; we used Viterbi decoding to find the sequence of part-of-speech tags which was optimal for the whole sentence.

The Maximum Entropy Markov Model (or MEMM) allows us to achieve this same advantage, by mating the Viterbi algorithm with MaxEnt. Let's see how it works, again looking at part-of-speech tagging. It is easiest to understand an MEMM when comparing it to an HMM. Remember that in using an HMM to model the most probable part-of-speech tag sequence we rely on Bayes rule, computing $ P(W|T)P(W) $ instead of directly computing $ P(T|W) $:

$$ \begin{aligned}\hat{T}&=\underset{T}{\argmax}P(T|W)\\&=\underset{T}{\argmax}P(W|T)P(T)\end{aligned} $$

$$ =\underset{T}{\operatorname{a r g m a x}}\prod_{i}P(w o r d_{i}|t a g_{i})\prod_{i}P(t a g_{i}|t a g_{i-1}) $$

That is, an HMM as we've described it is a generative model that optimizes the likelihood $ P(W|T) $, and we estimate the posterior by combining the likelihood and the prior $ P(T) $.

In an MEMM, by contrast, we compute the posterior $ P(T|W) $ directly. Because we train the model directly to discriminate among the possible tag sequences, we call an MEMM a discriminative model rather than a generative model. In an MEMM, we break down the probabilities as follows:

$$ \begin{aligned}\hat{T}&=\underset{T}{\operatorname{argmax}}P(T|W)\\&=\underset{T}{\operatorname{argmax}}\prod_{i}P(tag_{i}|word_{i},tag_{i-1})\end{aligned} $$

Thus in an MEMM instead of having a separate model for likelihoods and priors, we train a single probabilistic model to estimate $ P(tag_i|word_i,tag_{i-1}) $. We will use MaxEnt for this last piece, estimating the probability of each local tag given the previous tag, the observed word, and, as we will see, any other features we want to include.

We can see the HMM versus MEMM intuitions of the POS tagging task in Fig. 6.20, which repeats the HMM model of Fig. ??a from Ch. 5, and adds a new model for the MEMM. Note that the HMM model includes distinct probability estimates for each transition and observation, while the MEMM gives one probability estimate per hidden state, which is the probability of the next tag given the previous tag and the observation.

Fig. 6.21 emphasizes another advantage of MEMMs over HMMs not shown in Fig. 6.20: unlike the HMM, the MEMM can condition on any useful feature of the input observation. In the HMM this wasn't possible because the HMM is likelihood-based, hence would have needed to compute the likelihood of each feature of the observation.

More formally, in the HMM we compute the probability of the state sequence given the observations as:

$$ P(Q|O)=\prod_{i=1}^{n}P(o_{i}|q_{i})\times\prod_{i=1}^{n}P(q_{i}|q_{i-1}) $$

In the MEMM, we compute the probability of the state sequence given the observations as:

$$ P(Q|O)=\prod_{i=1}^{n}P(q_{i}|q_{i-1},o_{i}) $$

In practice, however, an MEMM can also condition on many more features than the HMM, so in general we condition the right-hand side on many more factors.

To estimate the individual probability of a transition from a state $ q' $ to a state q producing an observation o, we build a MaxEnt model as follows:

$$ P(q|q^{\prime},o)=\frac{1}{Z(o,q^{\prime})}\exp\left(\sum_{i}w_{i}f_{i}(o,q)\right) $$