6.6.4 Advanced: Learning in logistic regression

In linear regression, learning consisted of choosing the weights w which minimized the sum-squared error on the training set. In logistic regression, by contrast, we generally use conditional maximum likelihood estimation. What this means is that we choose the parameters w which makes the probability of the observed y values in the training data to be the highest, given the observations x. In other words, for an individual training observation x, we want to choose the weights as follows:

$$ \hat{w}=\underset{w}{\argmax}P(y^{(i)}|x^{(i)}) $$

And we'd like to choose the optimal weights for the entire training set:

$$ \hat{w}=\underset{w}{\argmax}\prod_{i}P(y^{(i)}|x^{(i)}) $$

We generally work with the log likelihood:

$$ \hat{w}=\underset{w}{\argmax}\sum_{i}\log P(y^{(i)}|x^{(i)}) $$

So, more explicitly:

$$ \hat{w}=\underset{w}{\operatorname{a r g m a x}}\sum_{i}\log\left\{\begin{array}{l l}{P(y^{(i)}=1|x^{(i)}))}&{\mathrm{f o r~}y^{(i)}=1}\\ {P(y^{(i)}=0|x^{(i)}))}&{\mathrm{f o r~}y^{(i)}=0}\end{array}\right. $$

This equation is unwieldy, and so we usually apply a convenient representational trick. Note that if y = 0 the first term goes away, while if y = 1 the second term goes away:

$$ \hat{w}=\underset{w}{\operatorname{a r g m a x}}\sum_{i}y^{(i)}\log P(y^{(i)}=1|x^{(i)}))+(1-y^{(i)})\log P(y^{(i)}=0|x^{(i)}) $$

Now if we substitute in (6.66) and (6.68), we get:

$$ \hat{w}=\underset{w}{\operatorname{a r g m a x}}\sum_{i}y^{(i)}\log\frac{1}{1+e^{-w\cdot f}}+(1-y^{(i)})\log\frac{e^{-w\cdot f}}{1+e^{-w\cdot f}} $$

Finding the weights which result in the maximum log-likelihood according to (6.76) is a problem in the field known as convex optimization. Among the most commonly used algorithms are quasi-Newton methods like L-BFGS, as well as gradient ascent, conjugate gradient, and various iterative scaling algorithms (Darroch and Ratliff, 1972; Della Pietra et al., 1997; Malouf, 2002). These learning algorithms are available in the various MaxEnt modeling toolkits but are too complex to define here; interested readers should see the machine learning textbooks suggested at the end of the chapter.

6.7 MAXIMUM ENTROPY MODELING

We showed above how logistic regression can be used to classify an observation into one of two classes. But most of the time the kinds of classification problems that come up in language processing involve larger numbers of classes (such as the set of part-of-speech classes). Logistic regression can also be defined for such functions with many discrete values. In such cases it is called multinomial logistic regression. As we mentioned above, multinomial logistic regression is called MaxEnt in speech and language processing (see Sec. 6.7.1 on the intuition behind the name 'maximum entropy').

The equations for computing the class probabilities for a MaxEnt classifier are a generalization of Eqs. 6.63-6.64 above. Let's assume that the target value y is a random variable which can take on C different values corresponding to the classes $ c_1, c_2, ..., c_C $.

We said earlier in this chapter that in a MaxEnt model we estimate the probability that y is a particular class c as:

(6.77)

$$ p(c|x)=\frac{1}{Z}\exp\sum_{i}w_{i}f_{i} $$

Let's now add some details to this schematic equation. First we'll flesh out the normalization factor Z, specify the number of features as N, and make the value of the weight dependent on the class c. The final equation is:

$$ \begin{array}{c} p(c|x)~=~\frac{\exp\left(\displaystyle\sum_{i=0}^{N} w_{c|i}f_{i}\right)}{\displaystyle\sum_{c^{\prime}\in C}\exp\left(\displaystyle\sum_{i=0}^{N} w_{c^{\prime}i}f_{i}\right)}\end{array} $$

Note that the normalization factor Z is just used to make the exponential into a true probability;

$$ Z=\sum_{C}p(c|x)=\sum_{c^{\prime}\in C}\exp\left(\sum_{i=0}^{N}w_{c^{\prime}i}f_{i}\right) $$

We need to make one more change to see the final MaxEnt equation. So far we've been assuming that the features $f_i$ are real-valued. It is more common in speech and language processing, however, to use binary-valued features. A feature that only takes on the values 0 and 1 is also called an indicator function. In general, the features we use are indicator functions of some property of the observation and the class we are considering assigning. Thus in MaxEnt, instead of the notation $f_i$, we will often use the notation $f_i(c,x)$, meaning a feature $i$ for a particular class $c$ for a given observation $x$.

The final equation for computing the probability of y being of class c given x in MaxEnt is:

$$ \begin{array}{c} p(c|x)~=~\frac{\exp\left(\displaystyle\sum_{i=0}^{N} w_{c i}f_{i}(c,x)\right)}{\displaystyle\sum_{c^{\prime}\in C}\exp\left(\displaystyle\sum_{i=0}^{N} w_{c^{\prime}i}f_{i}(c^{\prime},x)\right)}\end{array} $$

To get a clearer intuition of this use of binary features, let's look at some sample features for the task of part-of-speech tagging. Suppose we are assigning a part-of-speech tag to the word race in (6.81), repeated from (??):

