Must an MEMM examine only the current word?

No. Features can include surrounding or other observed context.

Is greedy decoding always optimal?

No. The worked example shows a lower-probability first choice leading to the best full sequence.

Does label bias mean demographic bias?

No. Here it names a technical consequence of local normalization, although deployed models may separately have demographic performance disparities.

AI Glossary / Mathematics and optimization / Intermediate

Maximum-entropy Markov model

Definition

A maximum-entropy Markov model, or MEMM, is a conditional sequence-labeling model that uses a log-linear classifier to predict each label from the preceding label and observed features. It combines a Markov dependency between labels with flexible information from the input. The probability of a complete label sequence is the product of locally normalized conditional transition probabilities.

What it means

A sequence labeler might assign a tag to each word in a sentence or a category to each segment of a record. Adjacent labels often depend on one another, while the observed input provides additional clues. An MEMM uses both kinds of information.
Maximum entropy refers to the log-linear modeling framework behind the local classifiers. It does not mean predictions are deliberately made as uncertain as possible after training. The model learns weights that distinguish labels from examples. Because it directly models labels conditional on observations, it need not separately specify a probability model for how every input feature was generated.

How it works

At position t, compute a score for each possible next label using weighted features of that label, the preceding label, and the observed input. Exponentiate the scores and divide by their sum over allowed next labels. This local softmax produces p(y_t|y_(t−1),x).
For a fixed starting state, multiply these probabilities along a candidate label sequence. Training with fully observed labels fits the local conditional decisions, often with regularization. Decoding can use dynamic programming to find the highest-probability complete sequence rather than greedily choosing one label at a time. Input features may include neighboring or more distant observed words; the Markov restriction concerns the modeled label history, not necessarily the observation window.

Three practical examples

A document-processing system can label tokens as parts of names, dates, or ordinary text using both word features and neighboring label transitions.
A text-analysis pipeline can assign part-of-speech tags while combining spelling clues with previous-tag information.
A record-segmentation task can label consecutive fields using formatting features and a permitted sequence of field types.

Think of it this way

Think of a series of classification decisions in which each decision sees the input clues and the previous category. A route planner then compares complete chains of decisions. The analogy is limited because an MEMM assigns normalized probabilities using learned weights; it does not reason about the text like a human reviewer, and its local normalizations impose specific restrictions.

Worked example

Consider an original two-token example with labels N for name and O for other. At the first token, suppose the start-state scores are log 3 for N and log 2 for O. Softmax converts these to probabilities 3/(3+2)=0.6 and 2/(3+2)=0.4.
At the second token, suppose that after N the two scores are equal, giving p(N|N,x)=0.5 and p(O|N,x)=0.5. After O, suppose the scores are log 9 for N and zero for O, giving probabilities 0.9 and 0.1.
The complete sequence probabilities are NN: 0.6×0.5=0.30; NO: 0.6×0.5=0.30; ON: 0.4×0.9=0.36; and OO: 0.4×0.1=0.04. They sum to one. A greedy first decision chooses N and can finish with probability only 0.30, while sequence decoding finds ON with probability 0.36.
Notice that N remains the more probable first label marginally: 0.30+0.30=0.60. The first label of the most probable complete sequence need not equal the individually most probable first label. These are different inference questions.
A separate miniature example illustrates local normalization. If a state permits only one outgoing label, that transition has probability exp(s)/exp(s)=1 for any finite score s. Lowering the score because an observation seems implausible cannot reduce that outgoing probability. This mechanism helps explain label bias; it is a structural issue, not simply an error caused by choosing greedy decoding.

Illustrative case study

In a fictional forms-processing team, a developer uses an MEMM to label two adjacent text fields. The team first checks complete path probabilities on the example above, then tests whether the decoder actually returns the best path. It separately reviews state structures that allow only one continuation. This is an illustrative evaluation exercise; it does not claim a particular extraction accuracy or demonstrate that a model understands the underlying document.

Common misconceptions and mistakes

The model should not be confused with a hidden Markov model, which conventionally specifies a joint generative distribution over states and observations. Nor is an MEMM identical to a linear-chain conditional random field. The latter normalizes over complete label sequences rather than separately over each state's next-label alternatives.
Local normalization can create label bias, especially where the permitted outgoing distribution is highly constrained. Richer observation features may help a particular task, but they do not turn local normalization into global normalization. Viterbi decoding solves the best-path problem for the specified model; it does not remove the model's structural limitations or repair poorly calibrated probabilities.

Business use

For business document extraction, an MEMM can provide an inspectable sequence-labeling baseline when labeled examples and useful features are available. Evaluate complete extracted spans and downstream fields, not only token accuracy. Record how unknown words, unusual formatting, invalid transitions, and domain changes are handled. Compare alternatives using the same data split and operational error costs rather than relying on the model's name.

Check your understanding

Why does sequence ON win in the example even though O is initially less likely?

Answer: Its strong second transition gives 0.4×0.9=0.36, exceeding both paths beginning with N, each of which has probability 0.30.

Related terms

Learn next

Change p(N|O,x) to 0.7 and its complementary probability to 0.3. Recalculate all four path probabilities, identify any ties for the best sequence, and compare the result with a greedy first decision.

Sources

Primary author exposition: Sutton and McCallum, An Introduction to Conditional Random Fields, section 5.1.3 on MEMMs and label bias: https://arxiv.org/pdf/1011.4088 . Original MEMM research is identified in its references as McCallum, Freitag, and Pereira, ICML 2000. Worked examples here are original.

Previous: Maximum entropy inverse reinforcement learning Next: Maximum entropy reinforcement learning