Morphology and Sequence Labeling

Introduction

Natural language processing (NLP) systems rarely operate directly on complete documents. They analyze sequences of linguistic units—characters, morphemes, words, and sentences—and assign structure to those sequences. Two foundational tasks are therefore morphological analysis and sequence labeling.

Morphological analysis studies how words are constructed and how their forms express grammatical or lexical meaning. Sequence labeling assigns a label to each item in an ordered input, such as a part-of-speech (POS) tag to every word or a named-entity category to every token. These tasks support information extraction, search, speech recognition, machine translation, question answering, text classification, and conversational systems.

This chapter develops finite-state methods for word formation, stemming, and lemmatization, followed by probabilistic and discriminative models for POS tagging and named-entity recognition (NER). The emphasis is on modeling assumptions, implementation choices, evaluation, and the limitations of each approach.

Learning Objectives

By the end of this chapter, you should be able to:

1. Explain morphemes, morphological processes, and the distinction between inflection and derivation.
2. Model morphological analysis and generation using finite-state transducers.
3. Compare stemming and lemmatization and implement rule-based approaches.
4. Formulate POS tagging as a sequence-labeling problem.
5. Derive and apply the principal equations of hidden Markov models (HMMs).
6. Explain maximum-entropy and conditional random field (CRF) models.
7. Design an NER pipeline and evaluate sequence-labeling systems appropriately.
8. Critically assess ambiguity, domain shift, multilinguality, and ethical risks.

1. Morphological Foundations

1.1 Morphemes and word structure

A morpheme is the smallest linguistic unit that contributes meaning or grammatical function. In unhappiness, un-, happy, and -ness are morphemes. A morpheme may be:

• Free, able to occur independently, as in book or quick.
• Bound, requiring attachment to another form, as in -ed, -s, or un-.
• Inflectional, expressing grammatical properties without normally creating a new dictionary entry, as in walk → walked.
• Derivational, creating a new lexeme or changing category, as in teach → teacher or kind → unkind.

A word’s lemma is its canonical dictionary form. The forms walk, walks, walked, and walking commonly share the lemma walk. A lexeme is the abstract vocabulary item represented by its inflected forms.

Languages differ greatly in morphological typology. English has relatively limited inflection but substantial derivation. Turkish is often described as agglutinative because grammatical morphemes can be concatenated transparently. Arabic frequently exhibits nonconcatenative root-and-pattern morphology. Chinese has comparatively little inflectional morphology but relies heavily on compounding and context. A robust NLP system must not assume that English-like word formation is universal.

1.2 Morphological processes

Important processes include:

Morphological analysis may be segmentation, which identifies morpheme boundaries; morphological parsing, which assigns features such as tense and number; or generation, which produces a surface form from a lemma and grammatical features.

For example, an analysis of replayed might be represented as:

re + play + ed

with features such as PREFIX=RE, LEMMA=play, and TENSE=PAST. In real systems, analyses may be ambiguous: unlockable can mean “not able to be locked” or “able to be unlocked.”

2. Finite-State Morphology

2.1 Finite-state machines and transducers

A finite-state automaton recognizes strings belonging to a regular language. A finite-state transducer (FST) maps an input string to an output string, possibly inserting, deleting, or replacing symbols. In morphology, one side commonly represents a lexical form and the other a surface form.

An FST can encode:

• Lexical entries and morpheme boundaries.
• Morphological feature combinations.
• Spelling changes at morpheme boundaries.
• Constraints that rule out impossible combinations.

A simple lexical representation might be:

walk + V + PAST → walked

The transducer maps the lexical sequence to the surface sequence by deleting the abstract boundary and realizing the past-tense suffix. Another rule can encode city + PL → cities, where y changes to ie before plural s.

FST composition is especially useful. Suppose one transducer maps a lemma and features to an intermediate representation, and another applies orthographic rules. Their composition produces a single transducer that directly maps lexical input to surface output. In notation, if T₁ and T₂ are compatible transducers, their composition is written:

Here, ∘ means that the output of T₁ becomes the input to T₂. Composition is valid when the intermediate symbol sets are compatible. The resulting network can support both generation and, if appropriately constructed, analysis by reversing the direction.