Secretariat/NNP is/BEZ expected/VBN to/TO race/?? tomorrow/

Again, for now we're just doing classification, not sequence classification, so let's consider just this single word. We'll discuss in Sec. 6.8 how to perform tagging for a whole sequence of words.

We would like to know whether to assign the class VB to race (or instead assign some other class like NN). One useful feature, we'll call it $ f_{1} $, would be the fact that the current word is race. We can thus add a binary feature which is true if this is the case:

$$ f_{1}(c,x)\;=\;\left\{\begin{array}{l l}{1\;\mathrm{i f~}\;{w o r d}_{i}={\mathrm{“r a c e~”}}\;\&\;c=\mathrm{N N}}\\ {0\;\mathrm{o t h e r w i s e}}\\ \end{array}\right. $$

Another feature would be whether the previous word has the tag TO:

$$ f_{2}(c,x)\;=\;\left\{\begin{array}{l}{{1\;\mathrm{i f}\ t_{i-1}=\mathrm{T O\ \&\}\ c=\mathrm{V B}}}}\\ {{0\;\mathrm{o t h e r w i s e}}}\end{array}\right. $$

Two more part-of-speech tagging features might focus on aspects of a word's spelling and case:

$$ f_{3}(c,x)\;=\;\left\{\begin{array}{l}{{1\;\mathrm{i f~s u f f i x}(w o r d_{i})=``\mathrm{i n g}~\&~\;c=\mathrm{V B G}}}\\ {{0\;\mathrm{o t h e r w i s e}}}\end{array}\right. $$

$$ f_{4}(c,x)\;=\;\left\{\begin{array}{l}{{1~\mathrm{{\scriptsize~i f}~i s\_{l} o w e r\_{c} a s e}(w o r d_{i})~\&~c=V B}}\\ {{0~\mathrm{{\scriptsize~o t h e r w i s e}}}}\\ \end{array}\right. $$

Since each feature is dependent on both a property of the observation and the class being labeled, we would need to have separate feature for, e.g., the link between race and VB, or the link between a previous TO and NN:

$$ f_{5}(c,x)\;=\;\left\{\begin{array}{l}{{1~\mathrm{i f}~\mathit{w o r d}_{i}={r a c e}}\\ {{0~\mathrm{o t h e r w i s e}}}\end{array}\right.\&\;\mathit{c}=\mathrm{V B} $$

$$ f_{6}(c,x)\;=\;\left\{\begin{array}{l}{{1~\mathrm{i f}~\ensuremath{t_{i-1}}=\mathrm{T O}~\&~\ensuremath{c=\mathrm{N N}}}}\\ {{0~\mathrm{o t h e r w i s e}}}\end{array}\right. $$

Each of these features has a corresponding weight. Thus the weight $ w_1(c,x) $ would indicate how strong a cue the word race is for the tag VB, the weight $ w_2(c,x) $ would indicate how strong a cue the previous tag TO is for the current word being a VB, and so on.

Let's assume that the feature weights for the two classes VB and VN are as shown in Fig. 6.19. Let's call the current input observation (where the current word is race) x. We can now compute $ P(NN|x) $ and $ P(VB|x) $, using Eq. 6.80:

$$ \begin{aligned}P(NN|x)&=\frac{e^{.8}e^{-1.3}}{e^{.8}e^{-1.3}+e^{.8}e^{.01}e^{.1}}=.20\\P(VB|x)&=\frac{e^{.8}e^{.01}e^{.1}}{e^{.8}e^{-1.3}+e^{.8}e^{.01}e^{.1}}=.80\end{aligned} $$

Notice that when we use MaxEnt to perform classification, MaxEnt naturally gives us a probability distribution over the classes. If we want to do a hard-classification and choose the single-best class, we can choose the class that has the highest probability, i.e.:

$$ \hat{c}=\underset{c\in C}{\operatorname{argmax}}P(c|x) $$

Classification in MaxEnt is thus a generalization of classification in (boolean) logistic regression. In boolean logistic regression, classification involves building one linear expression which separates the observations in the class from the observations not in the class. Classification in MaxEnt, by contrast, involves building a separate linear expression for each of C classes.

But as we'll see later in Sec. 6.8, we generally don't use MaxEnt for hard classification. Usually we want to use MaxEnt as part of sequence classification, where we want not the best single class for one unit, but the best total sequence. For this task, it's useful to exploit the entire probability distribution for each individual unit, to help find the best sequence. Indeed even in many non-sequence applications a probability distribution over the classes is more useful than a hard choice.

The features we have described so far express a single binary property of an observation. But it is often useful to create more complex features that express combinations of properties of a word. Some kinds of machine learning models, like Support Vector Machines (SVMs), can automatically model the interactions between primitive properties, but in MaxEnt any kind of complex feature has to be defined by hand. For example a word starting with a capital letter (like the word Day) is more likely to be a proper noun (NNP) than a common noun (for example in the expression United Nations Day). But a word which is capitalized but which occurs at the beginning of the sentence (the previous word is ), as in Day after day..., is not more likely to be a proper noun. Even if each of these properties were already a primitive feature, MaxEnt would not model their combination, so this boolean combination of properties would need to be encoded as a feature by hand: