Natural Language Processing (AD-802 (A)) Unit 3 Notes

How unit 3 is examined

This unit covers the word-level tasks of NLP: tokenization, tagging, stemming, lemmatization, NER, sense disambiguation, embeddings, POS-tagging methods, n-grams and collocations. No question from these topics appears in the supplied papers, so each is kept short but complete.

Tokenization

Not asked since 2022

Definition. Tokenization is the process of splitting raw text into smaller units called tokens, such as words, subwords, punctuation marks or sentences.

Key points.

Tokenization is the first step of almost every NLP pipeline, because later stages such as tagging and parsing work on tokens and not on raw characters.
Simple tokenizers split on whitespace and punctuation, but this fails on cases like "don't", "New York", "U.S.A." and email addresses.
Tokenizers can work at sentence level, word level, subword level (BPE, WordPiece) or character level.
Languages without spaces between words, such as Chinese, need word segmentation, which is a harder form of tokenization.

Part-of-Speech Tagging (POS Tagging)

Definition. POS tagging is the task of assigning each word in a sentence its grammatical category, such as noun, verb, adjective or adverb, according to its definition and its context.

Key points.

The input is a token sequence and the output is a tag sequence, for example "The/DT dog/NN barks/VBZ" using Penn Treebank tags.
The main difficulty is ambiguity: "book" is a noun in "a book" and a verb in "book a ticket", so context must decide the tag.
POS tags are used by parsing, information extraction, word sense disambiguation and speech synthesis.
Taggers are of three types: rule-based, stochastic and transformation-based.

Lemmatization

Definition. Lemmatization reduces an inflected word to its lemma, the dictionary base form, using vocabulary and morphological analysis.

Key points.

Lemmatization always returns a valid word: "better" becomes "good", "was" becomes "be" and "mice" becomes "mouse".
It needs the POS of the word, because "saw" is lemmatized to "see" as a verb but stays "saw" as a noun.
It is more accurate than stemming but slower, since it needs a dictionary such as WordNet.
It is preferred when the output must be a readable, meaningful word.

Stemming

Definition. Stemming is a crude rule-based process that chops affixes off a word to get its stem, which need not be a valid word.

Key points.

The Porter stemmer applies ordered suffix-stripping rules in steps: "caresses" becomes "caress", "ponies" becomes "poni" and "running" becomes "run".
Stemming is fast and needs no dictionary, so it is widely used in information retrieval to match word variants.
It makes two kinds of error: over-stemming, where different words collapse together ("universe" and "university"), and under-stemming, where related words stay apart.
Other stemmers are Lovins, Paice/Husk and the Snowball (Porter2) stemmer.

Stemming	Lemmatization
Chops suffixes by rules	Uses dictionary and POS
Output may be a non-word ("poni")	Output is a valid word ("pony")
Fast, less accurate	Slower, more accurate

Named Entity Recognition (NER)

Definition. Named Entity Recognition is the task of locating and classifying named entities in text into predefined categories such as person, organization, location, date and money.

Key points.

In "Sundar Pichai joined Google in 2004", NER marks Sundar Pichai as PERSON, Google as ORGANIZATION and 2004 as DATE.
NER has two parts: detecting the entity span and classifying its type.
Approaches are rule-based (gazetteers and patterns), statistical (HMM, CRF, MaxEnt) and neural (BiLSTM-CRF, transformers).
Difficulties are ambiguity ("Washington" can be a person or a place), new entities and variable spellings.

Word Sense Disambiguation (WSD)

Definition. Word Sense Disambiguation is the task of identifying which meaning of an ambiguous word is intended in a given context.

Key points.

"Bank" means a financial institution in "deposit money in the bank" and a river edge in "sat on the bank of the river".
The Lesk algorithm picks the sense whose dictionary gloss overlaps most with the words around the target word.
Approaches are knowledge-based (dictionary, WordNet), supervised (classifier trained on sense-tagged corpora) and unsupervised (clustering of contexts).
WSD helps machine translation, information retrieval and question answering.

Word Embedding

Definition. A word embedding is a dense, low-dimensional real-valued vector that represents a word so that words with similar meanings lie close together in vector space.

Key points.

Embeddings replace sparse one-hot vectors, which are huge and cannot show that "king" and "queen" are related.
They rest on the distributional idea that a word is known by the company it keeps.
Word2Vec learns vectors with CBOW (predict a word from its context) or Skip-gram (predict the context from a word); GloVe uses global co-occurrence counts.
Similarity is measured by cosine similarity, and vectors capture analogies such as king - man + woman ≈ queen.

Types of PoS Tagging: Rule-based

Definition. Rule-based tagging uses a dictionary to give each word its possible tags and then hand-written disambiguation rules to choose one tag from context.

Key points.

Stage one looks up every word in a lexicon and assigns all its possible tags.
Stage two applies rules, for example "if the previous word is a determiner, then choose noun and not verb".
The rules are linguistic and human-readable, so errors are easy to trace.
Writing and maintaining thousands of rules is costly, and the tagger does not transfer easily to a new language.

Stochastic

Definition. Stochastic tagging uses probabilities learned from a tagged corpus to choose the most likely tag or tag sequence for the words.

Key points.

The word-frequency approach assigns each word the tag it carries most often in the training corpus.
The tag-sequence approach picks the tag sequence with the highest probability, as an HMM tagger does using tag n-grams.
It needs an annotated corpus but no hand-written rules, and it adapts to new data.
Its weakness is unseen words, which need smoothing or suffix-based guessing.

Transformation-based

Definition. Transformation-based (Brill) tagging starts with an initial tagging and learns an ordered list of correction rules from a tagged corpus.