2.2 Analysis and generation

A morphological generator receives a lemma and features and returns one or more surface forms. An analyzer performs the reverse operation. Because language is ambiguous, the analyzer may return multiple candidates:

flies →

• fly + N + PL
• fly + V + 3SG

Disambiguation generally requires sentence context. In “Birds fly,” fly is a plural noun or a verb depending on the sentence; in “She flies,” the verb analysis is strongly favored by syntax and agreement.

Finite-state morphology is attractive because it is fast, interpretable, and reliable for productive regular patterns. However, it struggles with lexical exceptions, historical irregularity, semantic ambiguity, and phenomena that require unbounded agreement or broad context. It is therefore often combined with statistical sequence models.

3. Stemming and Lemmatization

3.1 Stemming

Stemming reduces related word forms to a common stem, usually through suffix-stripping or rewrite rules. A stem need not be a valid word. For example, an aggressive stemmer may map connected, connection, and connecting to forms such as connect or connect. The objective is usually information retrieval or approximate normalization, not linguistic correctness.

A stemmer may apply ordered rules such as:

1. Remove -ing if the remaining string satisfies a minimum length condition.
2. Remove -ed under an appropriate context.
3. Convert terminal -ies to -i.

Rule ordering matters. Applying a plural rule before a derivational rule can produce a different result from applying them in the reverse order. Classic algorithms such as the Porter stemmer use carefully designed suffix regions and conditions; Snowball provides language-specific successors and implementations.

3.2 Lemmatization

Lemmatization maps a word to a linguistically valid lemma, usually using a lexicon, morphological rules, and POS or other contextual information. Thus:

A lemmatizer is generally more precise than a stemmer but requires more resources and computation. Lemmatization is useful when downstream systems need interpretable lexical forms, morphological features, or semantic normalization.

3.3 Comparison and practical choice

Overstemming incorrectly merges unrelated words, whereas understemming fails to merge related forms. Evaluation must therefore use the intended application. For search, a slightly aggressive stemmer may improve recall; for semantic or linguistic analysis, it may be unacceptable.

4. Sequence Labeling

Given an input sequence of tokens x₁, x₂, ..., x_T, a sequence-labeling system predicts labels y₁, y₂, ..., y_T. POS tagging uses labels such as NOUN, VERB, and ADJ; NER commonly uses the BIO scheme:

• B-PER: beginning of a person entity.
• I-PER: continuation of a person entity.
• B-ORG, I-ORG, B-LOC, I-LOC: corresponding organization and location labels.
• O: outside any entity.

For “Ada Lovelace visited London,” a possible sequence is:

B-PER I-PER O B-LOC

The BIO scheme distinguishes adjacent entities and multi-token spans. The BIOES scheme adds E for the end and S for a single-token entity, sometimes making boundary information easier to learn.

Sequence labeling differs from independent classification. The best label for a token depends on neighboring words and labels. For example, May may be a month, a person’s name, or a modal verb. A model should use lexical, contextual, orthographic, syntactic, and document-level evidence.

5. Hidden Markov Models for POS Tagging

5.1 Model assumptions

An HMM represents an observed token sequence generated by hidden states. For POS tagging:

• Observations are words x_t.
• Hidden states are POS tags y_t.
• Transition probabilities model tag-to-tag behavior.
• Emission probabilities model words generated by tags.

The standard first-order HMM assumes:

1. The current tag depends only on the preceding tag.
2. The current word depends only on the current tag.

Under these assumptions, the joint probability is:

Here, T is sequence length, P(y₁) is the initial-state probability, P(y_t|y_t-1) is a transition probability, and P(x_t|y_t) is an emission probability. The probabilities are conditional on the model parameters and must be estimated from training data.

The most probable tag sequence is:

Because direct enumeration is exponential in T, the Viterbi algorithm uses dynamic programming. Define δ_t(s) as the highest probability of a path ending in state s at position t. Then:

The maximization ranges over all previous states r. Backpointers retain the maximizing predecessor. Initialization uses the start distribution and termination selects the highest final value. In implementation, log probabilities are preferred to avoid numerical underflow; products become sums and maximization is unchanged in principle.

5.2 Worked Viterbi example

Consider the two-word sentence “dogs bark” and two tags, N and V. Suppose:

• Initial probabilities: P(N)=0.6, P(V)=0.4.
• Transitions: P(N|N)=0.3, P(V|N)=0.7, P(N|V)=0.8, P(V|V)=0.2.
• Emissions: P(dogs|N)=0.5, P(dogs|V)=0.1, P(bark|N)=0.1, P(bark|V)=0.6.

At position 1:

• δ₁(N)=0.6×0.5=0.30.
• δ₁(V)=0.4×0.1=0.04.

At position 2:

• For N: max of 0.30×0.3=0.09 and 0.04×0.8=0.032, then multiply by P(bark|N)=0.1, giving 0.009.
• For V: max of 0.30×0.7=0.21 and 0.04×0.2=0.008, then multiply by P(bark|V)=0.6, giving 0.126.

The best final state is V, with a backpointer to N; hence the predicted sequence is N V. This example illustrates why both lexical evidence and tag transitions matter.

5.3 Smoothing and unknown words

Maximum-likelihood estimates can assign zero probability to unseen events. Additive smoothing replaces a count-based estimate with:

where α>0 is a smoothing constant and K is the number of possible outcomes. The formula assumes a categorical distribution and distributes pseudocount mass uniformly. More sophisticated systems use interpolation, deleted interpolation, suffix models, capitalization, word shape, and pretrained representations for unknown words.

HMM strengths include conceptual clarity, efficient decoding, and probabilistic interpretation. Their independence assumptions are restrictive: a first-order HMM cannot directly represent long-distance context, overlapping features, or arbitrary capitalization and orthographic evidence without expanding the state space.

6. Maximum-Entropy Sequence Models

A maximum-entropy classifier estimates a conditional distribution over labels using features. For a token or local context represented by feature vector f(x,y), the model is:

Here, θ is a learned weight vector, · is the dot product, and the denominator normalizes over all candidate labels. Features may indicate the current word, suffix, capitalization, neighboring words, preceding POS tag, or whether a token contains digits.

The model is called maximum entropy because, subject to feature-derived constraints, it selects the distribution with greatest entropy rather than adding unsupported assumptions. Training commonly maximizes conditional log-likelihood with regularization. With labeled examples (x^(i),y^(i)), an L2-regularized objective can be written:

where λ≥0 controls regularization strength. Larger λ penalizes large weights more strongly. Optimization may use iterative scaling, limited-memory quasi-Newton methods, or stochastic gradient methods.

For sequence labeling, local maximum-entropy models may condition on previously predicted labels. Such models can exploit rich features but may suffer from label bias and exposure bias: errors in earlier predictions affect later decisions, and training contexts may differ from inference contexts.

7. Conditional Random Fields

7.1 Definition

A linear-chain CRF directly models the conditional probability of a complete label sequence given an observation sequence:

The feature functions f_k may depend on adjacent labels, the current label, the complete observation sequence, and position t. Z(x) is the partition function:

The partition function sums scores over every legal label sequence, making the distribution normalized. A CRF does not require observations to be generated from labels; this permits overlapping, non-independent features.

7.2 Training and decoding

Training maximizes regularized conditional log-likelihood. Both the partition function and its gradients can be computed efficiently by the forward–backward algorithm. Decoding seeks the highest-scoring sequence:

For a linear-chain CRF, Viterbi decoding applies because the score decomposes over adjacent labels. The computational cost is approximately O(TL²), where T is sequence length and L is the number of labels, ignoring feature-extraction cost. The same order applies to standard forward–backward inference.

7.3 HMM, maximum entropy, and CRF comparison

CRFs often outperform basic HMMs when sufficient labeled data and informative features are available. They are not automatically superior: a poorly designed feature set, small training corpus, or severe domain shift can erase the advantage.

8. Named-Entity Recognition

NER identifies spans referring to entities such as people, organizations, locations, products, dates, or events. A practical pipeline includes:

1. Tokenization: preserve punctuation, hyphens, URLs, and relevant symbols.
2. Label design: define entity types and a BIO or BIOES convention.
3. Feature construction: use lexical, orthographic, contextual, gazetteer, and syntactic features.
4. Sequence modeling: train an HMM, maximum-entropy model, CRF, or neural model.
5. Post-processing: merge valid spans, normalize dates or locations, and apply domain rules.
6. Evaluation: compare predicted spans with gold-standard spans.

Useful features include capitalization patterns, character prefixes and suffixes, digit patterns, surrounding words, POS tags, membership in organization lists, and embeddings. However, gazetteers can introduce bias and fail for new entities. Capitalization is informative in English but unreliable in all-uppercase text and in languages whose writing systems do not mark case.

NER is domain-specific. In biomedical text, entity boundaries and types may involve genes, proteins, diseases, and chemical compounds. In finance, entities may include issuers, instruments, regulators, and monetary values. An annotation scheme must define nested entities, discontinuous spans, abbreviations, and ambiguous cases before model training.

9. Evaluation and Error Analysis

Token accuracy is common for POS tagging:

For NER, entity-level precision, recall, and F1 are more informative:

Here, TP is the number of correctly predicted entities, FP is the number of predicted entities absent from the gold annotation, and FN is the number of gold entities missed by the system. In strict entity-level evaluation, a prediction is correct only if both its span boundaries and type match exactly. Token-level scores can conceal boundary errors and should not replace span-level analysis.

Evaluation should use document-level or source-aware splits where leakage is possible. Randomly splitting sentences from the same documents can produce unrealistically high scores. Report performance by entity type, length, domain, language variety, and frequency. Inspect confusion matrices and representative errors rather than relying only on one aggregate number.

10. Applied Case: Financial News Entity Extraction

Background

This illustrative case concerns a financial analytics team processing news articles to identify companies, executives, locations, financial instruments, and monetary values. The system feeds a monitoring dashboard and must recognize new company names and ambiguous abbreviations.

Problem

A baseline dictionary matcher has high precision for well-known companies but misses newly listed firms, inflected names, and entities with punctuation. It also falsely labels ordinary words that happen to match a company name. The team needs a trainable sequence-labeling solution.

Analysis

The team defines BIOES labels for ORG, PERSON, GPE, PRODUCT, and MONEY. It creates annotation guidelines for possessives, ticker symbols, nested names, and monetary expressions. The corpus is split by publication date so that future articles are not inadvertently represented in training data.

Approach

A CRF is trained with features for the current and neighboring tokens, lowercase forms, prefixes and suffixes, capitalization, character classes, POS tags, dictionary indicators, and selected word-shape patterns. A finite-state module normalizes dates and currency expressions. A review queue sends low-confidence or previously unseen patterns to human annotators. The team compares the CRF against the dictionary baseline and an HMM baseline.

Outcome

The CRF improves recall for unseen organizations and handles contextual ambiguity better than the dictionary matcher. The largest remaining errors involve nested entities, company names that resemble ordinary phrases, and documents containing noisy automatic transcripts. Error analysis reveals that high overall F1 hides weak performance on rare entity types. The team therefore reports per-type scores and monitors performance after each change in annotation policy.

Learning points

1. Label definitions and annotation consistency are as important as model choice.
2. Finite-state rules remain valuable for structured expressions and normalization.
3. Conditional sequence models benefit from contextual and orthographic features.
4. Temporal evaluation is essential when the production environment changes.
5. Human review is a governance mechanism, not merely a fallback for failed automation.

11. Challenges, Ethics, and Contemporary Practice

Ambiguity and domain shift

Words and names change meaning across domains. A model trained on edited news may fail on social media, legal documents, or clinical notes. New products, geopolitical events, and organizations create out-of-vocabulary entities. Continuous evaluation and carefully governed adaptation are necessary.

Multilingual and low-resource settings

Morphological richness increases the number of surface forms and data sparsity. Subword features, character models, multilingual lexicons, transfer learning, and active learning can help. Yet transfer is not guaranteed: label inventories, tokenization conventions, and cultural naming patterns differ across languages.

