Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Part-of-Speech Tagging › Statistical Taggers

Michael BrenndoerferApril 16, 20259 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 36Part-of-Speech Tagging › Statistical Taggers

Reading section 7 of 18 · Statistical Taggers · 9 minSection 7 of 18 · 9 min

Section 7 of 18 · 9 min read

Part-of-Speech Tagging › Statistical TaggersOne section · Sections in this chapter7 / 18 ↓

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Statistical taggers learn tag assignments from annotated corpora without hand-crafted rules. They model the probability of tag sequences and select the most probable sequence.

Baseline: Most-Frequent-TagLink Copied

The simplest statistical tagger assigns each word its most frequent tag from the training corpus and assigns a default tag (typically NN) to unknown words. Despite its simplicity, this baseline achieves surprisingly high accuracy: around 90-92% on standard benchmarks. Most words in natural text are unambiguous in context, and even for ambiguous words, the most frequent reading is often correct.

This baseline is important for calibration. Any more sophisticated method must substantially beat 90%+ accuracy to justify its complexity.

In[13]:

Code

import nltk

nltk.download("brown", quiet=True)
nltk.download("universal_tagset", quiet=True)

from collections import Counter, defaultdict

from nltk.corpus import brown

# Load a subset of Brown corpus
sents = brown.tagged_sents(tagset="universal")[:4000]
train_sents = sents[:3200]
test_sents = sents[3200:]

# Build word -> most-frequent-tag mapping
word_tag_freq = defaultdict(Counter)
for sent in train_sents:
    for word, tag in sent:
        word_tag_freq[word.lower()][tag] += 1

most_frequent_tag = {
    w: c.most_common(1)[0][0] for w, c in word_tag_freq.items()
}

# Compute overall tag distribution for default
all_tag_counts = Counter(tag for sent in train_sents for _, tag in sent)
default_tag = all_tag_counts.most_common(1)[0][0]  # Most common overall tag

Out[14]:

Console

Baseline Most-Frequent-Tag Tagger
========================================
Training sentences : 3,200
Test sentences     : 800
Default tag        : NOUN
Accuracy           : 0.907  (90.7%)

The 90%+ baseline accuracy comes largely from function words, which are extremely common and almost never ambiguous. "The" is almost always DT; "of" is almost always ADP. The hard cases are the content words with multiple possible tags.

Probabilistic Sequence ModelingLink Copied

Better taggers model the entire tag sequence jointly. The key idea is to find the tag sequence $\mathbf{t} = (t_1, t_2, \ldots, t_n)$ that maximizes the probability given the word sequence $\mathbf{w} = (w_1, w_2, \ldots, w_n)$ :

\hat{\mathbf{t}} = \arg\max_{\mathbf{t}} P(\mathbf{t} \mid \mathbf{w})

This formulation treats tagging as searching for the globally optimal sequence, not assigning each token independently. The key question is how to model $P(\mathbf{t} \mid \mathbf{w})$ efficiently without enumerating all possible tag sequences (which grows exponentially with sentence length).

Hidden Markov Models (covered in the next chapter) approach this by decomposing the joint probability $P(\mathbf{w}, \mathbf{t})$ using the Markov assumption: each tag depends only on the previous tag (the transition probability) and each word depends only on its tag (the emission probability). This decomposition allows efficient computation via dynamic programming.

P(\mathbf{w}, \mathbf{t}) = \prod_{i=1}^{n} P(t_i \mid t_{i-1}) \cdot P(w_i \mid t_i)

where:

$P(t_i \mid t_{i-1})$ : the probability of transitioning from tag $t_{i-1}$ to tag $t_i$ (transition probability)
$P(w_i \mid t_i)$ : the probability of generating word $w_i$ given tag $t_i$ (emission probability)

Both probability tables are estimated from counts in the annotated training corpus.