Key points.

Step 1 tags every word with its most frequent tag; Step 2 tries rule templates and keeps the rule that removes the most errors; Step 3 repeats until the gain is negligible.
A learned rule looks like "change NN to VB when the previous tag is TO".
It combines rule-based readability with statistical learning, and its rules are compact.
The learned rules must be applied in the order they were learned.

Lexical

Definition. Lexical tagging assigns a tag using lexical probabilities, that is the probability of each tag for a word taken from the lexicon, without looking at context.

Key points.

The lexical probability is $P(\text{tag} \mid \text{word})$, estimated as count(word, tag) divided by count(word).
Choosing the highest-probability tag per word gives a simple baseline that already reaches about 90 percent accuracy on English.
It fails on ambiguous words because it ignores neighbours, which contextual models add.
Unknown words get tags from suffix or capitalization cues.

Hidden Markov model and Maximum Entropy model

Definition. An HMM tagger treats tags as hidden states and words as observations, and finds the tag sequence maximizing the product of transition and emission probabilities.

Key points.

With the bigram assumption the best tags maximize $\prod_i P(w_i \mid t_i)\,P(t_i \mid t_{i-1})$, where the first term is the emission and the second the transition probability.
The Viterbi algorithm finds the best sequence efficiently by dynamic programming.
A Maximum Entropy model instead directly models $P(t \mid \text{context})$ as a log-linear function of features, and among all models fitting the data it chooses the one with highest entropy, so it assumes nothing extra.
MaxEnt can use rich overlapping features such as suffix, capitalization and neighbouring words, which an HMM cannot easily do.

n-grams

Definition. An n-gram is a contiguous sequence of n words, and an n-gram language model predicts the next word from the previous n-1 words.

Key points.

Unigram, bigram and trigram mean n = 1, 2 and 3, for example the bigrams of "I love NLP" are "I love" and "love NLP".
The bigram probability is $P(w_n \mid w_{n-1}) = \dfrac{C(w_{n-1}, w_n)}{C(w_{n-1})}$.
The sentence probability is the product of these conditional probabilities.
Unseen n-grams get zero probability, so smoothing such as add-one (Laplace) is used.

Collocations

Definition. A collocation is a sequence of words that occur together more often than chance and whose meaning is often not simply the sum of its parts.

Key points.

Examples are "strong tea", "make a decision" and "New York"; "powerful tea" sounds wrong though it is grammatical.
Collocations are found by frequency, mean and variance of word distance, hypothesis tests (t-test, chi-square) and pointwise mutual information.
Pointwise mutual information is $\log_2 \dfrac{P(x,y)}{P(x)P(y)}$, which is high when two words co-occur far above chance.
They matter in machine translation and lexicography, since they cannot be translated word by word.

Applications of NER

Definition. NER applications are the uses of extracted entities to structure text and answer questions from it.

Key points.

Information extraction and search: entities are indexed so that queries about a person or place return exact results.
Question answering and chatbots use entities such as dates and locations to fill slots and answer "who" and "where" questions.
News and content classification tag articles by the people and organizations they mention.
Other uses are resume screening, customer support routing, medical record analysis and financial or legal document processing.

Last-minute revision

Tokenization splits text into tokens; it is the first NLP pipeline step.
POS tagging assigns a grammatical category to each word using context.
Stemming chops suffixes by rules (output may be a non-word); lemmatization gives the dictionary form using POS.
NER finds and classifies entities: person, organization, location, date.
WSD picks the right sense of an ambiguous word; the Lesk algorithm uses gloss overlap.
Word2Vec has CBOW and Skip-gram; GloVe uses global co-occurrence counts.
The three POS tagger types are rule-based, stochastic and transformation-based (Brill).
HMM tagging maximizes emission times transition probability and uses Viterbi.
MaxEnt is a log-linear model with rich features and maximum entropy.
Bigram probability is $C(w_{n-1}, w_n)/C(w_{n-1})$; smoothing fixes zero counts.
A collocation is a word combination occurring more often than chance, found by PMI or t-test.

Memory hooks

Stem chops, lemma looks up: stemming is a knife, lemmatization is a dictionary.
Brill: "Baseline, then Repair, then Iterate, then Learn".
HMM tagging: emission asks "which word from this tag", transition asks "which tag after this tag".
CBOW guesses the centre word; Skip-gram spreads outward from it.
PMI: high when two words are together far more than chance.

Coverage checklist

Tokenization: covered, no past questions.
Part-of-Speech Tagging (POS Tagging): covered, no past questions.
Lemmatization: covered, no past questions.
Stemming: covered, no past questions.
Named Entity Recognition (NER): covered, no past questions.
Word Sense Disambiguation (WSD): covered, no past questions.
Word Embedding: covered, no past questions.
Types of PoS Tagging: Rule-based: covered, no past questions.
Stochastic: covered, no past questions.
Transformation-based: covered, no past questions.
Lexical: covered, no past questions.
Hidden Markov model and Maximum Entropy model: covered, no past questions.
n-grams: covered, no past questions.
Collocations: covered, no past questions.
Applications of NER: covered, no past questions.

Account

Natural Language Processing (AD-802 (A)) - Unit 3 Short Notes

How unit 3 is examined

Tokenization

Part-of-Speech Tagging (POS Tagging)

Lemmatization

Stemming

Named Entity Recognition (NER)

Word Sense Disambiguation (WSD)

Word Embedding

Types of PoS Tagging: Rule-based

Stochastic

Transformation-based

Lexical

Hidden Markov model and Maximum Entropy model

n-grams

Collocations

Applications of NER

Last-minute revision

Memory hooks

Coverage checklist