I'm building a Maximum Entropy Model to classify some text, based on paper "A Maximum Entropy Approach to Natural Language Processing" by Berger et.al. It's similar to POS tagging. Below is some reduced sample of the training data, in the form of LABEL::text:

["PLACE::Worthington Street", "COURSE_SN::F0XN9", "COURSE_NAME::Advanced Listening", "COURSE_SEQUENCE::1-2", "COURSE_COLLECTION::English 9A", "ROOM::VIPA"],
["PLACE::Ackton Tower", "NAME::Jimmy James", "COURSE_SN::98CC", "COURSE_NAME::Beginning Spanish", "COURSE_COLLECTION::Spanish Basics 4", "ROOM::201"]

Note that the incoming data will be segmented like above, and segmentation isn't a part of this task. The goal is to recognize 'field types' of each segment in a sequence. The order of which might be partially randomized. And each line may have only a selection of fields. The test data looked like this:

["Ackton Tower", "Jimmy James", "98CC", "Beginning Spanish", "Spanish Basics 4", "201"]

You can see that feature functions are somewhat straightforward to define. Basically, the word shape, its position, and the previous label played major roles. But I'm having trouble deciding what to include as context.

My current implementation uses (word_shape, last_label) as context. The feature function will only see this context, and nothing else. In other words, the feature function sees the first line of the sample data as:


I have to use word_shape because I need to be able to deal with potentially unseen text.

This leads to 2 problems:

  1. The likelihood calculation requires $\tilde{p}(x,y)$, which requires the context $x$ already exist in the training sample. How do I deal with unseen contexts? Suppose I have ("Xx Xx Xx", COURSE_SN), because it isn't seen in the sample, $\tilde{p}(x,y) = 0$. Then its likelihood will always be 0 for all labels. How do I decide a label for it?

  2. By localizing context to the actual words, I can maintain 100% accuracy with training data recognition even without feature functions. Say I choose the first word as the context, you can see that Jimmy is pretty much only used in NAME and nothing else. Therefore $\tilde{p}("Jimmy",y)$ is only defined when $y=NAME$. It'll be the only likelihood I'm going to get. But again, this doesn't mean I can deal with unseen data.

How do I select context and features in this task?


Gaussian priors helps with accuracy, but it doesn't answer my question at hand. What I'm really asking, is consider the following sample data:

NAME::Lily NAME::Kelly ADV::surprisingly VERB::knows

Say that I have 2 feature functions, one depended on whether the first letter is capital, and the other depends on whether the word ends with ~ly. How do I define context?

Under my original assumption, I define a rigid context for all segments. Everything will be using the same context word_shape. Then $\tilde{p}(x)$ will be:

'Xx~ly' = 2/4
'x~ly'  = 1/4
'x'     = 1/4

But instead, can I have contexts like this?

ctxA-'Xx'  = 2/4
ctxA-'x'   = 2/4
ctxB-'~ly' = 3/4

This way, each segment will produce multiple contexts. And they are treated independently as different $x$ in $\tilde{p}(x)$. This way I will be able to match far more content, because the complexity of context is reduced.

Note how in the first rigid case, $\sum \tilde{p}(x)$ equals 1, while in the second case, it will be much larger than 1.

It might be dumb to ask but is this the practical way?

  • $\begingroup$ what is word_shape? $\endgroup$
    – Aaron
    Jul 6 '14 at 13:22
  • $\begingroup$ @Aaron , Word Shape is something I learned from Stanford NLP course. It basically defines whether the letter is capital or not, and consequent letters in the same case are treated as a single character. You can see some information here: nlp.stanford.edu/nlp/javadoc/javanlp/edu/stanford/nlp/process/… . That's why I used 'Xx'. In other cases, you might define a word as '*ing' or '*ly' as word shape depending on what you are trying to do. It is like feature extraction. $\endgroup$
    – He Shiming
    Jul 6 '14 at 13:36

To answer your first question: You should set up a vocabulary before you train your model that covers all possible word_shapes. So if the maximum number of words in a segment is 7 then you would have $2^7$ possible word shapes. You can made an indicator vector like this $[0, 0, 0, 1, 0, 0 ...]$ where the one is in the ith position whenever the ith word shape is seen. This will make sure you have a label for all possible inputs.

To answer your second question: The maximum entropy model will apply some smoothing to make sure that there are no zero probabilities. "maximum entropy" means to make as little assumptions as possible so as to be able to deal with unseen data.

  • $\begingroup$ Thanks. I can enumerate all possible word shapes, however, I don't have training data for all of them. Shall I make up those? And what smoothing are you talking about here? I understand Naive Bayes model have +1 / laplace smoothing. But I'm not seeing such in maxent models. To me, it's just not possible to avoid zero probabilities. $\endgroup$
    – He Shiming
    Jul 6 '14 at 13:50
  • $\begingroup$ You don't have to make up new training data. The smoothing for the maxent model comes in the form of adding a prior. class.coursera.org/nlp/lecture/136 $\endgroup$
    – Aaron
    Jul 6 '14 at 14:14
  • $\begingroup$ Hi again. I researched and gaussian priors isn't the answer I'm looking for at this particular stage. My question is still regarding the selection of context. Could you see the 'update' section of the question and check if my new selection of context is correct? $\endgroup$
    – He Shiming
    Jul 7 '14 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.