Back

Maximum Entropy Markov Models for Information Extraction and Segmentation

A. McCallumDayne FreitagFernando C Pereira

article2000ICML1,655 citations

Introduces Maximum Entropy Markov Models to overcome the generative limitations of standard hidden Markov models by directly predicting conditional state sequences with rich, overlapping observation features for information extraction and text segmentation.

Listen

Extracting structured information and segmenting text from unstructured digital documents is a critical capability for modern automated text-processing systems. Traditional sequence models, such as standard Hidden Markov Models, model the probability of text generation using discrete vocabulary words. However, this approach struggles when text elements are characterized by rich, overlapping characteristics—such as formatting, capitalization, or layout—or when the primary objective is to predict labels directly from given inputs rather than generating text.

The article introduces and evaluates Maximum Entropy Markov Models, a sequence modeling framework designed to overcome these constraints. The primary objective is to demonstrate that conditioning state transitions directly on arbitrary, overlapping input features improves the accuracy and reliability of automated text segmentation compared to traditional probabilistic models.

To evaluate this framework, the authors conducted empirical experiments on a benchmark dataset consisting of 38 multi-part online FAQ documents. They framed the problem as segmenting each line of text into four functional sections: header, question, answer, and tail. The study defined 24 simple structural and linguistic features per line, such as punctuation and indentation patterns. The proposed model was evaluated using a cross-validation approach where models trained on a single labeled document were tested on unseen documents from the same group, and its performance was compared against baseline models, including traditional token-based and feature-based Markov models and an isolated feature classifier.

The findings show that the new framework significantly outperforms alternative approaches. First, the proposed model achieved an exact segmentation precision of 86.7%, more than doubling the 41.3% precision achieved by the feature-based traditional Markov model and dramatically exceeding the standard token-based model (27.6%). Second, it delivered the highest segmentation recall at 68.1%, compared to 52.9% for the feature-based baseline and 14.0% for the token-based baseline. Third, the results confirmed that while feature representations are vital, modeling sequential document structure is indispensable; an isolated classifier that ignored sequence structure failed almost entirely, achieving only 3.8% precision.

These results indicate that combining rich contextual features with sequential structure produces segmentation accurate enough for practical deployment in automated downstream pipelines, such as question-answering systems, without requiring heavy manual post-processing. Because the new architecture avoids predicting entire input distributions and focuses purely on conditional labeling, it significantly reduces classification errors and boundary confusion.

Organizations developing automated text-extraction workflows should consider adopting this conditional modeling framework, particularly when handling complex document formatting. For next steps, the authors recommend exploring distributed state representations to manage parameter growth, integrating semi-supervised training with partially labeled data, and evaluating the architecture on broader information extraction tasks such as entity recognition.

A key limitation noted in the article is the proliferation of parameters that occurs when transition functions depend on both complex features and multiple states, which could lead to data sparseness in larger domains. While confidence in the reported performance is high within the tested document collections, stakeholders should exercise caution and conduct domain-specific pilot testing before applying the model to unstructured texts that lack clear internal formatting conventions.

AT&T Labs—ResearchJust Researchcross validationhidden markov model (hmm)hidden markov modelsMaximum Entropy Markov Modelsinformation extractiontext segmentation
McCallum et al (2000).pdf
  • Paper: Text Chunking using Transformation-Based Learning, Lance A. Ramshaw et al. (1995). This paper establishes the foundational formulation of text segmentation and chunking as sequential tag-labeling problems, which the source builds upon directly using conditional probabilistic modeling.
  • Paper: Message Understanding Conference- 6: A Brief History, Ralph Grishman et al. (1996). Reading this paper provides essential background on standardized information extraction benchmarks and modular sequence labeling tasks that motivated the development of Maximum Entropy Markov Models.
Cover for Maximum Entropy Markov Models for Information Extraction and Segmentation

Abstract

