Classical NLP and Statistical Language Models

Introduction

Natural Language Processing (NLP) is concerned with enabling computers to analyse, interpret and generate human language. Before the development of large neural language models, most practical NLP systems were constructed from symbolic rules, finite-state machines, statistical models and carefully engineered features. These classical methods remain important because they are interpretable, computationally efficient, useful in low-resource settings and foundational to modern NLP systems.

This chapter examines regular expressions, finite-state methods, n-gram language models, TF–IDF, probabilistic sequence models and feature engineering. These methods support tasks such as text classification, part-of-speech tagging, shallow parsing, named-entity recognition and information extraction.

Learning Objectives

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

1. Apply regular expressions to identify and extract linguistic patterns.
2. Explain finite-state automata and finite-state transducers in NLP.
3. Construct and evaluate unigram, bigram and trigram language models.
4. Explain smoothing, interpolation and perplexity.
5. Calculate and interpret TF–IDF features.
6. Describe probabilistic models for tagging and sequence labelling.
7. Design useful lexical, syntactic and contextual features for classification.
8. Evaluate the strengths, limitations and ethical risks of classical NLP systems.

1. Text as a Computational Object

Human language is variable, ambiguous and context-dependent. The word “bank” may denote a financial institution or the side of a river. The sentence “I saw the man with the telescope” has more than one possible syntactic interpretation. A computational system therefore needs representations that make linguistic structure measurable.

A typical classical NLP pipeline contains the following stages:

1. Normalisation: handling case, punctuation, encoding and spelling variation.
2. Segmentation: dividing text into documents, sentences or tokens.
3. Representation: converting tokens into counts, features or structured symbols.
4. Inference: assigning labels, constructing parses or extracting entities.
5. Evaluation: comparing predictions with annotated reference data.

Preprocessing decisions are not neutral. Lowercasing may improve matching but remove information about proper nouns. Removing punctuation may simplify classification but damage sentiment or syntactic analysis. Good systems therefore define preprocessing according to the task rather than applying a fixed sequence mechanically.

Important terminology

A token is an occurrence of a linguistic unit in a text. A type is a distinct token form. In “data data science”, there are three tokens but two types. A corpus is a collection of texts. A vocabulary is the set of recognised types. A sentence boundary marks the beginning or end of a sentence, while tokenisation identifies word-like or symbol-like units.

2. Regular Expressions for Pattern Recognition

A regular expression (regex) describes a set of strings using symbols and operators. It is especially useful for predictable surface patterns such as dates, product codes, email-like strings, URLs and measurements.

Common constructs include:

For example, a simple date pattern may be written as \b[0-9]{4}-[0-9]{2}-[0-9]{2}\b. This recognises strings in the form YYYY-MM-DD, but it does not guarantee that the date is calendar-valid; it may accept month 19. Regex should therefore be viewed as pattern recognition, not full semantic validation.

A regex for extracting an amount with an optional currency symbol might be (?:£|\$|€)?[0-9]+(?:\.[0-9]{2})?. The non-capturing group is implementation-dependent but common in modern regex engines.

Regex limitations

Regular expressions are weak at representing long-distance dependencies, nested structures and contextual meaning. They cannot reliably determine whether “May” is a month or a person’s name without additional context. Complex regexes can also become difficult to maintain and may create catastrophic backtracking in unsafe implementations. Production systems should use timeouts, input limits and tested patterns when processing untrusted input.

3. Finite-State Methods

A finite automaton is a computational model with a finite set of states and transitions. A deterministic finite automaton (DFA) has exactly one possible transition for each state and input symbol under a given transition function. A nondeterministic finite automaton (NFA) may have several possible transitions, including epsilon transitions.

Formally, an automaton can be represented as:

Here, Q is the finite set of states, Σ is the input alphabet, δ is the transition function, q₀ is the initial state and F is the set of accepting states. The model accepts a string if processing the complete string ends in an accepting state.

Finite-state methods are important in NLP because many lexical phenomena are local and sequential. Applications include tokenisation, morphological analysis, spelling rules, phonological transformations and shallow grammar recognition.

A finite-state transducer (FST) extends an automaton by producing output symbols. It can map an input string to an output string, for example:

• walked → walk + PAST
• unhappiness → un + happy + ness
• surface spelling → normalised spelling

