Abstract
In statistical Natural Language Processing (NLP), the choice of a decision rule is often decoupled from the metric used for evaluation. This study re-examines the Bayes decision rule in the context of Part-of-Speech (POS) tagging, comparing the standard Viterbi-based string error minimization against a symbol-level error minimization approach. Through experiments on the Wall Street Journal (WSJ) and Münster Tagging Project (MTP) corpora, we demonstrate that the theoretically optimal symbol-level rule does not consistently outperform the string-level rule, particularly in direct modeling frameworks.
Introduction
The fundamental goal of a statistical NLP system is to map an input sequence (words) to an output sequence (tags) using a decision rule that minimizes expected loss. Traditionally, researchers employ the Bayes decision rule to minimize the probability of any error in the entire sequence—known as string error. This is efficiently computed using the Viterbi algorithm.
However, most POS tagging tasks are evaluated based on symbol error, or the percentage of individual words tagged incorrectly. There is a mathematical mismatch here: we optimize for the whole sentence but evaluate by the word. This paper explores whether aligning the decision rule with the evaluation metric—specifically using a rule designed to minimize symbol error—leads to better performance.
Decision Rules and Modeling Approaches
The authors contrast two primary decision rules:
- String Error Minimization: This rule selects the tag sequence that maximizes the joint probability of the entire sentence. It is the "all-or-nothing" approach where a single mistake makes the whole sequence "wrong."
- Symbol Error Minimization: This rule optimizes each position independently by maximizing the marginal probability. It effectively sums over all possible tag sequences that contain a specific tag at a given position.
These rules were tested across two model architectures:
- Generative Models (HMMs): Trigram models where symbol error minimization is achieved via an extension of the Forward-Backward algorithm.
- Direct Models (Maximum Entropy): Log-linear models that predict tags based on local context windows. For these models, the symbol-level rule can be implemented using only a Forward pass.
Experimental Results
The researchers evaluated these configurations on the English Wall Street Journal (WSJ) corpus and the German Münster Tagging Project (MTP) corpus.
As shown in the WSJ results (Figure 4), the performance difference between the two rules is minimal for generative models, with both achieving a 3.5% error rate. Surprisingly, for the Direct (MaxEnt) model, the "standard" string-level rule actually outperformed the symbol-level rule (3.0% vs 3.3% error). Similar trends were observed in the German MTP dataset, where the string rule maintained a slight edge in the Direct model (5.4% vs 5.6%).
Qualitative Analysis and Linguistic Coherency
Why does the mathematically "optimal" symbol rule fail to provide a boost? One primary reason is linguistic coherency. Because the symbol-level rule optimizes each position independently, it may choose tags that are individually likely but collectively improbable or syntactically inconsistent.
Figure 5 illustrates these discrepancies. In several cases, the symbol-level rule reverts to a more frequent tag for a specific word, ignoring the broader syntactic constraints that the string-level rule (Viterbi) preserves. For instance, in the VBN → VBD example, the symbol rule might favor a common past-tense interpretation that breaks the global sentence structure, whereas the string rule correctly identifies the participle based on the surrounding context.
Conclusion
This study reveals that for POS tagging, the theoretical advantage of symbol-level Bayes decision rules does not translate into empirical gains. The robustness of the Viterbi algorithm (string-level rule) likely stems from its ability to maintain global linguistic consistency. Furthermore, the slight degradation in Direct models suggests that the interaction between model structure and marginalization is complex. Future work should investigate whether training models specifically to minimize symbol-level loss—rather than just changing the inference rule—might unlock the expected performance benefits.
Summary updated