Hidden Markov models (HMMs) are a powerful probabilistic tool for modeling sequential data, and have been applied with success to many text-related tasks, such as part-of-speech tagging, text segmentation and information extraction. In these cases, the observations are usually modeled as multinomial distributions over a discrete vocabulary, and the HMM parameters are set to maximize the likelihood of the observations. This paper presents a new Markovian sequence model, closely related to HMMs, that allows observations to be represented as arbitrary overlapping features (such as word, capitalization, formatting, part-of-speech), and defines the conditional probability of state sequences given observation sequences. It does this by using the maximum entropy framework to fit a set of exponential models that represent the probability of a state given an observation and the previous state. We present positive experimental results on the segmentation of FAQ's.

Topics

cross validationhidden markov model (hmm)hidden markov modelsinformation extractioninput featuresmarkov modelprobabilistic modelstext documentvalidationvocabulary

Keywords

Maximum Entropy Markov Modelsinformation extractiontext segmentationentity recognitionmaximum entropy frameworkgraphical modelsstatistical language modeling

Table of Contents

  • 1. Introduction
  • 2. Maximum-Entropy Markov Models
  • 2.1 The New Model
  • 2.2 State Estimation from Observations
  • 2.4 Parameter Estimation by Generalized Iterative Scaling
  • 2.5 Parameter Estimation with Unknown State
  • 2.6 Variations
  • 3. Experimental Results
  • 4. Related Work
  • 5. Conclusions and Further Work
  • Acknowledgements
  • References

