TnT – A Statistical Part-of-Speech Tagger

Thorsten Brants

article2000Applied Natural Language Processing Conference2,015 citations

Presents TnT, a fast and accurate part-of-speech tagger based on second-order Markov models, demonstrating that optimized smoothing and suffix-based unknown-word handling allow classical statistical approaches to match or outperform complex Maximum Entropy models.

Listen

Automated natural language processing systems rely heavily on part-of-speech tagging as an essential initial stage to label words with their grammatical categories. Despite significant research, developers have debated which statistical or rule-based methods deliver the best balance of speed and precision. The article investigates whether a system built on standard Markov models—often dismissed in previous studies as inferior—can match or outperform leading modern alternatives when implemented with careful smoothing and unknown-word handling techniques.

To evaluate this question, the article introduces and assesses the Trigrams'n'Tags (TnT) tagger using rigorous empirical testing on major benchmarks. The evaluation utilizes standard German and English newspaper corpora—the NEGRA corpus and the Wall Street Journal section of the Penn Treebank—employing ten-fold cross-validation across varying training set sizes. The system incorporates context-independent linear interpolation for smoothing, specialized suffix analysis for handling unknown terms, capitalization cues, and beam search optimization to accelerate runtime performance.

The findings demonstrate that the system achieves overall tagging accuracy between 96% and 97% across both languages, matching or slightly exceeding complex maximum entropy frameworks while operating at significantly higher speeds (tagging 30,000 to 60,000 tokens per second). Accuracy on previously seen words remains exceptionally high at over 95% even when trained on as few as 1,000 tokens, whereas unknown words are handled effectively via suffix modeling, reaching 85.5% to 89.0% accuracy. Furthermore, by evaluating the probability margin between the best and second-best candidate tags, the system can reliably isolate a subset of decisions that exceed 99% accuracy.

These results demonstrate that implementation details—such as handling sequence boundaries, parameter weighting, and capitalization—matter as much as the overarching model architecture. The high processing speed and robust precision make this approach highly practical for large-scale production environments and corpus annotation projects, reducing computational overhead and manual correction costs.

Organizations developing language processing pipelines should consider Markov model taggers as viable, lightweight, and highly competitive options. Corpus curation teams can immediately leverage the probability confidence metrics to flag uncertain tags for human review while automating the highly confident bulk of the data. Future research should focus on exploring combinations of Markov models and maximum entropy methods to determine whether hybrid architectures can yield even higher accuracy.

Saarland University markov model speech signals markov chains part-of-speech tagging Markov models Penn Treebank

arXiv: cs/0003055

Paper: An Empirical Study of Smoothing Techniques for Language Modeling, Stanley F. Chen et al. (1996). This empirical study establishes the foundational n-gram smoothing and deleted interpolation techniques directly utilized by TnT to estimate robust statistical transition and emission probabilities.

Paper: Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, J. Lafferty et al. (2001). This paper introduces Conditional Random Fields, which directly overcome the label bias problem inherent in generative Markov sequence taggers like TnT by globally normalizing over observation sequences.
Paper: Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network, Kristina Toutanova et al. (2003). This work advances statistical part-of-speech tagging beyond TnT's unidirectional Markov chain by incorporating bidirectional context through cyclic dependency networks.
Paper: Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms, Michael Collins (2002). This paper introduces discriminatively trained Hidden Markov Models via the perceptron algorithm to improve sequence tagging accuracy over standard maximum-likelihood Markov taggers.
Paper: Bidirectional LSTM-CRF Models for Sequence Tagging, Zhiheng Huang et al. (2015). This paper modernizes sequence tagging benchmarks by replacing traditional n-gram HMMs with bidirectional LSTM-CRF neural architectures.
Paper: End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF, Xuezhe Ma et al. (2016). This work extends POS tagging methodologies to an end-to-end neural sequence labeling framework combining CNN character representations with BiLSTM-CRFs.
Paper: Natural Language Processing (almost) from Scratch, Ronan Collobert et al. (2011). This seminal work demonstrates how unified neural network architectures can perform core NLP tasks like POS tagging without relying on traditional n-gram statistical models.
Paper: NLTK: The Natural Language Toolkit, Steven Bird (2006). This toolkit implements and provides standard educational and operational interfaces for statistical taggers and related sequence analysis algorithms.
Paper: The Stanford CoreNLP Natural Language Processing Toolkit, Christopher D. Manning et al. (2014). This software pipeline provides modern production-ready implementations of statistical and neural sequence taggers across multi-stage linguistic workflows.