To understand why this decomposition is useful, consider the naive alternative. Without any structural assumption, $P(\mathbf{t} \mid \mathbf{w})$ is a distribution over all possible tag sequences of length $n$ . If there are $K$ possible tags, there are $K^n$ possible sequences for a sentence of length $n$ . For English with 36 Penn Treebank tags and a sentence of 20 words, that is $36^{20} \approx 10^{31}$ sequences to compare. The Markov assumption reduces this to $O(K^2 \cdot n)$ computations using the Viterbi algorithm, which is polynomial rather than exponential.

The Markov assumption is a simplification, of course. In reality, the correct tag for a word might depend on context three or four words away. Trigram HMMs (where each tag depends on the two previous tags) capture more context and generally outperform bigram HMMs. But even trigram models eventually hit the limits of local context modeling, and the jump to CRFs and neural models comes from allowing conditioning on the full input sequence.

Transition and Emission ProbabilitiesLink Copied

Let us build intuition for these two probability types by computing them from real data.

In[15]:

Code

# Estimate transition probabilities: P(tag_i | tag_{i-1})
# Count bigrams of consecutive tags
tag_bigrams = Counter()
tag_unigrams = Counter()

for sent in train_sents:
    tags = ["<START>"] + [t for _, t in sent] + ["<END>"]
    for i in range(len(tags) - 1):
        tag_bigrams[(tags[i], tags[i + 1])] += 1
        tag_unigrams[tags[i]] += 1


def transition_prob(prev_tag, curr_tag, bigrams, unigrams, vocab_size):
    """Laplace-smoothed transition probability."""
    numerator = bigrams[(prev_tag, curr_tag)] + 1
    denominator = unigrams[prev_tag] + vocab_size
    return numerator / denominator


# Estimate emission probabilities: P(word | tag)
# Count (word, tag) co-occurrences
emission_counts = defaultdict(Counter)
for sent in train_sents:
    for word, tag in sent:
        emission_counts[tag][word.lower()] += 1


def emission_prob(word, tag, emit_counts, unigrams, vocab_size):
    """Laplace-smoothed emission probability."""
    tag_total = sum(emit_counts[tag].values())
    numerator = emit_counts[tag].get(word.lower(), 0) + 1
    denominator = tag_total + vocab_size
    return numerator / denominator

Out[16]:

Console

Transition Probabilities: P(next_tag | current_tag)
-------------------------------------------------------
            NOUN    VERB     ADJ     DET     ADP
DET        0.665   0.054   0.220   0.005   0.008
NOUN       0.282   0.133   0.016   0.012   0.206
VERB       0.137   0.208   0.046   0.175   0.175
ADJ        0.722   0.018   0.062   0.005   0.070

Emission Probabilities: P(word | tag) for selected words
-------------------------------------------------------
  P('the' | DET)  =  0.5637
  P('run' | VERB)  =  0.0013
  P('quick' | ADJ)  =  0.0012
  P('of' | ADP)  =  0.2358
  P('barked' | NOUN)  =  0.0000

The transition table reveals clear linguistic patterns. After DET (determiner), NOUN gets a high probability because determiners introduce noun phrases. After VERB, ADP (adposition/preposition) is likely because verbs are often followed by prepositional phrases. These patterns are exactly what a syntactic parser exploits, but here they emerge automatically from corpus statistics.

The emission probabilities tell a complementary story. A word like "the" has very high emission probability under the DET tag and near-zero probability under any other tag. A word like "run" has moderate emission probability under both VERB and NOUN. This reflects its ambiguity. The ratio of these emission probabilities is what the HMM uses to decide which tag is more likely in context: if the transition probabilities favor VERB in a given position, and "run" has moderate emission probability under VERB, then VERB wins.

Laplace smoothing (adding 1 to all counts) prevents zero probabilities for unseen word-tag combinations. Without smoothing, any word not seen in training with a given tag gets an emission probability of exactly 0, which would prevent the model from ever assigning that tag to that word. Smoothing distributes a small amount of probability mass to unseen combinations, allowing the model to handle novel words by falling back on the tag distribution implied by the transition probabilities.

A MaxEnt Sequence TaggerLink Copied

Beyond HMMs, discriminative classifiers can be applied in a "greedy left-to-right" mode: tag each word using the current word's features plus the predicted tag of the previous word. This is not globally optimal like Viterbi decoding, but it allows rich, overlapping feature sets.

