NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

NATURAL LANGUAGE
PROCESSING
UNIT 2 — Word Level, Syntactic & Semantic Analysis

✦ Corpora & Their Construction

✦ Regular Expressions & Finite State Automata

✦ Morphological Parsing

✦ Spelling Error Detection & Correction

✦ Words, Word Classes & Part-of-Speech Tagging

✦ Context-Free Grammar & Constituency Parsing

✦ Dependency Parsing & Probabilistic Parsing

✦ Meaning Representation, Ambiguity Resolution & WSD

Course Natural Language Processing

Unit Unit 2 of 2

Word Level · Syntactic Analysis · Semantic

Sections Analysis

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 1

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Table of Contents
PART A: WORD LEVEL ANALYSIS
1. Corpora and Their Construction

2. Regular Expressions

3. Finite State Automata (FSA)

4. Morphological Parsing

5. Spelling Error Detection & Correction

6. Words and Word Classes

7. Part-of-Speech Tagging

PART B: SYNTACTIC ANALYSIS

8. Context-Free Grammar (CFG)

9. Constituency Parsing

10. Dependency Parsing

11. Probabilistic Parsing

PART C: SEMANTIC ANALYSIS

12. Meaning Representation

13. Ambiguity Resolution

14. Word Sense Disambiguation (WSD)

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 2

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

PART A — WORD LEVEL ANALYSIS

Chapter
1 Corpora and Their Construction

Definition — Corpus (pl. Corpora):

A corpus is a large, structured collection of texts (written or spoken) assembled for linguistic
analysis and NLP model training. It serves as the empirical foundation from which statistical
patterns, linguistic rules, and machine learning models are derived.

The quality, size, and diversity of a corpus directly determine the quality of an NLP system trained on it.
A biased or too-small corpus leads to brittle, unreliable models.

1.1 Types of Corpora

Type Description Example

Raw Corpus Unannotated text — collected Common Crawl (web), Project Gutenberg
as-is

Annotated Corpus Text with linguistic labels Penn Treebank (POS + parse trees)

Parallel Corpus Same text in multiple Europarl (EU parliamentary debates)

languages

Balanced Corpus Covers multiple Brown Corpus (500 samples, 15 genres)

genres/domains

Monitor Corpus Continuously updated with British National Corpus (BNC)

new text

Spoken Corpus Transcribed speech data Switchboard (telephone conversations)

Treebank Parsed sentences with syntax Penn Treebank, Universal Dependencies

trees

Propbank Predicate-argument PropBank, FrameNet

annotations

1.2 Steps in Corpus Construction

• 1. Data Collection: Gather raw text from sources — web scraping, books, social media, news,
scientific papers.

• 2. Data Cleaning: Remove HTML tags, boilerplate, duplicate text, encoding errors, and irrelevant
content.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 3

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

• 3. Annotation: Add linguistic labels — POS tags, parse trees, named entities, sentiment labels —
using human annotators or automatic tools.

• 4. Inter-Annotator Agreement: Measure consistency between multiple annotators using metrics like
Cohen's Kappa to ensure quality.

• 5. Validation & Quality Check: Random sampling, consistency checks, error analysis.

• 6. Formatting & Distribution: Standardize format (XML, JSON, CoNLL); apply licensing; publish.

✎ Example — CoNLL Format — Annotated Token

Word POS Chunk NER
John NNP B-NP B-PER
Smith NNP I-NP I-PER
works VBZ B-VP O
at IN B-PP O
Google NNP B-NP B-ORG

Each column represents a different annotation layer.

Key Corpora in NLP:

• Brown Corpus (1964): First major electronic corpus; 1 million words, 15 text categories.

• Penn Treebank (1993): 4.5 million words of Wall Street Journal text with POS and parse trees.

• Wikipedia Dumps: Multi-lingual; billions of words; commonly used for pre-training.

• Common Crawl: Petabytes of web text; used to train GPT-3, T5, and many LLMs.

• Universal Dependencies (UD): Dependency-annotated treebanks for 100+ languages.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 4

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter
2 Regular Expressions

Definition — Regular Expression (Regex):

A regular expression is a formal pattern specification used to match, search, and manipulate
strings. In NLP, regular expressions are used for tokenization, information extraction, text
normalization, and pattern detection.

2.1 Core Regex Syntax

Symbol Meaning Example Matches

. Any character (except c.t cat, cut, cot, c3t

newline)

* Zero or more of previous ab*c ac, abc, abbc, abbbc

+ One or more of previous ab+c abc, abbc (not ac)

? Zero or one of previous colou?r color, colour

^ Start of string ^The Lines starting with 'The'

$ End of string ing$ running, jumping

[] Character class [aeiou] Any vowel

[^ ] Negated class [^0-9] Any non-digit

{n,m} n to m repetitions [0-9]{3,5} 123, 4567, 89012

| Alternation (OR) cat|dog cat or dog

() Grouping / capture group (ab)+ ab, abab, ababab

\d Digit [0-9] \d{4} 2024, 1999

\w Word char [a-zA-Z0-9_] \w+ hello, NLP_2024

\s Whitespace \s+ Spaces, tabs, newlines

2.2 NLP Applications of Regex

✎ Example — Email Extraction

Pattern: [a-zA-Z0-9._%+\-]+@[a-zA-Z0-9.\-]+\.[a-zA-Z]{2,}
Input: 'Contact us at support@[Link] for help.'
Match: support@[Link]

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 5

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — Date Extraction

Pattern: \d{1,2}[/\-]\d{1,2}[/\-]\d{2,4}
Input: 'The conference is on 15/08/2024 and 3-9-2024.'
Matches: ['15/08/2024', '3-9-2024']

✎ Example — Phone Number

Pattern: (\+91[\-\s]?)?[6-9]\d{9}
Input: 'Call +91-9876543210 or 8123456789'
Matches: ['+91-9876543210', '8123456789']

■ Note: Regex is powerful for well-structured patterns (emails, dates, phone numbers) but fails at
semantic understanding. Regex alone cannot distinguish 'the bank' (financial) from 'river bank' — for
that, we need statistical or neural approaches.

3. Finite State Automata (FSA)

Definition — Finite State Automaton (FSA):

A Finite State Automaton is a mathematical model of computation consisting of a finite set of
states, a set of input symbols (alphabet), a transition function, a start state, and a set of accept
states. FSAs are the theoretical foundation for regular expressions and are widely used in NLP
for tokenization and morphological analysis.

Formal Definition of an FSA:

An FSA M is a 5-tuple M = (Q, Σ, δ, q0, F) where:

• Q = finite set of states

• Σ = input alphabet (set of valid symbols)

• δ : Q × Σ → Q = transition function

• q0 ∈ Q = start state

• F ⊆ Q = set of accept (final) states

✎ Example — FSA for Recognizing 'sheep' (and variations)

States: q0 →(s)→ q1 →(h)→ q2 →(e)→ q3 →(e)→ q3 [loop] →(p)→ q4 [ACCEPT]

This FSA accepts: 'sheep', 'sheeep', 'sheeeep', etc. (one or more 'e's)
Rejects: 'shep', 'sheep!', 'sheap'

Corresponding regex: she+p

Types of FSA:

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 6

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

• Deterministic FSA (DFA): Each state has exactly one transition per input symbol. Faster and
simpler to implement.

• Non-Deterministic FSA (NFA): A state may have multiple transitions for the same input. More
expressive notation; can be converted to DFA using subset construction.

• Finite State Transducer (FST): An extension that produces output for each transition. Used in
morphological analysis to map word forms to their stems + features.

✎ Example — Finite State Transducer — Morphological Mapping

Input: 'running'
Transitions: r:r u:u n:n n:n i:0 n:0 g:0 → output 'run' + tag:VBG

FST maps surface form to lexical form:

foxes → fox+N+PL
walked → walk+V+PAST
bigger → big+ADJ+COMP

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 7

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter
4 Morphological Parsing

Definition — Morphological Parsing:

Morphological parsing (also called morphological analysis) is the process of analyzing the
internal structure of words to determine their component morphemes — the smallest meaningful
units of language. The goal is to map a surface word form to its lemma and morphological
features.

4.1 Key Concepts in Morphology

Morpheme Types:
Morpheme Type Description Example

Root/Stem Core meaning-bearing part run, play, happy

Prefix Morpheme added before root un- in unhappy, re- in rerun

Suffix Morpheme added after root -ness in happiness, -ing in running

Inflection Changes grammatical form, not walk → walked, walks, walking

word class

Derivation Creates new words, often happy(ADJ) → happiness(N)

changes word class

Compounding Combining two or more roots tooth + brush = toothbrush

