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.
HMM Components
1. States (Q)
- Possible hidden states.
- Example: .
2. Transition Matrix (A)
- Probability of moving from one state to another.
- Formula:
- Example: .
3. Emission Matrix (B)
- Probability of a state generating a word.
- Formula:
- Example: .
4. Initial Probabilities ()
- Probability that a sentence starts with a tag.
- Example: .
HMM Assumptions
- Markov assumption: the current state depends only on the previous state.
- Output independence: the observation depends only on the current state.
Transition Probability
- The numerator is the count of the transition, and the denominator is the count of the previous tag.
Emission Probability
- 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: , where is the sequence length and is the number of states.
Viterbi Steps
1. Initialization
- Compute probabilities for the first observation.
2. Recursion
- Compute the best path to each state.
- Store the maximum probability and a backpointer.
3. Termination
- Choose the highest final probability.
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
Vocabulary
Initial Probabilities
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.