FSTs can be composed. If transducer T₁ maps spelling to morphological analysis and T₂ maps morphology to a grammatical representation, their composition can perform both transformations in one network. This makes finite-state technology efficient for lexicons and rule-based morphological analysers.

Finite-state methods are less suitable for unrestricted syntax, where nested structures and long-distance agreement are common. Nevertheless, finite-state cascades are often effective for named-entity recognition and information extraction when patterns are relatively local.

4. Statistical Language Models

A language model assigns probabilities to sequences of words. For a sentence containing words w₁, w₂, ..., w_T, the chain rule gives:

The chain rule is exact, but estimating long histories requires enormous amounts of data. An n-gram model makes a Markov approximation: the probability of a word depends only on the preceding n−1 words.

For a bigram model:

For a trigram model:

Sentence boundary symbols such as <s> and </s> are normally added so that the model represents sentence beginnings and endings.

Maximum-likelihood estimation

For a bigram model, the maximum-likelihood estimate is:

where C(wᵢ₋₁, wᵢ) is the count of the bigram and C(wᵢ₋₁) is the count of the history word. This estimate is appropriate when counts are reliable. However, an unseen bigram receives probability zero, causing the entire sentence probability to become zero.

Worked example: a bigram model

Suppose a training corpus contains the following two sentences:

<s> cats chase mice </s>

<s> cats eat fish </s>

The count of <s> cats is 2 and the count of <s> is 2, so:

The count of chase mice is 1 and the count of chase is 1, so:

The probability of <s> cats chase mice </s> is the product of its bigram probabilities. The model may assign zero probability to a sentence containing a sequence such as cats drive, because that bigram was absent from training.

Smoothing

Smoothing assigns some probability mass to events not observed in training. Add-one smoothing is simple but often too aggressive for large vocabularies. For a vocabulary of size V, add-one smoothing is:

Here, h is the history and w is the predicted word. The denominator adds V because one count is added for each vocabulary item.

Other methods include add-k smoothing, interpolation, backoff, Good–Turing estimation and Kneser–Ney smoothing. Interpolation combines models of different orders:

where λ₁ + λ₂ + λ₃ = 1 and each weight is non-negative. The component models are trigram, bigram and unigram probabilities. The weights may be selected on held-out validation data.

Perplexity

Perplexity measures how well a language model predicts a test sequence. For a sequence of N tokens:

Equivalently, using log probabilities:

The logarithm base determines the exponential base. Lower perplexity indicates better predictive performance on the same test set and tokenisation scheme. Perplexity should not be compared across incompatible datasets, vocabularies or tokenisation methods without care.

5. TF–IDF Representation

TF–IDF represents a document using word importance. Term frequency measures how often a term occurs in a document, while inverse document frequency reduces the weight of terms appearing in many documents.

A common term-frequency definition is:

where fₜ,ᵈ is the count of term t in document d. A binary or logarithmic alternative may be used. The standard inverse document frequency is:

where N is the number of documents and df(t) is the number of documents containing the term. The basic TF–IDF weight is:

If a term occurs in every document, df(t) = N, so its IDF is zero. This reflects low discriminative value. In practical software, smoothed forms such as log((N+1)/(df+1)) + 1 prevent extreme behaviour and ensure defined values.

Worked example

Assume there are 100 documents. The term “neural” occurs in 10 documents and appears twice in document d. Using raw term frequency:

Using natural logarithms, log(10) ≈ 2.303, so:

The numerical value depends on the logarithm base and any normalisation. TF–IDF vectors are commonly normalised so that document length does not dominate similarity calculations.

TF–IDF is useful for document classification, search, clustering and keyword extraction. Its bag-of-words representation ignores word order and usually treats semantically different words as unrelated dimensions.

6. Probabilistic Sequence Labelling

Many NLP tasks assign one label to each token. Examples include part-of-speech tagging, named-entity recognition and chunking. The central difficulty is that the correct label depends both on the token and on neighbouring labels.

Hidden Markov models

A hidden Markov model (HMM) represents observed words as emissions from hidden states such as part-of-speech tags. A first-order HMM uses:

• transition probabilities P(tᵢ | tᵢ₋₁), and
• emission probabilities P(wᵢ | tᵢ).

The best tag sequence is:

By Bayes’ rule, maximising the posterior is equivalent to maximising the joint probability:

The Viterbi algorithm finds the most probable sequence efficiently through dynamic programming. It stores the best score for each state at each position rather than enumerating every possible sequence.

HMM assumptions are useful approximations but linguistically restrictive. The model assumes that the current tag depends only on the previous tag and that the current word depends only on the current tag. Unknown words require special handling, often using suffixes, prefixes, character classes or a dedicated unknown-word model.

Maximum entropy and feature-based models

A conditional log-linear model can represent many overlapping features. For an input x and label y:

Here, f(x,y) is a feature vector, θ is a learned weight vector and the denominator normalises probabilities over all candidate labels. Features may indicate capitalisation, neighbouring words, suffixes, punctuation or dictionary membership.

Conditional random fields (CRFs) extend this idea to sequences. A linear-chain CRF models the probability of a complete label sequence conditional on the observed sentence and can include transition and observation features. Unlike an HMM, it does not require a generative model of the observations.

7. Feature Engineering for NLP

Feature engineering converts linguistic observations into variables that a statistical classifier can use. Effective features are task-specific and should be constructed without using information unavailable at prediction time.

Lexical features

Examples include:

• word identity and word n-grams;
• character n-grams;
• prefixes and suffixes;
• word length;
• frequency and vocabulary membership;
• presence of negation terms.

Character n-grams are useful for spelling variation, morphology and noisy user-generated text. They can also improve robustness to unseen words.

Orthographic features

These include whether a token is capitalised, all uppercase, numeric, alphanumeric, hyphenated or contains punctuation. In named-entity recognition, capitalisation may help identify persons or organisations, although it becomes less reliable in languages or settings without consistent capitalisation.

Contextual and syntactic features

A classifier may use neighbouring tokens, preceding and following part-of-speech tags, dependency relations, sentence position and phrase-level patterns. Context features reduce ambiguity: “river bank” and “bank account” provide different signals.

Feature quality and leakage

Features should be evaluated for relevance, stability and cost. Data leakage occurs when a feature indirectly reveals the target through information that would not exist at deployment time. For example, using a document’s manually assigned category as a feature produces unrealistic evaluation. Feature extraction must be fitted only on training data when it learns vocabulary, IDF values or other corpus statistics.

8. Classification, Tagging, Parsing and Information Extraction

Text classification

In classification, an input document is assigned to one or more categories. A standard classical pipeline uses tokenisation, stop-word decisions, TF–IDF or n-gram features, and a classifier such as multinomial naïve Bayes, logistic regression or a linear support vector machine.

Multinomial naïve Bayes estimates:

where c is a class, d is a document and count(t,d) is the term count. The “naïve” assumption treats term occurrences as conditionally independent given the class. This assumption is false in natural language, but the model can still perform well, especially with suitable smoothing.

Part-of-speech tagging

Part-of-speech tagging assigns labels such as noun, verb, adjective and determiner. Ambiguity is common: “book” may be a noun or a verb. Taggers use word identity, context, morphology and sentence position. HMMs, CRFs and discriminative classifiers are classical approaches.

Shallow parsing

Chunking identifies non-overlapping phrases such as noun phrases and verb phrases. A BIO scheme represents chunks with labels such as B-NP, I-NP and O. The B label begins a chunk, I continues it and O indicates material outside a chunk. BIO conventions require careful treatment of adjacent and nested entities.

Information extraction

Information extraction converts unstructured text into structured records. A system may identify entities, relations, events or attributes. A rule-based extractor might detect patterns such as “Company acquired Company” and emit an acquisition relation. Statistical models can combine lexical, syntactic and gazetteer features.

Evaluation must distinguish entity-level and token-level correctness. Precision, recall and F1 are commonly used:

Here, TP, FP and FN denote true positives, false positives and false negatives. These measures assume clearly defined matching criteria. Partial entity matches may require separate reporting.

9. Applied Case: Customer-Support Ticket Routing

The following is an illustrative case study.

Background

A utility company receives customer messages that must be routed to billing, outages, new connections or safety teams. The organisation has 30,000 historically labelled tickets but limited computing resources and a requirement that predictions be explainable.

Problem

Messages contain spelling errors, short descriptions and overlapping topics. A keyword-only system routes “power bill is unusually high” to billing but may misclassify “power is out and my bill is overdue”. The organisation needs a model that balances accuracy, speed and auditability.