Annotation and fairness

Annotation decisions encode institutional assumptions. Entity categories may inadequately represent Indigenous names, non-Western naming conventions, gender diversity, or informal identities. Systems used for hiring, policing, immigration, credit, or healthcare can amplify errors if names are treated as reliable proxies for sensitive attributes. Teams should document label definitions, measure subgroup performance where legally and ethically appropriate, protect personal data, and provide human oversight for consequential decisions.

Best practices

• Establish a clear annotation manual and measure inter-annotator agreement.
• Keep training, development, and test data strictly separated.
• Use explicit handling for unknown words, Unicode, punctuation, and code-switching.
• Prefer span-level evaluation for NER.
• Preserve confidence scores and abstention options rather than forcing every prediction.
• Log model versions, lexicons, feature changes, and data provenance.
• Test on temporally and geographically distinct data.
• Combine finite-state constraints with statistical models where rules are reliable.
• Reassess performance after changes in taxonomy, domain, or editorial style.

Chapter Summary

Morphology explains how words encode lexical and grammatical information. Morphemes may be free or bound, and morphological processes include affixation, compounding, internal change, and suppletion. Finite-state transducers provide efficient, interpretable mappings between lexical representations and surface forms and are particularly effective for regular morphology and structured normalization.

Stemming is a fast, heuristic reduction method, whereas lemmatization seeks a linguistically valid canonical form and often requires lexical and contextual information. Sequence labeling assigns a structured label sequence to an input sequence. HMMs provide a generative baseline using transition and emission probabilities and decode efficiently with Viterbi. Maximum-entropy models support rich features but can suffer from local-decision problems. CRFs directly model whole label sequences, accommodate overlapping features, and use dynamic programming for training and decoding.

POS tagging and NER require attention to ambiguity, unknown words, annotation design, domain shift, and evaluation. Entity-level precision, recall, and F1 are essential for NER. In professional systems, model selection is only one part of the solution: data governance, reproducibility, fairness, human review, and continuous monitoring are equally important.

Key Terms

Morpheme: The smallest linguistic unit that contributes meaning or grammatical function.

Lemma: The canonical dictionary form associated with related word forms.

Lexeme: An abstract vocabulary item represented by its inflected forms.

Inflection: Morphological marking of grammatical properties such as tense or number.

Derivation: Word formation that creates a new lexeme or changes grammatical category.

Finite-state transducer: A finite-state device that maps strings or symbol sequences to other strings.

Morphological analysis: The identification of a word’s structure and grammatical features.

Morphological generation: Production of a surface word from a lemma and features.

Stemming: Heuristic reduction of word forms to a common stem.

Lemmatization: Mapping a word form to a valid canonical lemma.

Overstemming: Incorrectly merging unrelated words during stemming.

Sequence labeling: Assigning an ordered label to each item in an input sequence.

Part-of-speech tagging: Assigning grammatical categories to tokens.

Named-entity recognition: Detecting and classifying spans that refer to entities.

Hidden Markov model: A generative probabilistic model with hidden states and observed outputs.

Viterbi algorithm: Dynamic programming algorithm for the highest-probability state sequence.

Maximum-entropy model: A conditional model using weighted features and normalized label probabilities.

Conditional random field: A conditional sequence model that scores complete label sequences with feature functions.

BIO encoding: A labeling scheme using beginning, inside, and outside entity labels.

Partition function: The normalizing sum over all possible label sequences in a CRF.

Review Questions

5 Short Answer Questions

1. What is the difference between an inflectional and a derivational morpheme?
2. Why can a finite-state transducer be used for both morphological analysis and generation?
3. Distinguish stemming from lemmatization.
4. What do the B, I, and O labels represent in BIO encoding?
5. Why is entity-level evaluation important in NER?

5 Long Answer Questions

1. Explain the architecture of a finite-state morphological analyzer, including lexical representations, surface forms, and spelling rules.
2. Describe the HMM assumptions for POS tagging and explain how Viterbi decoding finds the best tag sequence.
3. Compare HMMs, maximum-entropy models, and CRFs in terms of probability direction, feature flexibility, and inference.
4. Design an NER pipeline for a specialized domain and justify its tokenization, labels, features, and evaluation method.
5. Discuss the principal sources of error in multilingual morphological analysis and sequence labeling.

3 Analytical / Application Questions

1. A search engine must retrieve documents containing connect, connected, and connection. Would you choose stemming, lemmatization, or both? Justify the decision in terms of recall, precision, and computational cost.
2. Design feature functions for a CRF that distinguishes organization names from ordinary noun phrases in financial news. Explain how each feature could help and where it might fail.
3. A POS tagger achieves 97% token accuracy but performs poorly on rare names and technical terms. Propose an error-analysis and improvement plan that addresses data, features, evaluation, and deployment risk.

Multiple Choice Questions with Answers

Question 1

Which statement best distinguishes stemming from lemmatization?

A. Stemming always produces a valid dictionary word, while lemmatization does not.

B. Stemming is usually heuristic reduction, while lemmatization seeks a linguistically valid canonical form.

C. Stemming requires sentence context in every case, while lemmatization never uses context.

D. Stemming applies only to verbs, while lemmatization applies only to nouns.

Correct Answer: B. Stemming is usually heuristic reduction, while lemmatization seeks a linguistically valid canonical form.

Question 2

In a finite-state morphology system, what is the principal role of a transducer?

A. To map one symbol sequence or representation to another

B. To store only numerical word-frequency counts

C. To replace all probabilistic models with neural networks

D. To calculate document-level F1 without labeled data

Correct Answer: A. To map one symbol sequence or representation to another

Question 3

In the standard HMM formulation for POS tagging, what does P(xₜ | yₜ) represent?

A. The probability of a tag given the previous tag

B. The probability of the complete sentence given its length

C. The probability of the observed word given the current tag

D. The probability of the previous word given the current word

Correct Answer: C. The probability of the observed word given the current tag

Question 4

What problem does the Viterbi algorithm solve in an HMM POS tagger?

A. It finds the highest-probability hidden-state sequence for the observations.

B. It determines the number of morphemes in every dictionary entry.

C. It calculates only the marginal probability of the first tag.

D. It removes all unknown words from the test corpus.

Correct Answer: A. It finds the highest-probability hidden-state sequence for the observations.

Question 5

Which property is characteristic of a linear-chain CRF?

A. It models observations as independent of all labels.

B. It directly models a conditional distribution over complete label sequences.

C. It requires every word to have exactly one dictionary entry.

D. It can use only one feature at each token position.

Correct Answer: B. It directly models a conditional distribution over complete label sequences.

Question 6

For the BIO sequence B-PER I-PER O B-LOC, how many entity spans are represented?

A. One

B. Two

C. Three

D. Four

Correct Answer: B. Two

Question 7

If a named-entity system predicts 80 correct entities, 20 false positives, and 10 false negatives, what is its precision?

A. 0.70

B. 0.80

C. 0.89

D. 0.90

Correct Answer: B. 0.80

Question 8

Why can a dictionary-only NER system miss newly formed company names?

A. Dictionaries cannot represent any alphabetic characters.

B. A dictionary contains only entries available when it was constructed or updated.

C. Dictionaries always label every common noun as an organization.

D. Dictionary matching cannot compare a token with a stored string.

Correct Answer: B. A dictionary contains only entries available when it was constructed or updated.

Question 9

What is a major limitation of a first-order HMM for sequence labeling?

A. It cannot use transition probabilities.

B. It cannot decode sequences efficiently.

C. Its conditional-independence assumptions restrict contextual and feature modeling.

D. It cannot assign labels to words that occur in training data.

Correct Answer: C. Its conditional-independence assumptions restrict contextual and feature modeling.

Question 10

Why should NER evaluation commonly use strict entity-level scoring?

A. It rewards predictions with incorrect boundaries if the token types are similar.

B. It checks whether both the entity span and its type are correct.

C. It avoids the need for a gold-standard annotation.

D. It measures only the speed of the tokenizer.

Correct Answer: B. It checks whether both the entity span and its type are correct.