Clitics Reduced forms attached to it's = it is, I've = I have

words

4.2 Lemmatization vs. Stemming

Two major morphological reduction techniques are widely used in NLP:

Stemming:
Stemming crudely removes word suffixes using heuristic rules. It is fast but imprecise — the resulting
stem may not be a valid dictionary word.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 8

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — Porter Stemmer Examples

running → run (remove -ing)
happiness → happi (remove -ness, -y → i)
caresses → caress (remove -es)
studies → studi (over-stem: not the correct stem)
generously → generous → gener (two-step reduction)

Lemmatization:
Lemmatization uses vocabulary and morphological analysis to return the dictionary base form (lemma)
of a word. It requires knowing the word's POS tag to be accurate.

✎ Example — Lemmatization Examples

running (VBG) → run better(JJR) → good
studies (VBZ) → study was (VBD) → be
mice (NNS) → mouse went (VBD) → go

Note: POS tag is needed — 'studies' as a noun lemmatizes to 'study',

but as a verb it also lemmatizes to 'study'. Without POS, ambiguity remains.

Comparison:
Aspect Stemming Lemmatization

Speed Very fast Slower (uses lexicon)

Accuracy Lower (may produce Higher (produces valid words)

non-words)

Requires POS? No Yes (for best results)

Output of 'better' better good

Output of 'running' run run

Use case IR, keyword search NLP tasks needing meaning

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 9

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter Spelling Error Detection &

5
Correction
Spelling errors are extremely common in user-generated text — social media, search queries, OCR
output, and informal writing. Detecting and correcting them is a fundamental preprocessing step in many
NLP applications.

5.1 Types of Spelling Errors

• Non-Word Errors: The misspelled string is not a valid dictionary word. Easy to detect.

✎ Example — Non-Word Error

'graet' → not in dictionary → spelling error → likely 'great'

• Real-Word Errors: The misspelled string happens to be a valid word. Hard to detect.

✎ Example — Real-Word Error

'I will be their' (should be 'there') — 'their' is a valid word!
'The whether is nice' (should be 'weather')

• Typographic Errors: Caused by adjacent key presses — 'teh' for 'the', 'hte' for 'the'.

• Phonetic Errors: Sound-alike substitutions — 'fone' for 'phone', 'nite' for 'night'.

• Cognitive Errors: Confusion of similar words — 'affect/effect', 'its/it\'s'.

5.2 Edit Distance — The Core Algorithm

Definition — Levenshtein Edit Distance:

The minimum number of single-character operations (insertion, deletion, substitution) needed to
transform one string into another. It is the most widely used metric for spelling correction
candidate generation.

✎ Example — Edit Distance Computation

Transform 'kitten' → 'sitting':
kitten → sitten (substitute k→s)
sitten → sittin (substitute e→i)
sittin → sitting (insert g at end)
Edit Distance = 3

Transform 'graet' → 'great':

graet → great (swap a and e — transposition)
Damerau-Levenshtein distance = 1 (includes transpositions)

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 10

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Edit distance is computed using dynamic programming in O(mn) time where m and n are the lengths
of the two strings. The DP table stores the edit distance between all prefixes of both strings.

5.3 Noisy Channel Model for Spelling Correction

The Noisy Channel Model treats spelling correction as a probabilistic inference problem: given the
observed (possibly misspelled) word x, find the most probable intended word w:

✎ Example — Noisy Channel Model

P(w|x) ∝ P(x|w) × P(w)

P(w) = Language model probability of word w (is it a common word?)

P(x|w) = Channel model = probability of typing x when you meant w
(based on edit distance and confusion matrices)

Candidate words for 'graet': great, greet, grate

P(great) >> P(greet) >> P(grate) in typical English
Best correction: 'great'

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 11

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter
6 Words and Word Classes
A word is the basic unit of meaning in a language. In NLP, we must precisely define what we mean by a
'word', as the same surface form can have different meanings, and different forms can represent the
same concept. Word classes (also called parts of speech) are grammatical categories that group
words with similar syntactic and semantic behavior.

6.1 Open vs. Closed Class Words

• Open Class Words (Content Words): Accept new members regularly. Include nouns, verbs,
adjectives, adverbs. Examples: 'selfie', 'google', 'unfriend' — all new nouns/verbs.

