Sequence Labeling for Parts of Speech and Named Entities

From the grammatical sketch of Greek attributed to Dionysius Thrax (c. 100 B.C.): noun, verb, pronoun, preposition, adverb, conjunction, participle, article. It became the basis for describing European languages for 2000 years.

They are clues to structure and meaning: a word’s POS predicts its neighbors (determiners before nouns) and syntactic links (verbs to nouns), making tagging key for parsing; knowing whether Washington is a person, place or university matters for QA, stance detection and information extraction.

Assigning each word \(x_i\) of an input sequence a label \(y_i\), so the output has the same length as the input; e.g. POS tagging and NER.

The generative Hidden Markov Model (HMM) and the discriminative Conditional Random Field (CRF).

Not primarily: although classes have semantic tendencies, they are defined by grammatical relationships with neighboring words and by morphological properties of their affixes.

17 tags: open class ADJ, ADV, NOUN, VERB, PROPN, INTJ; closed class ADP, AUX, CCONJ, DET, NUM, PART, PRON, SCONJ; other PUNCT, SYM, X. Features can add finer distinctions (number, case…).

open	closed	other
NOUN VERB ADJ ADV PROPN INTJ	ADP AUX CCONJ DET NUM PART PRON SCONJ	PUNCT SYM X

Closed classes (prepositions, determiners…) have relatively fixed membership, mostly short, frequent function words with grammatical uses. Open classes (nouns, verbs, adjectives, adverbs, interjections) constantly gain new members (iPhone, to fax).

Closed-class words like of, it, and, you: very short, frequent, and often structuring the grammar.

They can occur with determiners (a goat), take possessives (IBM’s revenue), and may be plural (goats). Common nouns include concrete terms, abstractions and verb-like terms (his pacing).

Count nouns have singular and plural and can be counted (one goat, two goats). Mass nouns denote something conceptualized as a homogeneous group and aren’t counted (snow, salt, communism; *two snows).

Not necessarily: some argue Riau Indonesian and Tongan don’t distinguish nouns and verbs; in Korean, words corresponding to English adjectives behave as a subclass of verbs (“to be beautiful”).

Locative/directional (home, here), degree (extremely, very), manner (slowly, delicately), and temporal (yesterday, Monday). Adverbs modify verbs, other adverbs and whole verb phrases.

A small open class: exclamations (oh, alas, um), greetings (hello), and question responses (yes, uh-huh).

Spatial or temporal relations, literal (on it, before then) or metaphorical (on time, beside herself), and others like marking the agent (written by Shakespeare).

A particle resembles a preposition or adverb but combines with a verb, often with an extended meaning (turned the paper over). A verb plus particle acting as a unit is a phrasal verb, often non-compositional (turn down = reject, rule out = eliminate).

Determiners (this, that) can mark the start of a noun phrase; articles (a, an, the) are frequent determiners marking discourse properties of the noun.

Coordinating conjunctions (and, or, but) join elements of equal status. Subordinating conjunctions join a main clause with an embedded one. Those linking a verb to its clausal argument, like that in “I thought that you might like some milk”, are complementizers.

Personal (you, she, it), possessive (my, their: possession or abstract relation), and wh-pronouns (what, who), used in questions or as complementizers.

Semantic features of the main verb: tense, aspect (completed?), polarity (negated?) and mood (necessary, possible, desired). English: the copula be, do, have, and modals like can, may, must.

An English-specific tagset (36 core tags) used for many syntactically annotated corpora; unlike UD it distinguishes verb tenses and participles (VBD, VBN, VBG, VBZ…) and has a tag for existential there (EX).

Each component noun is tagged as a proper noun (PROPN/NNP), even journal and medicine.

Words are ambiguous between parts of speech (book as verb or noun, that as determiner or complementizer), and the tagger must choose the right one in context.

Very accurate: for English (and many UD languages) taggers of all kinds (HMM, CRF, BERT) reach about human-level accuracy, in the high 90s percent.

Most word types are unambiguous, but the ambiguous ones are very frequent, so a majority of word tokens in running text are ambiguous (that, back, down, put, set).

Adjective (a back seat), noun (in the back), verb (senators back the bill), particle (buy back debt), adverb (back then).

Assign each token the tag it occurred with most often in training. It is surprisingly strong (only a few points below state of the art for English POS tagging), so classifiers should always be compared against at least this baseline.

POS tagging says Janet, Stanford University, Colorado are proper nouns; NER says what kind of entity each refers to: person, organization, location.

Finding spans of text that are proper names and tagging their type: PER, LOC, ORG, GPE; often extended to dates, times and prices.

Entity-directed sentiment analysis, question answering, linking text to knowledge bases like Wikipedia, and extracting events and relations between participants.

It has a segmentation problem (finding entity spans and their boundaries, when most words aren’t entities) and type ambiguity (JFK as person, airport, school…).

B for the first token of a span, I for tokens inside a span, O outside; with B and I per entity type, \(2n + 1\) tags for \(n\) types. It turns span recognition into per-token labeling.

IO drops B (losing boundaries between adjacent entities); BIOES adds E for a span’s last token and S for single-token spans.

A model of the probabilities of sequences of states, assuming that to predict the next state only the current state matters: \(P(q_i \mid q_1 \ldots q_{i-1}) = P(q_i \mid q_{i-1})\).

A set of states \(Q\), a transition matrix \(A\) with \(a_{ij}\) = probability of moving from state \(i\) to state \(j\) (rows sum to 1), and an initial distribution \(\pi\) over states.

A bigram language model: each transition is \(p(w_i \mid w_j)\).

We observe words, not tags; the tags are hidden events we treat as causal factors, which the HMM relates to the observed words.

States \(Q\), transition probabilities \(A\), emission (observation likelihood) probabilities \(B = b_i(o_t)\) for each observation given each state, and an initial distribution \(\pi\).

The Markov assumption (a state depends only on the previous state) and output independence (an observation depends only on the state that produced it).

By counting on a tagged corpus: \(P(t_i \mid t_{i-1}) = \frac{C(t_{i-1}, t_i)}{C(t_{i-1})}\) and \(P(w_i \mid t_i) = \frac{C(t_i, w_i)}{C(t_i)}\).

Not “which tag is most likely for will?” (that is \(P(\text{MD} \mid \text{will})\)), but “if we generate a modal, how likely is it to be will?”

Given the HMM \(\lambda = (A, B)\) and an observation sequence, find the most probable sequence of hidden states.

\(\hat{t}_{1:n} = \arg\max P(t_{1:n} \mid w_{1:n}) = \arg\max P(w_{1:n} \mid t_{1:n})P(t_{1:n})\) (Bayes, dropping the denominator) \(\approx \arg\max\prod_i P(w_i \mid t_i)\,P(t_i \mid t_{i-1})\): emission × transition.

The probability that the HMM is in state \(j\) after the first \(t\) observations, having followed the most probable state sequence to get there: \(\max_{q_{1:t-1}} P(q_{1:t-1}, o_{1:t}, q_t = j \mid \lambda)\).

\(v_t(j) = \max_{i=1}^{N} v_{t-1}(i)\,a_{ij}\,b_j(o_t)\): previous path probability × transition probability × observation likelihood, keeping a backpointer to the best \(i\).

Initialize \(v_1(s) = \pi_s b_s(o_1)\); fill the lattice column by column with the recursion and backpointers; at the end take the best final cell and follow backpointers to recover the best path. It is dynamic programming, like minimum edit distance.

Janet only ever appears as NNP in training, so the emission probability \(P(\text{Janet} \mid t)\) is 0 for every other tag.

As generative models, all knowledge must be encoded in \(P(\text{tag} \mid \text{tag})\) and \(P(\text{word} \mid \text{tag})\); adding arbitrary features cleanly is hard. Log-linear models handle arbitrary features, but logistic regression isn’t a sequence model.

A discriminative sequence model: a log-linear model assigning a probability to an entire tag sequence given the entire input, \(p(Y \mid X) = \frac{\exp\sum_k w_kF_k(X, Y)}{Z(X)}\), like a giant sequential multinomial logistic regression.

The HMM uses Bayes’ rule and the likelihood, \(\arg\max_Y p(X \mid Y)p(Y)\); the CRF computes the posterior \(p(Y \mid X)\) directly, aggregating local log-linear feature scores and normalizing globally.

Global features \(F_k(X, Y)\) are properties of the whole input and output sequences, computed as sums of local features at each position: \(F_k(X, Y) = \sum_i f_k(y_{i-1}, y_i, X, i)\).