Analysis

The team examines class frequencies, vocabulary, spelling variation and temporal drift. It separates training, validation and test data chronologically so that later tickets do not influence earlier predictions. This is important because random splitting can make performance look better when similar templates occur in both sets.

Approach and solution

The system performs Unicode normalisation, sentence-aware tokenisation and limited lowercasing. It creates word and character TF–IDF features. Word features capture domain terms such as “meter” and “invoice”; character features handle forms such as “re-connect” and spelling errors. A regular expression extracts account references but excludes the account number itself from classification features to reduce privacy risk.

A linear logistic regression classifier is trained with class weights because safety tickets are rare but important. A confidence threshold sends uncertain or safety-related messages to human review. Feature coefficients are inspected for spurious indicators, and errors are categorised by topic, language variety and message length.

Outcome

The model improves routing over a keyword baseline and provides a ranked list of influential features. Human review remains necessary for ambiguous or high-risk tickets. Monitoring is established for class distribution, drift, false negatives in safety messages and changes in customer vocabulary.

Learning points

1. Simple representations can be highly effective when aligned with the task.
2. Character features improve robustness to spelling and formatting variation.
3. Accuracy alone is inadequate when error costs differ by class.
4. Explainability, privacy and escalation rules are part of system design.
5. Evaluation must reflect deployment time and operational risk.

10. Limitations, Ethics and Governance

Classical NLP systems inherit biases from their corpora and annotation schemes. A sentiment classifier may perform differently across dialects. A named-entity system may under-recognise names from underrepresented cultures. Historical labels can encode institutional prejudice.

Privacy is also important. Text may contain names, addresses, health information or account identifiers. Systems should minimise collection, restrict access, remove unnecessary identifiers and define retention periods. Regex extraction must not accidentally expose sensitive data through logs.

Evaluation should include subgroup analysis where lawful and ethically justified. Accuracy, precision and recall should be reported by relevant language variety, document type or risk category when this does not create additional privacy harms. High-impact decisions require human oversight, traceability and an appeals process.

Classical models are often more interpretable than large neural models, but interpretability is not automatically fairness. A transparent model can still make systematically harmful decisions. Governance therefore includes documentation, version control, audit logs, security testing, monitoring and clear responsibility for intervention.

11. Contemporary Relevance

Neural language models now dominate many benchmarks, but classical NLP remains valuable. TF–IDF and linear models are fast baselines, finite-state systems remain strong for morphology and constrained extraction, and n-gram models are useful for autocomplete, decoding and teaching probabilistic prediction. Hybrid systems often combine rules, statistical models and neural representations.

Classical methods also provide diagnostic tools. If a complex model fails, a TF–IDF baseline can reveal whether the task depends mainly on lexical cues. Error analysis using regexes, confusion matrices and feature inspection can expose data problems that a large model may obscure.

Best practice is therefore comparative: establish a simple, reproducible baseline; use appropriate validation; inspect errors; add complexity only when it provides measurable and justified value.

Chapter Summary

Classical NLP represents language through symbolic patterns, finite-state structures, counts and engineered features. Regular expressions identify local surface patterns, while finite-state automata and transducers support efficient lexical and morphological processing. N-gram language models estimate sequence probabilities using limited histories, but require smoothing to handle unseen events. Perplexity evaluates predictive performance under a fixed tokenisation and test set.

TF–IDF weights terms according to their frequency in a document and rarity across documents. HMMs model hidden labels through transitions and emissions, while feature-based models and CRFs incorporate diverse contextual evidence. Feature engineering is central to classification, tagging, chunking and information extraction, but must avoid data leakage and account for deployment conditions.

Classical systems remain useful because they are efficient, interpretable and effective in many constrained applications. Their limitations include weak semantic representation, independence assumptions, sensitivity to feature design and possible social bias. Responsible deployment requires privacy protection, subgroup evaluation, human oversight and continuous monitoring.

Key Terms

Regular expression: A formal pattern used to match or extract strings.

Token: An individual occurrence of a linguistic unit in text.

Corpus: A structured collection of texts used for analysis or training.

Finite automaton: A machine with a finite set of states and transitions.

Finite-state transducer: A finite-state machine that maps input symbols to output symbols.