In[17]:

Code

from sklearn.feature_extraction import DictVectorizer
from sklearn.preprocessing import LabelEncoder


def word_features(sent_words, i, prev_tag=None):
    """Features for position i in sentence."""
    word = sent_words[i]
    feats = {
        "word": word.lower(),
        "suffix2": word[-2:].lower() if len(word) >= 2 else word.lower(),
        "suffix3": word[-3:].lower() if len(word) >= 3 else word.lower(),
        "is_upper": word.isupper(),
        "is_title": word.istitle(),
        "is_digit": word.isdigit(),
        "has_hyphen": "-" in word,
        "is_first": i == 0,
        "prev_word": sent_words[i - 1].lower() if i > 0 else "<START>",
        "next_word": sent_words[i + 1].lower()
        if i < len(sent_words) - 1
        else "<END>",
    }
    if prev_tag is not None:
        feats["prev_tag"] = prev_tag
    return feats


# Build training data
X_list, y_list = [], []
for sent in train_sents:
    words = [w for w, _ in sent]
    tags = [t for _, t in sent]
    for i, (word, tag) in enumerate(zip(words, tags)):
        prev_tag = tags[i - 1] if i > 0 else "<START>"
        X_list.append(word_features(words, i, prev_tag))
        y_list.append(tag)

vec = DictVectorizer(sparse=True)
le = LabelEncoder()

X_train = vec.fit_transform(X_list)
y_train = le.fit_transform(y_list)

In[18]:

Code

# Train logistic regression classifier
from sklearn.linear_model import LogisticRegression

clf = LogisticRegression(
    max_iter=300, C=1.0, solver="saga", n_jobs=-1, random_state=42
)
clf.fit(X_train, y_train)

In[19]:

Code

def tag_sentence_greedy(words, clf, vec, le):
    """Tag a sentence left-to-right using predicted previous tags."""
    predicted_tags = []
    prev_tag = "<START>"
    for i, word in enumerate(words):
        feats = word_features(words, i, prev_tag)
        x = vec.transform([feats])
        tag_idx = clf.predict(x)[0]
        tag = le.inverse_transform([tag_idx])[0]
        predicted_tags.append(tag)
        prev_tag = tag
    return list(zip(words, predicted_tags))


# Evaluate on test set
correct = total = 0
for sent in test_sents:
    words = [w for w, _ in sent]
    gold = [t for _, t in sent]
    pred = [t for _, t in tag_sentence_greedy(words, clf, vec, le)]
    correct += sum(g == p for g, p in zip(gold, pred))
    total += len(gold)

maxent_accuracy = correct / total

Out[20]:

Console

MaxEnt (Logistic Regression) Sequence Tagger
=============================================
Training tokens : 68,422
Feature space   : 33,322 features
Tag classes     : 12
Accuracy        : 0.947  (94.7%)

Improvement over most-frequent baseline: 4.0 pp

The improvement from adding rich features and the previous predicted tag demonstrates the value of contextual information. Even a simple greedy left-to-right decoding with logistic regression substantially outperforms the most-frequent-tag baseline.

The greedy decoding strategy introduces a potential problem: errors compound. If the tagger predicts the wrong tag for position $i$ , it uses that wrong tag as a feature for position $i+1$ , which can cause a cascade of errors. For most sentences, this compounding effect is mild because the model can recover from a single-token error once sufficient new context is available. But in pathological cases, especially at the start of ambiguous sentences, a single wrong prediction can derail the entire sequence.

This is one of the key advantages of global decoding methods like the Viterbi algorithm used in HMMs and CRFs. Those methods compute the globally optimal sequence rather than making locally greedy decisions, so a single locally bad choice does not necessarily propagate. The tradeoff is computational: greedy decoding is $O(n \cdot K)$ while Viterbi is $O(n \cdot K^2)$ , where $K$ is the number of tags. For small tag sets (like the 17 UD tags or 36 PTB tags), Viterbi is still very fast in practice.