IN440 — Chapter 2 Summary

md5 min readSummary of IN440

Sequence Labeling

  • Sequence labeling is the task of assigning a label to each item in a sequence.
  • In NLP, this means mapping words to labels.
  • Examples: POS tagging and Named Entity Recognition (NER).

Part-of-Speech (POS) Tagging

  • POS tagging assigns grammatical categories to words based on context and meaning.
  • Common POS tags include NOUN, VERB, ADJ, ADV, DET, and PRON.

Open vs Closed Class Words

Open Class (Content Words)

  • Open class words can grow over time.
  • Examples: nouns, verbs, adjectives, adverbs.
  • Examples: iPhone, Google, TikTok.

Closed Class (Function Words)

  • Closed class words are a fixed set of grammatical words.
  • Examples: the, a, she, on, under.

Common POS Tag Sets

Universal Dependencies (UD)

  • Language-independent tag set with 17 tags.
  • Examples: NOUN, VERB, ADJ, DET.

Penn Treebank

  • More detailed tag set with 45 tags.
  • Examples:
  • NN: Singular noun
  • NNS: Plural noun
  • VB: Verb (base form)
  • VBD: Past tense verb
  • JJ: Adjective
  • RB: Adverb
  • DT: Determiner

Why POS Tagging Matters

  • POS tagging is useful for text-to-speech, parsing, information extraction, and sentiment analysis.
  • A word like "object" can be a noun or a verb, so POS tags help determine pronunciation and meaning.

Ambiguity in POS Tagging

  • A word may have different tags depending on context.
  • Examples for "back":
  • the back door → ADJ
  • back the bill → VERB
  • the back of the room → NOUN
  • win the money back → PARTICLE

Sources of Information for POS Tagging

  • Prior probabilities: some words are usually associated with specific tags, such as "will" → AUX.
  • Neighboring words: context matters, and "the ___" is usually followed by a noun.
  • Morphology and word shape: prefixes like un-, suffixes like -ly, and capitalization like Janet help with tagging.

Named Entity Recognition (NER)

Definition

  • NER identifies and classifies entities in text.
  • Common entity types include PER, ORG, LOC, GPE, TIME, MONEY, and DATE.

POS vs NER

POS Tagging

  • POS tagging focuses on grammatical category.
  • Example: Microsoft → Proper Noun.

NER

  • NER focuses on semantic meaning.
  • Example: Microsoft → Organization.

Why NER Matters

  • NER is useful for question answering, relation extraction, information retrieval, and document summarization.
  • Example: Microsoft acquired GitHub for $7.5 billion.
  • Extracted entities: Microsoft → ORG, GitHub → ORG, $7.5 billion → MONEY.

Challenges in NER

  • Segmentation: determining entity boundaries, such as in New York University.
  • Type ambiguity: Washington could refer to a person, location, organization, or government.

BIO Tagging

  • NER is often transformed into a sequence labeling problem using BIO tags.
  • Tags: B = Beginning of entity, I = Inside entity, O = Outside entity.
  • Example: Jane Villanueva works at Google → Jane = B-PER, Villanueva = I-PER, works = O, at = O, Google = B-ORG.

BIO Variants

IO

  • Uses only I and O.
  • It loses the beginning information.

BIOES

  • Adds E for End and S for Single-word entity.

Hidden Markov Models (HMM)

Main Idea

  • In HMMs, states are hidden and observations are visible.
  • For POS tagging, hidden states are POS tags and observations are words.

Markov Assumption

  • The current state depends only on the previous state.
  • P(qi∣q1…qi−1)=P(qi∣qi−1)P(q_i \mid q_1 \ldots q_{i-1}) = P(q_i \mid q_{i-1})

HMM Components

1. States (Q)

  • Possible hidden states.
  • Example: Q={NN,VB,DT}Q = \{NN, VB, DT\}.

2. Transition Matrix (A)

  • Probability of moving from one state to another.
  • Formula: P(ti∣ti−1)P(t_i \mid t_{i-1})
  • Example: P(VB∣NN)P(VB \mid NN).

3. Emission Matrix (B)

  • Probability of a state generating a word.
  • Formula: P(wi∣ti)P(w_i \mid t_i)
  • Example: P(runs∣VB)P(\text{runs} \mid VB).

4. Initial Probabilities (π\pi)

  • Probability that a sentence starts with a tag.
  • Example: P(DT)P(DT).

HMM Assumptions

  • Markov assumption: the current state depends only on the previous state.
  • Output independence: the observation depends only on the current state.
  • P(oi∣q1…qT,o1…oT)=P(oi∣qi)P(o_i \mid q_1 \ldots q_T, o_1 \ldots o_T) = P(o_i \mid q_i)

Transition Probability

  • P(ti∣ti−1)=C(ti−1,ti)C(ti−1)P(t_i \mid t_{i-1}) = \dfrac{C(t_{i-1}, t_i)}{C(t_{i-1})}
  • The numerator is the count of the transition, and the denominator is the count of the previous tag.

Emission Probability

  • P(wi∣ti)=C(ti,wi)C(ti)P(w_i \mid t_i) = \dfrac{C(t_i, w_i)}{C(t_i)}
  • The numerator is the count of the word-tag pair, and the denominator is the count of the tag.

Decoding

  • The goal is to find the most probable tag sequence for a sentence.
  • Input: words
  • Output: tags

Viterbi Algorithm

  • The Viterbi algorithm is a dynamic programming method used to find the most probable hidden state sequence.
  • Complexity: O(T×N2)O(T \times N^2), where TT is the sequence length and NN is the number of states.

Viterbi Steps

1. Initialization

  • Compute probabilities for the first observation.
  • v1(s)=πs×bs(o1)v_1(s) = \pi_s \times b_s(o_1)

2. Recursion

  • Compute the best path to each state.
  • vt(j)=max⁡i(vt−1(i)×aij)×bj(ot)v_t(j) = \max_i\big(v_{t-1}(i) \times a_{ij}\big) \times b_j(o_t)
  • Store the maximum probability and a backpointer.

3. Termination

  • Choose the highest final probability.
  • P∗=max⁡jvT(j)P^* = \max_j v_T(j)

4. Backtrace

  • Follow backpointers backward to reconstruct the best sequence.

Example: HMM POS Tagging

  • Training corpus:
  • the/DT dog/NN runs/VB
  • the/DT lion/NN runs/VB
  • dog/NN is/VB an/DT animal/NN
  • cat/NN is/VB an/DT animal/NN

Tag Set

  • Q={DT,NN,VB}Q = \{DT, NN, VB\}

Vocabulary

  • {the,dog,lion,runs,is,an,animal,cat}\{\text{the}, \text{dog}, \text{lion}, \text{runs}, \text{is}, \text{an}, \text{animal}, \text{cat}\}

Initial Probabilities

  • P(DT)=0.5P(DT) = 0.5
  • P(NN)=0.5P(NN) = 0.5
  • P(VB)=0P(VB) = 0

Transition Matrix

  • From → To: DT, NN, VB
  • DT: 0, 1, 0
  • NN: 0, 0, 1
  • VB: 1, 0, 0

Example Decoding

  • Sentence: the cat runs
  • Predicted tags: DT NN VB

Key Takeaways

  • POS tagging assigns grammatical labels, is context-dependent, and is a sequence labeling task.
  • NER detects semantic entities, uses BIO tagging, and is hard because of ambiguity and segmentation.
  • HMM uses hidden states that generate observations through transition, emission, and initial probabilities.
  • Viterbi is an efficient decoding algorithm that finds the most likely hidden sequence with dynamic programming.