Cover for TnT – A Statistical Part-of-Speech Tagger

Abstract

Trigrams'n'Tags (TnT) is an efficient statistical part-of-speech tagger. Contrary to claims found elsewhere in the literature, we argue that a tagger based on Markov models performs at least as well as other current approaches, including the Maximum Entropy framework. A recent comparison has even shown that TnT performs significantly better for the tested corpora. We describe the basic model of TnT, the techniques used for smoothing and for handling unknown words. Furthermore, we present evaluations on two corpora.

Topics

markov model speech signals markov chains

Keywords

part-of-speech tagging Markov models Penn Treebank NEGRA corpus Maximum Entropy framework beam search maximum likelihood probabilities

1 Introduction
2 Architecture
2.1 The Underlying Model
2.2 Smoothing
2.3 Handling of Unknown Words
2.4 Capitalization
2.5 Beam Search
3 Evaluation
3.1 Tagging the NEGRA corpus
3.2 Tagging the Penn Treebank
3.3 Summary of Part-of-Speech Tagging Results
4 Conclusion
References

Knowls

Knowl 1 — TnT Second-Order Hidden Markov Model Tagging Formulation
model/method
TnT (Trigrams'n'Tags) implements part-of-speech tagging using a second-order Hidden Markov Model (HMM). Given an input sequence of words $w_1, \dots, w_T$ of length $T$ , the optimal tag sequence $t_1, \dots, t_T$ is determined by maximizing the joint probability of state transitions and lexical emissions:

$\operatorname{argmax}_{t_1 \dots t_T} \left[ \prod_{i=1}^T P(t_i \mid t_{i-1}, t_{i-2}) P(w_i \mid t_i) \right] P(t_{T+1} \mid t_T)$

where each $t_i$ is a part-of-speech tag from a predefined tagset $\mathcal{T}$ , $t_{-1}$ and $t_0$ represent start-of-sequence markers, and $t_{T+1}$ represents an end-of-sequence marker. If sentence boundaries are not explicitly annotated in the input, the tagger inserts boundary markers whenever encountering punctuation tokens in $[.!?;]$ .

The maximum likelihood estimates $\hat{P}$ derived from training corpus frequency counts $f(\cdot)$ with total token count $N$ are:
- Tag unigram: $\hat{P}(t_3) = \frac{f(t_3)}{N}$
- Tag bigram: $\hat{P}(t_3 \mid t_2) = \frac{f(t_2, t_3)}{f(t_2)}$
- Tag trigram: $\hat{P}(t_3 \mid t_1, t_2) = \frac{f(t_1, t_2, t_3)}{f(t_1, t_2)}$
- Lexical emission: $\hat{P}(w_3 \mid t_3) = \frac{f(w_3, t_3)}{f(t_3)}$
If both the numerator and denominator for any relative frequency are zero, the maximum likelihood estimate is set to zero.
Knowl 2 — Deleted Interpolation Algorithm for Estimating Linear Interpolation Weights
algorithm
The context-independent interpolation weights $\lambda_1, \lambda_2, \lambda_3$ for smoothing trigram transitions are estimated via deleted interpolation. The algorithm iterates over all distinct trigrams observed in the training corpus and credits the trigram frequency $f(t_1, t_2, t_3)$ to the specific $n$ -gram model that maximizes the leave-one-out probability. The computational complexity scales linearly with the number of distinct trigrams.
Input: N-gram frequencies $f(t_1, t_2, t_3)$ , $f(t_2, t_3)$ , $f(t_1, t_2)$ , $f(t_3)$ , $f(t_2)$ , and total training tokens $N$
Output: Normalized weights $\lambda_1, \lambda_2, \lambda_3$
$\lambda_1 = 0$
$\lambda_2 = 0$
$\lambda_3 = 0$
for each trigram $(t_1, t_2, t_3)$ with $f(t_1, t_2, t_3) > 0$ :
    if $f(t_1, t_2) - 1 > 0$ :
         $c_3 = (f(t_1, t_2, t_3) - 1) / (f(t_1, t_2) - 1)$
    else:
         $c_3 = 0$
    if $f(t_2) - 1 > 0$ :
         $c_2 = (f(t_2, t_3) - 1) / (f(t_2) - 1)$
    else:
         $c_2 = 0$
    if $N - 1 > 0$ :
         $c_1 = (f(t_3) - 1) / (N - 1)$
    else:
         $c_1 = 0$
    if $c_3 \ge c_2$ and $c_3 \ge c_1$ :
         $\lambda_3 = \lambda_3 + f(t_1, t_2, t_3)$
    else if $c_2 \ge c_3$ and $c_2 \ge c_1$ :
         $\lambda_2 = \lambda_2 + f(t_1, t_2, t_3)$
    else:
         $\lambda_1 = \lambda_1 + f(t_1, t_2, t_3)$
$\text{total} = \lambda_1 + \lambda_2 + \lambda_3$
$\lambda_1 = \lambda_1 / \text{total}$
$\lambda_2 = \lambda_2 / \text{total}$
$\lambda_3 = \lambda_3 / \text{total}$
return $\lambda_1, \lambda_2, \lambda_3$
Subtracting 1 in the probability numerators and denominators simulates omitting the target instance from the training counts, accounting for unseen data and avoiding overfitting.
Knowl 3 — Context-Independent Linear Interpolation Smoothing for Trigram Transitions
model/method
To mitigate data sparsity and prevent zero probabilities when encountering unseen tag transitions, trigram transition probabilities are smoothed via linear interpolation of maximum likelihood unigram, bigram, and trigram estimates:

$P(t_3 \mid t_1, t_2) = \lambda_1 \hat{P}(t_3) + \lambda_2 \hat{P}(t_3 \mid t_2) + \lambda_3 \hat{P}(t_3 \mid t_1, t_2)$

where $\hat{P}$ denotes the relative frequency estimates and $\lambda_1 + \lambda_2 + \lambda_3 = 1$ with $\lambda_i \ge 0$ .

The smoothing parameters $\lambda_1, \lambda_2, \lambda_3$ are context-independent, sharing a single global set of weights across all tag transitions. Grouping trigrams into frequency classes to estimate context-dependent tied weights does not yield improvements over global context-independent interpolation and, in several configurations, degrades tagging accuracy.
Knowl 4 — Successive Abstraction Suffix Model for Unknown Word Handling
model/method
For words not present in the training lexicon, emission probabilities are derived from character suffix distributions using successive abstraction. Suffix statistics are gathered exclusively from infrequent words in the lexicon with training frequencies $f(w) \le 10$ , as their morphological behavior closely matches unknown words.

For an $n$ -character unknown word with suffix $l_{n-m+1} \dots l_n$ of length $m \le 10$ (where $m$ is the longest suffix appearing at least once in the training corpus), tag conditional probabilities are computed recursively:

$P(t \mid l_{n-i+1}, \dots, l_n) = \frac{\hat{P}(t \mid l_{n-i+1}, \dots, l_n) + \theta_i P(t \mid l_{n-i+2}, \dots, l_n)}{1 + \theta_i}$

for $i = m, m-1, \dots, 1$ , initialized at $i=0$ with the unconditioned tag probability $P(t) = \hat{P}(t)$ . The relative frequency estimate is:

$\hat{P}(t \mid l_{n-i+1}, \dots, l_n) = \frac{f(t, l_{n-i+1}, \dots, l_n)}{f(l_{n-i+1}, \dots, l_n)}$

Inverse emission probabilities $P(l_{n-m+1}, \dots, l_n \mid t)$ for the HMM are obtained via Bayesian inversion. Separate suffix models are trained and queried for capitalized versus lowercase words.
Knowl 5 — Context-Independent Variance-Based Weighting for Suffix Smoothing
equation
In the successive abstraction suffix smoothing recursion:

$P(t \mid l_{n-i+1}, \dots, l_n) = \frac{\hat{P}(t \mid l_{n-i+1}, \dots, l_n) + \theta_i P(t \mid l_{n-i+2}, \dots, l_n)}{1 + \theta_i}$

the smoothing weights $\theta_i$ for all levels $i = 0, \dots, m-1$ are set context-independently to the sample variance of the unconditioned maximum likelihood tag probabilities across the tagset:

$\theta_i = \frac{1}{s - 1} \sum_{j=1}^s \left( \hat{P}(t_j) - \bar{P} \right)^2$

where $s = |\mathcal{T}|$ is the total number of distinct tags in the tagset, $\hat{P}(t_j) = \frac{f(t_j)}{N}$ is the empirical unigram probability of tag $t_j$ , and $\bar{P}$ is the mean tag probability across the tagset:

$\bar{P} = \frac{1}{s} \sum_{j=1}^s \hat{P}(t_j)$

In standard POS corpora, this formula yields $\theta_i$ values typically in the range of $0.03$ to $0.10$ .
Knowl 6 — Capitalization Feature Integration into Transition Probabilities
model/method
To exploit capitalization cues for part-of-speech disambiguation, binary capitalization indicators $c_i \in \{\text{true}, \text{false}\}$ indicating whether token $w_i$ is capitalized are incorporated directly into the Markov transition distributions.

Instead of computing standard tag transitions $P(t_3 \mid t_1, t_2)$ , the model conditions on pairs of tags and capitalization states:

$P(t_3, c_3 \mid t_1, c_1, t_2, c_2)$

This formulation effectively doubles the tagset size by distinguishing capitalized from non-capitalized occurrences of every tag, with transition frequencies and linear interpolation formulas updated accordingly.
Knowl 7 — Beam Search Pruning in Viterbi POS Decoding
model/method
To accelerate decoding, TnT integrates a beam search threshold into the Viterbi algorithm. At each token position $i$ , after evaluating forward probabilities $\delta$ across states, any state whose $\delta$ satisfies:

$\delta < \frac{\delta_{\max}}{\theta}$

is excluded from subsequent path expansions, where $\delta_{\max} = \max_j \delta(j, i)$ is the highest path probability at the current position and $\theta$ is the beam threshold factor.

Setting $\theta = 1000$ doubles the decoding throughput (achieving between 30,000 and 60,000 tokens per second on a 500 MHz Pentium) without any observable degradation in tagging accuracy compared to exact Viterbi decoding.
Knowl 8 — Tagging Confidence Metric via Probability Ratio
model/method
TnT estimates the reliability of each assigned part-of-speech tag using the ratio between the probability of the most likely tag sequence assignment $t_{\text{best}}$ and the probability of the best alternative assignment $t_{\text{alt}}$ :

$R = \frac{P(t_{\text{best}})}{P(t_{\text{alt}})}$

For unambiguously tagged tokens, $R = \infty$ . An assignment is designated reliable if $R \ge \theta_{\text{reliability}}$ for a threshold $\theta_{\text{reliability}} \ge 1$ .

On the NEGRA and Penn Treebank corpora, selecting assignments with high ratio thresholds isolates subsets comprising 62%–65% of all tokens with accuracy exceeding 99.4%, while the complementary unreliable subsets exhibit accuracy below 92%, enabling selective manual review or downstream ambiguity retention.

Knowl 9 — Part-of-Speech Tagging Accuracy on NEGRA and Penn Treebank Corpora

data/table

TnT's tagging performance was evaluated on the German NEGRA corpus (20,000 sentences, 355,000 tokens) and the English Penn Treebank Wall Street Journal corpus (approx. 50,000 sentences, 1.2 million tokens) using 10-fold cross-validation with disjoint contiguous 90% training / 10% test splits.

The 96.7% overall accuracy on Penn Treebank matches or slightly exceeds the 96.6% accuracy reported by Ratnaparkhi (1996) for Maximum Entropy tagging. On both corpora, known-word accuracy exceeds 95% with as few as 1,000 training tokens.

Coverage note — No substantial contributed material was omitted; third-party black-box tagger comparison rankings cited in the introduction and discussion were excluded as background.

References

1.Thorsten Brants, Wojciech Skut, and Hans Uszkoreit. 1999. Syntactic annotation of a German newspaper corpus. In Proceedings of the ATALA Treebank Workshop, pages 69–76, Paris, France.
2.Eric Brill. 1993. A Corpus-Based Approach to Language Learning. Ph.D. Dissertation, Department of Computer and Information Science, University of Pennsylvania.
3.Eugene Charniak, Curtis Hendrickson, Neil Jacobson, and Mike Perkowitz. 1993. Equations for part-of-speech tagging. In Proceedings of the Eleventh National Conference on Artificial Intelligence, pages 784–789, Menlo Park: AAAI Press/MIT Press.
4.Doug Cutting, Julian Kupiec, Jan Pedersen, and Penelope Sibun. 1992. A practical part-of-speech tagger. In Proceedings of the 3rd Conference on Applied Natural Language Processing (ACL), pages 133–140.
5.Walter Daelemans, Jakub Zavrel, Peter Berck, and Steven Gillis. 1996. Mbt: A memory-based part of speech tagger-generator. In Proceedings of the Workshop on Very Large Corpora, Copenhagen, Denmark.
6.Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330.
7.Lawrence R. Rabiner. 1989. A tutorial on Hidden Markov Models and selected applications in speech recognition. In Proceedings of the IEEE, volume 77(2), pages 257–285.
8.Adwait Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of the Conference on Empirical Methods in Natural Language Processing EMNLP-96, Philadelphia, PA.
9.Christer Samuelsson. 1993. Morphological tagging based entirely on Bayesian inference. In 9th Nordic Conference on Computational Linguistics NODALIDA-93, Stockholm University, Stockholm, Sweden.
10.Helmut Schmid. 1995. Improvements in part-of-speech tagging with an application to German. In Helmut Feldweg and Erhard Hinrichts, editors, Lexikon und Text. Niemeyer, Tübingen.
11.Wojciech Skut, Brigitte Krenn, Thorsten Brants, and Hans Uszkoreit. 1997. An annotation scheme for free word order languages. In Proceedings of the Fifth Conference on Applied Natural Language Processing ANLP-97, Washington, DC.
12.Hans van Halteren, Jakub Zavrel, and Walter Daelemans. 1998. Improving data driven wordclass tagging by system combination. In Proceedings of the International Conference on Computational Linguistics COLING-98, pages 491–497, Montreal, Canada.
13.Martin Volk and Gerold Schneider. 1998. Comparing a statistical and a rule-based tagger for german. In Proceedings of KONVENS-98, pages 125–137, Bonn.
14.Jakub Zavrel and Walter Daelemans. 1999. Evaluatie van part-of-speech taggers voor het corpus gesproken nederlands. CGN technical report, Katholieke Universiteit Brabant, Tilburg.

Citation

MLA

Brants, T. “TnT - A Statistical Part-of-Speech Tagger”. Proceedings of ANLP-2000, Seattle, WA, 2000, http://arxiv.org/abs/cs/0003055v1.

APA

Brants, T. (2000). TnT - A Statistical Part-of-Speech Tagger. Proceedings of ANLP-2000, Seattle, WA. http://arxiv.org/abs/cs/0003055v1

Chicago

Brants, T. 2000. “TnT - A Statistical Part-of-Speech Tagger”. Proceedings of ANLP-2000, Seattle, WA. http://arxiv.org/abs/cs/0003055v1.

Harvard

Brants, T. (2000) “TnT - A Statistical Part-of-Speech Tagger”, Proceedings of ANLP-2000, Seattle, WA [Preprint]. Available at: http://arxiv.org/abs/cs/0003055v1.

Vancouver

1. Brants T (2000) TnT - A Statistical Part-of-Speech Tagger. Proceedings of ANLP-2000, Seattle, WA

BibTeX

@article{brants2000tnt,
  title = {TnT - A Statistical Part-of-Speech Tagger},
  author = {Brants, Thorsten},
  year = {2000},
  journal = {Proceedings of ANLP-2000, Seattle, WA},
  url = {http://arxiv.org/abs/cs/0003055v1},
  eprint = {cs/0003055}
}

Metadata:arXiv

Access the Paper

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

Open PDF

Corpus	Percentage Unknowns	Known Accuracy (%)	Unknown Accuracy (%)	Overall Accuracy (%)
NEGRA corpus	11.9%	97.7 $\pm$ 0.23	89.0 $\pm$ 0.72	96.7 $\pm$ 0.29
Penn Treebank	2.9%	97.0 $\pm$ 0.15	85.5 $\pm$ 0.69	96.7 $\pm$ 0.15

TnT – A Statistical Part-of-Speech Tagger

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — TnT Second-Order Hidden Markov Model Tagging Formulation

Knowl 2 — Deleted Interpolation Algorithm for Estimating Linear Interpolation Weights

Knowl 3 — Context-Independent Linear Interpolation Smoothing for Trigram Transitions

Knowl 4 — Successive Abstraction Suffix Model for Unknown Word Handling

Knowl 5 — Context-Independent Variance-Based Weighting for Suffix Smoothing

Knowl 6 — Capitalization Feature Integration into Transition Probabilities

Knowl 7 — Beam Search Pruning in Viterbi POS Decoding

Knowl 8 — Tagging Confidence Metric via Probability Ratio

Knowl 9 — Part-of-Speech Tagging Accuracy on NEGRA and Penn Treebank Corpora

References

Citation

BibTeX

Access the Paper