N-gram: A contiguous sequence of n items, commonly words or characters.

Language model: A model that assigns probabilities to linguistic sequences.

Smoothing: A method for assigning probability to unseen or rare events.

Perplexity: A measure of how well a language model predicts a test sequence.

TF–IDF: A term-weighting method based on document frequency and corpus rarity.

Feature engineering: Designing measurable variables for a statistical model.

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

Emission probability: The probability of an observation given a hidden state.

Transition probability: The probability of one state given a preceding state.

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

Chunking: Identifying shallow, non-overlapping syntactic phrases.

Information extraction: Producing structured facts from unstructured text.

Data leakage: Use of information during training that would not be available at prediction time.

Precision: The proportion of predicted positives that are correct.

Recall: The proportion of actual positives that are recovered.

Review Questions

5 Short Answer Questions

1. What is the difference between a token and a type?
2. Why can an unsmoothed n-gram model assign zero probability to a sentence?
3. What does IDF measure in TF–IDF?
4. State the two principal probability components of a first-order HMM.
5. What is data leakage in feature engineering?

5 Long Answer Questions

1. Explain how regular expressions and finite-state transducers can be used in morphological analysis. Discuss their limitations.
2. Derive the maximum-likelihood estimate for a bigram model and explain why smoothing is necessary.
3. Compare TF–IDF, multinomial naïve Bayes and logistic regression as tools for document classification.
4. Explain how the Viterbi algorithm supports sequence tagging in an HMM.
5. Discuss ethical, privacy and governance requirements for a classical NLP system used in customer support.

3 Analytical / Application Questions

1. Design a feature set for distinguishing financial uses of “bank” from geographical uses. Explain why each feature may help.
2. A named-entity system produces 80 true positives, 20 false positives and 40 false negatives. Calculate precision, recall and F1, showing your working.
3. Propose an evaluation plan for a ticket-routing system in which safety-related false negatives are more serious than billing false positives. Explain your metrics, data split and escalation policy.

Multiple Choice Questions with Answers

Question 1

Which regex construct commonly denotes one or more repetitions?

A. *

B. +

C. ?

D. $

Correct Answer: B. +

Question 2

In a finite-state transducer, what distinguishes it from a basic acceptor?

A. It must use neural embeddings

B. It can produce output symbols while processing input

C. It cannot contain accepting states

D. It can recognise only numbers

Correct Answer: B. It can produce output symbols while processing input

Question 3

What is the main problem caused by an unseen n-gram in an unsmoothed language model?

A. It receives probability one

B. It makes every unigram frequency equal

C. It receives probability zero

D. It increases vocabulary size automatically

Correct Answer: C. It receives probability zero

Question 4

If a term occurs in every document, what is its basic IDF under IDF = log(N ÷ df(t))?

A. 0

B. 1

C. N

D. Undefined

Correct Answer: A. 0

Question 5

Which component of an HMM represents the probability of a word given a tag?

A. Transition probability

B. Emission probability

C. Perplexity

D. Inverse document frequency

Correct Answer: B. Emission probability

Question 6

What does lower perplexity generally indicate when models use the same test set and tokenisation?

A. Worse predictive performance

B. Better predictive performance

C. More false positives

D. A larger vocabulary necessarily

Correct Answer: B. Better predictive performance

Question 7

Which feature is especially useful for handling spelling variation and unknown words?

A. Character n-grams

B. Document title only

C. Random labels

D. Removing all punctuation and letters

Correct Answer: A. Character n-grams

Question 8

In information extraction, precision is calculated as:

A. TP ÷ (TP + FP)

B. TP ÷ (TP + FN)

C. FP ÷ (TP + FP)

D. FN ÷ (TP + FN)

Correct Answer: A. TP ÷ (TP + FP)

Question 9

What is the purpose of the Viterbi algorithm in an HMM tagger?

A. To compute TF–IDF values

B. To find the most probable state sequence efficiently

C. To remove stop words

D. To construct a regex alphabet

Correct Answer: B. To find the most probable state sequence efficiently

Question 10

Which practice helps prevent data leakage when using TF–IDF?

A. Fit IDF statistics using the test set

B. Fit vocabulary and IDF statistics on training data only

C. Duplicate test documents in training

D. Use the gold label as a feature

Correct Answer: B. Fit vocabulary and IDF statistics on training data only