Knowls

  1. Knowl 1 — Maximum Entropy Markov Model Formulation

    model/method

    Maximum Entropy Markov Models (MEMMs) are conditional Markovian sequence models that replace the separate generative transition and observation distributions of Hidden Markov Models (HMMs) with a single conditional transition function P(s∣s′,o)P(s \mid s', o), representing the probability of the current state s∈Ss \in S given the previous state s′∈Ss' \in S and the current observation o∈Oo \in O.

    In an MEMM, the model parameters are split into ∣S∣|S| separately trained transition distributions Ps′(s∣o)=P(s∣s′,o)P_{s'}(s \mid o) = P(s \mid s', o) for each source state s′s'. Each transition function is parameterized as an exponential (log-linear) model conditioned on arbitrary, non-independent features of the observation:

    Ps′(s∣o)=1Z(o,s′)exp⁡(∑aλafa(o,s))P_{s'}(s \mid o) = \frac{1}{Z(o, s')} \exp\left( \sum_a \lambda_a f_a(o, s) \right)

    where:

    • fa(o,s)f_a(o, s) is a feature function over the observation oo and destination state ss (typically decomposed as f(b,s∗)(o,s)=1f_{(b, s^*)}(o, s) = 1 if binary observation predicate b(o)b(o) is true and s=s∗s = s^*, and 00 otherwise),
    • λa∈R\lambda_a \in \mathbb{R} is the weight parameter corresponding to feature faf_a,
    • Z(o,s′)Z(o, s') is the normalizing partition function summing over all next states:

    Z(o,s′)=∑s∈Sexp⁡(∑aλafa(o,s))Z(o, s') = \sum_{s \in S} \exp\left( \sum_a \lambda_a f_a(o, s) \right)

  2. Knowl 2 — State Estimation and Viterbi Decoding in MEMMs

    algorithm

    Given an observation sequence o1,…,omo_1, \dots, o_m and state space SS, state inference in Maximum Entropy Markov Models (MEMMs) evaluates the conditional probability of state sequences given the observation sequence using dynamic programming recurrences.

    The forward probability αt(s)\alpha_t(s) is the probability of being in state ss at time tt given observations o1,…,oto_1, \dots, o_t. The forward recurrence is:

    αt+1(s)=∑s′∈Sαt(s′)Ps′(s∣ot+1)\alpha_{t+1}(s) = \sum_{s' \in S} \alpha_t(s') P_{s'}(s \mid o_{t+1})

    The backward probability βt(s′)\beta_t(s') is the probability of starting from state s′s' at time tt given the future observations ot+1,…,omo_{t+1}, \dots, o_m. The backward recurrence is:

    βt(s′)=∑s∈SP(s∣s′,ot+1)βt+1(s)\beta_t(s') = \sum_{s \in S} P(s \mid s', o_{t+1}) \beta_{t+1}(s)

    To identify the most likely state sequence s^1,…,s^m\hat{s}_1, \dots, \hat{s}_m, the Viterbi path recurrence computes:

    vt+1(s)=max⁡s′∈S(vt(s′)⋅Ps′(s∣ot+1))v_{t+1}(s) = \max_{s' \in S} \left( v_t(s') \cdot P_{s'}(s \mid o_{t+1}) \right)

    tracking backpointers arg⁡max⁡s′(vt(s′)Ps′(s∣ot+1))\arg\max_{s'} (v_t(s') P_{s'}(s \mid o_{t+1})) to recover the optimal path from t=mt = m back to t=1t = 1.

  3. Knowl 3 — Generalized Iterative Scaling for Supervised MEMM Parameter Estimation

    algorithm

    When state sequences s1,…,sms_1, \dots, s_m corresponding to training observations o1,…,omo_1, \dots, o_m are known, the transition model Ps′(s∣o)P_{s'}(s \mid o) for each source state s′s' is trained independently using Generalized Iterative Scaling (GIS).

    GIS finds the maximum entropy parameters λa\lambda_a such that the expected value of each feature under the learned distribution matches its empirical expectation over training time steps tkt_k where previous state stk−1=s′s_{t_k-1} = s':

    1ms′∑k=1ms′fa(otk,stk)=1ms′∑k=1ms′∑s∈SPs′(s∣otk)fa(otk,s)\frac{1}{m_{s'}} \sum_{k=1}^{m_{s'}} f_a(o_{t_k}, s_{t_k}) = \frac{1}{m_{s'}} \sum_{k=1}^{m_{s'}} \sum_{s \in S} P_{s'}(s \mid o_{t_k}) f_a(o_{t_k}, s)

    where ms′m_{s'} is the number of transitions leaving s′s'.

    Input: Observation sequence o1,…,omo_1, \dots, o_m, state sequence s1,…,sms_1, \dots, s_m, features {faf_a}a=1n_{a=1}^n, source state s′s', constant C=max⁡o,s∑a=1nfa(o,s)C = \max_{o,s} \sum_{a=1}^n f_a(o,s)
    Output: Learned feature parameters λ\lambda for transition model Ps′(s∣o)P_{s'}(s \mid o)
    Identify time indices {tkt_k}k=1ms′_{k=1}^{m_{s'}} where stk−1=s′s_{t_k-1} = s'
    Add correction feature fn+1(o,s)=C−∑a=1nfa(o,s)f_{n+1}(o, s) = C - \sum_{a=1}^n f_a(o, s) so ∑a=1n+1fa(o,s)=C\sum_{a=1}^{n+1} f_a(o, s) = C for all o,so, s
    For each feature a∈1,…,n+1a \in {1, \dots, n+1}:
        Compute empirical average Fa=1ms′∑k=1ms′fa(otk,stk)F_a = \frac{1}{m_{s'}} \sum_{k=1}^{m_{s'}} f_a(o_{t_k}, s_{t_k})
    Initialize λa(0)←0\lambda_a^{(0)} \leftarrow 0 for all a∈1,…,n+1a \in {1, \dots, n+1}
    j←0j \leftarrow 0
    repeat
        For each feature a∈1,…,n+1a \in {1, \dots, n+1}:
            Compute expected value Ea(j)=1ms′∑k=1ms′∑s∈SPs′(j)(s∣otk)fa(otk,s)E_a^{(j)} = \frac{1}{m_{s'}} \sum_{k=1}^{m_{s'}} \sum_{s \in S} P_{s'}^{(j)}(s \mid o_{t_k}) f_a(o_{t_k}, s)
            where Ps′(j)(s∣o)=1Z(o,s′)exp⁡(∑b=1n+1λb(j)fb(o,s))P_{s'}^{(j)}(s \mid o) = \frac{1}{Z(o, s')} \exp(\sum_{b=1}^{n+1} \lambda_b^{(j)} f_b(o, s))
        For each feature a∈1,…,n+1a \in {1, \dots, n+1}:
            λa(j+1)←λa(j)+1Clog⁡(FaEa(j))\lambda_a^{(j+1)} \leftarrow \lambda_a^{(j)} + \frac{1}{C} \log\left(\frac{F_a}{E_a^{(j)}}\right)
        j←j+1j \leftarrow j + 1
    until convergence
    return λ\lambda

  4. Knowl 4 — Generalized Expectation-Maximization for MEMMs with Hidden States

    algorithm

    When training state sequences are partially or completely unobserved (e.g., multiple hidden states mapping to the same label or sequences missing annotations), Maximum Entropy Markov Models can be trained using an adapted Baum-Welch procedure based on Generalized Expectation-Maximization (GEM).

    The procedure alternates between:

    1. Expectation Step (E-step): Calculate state occupancies and posterior transition probabilities P(st−1=s′,st=s∣o1,…,om)P(s_{t-1} = s', s_t = s \mid o_1, \dots, o_m) using the forward-backward algorithm parameterized with the current transition functions Ps′(s∣o)P_{s'}(s \mid o).
    2. Maximization Step (M-step): Apply Generalized Iterative Scaling (GIS) using the expected feature frequencies computed from the E-step posterior occupancies to update the transition parameters λ\lambda.

    GIS does not need to be run to full convergence within each M-step; performing partial updates preserves the Generalized Expectation-Maximization guarantee of convergence to a local maximum of the conditional likelihood.

  5. Knowl 5 — Factored State Representation and Decoupled Observations in MEMMs

    model/method

    Standard MEMMs use ∣S∣|S| distinct exponential functions Ps′(s∣o)P_{s'}(s \mid o), requiring O(∣S∣2)O(|S|^2) transition parameters and risking data sparsity. Two architectural variants modify this parameterization:

    1. Factored State Representation: Rather than maintaining separate models Ps′(s∣o)P_{s'}(s \mid o) for each source state s′s', the previous state s′s' is represented as a feature vector (e.g., flags indicating whether document preambles or specific fields have been processed). Transitions are parameterized by a single maximum entropy model over joint state-observation feature conjunctions, enabling statistical parameter sharing across source states without manual parameter tying.

    2. Decoupled Transition and Observation Exponential Correction: Transitions can be decomposed into a baseline multinomial transition probability P(s∣s′)P(s \mid s') modulated by an observation-dependent exponential factor:

    P(s∣s′,o)=P(s∣s′)1Z(o,s′)exp⁡(∑aλafa(o,s))P(s \mid s', o) = P(s \mid s') \frac{1}{Z(o, s')} \exp\left( \sum_a \lambda_a f_a(o, s) \right)

    This treats previous state identity and observation features as conditionally independent evidence for destination state ss, reducing parameter count under severe data sparsity.

  6. Knowl 6 — FAQ Text Segmentation Dataset and Feature Representation

    experimental setup

    The experimental evaluation of Maximum Entropy Markov Models uses an information extraction and text segmentation benchmark comprising 38 multi-part Usenet FAQ files across 7 topics.

    Each line in the corpus is labeled into one of four functional categories:

    • head: Header lines, Usenet metadata, preamble, or table of contents.
    • question: Lines introducing a question in a question-answer pair.
    • answer: Text lines providing the answer body.
    • tail: Copyright notices, acknowledgments, and closing metadata.

    Lines are represented using 24 non-independent Boolean features capturing line-level formatting and character patterns: begins-with-number, begins-with-ordinal, begins-with-punctuation, begins-with-question-word, begins-with-subject, blank, contains-alphanum, contains-bracketed-number, contains-http, contains-non-space, contains-number, contains-pipe, contains-question-mark, contains-question-word, ends-with-question-mark, first-alpha-is-capitalized, indented, indented-1-to-4, indented-5-to-10, more-than-one-third-space, only-punctuation, prev-is-blank, prev-begins-with-ordinal, and shorter-than-30.

    Evaluation is performed via leave-one-document-out testing within each FAQ topic group (training on one document and testing on all remaining documents in that group).

  7. Knowl 7 — FAQ Segmentation Performance Comparison across Sequence Models

    data/table

    Four models were evaluated on the 38-file FAQ segmentation dataset using leave-one-out testing: ME-Stateless (a single maximum entropy classifier applied per line independently), TokenHMM (a 4-state HMM emitting token multinomials constrained to state switches at line boundaries), FeatureHMM (a 4-state HMM emitting line features via naive Bayes), and MEMM (the maximum entropy Markov model).

    Performance was evaluated across three metrics:

    • Co-occurrence Agreement Probability (COAP): The empirical probability Pμ(act,pred)=∑i,jDμ(i,j)(δact(i,j) ⊕‾ δpred(i,j))P_\mu(\text{act}, \text{pred}) = \sum_{i,j} D_\mu(i,j) \left( \delta_{\text{act}}(i,j) \ \overline{\oplus} \ \delta_{\text{pred}}(i,j) \right) that any two lines within a uniform window distance of 10 lines (DμD_\mu) agree on whether they belong to the same segment or different segments (ignoring label identity).
    • Segmentation Precision (SegPrec): The proportion of predicted segments that match an actual segment in both exact line boundaries and label category.
    • Segmentation Recall (SegRecall): The proportion of actual ground-truth segments correctly predicted with exact line boundaries and label category.
    Learner COAP SegPrec SegRecall
    ME-Stateless 0.520 0.038 0.362
    TokenHMM 0.865 0.276 0.140
    FeatureHMM 0.941 0.413 0.529
    MEMM 0.965 0.867 0.681

    All averages have 95% confidence intervals of 0.01 or less. MEMM more than doubles the segmentation precision of FeatureHMM (0.867 vs. 0.413) and achieves the highest COAP and recall, showing that combining rich overlapping line features with sequential state conditioning eliminates spurious segment interpolations.

Coverage note — None was omitted; all key theoretical definitions, algorithms (Viterbi, GIS, Baum-Welch/GEM), structural variations, dataset details, and empirical benchmark comparisons are covered. The brief theoretical note on extending transitions to reinforcement learning action spaces $P(s \mid s', o, a)$ was omitted as it is an unelaborated conceptual remark.

References

  1. 1.Argamon, S., Dagan, I., & Krymolowski, Y. (1998). A memory-based approach to learning shallow natural language patterns. In COLING-ACL 98, pp. 67–73 New Brunswick, New Jersey. Association for Computational Linguistics.
  2. 2.Beeferman, D., Berger, A., & Lafferty, J. (1999). Statistical models for text segmentation. Machine Learning, 34(1–3), 177–210.
  3. 3.Bikel, D. M., Schwartz, R. L., & Weischedel, R. M. (1999). An algorithm that learns what’s in a name. Machine Learning Journal, 34, 211–231.
  4. 4.Borthwick, A., Sterling, J., Agichtein, E., & Grishman, R. (1998). Exploiting diverse knowledge sources via maximum entropy in named entity recognition. In Proceedings of the Sixth Workshop on Very Large Corpora New Brunswick, New Jersey. Association for Computational Linguistics.
  5. 5.Brill, E. (1995). Transformation-based error-driven learning and natural language processing: a case study in part of speech tagging. Computational Linguistics, 21(4), 543–565.
  6. 6.Burke, R., Hammond, K., Kulyukin, V., Lytinen, S., & Tomuro, N. (1997). Question answering from frequently-asked question files: Experiences with the FAQ Finder system. AI Magazine, 18, 57–66.
  7. 7.Chen, S., & Rosenfeld, R. (1999). Efficient sampling and feature selection in whole sentence maximum entropy language models. In Proceedings of ICASSP’99. IEEE.
  8. 8.Darroch, J. N., & Ratcliff, D. (1972). Generlized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5), 1470–1480.
  9. 9.Della Pietra, S., Della Pietra, V., & Lafferty, J. (1997). Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4).
  10. 10.Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1), 1–38.
  11. 11.Freitag, D., & McCallum, A. K. (1999). Information extraction using hmms and shrinkage. In Papers from the AAAI-99 Workshop on Machine Learning for Information Extration, pp. 31–36 Menlo Park, California. AAAI.
  12. 12.Ghahramani, Z., & Jordan, M. I. (1996). Factorial hidden Markov models. In Mozer, M., Touretzky, D., & Perrone, M. (Eds.), Advances in Neural Information Processing Systems 8. MIT Press.
  13. 13.Kanazawa, K., Koller, D., & Russell, S. (1995). Stochastic simulation algorithms for dynamic probabilistic networks. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence Montreal, Canada. Morgan Kaufmann.
  14. 14.Kupiec, J. (1992). Robust part-of-speech tagging using a hidden Markov model. Computer Speech and Language, 6, 225–242.
  15. 15.Leek, T. R. (1997). Information extraction using hidden Markov models. Master’s thesis, UC San Diego.
  16. 16.Paz, A. (1971). Introduction to Probabilistic Automata. Academic Press.
  17. 17.Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257–285.
  18. 18.Ratnaparkhi, A. (1998). Maximum Entropy Models for Natural Language Ambiguity Resolution. Ph.D. thesis, University of Pennsylvania.
  19. 19.Rosenfeld, R. (1994). Adaptive Statistical Language Modeling: A Maximum Entropy Approach. Ph.D. thesis, Carnegie Mellon University.
  20. 20.Roth, D. (1998). Learning to resolve natural language ambiguities: a unified approach. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pp. 806–813 Menlo Park, California. AAAI Press.
  21. 21.Saul, L., & Rahim, M. (1999). Markov processes on curves for automatic speech recognition. In Kearns, M. S., Solla, S. A., & Cohn, D. A. (Eds.), Advances in Neural Information Processing Systems, Vol. 11 Cambridge, Massachusetts. MIT Press.
  22. 22.Yamron, J., Carp, I., Gillick, L., Lowe, S., & van Mulbregt, P. (1998). A hidden Markov model approach to text segmentation and event tracking. In Proceedings of ICASSP’98. IEEE.

Citation

MLA
McCallum, A., et al. “Maximum Entropy Markov Models for Information Extraction and Segmentation”. 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.2034.
APA
McCallum, A., Freitag, D., & Pereira, F. C. N. (2000). Maximum Entropy Markov Models for Information Extraction and Segmentation. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.2034
Chicago
McCallum, A., D. Freitag, and F. C. N. Pereira. 2000. “Maximum Entropy Markov Models for Information Extraction and Segmentation”. Preprint. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.2034.
Harvard
McCallum, A., Freitag, D. and Pereira, F.C.N. (2000) “Maximum Entropy Markov Models for Information Extraction and Segmentation”. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.2034.
Vancouver
1. McCallum A, Freitag D, Pereira FCN (2000) Maximum Entropy Markov Models for Information Extraction and Segmentation.

BibTeX

@article{mccallum2000maximum,
  title = {Maximum Entropy Markov Models for Information Extraction and Segmentation},
  author = {McCallum, Andrew and Freitag, Dayne and Pereira, Fernando C. N.},
  year = {2000},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.2034}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF