A Hybrid Markov/Semi-Markov Conditional Random Field for Sequence Segmentation

Galen AndrewEMNLP 2006 · OpenReview

Abstract

Markov order-1 conditional random fields (CRFs) and semi-Markov CRFs are two popular models for sequence segmentation and labeling. Both models have advantages in terms of the type of features they most naturally represent. We propose a hybrid model that is capable of representing both types of features, and describe efficient algorithms for its training and inference. We demonstrate that our hybrid model achieves error reductions of 18% and 25% over a standard order-1 CRF and a semi-Markov CRF (resp.) on the task of Chinese word segmentation. We also propose the use of a powerful feature for the semi-Markov CRF: the log conditional odds that a given token sequence constitutes a chunk according to a generative model, which reduces error by an additional 13%. Our best system achieves 96.8% F-measure, the highest reported score on this test set.

Introduction

In natural language processing, sequence segmentation involves partitioning a continuous stream of data into meaningful units. A prominent example is Chinese Word Segmentation (CWS), where text lacks explicit word boundaries. Historically, researchers have relied on two discriminative models: standard Markov order-1 CRFs and semi-Markov CRFs (Semi-CRFs).

Standard CRFs treat segmentation as a token-by-token labeling task, excelling at identifying local, sub-lexical patterns like common prefixes or suffixes. However, they are inherently "myopic" due to strict Markov independence assumptions, making it difficult to incorporate features based on the entire length or identity of a multi-character word. Conversely, Semi-CRFs model the distribution of chunks directly, allowing for word-level features. Despite this theoretical advantage, previous Semi-CRF implementations often failed to outperform standard CRFs in CWS tasks. This paper posits that Semi-CRFs underperformed because they traditionally discarded the highly effective local boundary features used by standard CRFs. We propose a hybrid model that leverages the strengths of both approaches.

Methods

Theoretical Expressiveness and Efficiency

The proposed hybrid model is built on the proof that a semi-CRF is strictly more expressive than an order-1 CRF; any feature usable in a standard CRF can be mathematically represented within a semi-CRF framework. To prevent the computational complexity from ballooning to $O(n^3)$ when injecting standard CRF features into a semi-CRF, we introduce a dynamic programming approach. By pre-computing and caching chunk scores, the algorithm maintains quadratic time complexity ($O(n^2)$), or linear time if the maximum word length is capped.

Log Conditional Odds Feature

A common technique in discriminative modeling is to use the output of a generative model (e.g., Naive Bayes) as a feature. Typically, this is the log-probability of a chunk being a word. However, log-probability suffers from an asymmetry: while a generative model can strongly signal that a chunk is not a word (probability near zero, log-probability near negative infinity), it cannot as strongly signal that it is a word (probability capped at 1, log-probability capped at 0). To resolve this, we introduce the log conditional odds—the ratio of the probability that a chunk is a word to the probability that it is not. This provides a symmetric signal that scales in both directions, offering a more robust feature for the discriminative model.

Experimental Setup

The model was evaluated on the Microsoft Research (MSR) Beijing Corpus from the Second International Chinese Word Segmentation Bakeoff (2005). The dataset includes 87K training sentences (2.37M words) and 107K test words. Experiments were conducted under strict "closed test" conditions, prohibiting the use of external lexicons or language-specific prior knowledge beyond the training set.

Results and Discussion

The hybrid model demonstrates significant performance gains by combining complementary feature sets. While Semi-CRF features (word identity and length) excel at segmenting known strings, standard CRF features (character-level boundary indicators) are essential for generalizing to out-of-vocabulary words.

F-measure results for various feature combinations on the MSR corpus.

As shown in the results table, the inclusion of "semi" features consistently improves performance over the baseline ("none"). Furthermore, the log conditional odds feature ("odds") proved vastly superior to standard log-probability ("prob"). Adding the log-odds feature to a baseline model reduced errors by 24%, compared to only 7.6% for log-probability. The final combined system achieved a 96.8% F-measure, representing a 12% relative error reduction over the previous state-of-the-art (96.4%) from the 2005 Bakeoff.

Conclusion

By unifying the sub-lexical strengths of Markov CRFs with the word-level expressiveness of semi-Markov CRFs, and introducing the log conditional odds feature, we established a new performance benchmark for Chinese Word Segmentation. While the model currently requires a maximum word length cap (set to 15 in these tests) to maintain efficiency, it covers 99.99% of training data. Future work will explore the application of log conditional odds in other NLP domains, such as machine translation and parsing, where log-probabilities are standard.

Summary updated

Abstract

Markov order-1 conditional random fields (CRFs) and semi-Markov CRFs are two popular models for sequence segmentation and labeling. Both models have advantages in terms of the type of features they most naturally represent. We propose a hybrid model that is capable of representing both types of features, and describe efficient algorithms for its training and inference. We demonstrate that our hybrid model achieves error reductions of 18% and 25% over a standard order-1 CRF and a semi-Markov CRF (resp.) on the task of Chinese word segmentation. We also propose the use of a powerful feature for the semi-Markov CRF: the log conditional odds that a given token sequence constitutes a chunk according to a generative model, which reduces error by an additional 13%. Our best system achieves 96.8% F-measure, the highest reported score on this test set.
BibTeX
@inproceedings{andrew2006hybrid,
  author = {Galen Andrew},
  title = {{A Hybrid Markov/Semi-Markov Conditional Random Field for Sequence Segmentation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2006},
  url = {https://openreview.net/forum?id=BJbjBMGubB},
}
Figure