Each local feature may use only the current tag \(y_i\), the previous tag \(y_{i-1}\), the whole input \(X\) and the position \(i\). This permits efficient Viterbi and forward-backward algorithms; general CRFs allow distant output dependencies but need harder inference.

\(\mathbb{1}\{x_i = \text{the}, y_i = \text{DET}\}\), \(\mathbb{1}\{y_i = \text{PROPN}, x_{i+1} = \text{Street}, y_{i-1} = \text{NUM}\}\), \(\mathbb{1}\{y_i = \text{VERB}, y_{i-1} = \text{AUX}\}\); generated automatically from templates like \(\langle y_i, x_i\rangle\), \(\langle y_i, y_{i-1}\rangle\), \(\langle y_i, x_{i-1}, x_{i+2}\rangle\).

Abstract letter patterns for unknown words: lowercase → x, uppercase → X, digits → d, punctuation kept (I.M.F. → X.X.X., DC10-30 → XXdd-dd). Short word shape collapses repeated character types (DC10-30 → Xd-d, Well → Xx).

word	shape	short shape
well-dressed	xxxx-xxxxxxx	x-x
DC10-30	XXdd-dd	Xd-d
L’Occitane	X’Xxxxxxxx	X’Xx

Prefixes and suffixes (e.g. all of length ≤ 2 for POS, ≤ 4 for NER).

Each local feature is summed over the sentence into a global feature, and weights attach to the fixed set of \(K\) global features, so the parameter set is the same for any sentence length. Rare features (count < 5) are usually cut off.

Word identity and neighbors, embeddings, POS of the word and neighbors, gazetteer membership, prefixes and suffixes, word shape and short word shape of the word and neighbors.

A list of place names (often millions of entries with geographic and political information), used as a binary feature; similar lists exist for person names, companies and products.

\(\hat{Y} = \arg\max_Y\sum_i\sum_k w_kf_k(y_{i-1}, y_i, X, i)\) (exp and \(Z(X)\) don’t affect the argmax), using Viterbi because each step depends only on the previous tag.

The transition and emission probabilities are replaced by the sum of weighted features (in log space): \(v_t(j) = \max_i\, v_{t-1}(i) + \sum_k w_kf_k(y_{t-1}, y_t, X, t)\).

Like logistic regression: stochastic gradient descent maximizing the log-likelihood of the training corpus, with a CRF version of the forward-backward algorithm computing the derivatives, plus L1 or L2 regularization.

POS taggers by accuracy. NER by precision, recall and F1 over entities (the entity, not the word, is the unit of response), with paired bootstrap or randomization tests for significance.

Universal Dependencies (POS-tagged corpora in over a hundred languages), Penn Treebanks (English, Chinese, Arabic), OntoNotes (named entities in English, Chinese, Arabic), plus domain-specific NER corpora for biomedical and literary text.

Pragmatic combinations of lists, rules and some supervised learning, e.g. IBM System T compiling declarative rules (regexes, dictionaries, constraints) into efficient extractors.

(1) Tag unambiguous mentions with high-precision rules; (2) find substring matches of names found so far; (3) use application-specific name lists; (4) apply a supervised sequence labeler using earlier tags as features.

Two stages: a morphological analyzer returns all possible parts of speech for each word, then thousands of hand-written constraints rule out those inconsistent with the context.

Productive morphology gives huge vocabularies, hence many unknown words; and words carry information like case and gender that taggers must label.

Sequences of morphological tags rather than one primitive tag (Turkish izin: iz+Noun+A3sg+Pnon+Gen, iz+Noun+A3sg+P2sg+Nom, izin+Noun+A3sg+Pnon+Nom), giving much larger tagsets. A morphological analyzer proposes candidate analyses and the tagger disambiguates; this also handles unknown stems.

Two stages: a dictionary (plus morphological analysis) assigned each word its set of possible tags, then hand-written disambiguation rules winnowed them to one per word.

Church’s PARTS tagger (1988), described correctly in Church (1989); CLAWS and DeRose’s tagger were earlier approximations.

Ratnaparkhi’s MXPOST (a maximum entropy Markov model, MEMM, 1996), then CRFs (Lafferty et al., 2001) applied to NER; neural NER from Collobert et al. (CRF over a CNN), then biLSTMs with word and character embeddings, then transformers like BERT.

A third to half came from errors or inconsistencies in the training data, about a third might be solvable with richer linguistic models, and the rest reflect an underspecified or unclear task.