• Closed Class Words (Function Words): Fixed, small inventories. Include prepositions, determiners,
pronouns, conjunctions, auxiliaries. Rarely gain new members.

6.2 Major Word Classes (Penn Treebank Tagset)

Tag Name Description Example

NN Noun (singular) Person, place, thing cat, NLP, city

NNS Noun (plural) Plural form cats, cities

NNP Proper noun Specific named entity London, Python, Alice

VB Verb (base form) Action/state (infinitive) run, eat, compute

VBD Verb (past tense) Past action ran, ate, computed

VBG Verb (gerund/present Ongoing action running, computing

participle)

VBN Verb (past participle) Used in eaten, computed

passive/perfect

JJ Adjective Modifies noun fast, intelligent

JJR Adjective (comparative) Comparing two things faster, smarter

JJS Adjective (superlative) Comparing many fastest, smartest

RB Adverb Modifies quickly, very, not

verb/adj/adverb

DT Determiner Precedes noun phrase the, a, an, this

IN Preposition/Subord. conj. Shows relationship in, on, because, that

PRP Personal pronoun Replaces noun phrase I, you, he, she, it

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 12

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Tag Name Description Example

CC Coordinating conj. Connects equal and, but, or, yet

elements

CD Cardinal number Count or quantity one, 42, million

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 13

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter
7 Part-of-Speech Tagging

Definition — POS Tagging:

Part-of-speech (POS) tagging is the process of assigning a syntactic category label (POS tag) to
each token in a sentence. It is a fundamental NLP task because the POS tag of a word provides
crucial information for parsing, NER, and semantic interpretation.

✎ Example — POS Tagging Example

Sentence: 'The quick brown fox jumps over the lazy dog.'

The → DT (Determiner)
quick → JJ (Adjective)
brown → JJ (Adjective)
fox → NN (Noun, singular)
jumps → VBZ (Verb, 3rd person singular present)
over → IN (Preposition)
the → DT (Determiner)
lazy → JJ (Adjective)
dog → NN (Noun, singular)

7.1 Rule-Based POS Tagging

Early taggers like ENGTWOL used large manually crafted rule sets. A word is first assigned all possible
tags from a lexicon, then disambiguation rules remove incorrect tags.

✎ Example — Brill Tagger Rules

Rule: If a word is tagged as NN (noun) but the previous word is DT (determiner) and
the next word is VBZ (verb), change tag to NN.
Rule: If word ends in '-ing' and is tagged as NN, change to VBG.

Brill tagger learns these rules automatically from tagged corpora.

7.2 HMM-Based POS Tagging

A Hidden Markov Model (HMM) models POS tagging as a sequence labeling problem. The POS tags
are hidden states and the words are observations. The model uses two probabilities:

• Transition Probability P(tag_i | tag_{i-1}): How likely is it for tag T2 to follow tag T1? (e.g., 'DT is
usually followed by JJ or NN')

• Emission Probability P(word | tag): How likely is it for a word to be generated by a given tag? (e.g.,
'the word "run" is likely given VB tag')

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 14

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — HMM Tagging — Key Equations

Tag sequence: t* = argmax_t P(t1...tn | w1...wn)
≈ argmax_t ∏ P(wi|ti) × P(ti|ti-1)

Decoding: Viterbi Algorithm (dynamic programming)

— Finds the most probable tag sequence efficiently in O(n × |T|^2) time
— T = tag vocabulary, n = sentence length

7.3 Neural POS Tagging

Modern POS taggers use neural networks that automatically learn features from word embeddings
rather than hand-crafted features:

• BiLSTM-CRF: Bidirectional LSTM captures left and right context; CRF layer ensures globally
consistent tag sequences.

• Transformer-based taggers (BERT): Fine-tune pre-trained BERT with a classification head on top;
achieves near-human accuracy (~97% on Penn Treebank).

Method Approach Accuracy Speed

Rule-Based Hand-crafted rules ~90% Fast

HMM Statistical + Viterbi ~93-95% Fast

MaxEnt / CRF Log-linear sequence model ~96% Medium

BiLSTM-CRF Neural sequence model ~97% Medium

BERT Fine-tuned Transformer + classification ~97.5% Slow (GPU)

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 15

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

PART B — SYNTACTIC ANALYSIS

Chapter
8 Context-Free Grammar (CFG)

Definition — Context-Free Grammar (CFG):

A Context-Free Grammar G = (N, Σ, R, S) consists of: N (non-terminals = syntactic categories),
Σ (terminals = words), R (production rules of the form A → α), and S ∈ N (start symbol, typically
'S' for sentence). Each rule rewrites a non-terminal independently of surrounding context.

8.1 CFG Rules — Structure

CFG rules define how complex syntactic units are built from simpler ones. The standard phrase
structure rules for English look like:

✎ Example — Core English CFG Rules

S → NP VP (Sentence = Noun Phrase + Verb Phrase)
NP → DT N (NP = Determiner + Noun)
NP → DT JJ N (NP = Det + Adj + Noun)
NP → PRP (NP = Pronoun)
NP → NP PP (NP can contain PP, e.g. 'the cat on the mat')
VP → V NP (VP = Verb + Object NP)
VP → V NP PP (VP = Verb + NP + Prepositional Phrase)
VP → V S (VP = Verb + embedded Sentence)
PP → P NP (PP = Preposition + NP)

Lexical rules:
DT → the | a | an | this | that
N → dog | cat | mouse | man | telescope
V → saw | hit | chased | loves
P → on | in | with | at | over

8.2 Parse Trees from CFG

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 16

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — CFG Parse Tree Example

Sentence: 'The dog chased the cat in the park.'

S
/\
NP VP
/\\
DT N VP
the dog / \
V NP
chased \
NP PP
/\/\
DT N P NP
the cat in |
DT N
the park

The Chomsky Normal Form (CNF) is a simplified CFG where every rule has the form A → BC (two
non-terminals) or A → a (one terminal). Many parsing algorithms require CNF. Any CFG can be
converted to CNF.

9. Constituency Parsing

Definition — Constituency Parsing:

Constituency parsing (also called phrase structure parsing) builds a hierarchical tree structure of
a sentence according to a CFG, where leaf nodes are words and internal nodes are syntactic
phrases. The result is a constituency parse tree.

CYK Algorithm (Cocke-Younger-Kasami):

The CYK algorithm is the most famous constituency parser. It works bottom-up using dynamic
programming on a grammar in CNF. It runs in O(n^3 × |G|) time where n is sentence length and |G| is
grammar size.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 17

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — CYK Parsing — Intuition

Sentence: 'She eats fish' (3 words → 3×3 chart)

1. Fill diagonal (single words): She=NP, eats=V, fish=NP

2. Fill pairs: 'She eats' → VP? No. 'eats fish' → VP (V NP) ✓
3. Fill triple: 'She eats fish' → S (NP VP) ✓ → PARSE FOUND

Chart (lower triangle): each cell [i,j] stores all non-terminals

spanning words i through j.

Earley Parser:
A more flexible top-down + bottom-up parser that handles any CFG (not just CNF). It runs in O(n^3) in
the worst case but O(n^2) for unambiguous grammars and O(n) for right-linear grammars. Handles
empty productions and left recursion.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 18

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter
10 Dependency Parsing

Definition — Dependency Parsing:

Dependency parsing identifies the grammatical dependency relationships between words in a
sentence. It represents the sentence as a directed graph (dependency tree) where: each word is
a node; arcs connect words; each arc has a label indicating the grammatical relation (e.g., nsubj,
dobj, prep); every word has exactly one head except the root.

10.1 Dependency Relations (Universal Dependencies)

Relation Full Name Example

nsubj Nominal subject 'Alice' in 'Alice runs'

dobj / obj Direct object 'cake' in 'She ate cake'

iobj Indirect object 'him' in 'She gave him a book'

amod Adjectival modifier 'red' in 'red car'

advmod Adverbial modifier 'quickly' in 'runs quickly'

det Determiner 'the' in 'the dog'

prep / nmod Prepositional modifier 'on the mat' in 'cat on the mat'

aux Auxiliary 'will' in 'She will run'

conj Conjunction coordinates in 'cats and dogs'

punct Punctuation period, comma attached to head

✎ Example — Dependency Parse — Full Example

Sentence: 'The cat quickly ate the fresh fish.'

Root: ate
ate ←nsubj— cat
cat ←det— The
ate ←advmod— quickly
ate ←dobj— fish
fish ←det— the
fish ←amod— fresh
ate ←punct— .

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 19

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

10.2 Parsing Algorithms

Transition-Based Parsing (Arc-Standard):

Uses a stack and buffer. At each step, a classifier decides one of three actions: SHIFT (move buffer
word to stack), LEFT-ARC (add left dependency, pop from stack), RIGHT-ARC (add right dependency,
pop from stack). Very fast — O(n) — makes it suitable for real-time NLP. Used in spaCy and Stanford
NLP.

Graph-Based Parsing (Eisner / Chu-Liu-Edmonds):

Scores all possible dependency arcs, then finds the maximum spanning tree. O(n^2) or O(n^3). More
globally optimal than transition-based but slower. Modern deep learning-based parsers use biaffine
attention to score arcs.

11. Probabilistic Parsing

Real sentences are often syntactically ambiguous — multiple parse trees are valid. Probabilistic
Parsing assigns probabilities to competing parses and selects the most probable one.

Definition — Probabilistic Context-Free Grammar (PCFG):

A PCFG extends a CFG by assigning a probability to each production rule such that the
probabilities of all rules for a given non-terminal sum to 1. P(A → α) = probability of using this
rule when expanding A.

✎ Example — PCFG Rules with Probabilities

S → NP VP [1.0]
NP → DT NN [0.5]
NP → NNP [0.3]
NP → NP PP [0.2]
VP → VBD NP [0.4]
VP → VBZ [0.3]
VP → VP PP [0.3]

Probability of a tree T = product of all rule probabilities used.

Best parse = argmax_T P(T | sentence) (Viterbi for PCFGs)

PCFGs are typically estimated from treebanks: P(A → α) = count(A → α) / count(A). Limitations include
the independence assumption — rules are context-free, ignoring the parent or sibling nodes.
Lexicalized PCFGs (Collins parser) and neural parsers address this by conditioning on lexical heads.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 20

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

PART C — SEMANTIC ANALYSIS

Chapter
12 Meaning Representation
Meaning representation is the process of mapping natural language sentences to formal
representations that capture their semantic content in a way that computers can reason over. This is the
core goal of Natural Language Understanding (NLU).

12.1 First-Order Logic (FOL)

First-Order Logic (also called Predicate Logic) is one of the oldest formal systems for meaning
representation. It uses predicates, constants, variables, and quantifiers.

✎ Example — FOL Representation

Sentence: 'Every student likes some professor.'
FOL: ∀x [Student(x) → ∃y [Professor(y) ∧ Likes(x,y)]]

Sentence: 'Alice is a doctor and she works at the hospital.'

FOL: Doctor(Alice) ∧ WorksAt(Alice, Hospital)

Sentence: 'No cat is a dog.'

FOL: ¬∃x [Cat(x) ∧ Dog(x)] OR ∀x [Cat(x) → ¬Dog(x)]

12.2 Semantic Role Labeling (SRL)

Definition — Semantic Role Labeling:

SRL identifies the predicate (main verb) in a sentence and labels its arguments with semantic
roles: who did what to whom, when, where, why, and how. It answers: 'What is the event? Who
are the participants? What are their roles?'

✎ Example — SRL — PropBank Roles

Sentence: 'The doctor carefully examined the patient at the clinic yesterday.'

Predicate: examined
ARG0 (Agent): 'The doctor' → who performed the action
ARGM-MNR (Manner): 'carefully' → how
ARG1 (Patient/Theme):'the patient' → what was examined
ARGM-LOC (Location): 'at the clinic' → where
ARGM-TMP (Temporal): 'yesterday' → when

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 21

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

12.3 Abstract Meaning Representation (AMR)

AMR represents sentence meaning as a rooted directed acyclic graph where nodes are concepts
(predicate frames, named entities, or words) and edges are relationships. AMR abstracts away from
surface form — different sentences with the same meaning get the same AMR.

✎ Example — AMR Example

Sentence: 'The boy wants the girl to believe him.'

(w / want-01
:ARG0 (b / boy)
:ARG1 (b2 / believe-01
:ARG0 (g / girl)
:ARG1 b))

12.4 Frame Semantics & FrameNet

Frame Semantics (Fillmore) proposes that words evoke cognitive frames — structured knowledge
about a situation. FrameNet is a lexical database organized around frames with their frame elements
(participants/roles).

✎ Example — FrameNet — Commercial Transaction Frame

Frame: COMMERCE_BUY
Frame Elements: Buyer, Seller, Goods, Money

'Alice bought a laptop from Bob for $500.'

Buyer=Alice, Seller=Bob, Goods=laptop, Money=$500

'Alice purchased / acquired / paid for a laptop'

All evoke COMMERCE_BUY frame with Buyer=Alice

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 22

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter
13 Ambiguity Resolution
Ambiguity resolution is the process of determining the correct interpretation of an ambiguous expression
in context. Since ambiguity is pervasive at every level of language (lexical, syntactic, semantic,
pragmatic), NLP systems must have robust mechanisms to identify and resolve it.

13.1 PP Attachment Ambiguity Resolution

Prepositional Phrase (PP) attachment is one of the most studied forms of syntactic ambiguity. A PP can
attach to either the verb or the noun preceding it.

✎ Example — PP Attachment Resolution

Sentence: 'I saw the man with the binoculars.'

Interpretation 1: [VP saw [NP the man] [PP with the binoculars]]
→ I used binoculars to see him. (VP attachment)

Interpretation 2: [VP saw [NP the man [PP with the binoculars]]]
→ The man was carrying binoculars. (NP attachment)

Resolution: Use corpus frequency, world knowledge, or neural context.

Key question: Is it more common to 'see with binoculars' or 'man with binoculars'?

Approaches to PP Attachment Resolution:

• Hindle & Rooth (1993): Use corpus co-occurrence statistics to estimate which attachment is more
frequent.

• Neural models: Encode the full sentence context using LSTM or Transformer; classify attachment.

• World Knowledge: Semantic constraints rule out implausible attachments.

13.2 Selectional Restrictions

Selectional restrictions (also called selectional preferences) are semantic constraints imposed by
predicates (verbs/adjectives) on the type of arguments they can take. They help resolve ambiguity by
ruling out semantically implausible readings.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 23

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — Selectional Restrictions

'The bank was steep and eroded.'
'steep' and 'eroded' apply to physical objects (not financial institutions)
→ Selectional restriction resolves: bank = RIVERBANK ✓

'She ate the appointment.'

'eat' selects for FOOD argument → 'appointment' is not food
→ Selectional violation detected → metaphorical/error reading

13.3 Coreference Resolution

Coreference resolution identifies all expressions in a document that refer to the same real-world entity.
Mentions that refer to the same entity form a coreference chain (or cluster).

✎ Example — Coreference Resolution Example

'Elon Musk founded Tesla in 2003. He also started SpaceX in 2002.'
Chain 1: {Elon Musk, He} → both refer to person: Elon Musk
Chain 2: {Tesla} → company: Tesla
Chain 3: {SpaceX} → company: SpaceX

'The trophy did not fit in the suitcase because it was too big.'
'it' → trophy (not suitcase) — requires world knowledge + context

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 24

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Chapter
14 Word Sense Disambiguation (WSD)

Definition — Word Sense Disambiguation (WSD):

Word Sense Disambiguation is the task of determining which meaning (sense) of an ambiguous
word is intended in a given context. It is considered one of the central and most difficult problems
in NLP — sometimes called the 'AI-complete' problem because solving it fully requires
human-level intelligence.

✎ Example — WSD — The Classic 'bank' Example

Word: BANK
Sense 1 (Financial): 'I deposited money in the bank.'
Sense 2 (Riverbank): 'We picnicked on the river bank.'
Sense 3 (Turn/Tilt): 'The airplane banked steeply to the left.'

WSD system must assign the correct sense based on surrounding words/context.

14.1 Knowledge-Based WSD

Knowledge-based methods use external lexical resources — primarily WordNet — to determine word
senses without requiring labeled training data.

WordNet:
WordNet is a large lexical database of English organized into synsets (synonym sets). Each synset
represents one concept/sense. Words can belong to multiple synsets.

✎ Example — WordNet Entry for 'bank'

bank#1: 'a financial institution that accepts deposits...' (Hypernym: institution)
bank#2: 'sloping land beside a body of water' (Hypernym: slope, incline)
bank#3: 'a building used as a bank' (Hypernym: building)
bank#4: 'an arrangement of similar objects in a row' (e.g., bank of computers)

Lesk Algorithm:
The original (1986) knowledge-based WSD algorithm. For a target word, overlap the glosses (dictionary
definitions) of its senses with the glosses of surrounding words. The sense with the highest overlap
score wins.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 25

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — Lesk Algorithm

Target: 'bank' in 'I deposited my salary in the bank.'

Context words: deposited, salary, in

bank#1 gloss: 'financial institution accepts deposits manages money'
Overlap with context: {deposited} → score = 1
bank#2 gloss: 'sloping land beside body of water river stream'
Overlap with context: {} → score = 0

Winner: bank#1 (financial) ✓

14.2 Supervised WSD

Supervised methods treat WSD as a standard classification problem. For each ambiguous word, a
separate classifier is trained on sense-annotated examples. SemCor is the most widely used
sense-annotated corpus.

Features for Supervised WSD:

• Surrounding words (bag of words): Words in a window of ±k positions.

• POS tags: POS of the target word and neighbors.

• Collocations: Specific word combinations that strongly indicate a sense.

• Syntactic relations: The subject, object, or head of the target word.

✎ Example — Supervised WSD Feature Vector for 'bank'

Context: 'She walked along the river bank at sunset.'
Features: {prev_word=river, next_word=at, POS=NN, has_river=True, has_money=False}
Label: bank#2 (riverbank)

Context: 'He withdrew $500 from the bank.'

Features: {prev_word=the, prev_prev=from, has_$=True, has_river=False}
Label: bank#1 (financial)

14.3 Neural & Context-Based WSD

Modern WSD systems use contextualized word representations from transformer models. Unlike static
word embeddings (Word2Vec), where 'bank' always has the same vector, BERT produces different
embeddings for the same word in different contexts — naturally capturing word sense.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 26

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

✎ Example — BERT for WSD — Contextualized Embeddings

Sentence A: 'I went to the bank to deposit my cheque.'
BERT embedding of 'bank' → close to vectors of: money, finance, account

Sentence B: 'We sat by the bank and watched the river flow.'
BERT embedding of 'bank' → close to vectors of: river, shore, water

The same word token 'bank' gets a completely different vector in each context.
WSD is then a simple nearest-neighbor search in embedding space!

Method Type Requires Labels? Performance

Lesk Algorithm Knowledge-based No Low-Medium

WordNet + Walker Knowledge-based No Medium

Naive Bayes Supervised ML Yes Medium

SVM / MaxEnt Supervised ML Yes Medium-High

BiLSTM Neural supervised Yes High

BERT fine-tuned Neural supervised Yes (few-shot OK) State-of-the-art

Sense2Vec Unsupervised No Medium-High

neural

Unit 2 — Quick Revision Summary

Topic Key Points

Corpus Structured text collection; types: raw, annotated, parallel, treebank;

CoNLL format

Regex Pattern matching language; used for tokenization, extraction;

metacharacters: . * + ? [ ] |

FSA / FST States + transitions; DFA/NFA; FST maps input to output

(morphological analysis)

Morphological Parsing Analyze word structure; morphemes: root, prefix, suffix; stemming vs
lemmatization

Spelling Correction Edit distance (Levenshtein); Noisy Channel Model: P(w|x) ∝

P(x|w)×P(w)

Word Classes Open class (N,V,Adj,Adv) vs closed class (DT,IN,PRP); Penn

Treebank 45-tag set

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 27

NLP Study Notes | Unit 2: Word-Level, Syntactic & Semantic Analysis Academic Reference Guide

Topic Key Points

POS Tagging Rule-based → HMM (Viterbi) → CRF → BiLSTM → BERT; ~97.5%

accuracy

CFG 4-tuple (N,Σ,R,S); phrase structure rules; parse trees; CNF for CYK
algorithm

Constituency Parsing CYK (bottom-up DP); Earley (top-down + bottom-up); output = phrase
tree

Dependency Parsing Word-to-word arcs + labels; transition-based (O(n), spaCy) vs

graph-based

Probabilistic Parsing PCFG: P(rule) from treebank; best parse via Viterbi; lexicalized
PCFGs

Meaning Representation FOL, SRL (ARG0/ARG1), AMR (graph), FrameNet (frame + frame
elements)

Ambiguity Resolution PP attachment, selectional restrictions, coreference resolution chains

WSD Determine correct word sense; Lesk (knowledge), SVM (supervised),

BERT (neural, best)

■ Note: This concludes Unit 2. Together, Units 1 and 2 cover the complete foundational landscape of
NLP — from history and paradigms, through word-level and syntactic processing, to semantic
understanding. These concepts underpin all modern NLP systems including large language models
like GPT and BERT.

Unit 2 — Word-Level, Syntactic & Semantic Analysis Page 28