Natural Language Processing

CHAPTER 3: SYNTAX
ANALYSIS
By
Prof. Mukhtar Ansari
Department of Computer Engineering.
AIKTC –Anjuman-I-Islam’s Kalsekar Technical Campus.
 CHAPTER 3: SYNTAX ANALYSIS

• Part-Of-Speech tagging(POS): • Maximum Entropy model

• Tag set for English (Upenn Treebank) • Conditional random Field (CRF)
• Difficulties /Challenges in POS tagging • Parsers: Top down and Bottom up
• Types • Modelling constituency
• Rule-based, • Bottom-Up Parser:
• Stochastic and • CYK,
• Transformation-based tagging • PCFG (Probabilistic Context Free
• Generative Model: Grammar),
• Hidden Markov Model (HMM Viterbi) for • Shift Reduce Parser
POS tagging • Top-Down Parser:
• Issues in HMM POS tagging • Early Parser,
• Discriminative Model: • Predictive Parser
 PART-OF-SPEECH TAGGING(POS)

• Part-Of-Speech tagging (POS tagging) is the process in NLP

of labeling each word in a sentence with its correct
grammatical category, such as noun, verb, adjective, or
adverb, based on both its definition and context.
• POS tagging is fundamental in NLP because it helps
algorithms understand sentence structure, resolve ambiguities
in words with multiple meanings
 PART-OF-SPEECH TAGGING(POS)

• POS tagging is the process of assigning a grammatical

category (part of speech) to each word in a text, such as noun,
verb, adjective, etc., based on both its definition and context.
• Why POS Tagging
• Syntax parsing → Helps in understanding sentence structure.
• Information retrieval → Improves search accuracy by understanding
word roles.
• Machine translation → Aids in choosing correct word forms.
• Named Entity Recognition → Differentiates proper nouns from
common nouns.
 EXAMPLE

• Sentence:
"The quick brown fox jumps over the lazy dog."
Word Tag Meaning
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)
 TAG SETS

• The Penn Treebank Tag set (common in English NLP)

includes:
• Nouns: NN (singular), NNS (plural), NNP (proper noun, singular)
• Verbs: VB (base), VBD (past), VBG (gerund), VBZ (3rd person
present)
• Adjectives: JJ, JJR (comparative), JJS (superlative)
• Adverbs: RB, RBR, RBS
• Others: IN (preposition), DT (determiner), PRP (pronoun), CC
(conjunction)
 POS TAGGING APPROACHES

•Rule-based
•Statistical (HMM, CRF)
•Neural / Deep Learning
 POS TAGGING APPROACHES - RULE-BASED

• Uses handcrafted grammar rules and dictionaries.

• Example: If a word ends with -ly, it’s likely an adverb.
• Handcrafted lexicons + context rules decide each word’s tag.
• Classic representatives include dictionary/heuristic taggers and Brill’s transformation-based tagger.
• Strengths
• Transparent, explainable decisions; easy to debug.
• Good with specialized, stable domains when rules are known.
• Pitfalls
• Labor-intensive to build; brittle for slang/new words.
• Hard to scale to morphologically rich languages without many rules.
• When to use
• Teaching/diagnostics; closed domains with clear grammar guidelines; when interpretability is
critical.
 POS TAGGING APPROACHES - STATISTICAL (HMM, CRF)

• Uses probabilities from labeled corpora.

• Example: Hidden Markov Models predict the most probable tag
sequence.
• Strengths
• Simple, fast, data-driven; handles ambiguity better than rules alone.
• Can add unknown-word handling via suffixes, capitalization, etc.
• Pitfalls
• Generative independence assumptions (word depends only on its tag; tag
depends only on previous tag) can be limiting.
• Struggles when crucial cues are non-local (long-distance context).
 POS TAGGING APPROACHES - NEURAL / DEEP LEARNING

• Uses models like BiLSTM, Transformers (BERT) for context-

aware tagging.
• Most accurate in modern NLP.
• Why they work well
• Contextualization: the same word gets different vectors in different
contexts (solves “book/Book/refuse” ambiguity).
• Subword modeling: handles OOV and morphology (-ing, -tion, -ly)
without manual rules.
• Long-range dependencies: attention captures cues far away in the
sentence.
 POS TAGGING APPROACHES - NEURAL / DEEP LEARNING

• Mini examples (classic ambiguities):

• “Book a flight” vs “Read a book.”
• Neural models see different context patterns around book,
tagging it as VB in the first and NN in the second.“
• They refuse to permit us to obtain the refuse permit.”
• First refuse → VB, second refuse → NN; first permit → VB,
second permit → NN—resolved by surrounding words,
captured by attention.
 POS TAGGING APPROACHES - NEURAL / DEEP LEARNING

• Strengths
• State-of-the-art accuracy across domains and languages.
• Minimal feature engineering; robust to OOV and noisy text.
• Pitfalls
• Heavier compute; needs labeled data (though pretraining helps a lot).
• Less intrinsically interpretable (though attention/attribution helps).
• When to use
• Default for high-accuracy tagging today; especially for varied or
noisy domains.
 DIFFICULTIES /CHALLENGES IN POS TAGGING

• Ambiguity of Words
• Unknown / Out-of-Vocabulary Words
• Morphological Complexity
• Context Sensitivity
• Idiomatic Expressions
• Proper Nouns vs Common Nouns
• Code-Switching / Mixed Languages
• Domain Adaptation
• Tokenization Issues
• Sarcasm and Figurative Language
 AMBIGUITY OF WORDS

• Many words can have multiple possible POS tags

depending on context.
• Example:
• "Book a flight" → Book (verb)
• "Read a book" → Book (noun)
• Without context, the tagger can make the wrong choice.
 UNKNOWN / OUT-OF-VOCABULARY WORDS

• Words not in the training data (slang, new coinages,

technical jargon) may be hard to classify.
• Example:
• "cryptojacking" or "googlable" → no prior data to infer
tag.
 MORPHOLOGICAL COMPLEXITY

• In languages with rich morphology (e.g., Hindi,

Turkish, Finnish), a single word can encode tense,
number, gender, and case — making tagging harder.
• Example (Turkish):
• evlerinizden (“from your houses”) is one word but carries
multiple grammatical markers.
 CONTEXT SENSITIVITY

• Some words require longer context to determine the

correct tag, especially in complex sentences.
• Example:
• “Visiting relatives can be annoying"→
• “Visiting” could be a verb (present participle) or
adjective.
 IDIOMATIC EXPRESSIONS

• In fixed phrases, words may take non-standard

meanings.
• Example:
• "Kick the bucket" → "Kick" is not literally a verb of
physical action.
 PROPER NOUNS VS COMMON NOUNS

•Names, places, and brands can be mistaken for

normal words.
•Example: "Amazon":
• Proper noun (company/river)
• Common noun (mythical warrior women)
 CODE-SWITCHING / MIXED LANGUAGES

•In multilingual contexts, the same sentence may

switch languages mid-way.
•Example:
•"Main market se groceries le aaya" (Hindi +
English mix).
 DOMAIN ADAPTATION

•Models trained on news text may fail on

tweets or medical records because vocabulary,
grammar, and style differ.
 TOKENIZATION ISSUES

•Incorrect splitting of words (e.g., handling

contractions, hyphenated terms) can mislead the
tagger.
•Example:
• "don't" → should be "do" (VB) + "n't" (RB).
 SARCASM AND FIGURATIVE LANGUAGE

•Contextual meaning may not match literal

grammar.
•Example:
•"Oh great, another Monday" → “great” is positive
grammatically, but negative in meaning.
PENN TREEBANK WITH 47 POS TAGS
 GENERATIVE MODEL: HIDDEN MARKOV MODEL FOR POS TAGGING

• A Hidden Markov Model (HMM) is a probabilistic generative

model commonly used for part-of-speech (POS) tagging in
natural language processing.
• In this context, each word in a sentence is considered an
observation, while the grammatical categories (POS tags) are
the hidden states.
• The goal is to assign the most likely sequence of POS tags to a
sequence of words based on statistical relationships learned
from labeled data.
 HOW HMM WORKS FOR POS TAGGING

• States: The hidden states are the POS tags (e.g., Noun, Verb,
Determiner, Adjective).
• Observations: The words in the sentence (e.g., “book”,
“runs”, “the”).
• Transition Probabilities: Probability of one POS tag
following another (e.g., P(Verb|Noun)).
• Emission Probabilities: Probability of a word being
generated by a tag (e.g., P("book"|Noun)).
• Initial Probabilities: Probability distribution over the first tag
in a sentence.
 DECODING WITH THE VITERBI ALGORITHM

•The Viterbi algorithm is used to efficiently find the

tag sequence that maximizes the multiplication of
transition and emission probabilities for the entire
sentence.
 EXAMPLE BREAKDOWN

• For the phrase “the light book”, HMM would calculate:

• The best sequence of tags for “the”, “light”, “book”
(likely Determiner, Adjective/Noun, Noun/Verb).
• It scores all combinations and picks the one with the
highest probability based on the model's learned
probabilities.
 KEY POINTS

• HMMs make the Markov assumption: each state (tag)

depends only on the previous state, not the entire
sequence—a limitation for more complex dependencies.
• HMM-based POS taggers perform competitively on
standard benchmarks and are still a strong baseline,
though deep learning models like BiLSTM have
surpassed them in accuracy recently.
 POS TAGGING WITH HIDDEN MARKOV MODEL

•HMM (Hidden Markov Model) is a Stochastic

technique for POS tagging.
•Hidden Markov models are known for their
applications to reinforcement learning and
temporal pattern recognition such as speech,
handwriting, gesture recognition, musical score
following, bioinformatics.
 AN EXAMPLE

• Let us consider an example proposed by Dr. Luis

Serrano and find out how HMM selects an appropriate
tag sequence for a sentence.
 EXPLANATION

•In this example, we consider only 3 POS tags that

are noun, modal and verb.
•Let the sentence “ John can see Will ” be tagged as
noun, modal, verb and a noun and to calculate the
probability associated with this particular sequence
of tags we require their Transition probability and
Emission probability.
 TRANSITION PROBABILITY

•The transition probability is the likelihood of a

particular sequence for example, how likely is that
a noun is followed by a model and a model by a
verb and a verb by a noun.
•This probability is known as Transition probability.
•It should be high for a particular sequence to be
correct.
 EMISSION PROBABILITY

• Now, what is the probability that the word

• John is a noun,
• can is a model,
• see is a verb and
• Will is a noun.
• These sets of probabilities are Emission probabilities
and should be high for our tagging to be likely.
LET US CALCULATE THE ABOVE TWO PROBABILITIES FOR THE SET
OF SENTENCES BELOW

• Mary Jane can see Will

• Spot will see Mary
• Will Jane spot Mary?
• Mary will pat Spot

• Note that Mary Jane, Spot, and Will are all names.
 CALCULATING EMISSION PROBABILITIES

• In the above sentences, the word Mary appears four

times as a noun.
• To calculate the emission probabilities, let us create a
counting table in a similar manner.
COUNT THE OCCURRENCES OF EACH WORD UNDER EACH TAG:

Word Noun Modal Verb

Mary 4 0 0
Jane 2 0 0
Will 1 3 0
Spot 2 0 1
can 0 1 0
see 0 0 2
pat 0 0 1
EMISSION PROBABILITIES (NORMALIZED PER TAG COLUMN):

Word Noun Modal Verb

Mary 4/9 0 0
Jane 2/9 0 0
Will 1/9 3/4 0
Spot 2/9 0 1/4
can 0 1/4 0
see 0 0 2/4
pat 0 0 1/4
 FROM THE ABOVE TABLE, WE INFER THAT

• The probability that Mary is Noun = 4/9

• The probability that Mary is Model = 0
• The probability that Will is Noun = 1/9
• The probability that Will is Model = 3/4

• In a similar manner, you can figure out the rest of the

probabilities. These are the emission probabilities.
 CALCULATING TRANSITION PROBABILITIES

• Next, we have to calculate

the transition probabilities.
• So, we define two more
tags <S> and <E>.
• <S> is placed at the
beginning of each
sentence and <E> at the
end as shown in the figure
below.
LET US AGAIN CREATE A TABLE AND FILL IT WITH THE CO -
OCCURRENCE COUNTS OF THE TAGS.

N M V <E>

<S> 3 1 0 0

N 1 3 1 4

M 1 0 3 0

V 4 0 0 0
 EXPLANATION

• In the above figure, we can see that the <S> tag is followed by
the N tag three times, thus the first entry is 3.
• The model tag follows the <S> just once, thus the second
entry is 1.
• In a similar manner, the rest of the table is filled.
 CALCULATING TRANSITION PROBABILITIES

• Next, we divide each term in a

row of the table by the total
number of co-occurrences of
the tag in consideration.
• For example, The Model tag is
followed by any other tag four
times as shown below, thus we
divide each element in the
third row by four.
LET US AGAIN CREATE A TABLE AND FILL IT WITH THE CO -
OCCURRENCE COUNTS OF THE TAGS.

N M V <E>

<S> 3/4 1/4 0 0

N 1/9 3/9 1/9 4/9

M 1/4 0 3/4 0

V 4/4 0 0 0
 FINALLY

• These are the respective transition probabilities for the

above four sentences.
• Now how does the HMM determine the appropriate
sequence of tags for a particular sentence from the
above tables?

•Let us find it out.

 TAKE A NEW SENTENCE AND TAG THEM WITH WRONG TAGS.

• Let the sentence, ‘ Will can spot Mary’ be tagged as-

• Will as a model
• Can as a verb
• Spot as a noun
• Mary as a noun

• Now calculate the probability of this sequence being correct in

the following manner.
CALCULATING PROBABILITIES
 CALCULATING PROBABILITIES

• The probability of the tag Model (M) comes after the tag
<S> is 1/4 as seen in the table.
• Also, the probability that the word Will is a Model is 3/4.
• In the same manner, we calculate each and every probability
in the graph.
• Now the product of these probabilities is the likelihood that
this sequence is right.
• Since the tags are not correct, the product is zero.
1/4*3/4*3/4*0*1*2/9*1/9*4/9*4/9=0
NOW CALCULATE THE PROBABILITY OF THIS SEQUENCE BEING
CORRECT IN THE FOLLOWING MANNER.
NOW CALCULATE THE PROBABILITY OF THIS SEQUENCE BEING
CORRECT IN THE FOLLOWING MANNER.

• Calculating the product of these terms we get,

3/4*1/9*3/9*1/4*3/4*1/4*1*4/9*4/9=0.00025720164
 FOR OUR EXAMPLE,

• Keeping into consideration just three POS tags we have mentioned, 81

different combinations of tags can be formed.
• In this case, calculating the probabilities of all 81 combinations seems
achievable.
• But when the task is to tag a larger sentence and all the POS tags in
the Penn Treebank project are taken into consideration, the number of
possible combinations grows exponentially and this task seems
impossible to achieve.
• Now let us visualize these 81 combinations as paths and using the
transition and emission probability mark each vertex and edge as
shown below.
CALCULATING THE PROBABILITIES OF ALL 81 COMBINATIONS
DELETE ALL THE VERTICES AND EDGES WITH PROBABILITY ZERO

• The next step is to delete all the vertices and edges with
probability zero, also the vertices which do not lead to
the endpoint are removed.
 FINAL RESULT

• Now there are only two paths that lead to the end, let us calculate the
probability associated with each path.
• <S>→N→M→N→N→<E>
=3/4*1/9*3/9*1/4*1/4*2/9*1/9*4/9*4/9=0.00000846754

• <S>→N→M→N→V→<E>=3/4*1/9*3/9*1/4*3/4*1/4*1*4/9*4/9=0.
00025720164
• Clearly, the probability of the second sequence is much higher and
hence the HMM is going to tag each word in the sentence according
to this sequence.
 OPTIMIZING HMM WITH VITERBI ALGORITHM

•The Viterbi algorithm is a dynamic

programming algorithm for finding the most
likely sequence of hidden states—called the
Viterbi path—that results in a sequence of
observed events, especially in the context of
Markov information sources and hidden
Markov models (HMM).
 OPTIMIZING HMM WITH VITERBI ALGORITHM

•In the previous section, we optimized the HMM

and bought our calculations down from 81 to just
two.
•Now we are going to further optimize the HMM by
using the Viterbi algorithm.
•Let us use the same example we used before and
apply the Viterbi algorithm to it.
OPTIMIZING HMM WITH VITERBI ALGORITHM
 OPTIMIZING HMM WITH VITERBI ALGORITHM

• Consider the vertex encircled in the above example.

• There are two paths leading to this vertex as shown below
along with the probabilities of the two mini-paths.
 OPTIMIZING HMM WITH VITERBI ALGORITHM

• Now we are really concerned with the mini path having the
lowest probability.
• The same procedure is done for all the states in the graph as
shown in the figure below
 OPTIMIZING HMM WITH VITERBI ALGORITHM

• As we can see in the figure above, the probabilities of all paths

leading to a node are calculated and we remove the edges or
path which has lower probability cost.
• Also, you may notice some nodes having the probability of
zero and such nodes have no edges attached to them as all the
paths are having zero probability.
• The graph obtained after computing probabilities of all paths
leading to a node is shown below:
OPTIMIZING HMM WITH VITERBI ALGORITHM
 OPTIMIZING HMM WITH VITERBI ALGORITHM

• To get an optimal path, we start from the end and trace

backward, since each state has only one incoming edge, This
gives us a path as shown below
 OPTIMIZING HMM WITH VITERBI ALGORITHM

• As you may have noticed, this algorithm returns only one path as
compared to the previous method which suggested two paths.
• Thus by using this algorithm, we saved us a lot of computations.
• After applying the Viterbi algorithm the model tags the sentence as
following-

• Will as a noun
• Can as a model
• Spot as a verb
• Mary as a noun
 ISSUES IN HMM POS TAGGING

• Strong Independence Assumptions

• HMM assumes each tag depends only on the previous tag and each word
depends only on its tag.
• This ignores longer context and richer dependencies between words.
• Ambiguity Handling
• Many words can belong to multiple POS tags (e.g., “can” = verb or modal).
• HMM struggles to disambiguate using only local probabilities.
• Sparse Data Problem
• Some tag–tag or tag–word pairs may never appear in training, giving zero
probabilities.
• Requires smoothing, but performance still suffers on rare patterns.
 ISSUES IN HMM POS TAGGING

• Out-of-Vocabulary (OOV) Words

• Unseen words during training cannot be tagged reliably.
• Workarounds like <UNK> help but remain limited.
• Lack of Rich Features
• HMM uses only word identity and tag information.
• It cannot capture morphology, capitalization, or surrounding context.
• Bias Toward Frequent Tags
• Frequent tags dominate predictions due to probability estimates.
• Rare tags and less common usages are often misclassified.
 ISSUES IN HMM POS TAGGING

• Scalability
• Viterbi decoding has 𝑂(𝑛×∣𝑇∣2)O(n×∣T∣2) complexity.
• For large tag sets, this becomes computationally expensive.
• Domain Adaptation Issues
• Models trained on one domain (e.g., news) perform poorly on another (e.g.,
tweets).
• HMMs lack robustness to linguistic variations across domains.
• Lower Accuracy
• HMM taggers achieve ~90–93% accuracy.
• Modern CRF and neural models reach ~97%+.
 DISCRIMINATIVE MODEL

• Generative models are a wide class of machine learning

algorithms which make predictions by modelling joint
distribution P(y, x).
• An example of a generative model might be one that is trained
on collections of images from the real world in order to
generate similar images.
• Discriminative models are a class of supervised machine
learning models which make predictions by estimating
conditional probability P(y|x).
DISCRIMINATIVE MODEL
DISCRIMINATIVE MODEL
 DISCRIMINATIVE MODEL

• Also called conditional models.

• They estimate 𝑃(𝑦∣𝑥) directly.
• Examples: Logistic Regression, Maximum Entropy
Classifier.
• Used for classification or regression.
• Focus: decision boundaries between classes (e.g.,
pass/fail, alive/dead, healthy/sick).
 MAXIMUM ENTROPY MODEL

• The Maximum Entropy model is a probabilistic classification

model widely used in Natural Language Processing (NLP) and
machine learning.
• It belongs to the family of exponential models and is based on
the principle of maximum entropy.
• The principle states:
• When we don’t know the true distribution, we should prefer
the most uniform (maximum entropy) distribution possible
that still satisfies the known constraints.
PROBABILITY FORMULATION
 EXAMPLE

• We want to determine whether an email is Spam or Not

Spam.
• Possible classes:
• Spam
• Not Spam
• Features (observed signals in the email):
• Presence of the word “Free”
• Presence of the phrase “Click Here”
 FEATURES AS EVIDENCE

• If an email contains the word “Free”, it strongly

suggests spam.
• If an email contains the phrase “Click Here”, it is also
highly indicative of spam.
• These words act as features that guide the model’s
decision.
 MAXIMUM ENTROPY MODEL – CORE IDEA

• The model estimates the probability of a class 𝑦y given

features 𝑥x as:
• Where:
• 𝑓𝑖(𝑥,𝑦) = feature functions (e.g., does the email contain “Free”?)
• λi​ = weights/parameters (learned from training data, showing importance of features)
• 𝑍(𝑥)Z(x) = normalization factor ensuring all probabilities sum to 1

In simple terms:
The model combines all active features (like “Free”, “Click Here”), adds
their weights, and converts this into a probability through the exponential
function
 EXAMPLE CALCULATION

• Suppose during training the model learns the following

weights:
• Word “Free” → weight = +2.0 for Spam
• Phrase “Click Here” → weight = +1.5 for Spam
• Base bias for Spam → weight = +0.5
• So:
• Spam probability = 92%
• Not Spam probability = 8%
 INTERPRETATION

• The output:
𝑃(Spam∣Free, Click Here)=0.92
• means:
• If an email contains both “Free” and “Click Here,”
• The model predicts there is a 92% chance that the email
is Spam,
• And only 8% chance it is Not Spam.
 APPLICATIONS IN NLP

•Part-of-Speech (POS) tagging

•Named Entity Recognition (NER)
•Machine Translation
•Text classification (spam filtering, sentiment
analysis, etc.)
 CONDITIONAL RANDOM FIELDS (CRFS) - INTRODUCTION

• A Conditional Random Field (CRF for short) is a

discriminative sequence labelling model also called as a
sequence modelling algorithm.
• A Conditional Random Field (CRF) is a probabilistic
graphical model used in natural language processing (NLP)
for sequence labeling tasks such as part-of-speech (POS)
tagging and named entity recognition (NER).
• Conditional Random Fields (CRFs) are used for structured
prediction.
 CONDITIONAL RANDOM FIELDS (CRFS) - INTRODUCTION

•They are an extension of Maximum Entropy

Models (MaxEnt) to sequences (and more complex
structures).
•While MaxEnt makes predictions independently
for each item, CRFs consider the entire sequence
jointly, which makes them very powerful in
Natural Language Processing (NLP).
PROBABILITY FORMULATION
 EXAMPLE (POS TAGGING)

• Sentence: “She plays cricket”

• Observations: [She, plays, cricket]
• Labels: [PRON, VERB, NOUN]
• CRF considers:
• The word itself (e.g., “plays” → likely VERB)
• Surrounding words (context)
• Previous tags (if “She” is PRON, then “plays” is likely VERB)
• Thus, CRF predicts the entire tag sequence jointly rather than
word by word.
 EXAMPLE (NAMED ENTITY RECOGNITION)

• Sentence: "Alice lives in Paris"

• Observations: [Alice, lives, in, Paris]
• Labels: [B-PER, O, O, B-LOC]
• B-PER = Beginning of a Person name, B-LOC = Beginning of a
Location, O = Other (not a named entity)
• CRF considers:
• The word "Alice" (likely a person's name) gets B-PER, which
makes "lives" and "in" likely O, and makes “Paris” (which
comes after “in”) likely B-LOC.
 EXAMPLE (POS TAGGING)

• Sentence: "The cat sat"

• Observations: [The, cat, sat]
• Labels: [DET, NOUN, VERB]
• DET = Determiner, NOUN = Noun, VERB = Verb
• CRF considers:
• "The" starts a noun phrase, so “cat” following it is likely a
NOUN, which makes “sat” at the end very likely a VERB
due to common English sentence patterns.
 EXAMPLE (CHUNKING/ PHRASE LABELLING)

• Sentence: "Red apples are sweet"

• Observations: [Red, apples, are, sweet]
• Labels: [B-NP, I-NP, B-VP, I-VP]
• NP = Noun Phrase, VP = Verb Phrase, B = Beginning, I = Inside
• CRF considers:
• "Red" as a potential beginning of a noun phrase, followed by
another noun-like word “apples”. This context flags both as part
of NP. "Are" starts a verb phrase (B-VP), and "sweet" continues
it (I-VP).
 EXAMPLE (NAMED ENTITY RECOGNITION WITH DEPENDENCY )

• Sentence: "John works at Google"

• Observations: [John, works, at, Google]
• Labels: [B-PER, O, O, B-ORG]
• B-ORG = Beginning of an Organization
• CRF considers:
• "John" is labeled B-PER, so the organization entity “Google”,
which follows "at", is tagged B-ORG due to contextual
dependency and common sentence constructions in English.
 ADVANTAGES OF CRFS

•Overcomes Label Bias Problem (unlike MEMM)

•Considers entire sequence jointly for global
consistency
•Highly flexible features (can use word identity,
prefixes, suffixes, capitalization, etc.)
•Discriminative: directly models 𝑃(𝑦∣𝑥)P(y∣x)
 APPLICATIONS OF CRFS

• Part-of-Speech tagging
• Named Entity Recognition (NER)
• Chunking / Parsing
• Information extraction
• Bioinformatics (DNA/Protein sequence labelling)
 CHALLENGES IN PARSING

• Ambiguity: Same sentence can have multiple valid

parse trees.
• Example: “I saw the man with a telescope”
• Did I use the telescope, or did the man have the
telescope?
• Left Recursion: Can cause infinite loops in top-down
parsing.
• Efficiency: Large grammars (like in NLP) → parsing
can be slow.
 PARSING

• Parsing is the process of analyzing a sequence of

symbols, like words in a sentence or code in a program,
to determine its grammatical structure according to a set
of rules, often called a grammar.
• Two primary strategies for parsing are top-down and
bottom-up, which differ fundamentally in their approach
to building the parse tree, a hierarchical representation
of the input's structure.
 TYPES OF PARSING (BROADLY)

(A) Based on Direction

• Top-Down Parsing
• Start from start symbol (S) → expand until terminals match input.
• Works goal-directed (root → leaves).
• Example: Recursive Descent Parser.
• Bottom-Up Parsing
• Start from input tokens → reduce to start symbol (S).
• Works data-driven (leaves → root).
• Example: Shift-Reduce, LR Parsers.
 TYPES OF PARSING (BROADLY)

(B) Based on Purpose

• Syntactic Parsing
• Checks only structure (syntax).
• Example: Detects missing semicolon in code.
• Semantic Parsing
• Goes beyond structure → interprets meaning.
• Example in NLP:
• “Book the flight” → understood as a command, not about a
“book.”
 WHAT IS CONSTITUENCY?

• Constituency = the idea that sentences are made up of sub-

parts (constituents) which form a hierarchical structure.
• Each constituent is a group of words that function together as
a single unit in the sentence.
• In short grouping words into meaningful phrases & clauses.
• Example: “The man read this book”
• NP → The man
• VP → read this book
• S → NP + VP
 EXAMPLE

• Sentence: “The boy plays football.”

• Constituents:
• NP (Noun Phrase): “The boy”
• VP (Verb Phrase): “plays football”
• N (Noun): “boy”
• V (Verb): “plays”
• NP: “football”
So the sentence can be represented as a tree structure (called
a parse tree).
 EXAMPLE SENTENCE

• the cat sat on the mat

• Constituents:
• NP = the cat
• VP = sat on the mat
• PP = on the mat
 MODELLING CONSTITUENCY

• Top-down and bottom-up parsers are two fundamental

approaches to analyzing the structure of sentences in
language.
• Both play key roles in modelling constituency in NLP
by building parse trees.
• It represent how words group together into phrases and
sentences.
 TOP-DOWN PARSING

• How it works:
• Top-down parsing begins with the most general symbol (the root, usually "S" for Sentence)
and repeatedly breaks it down into smaller parts by applying grammar rules until it tries to
match the actual words of the sentence.
• Example:
• To parse "The cat sat," a top-down parser starts with "S".
• It applies rules like S → NP VP (Sentence = Noun Phrase + Verb Phrase), then expands NP
and VP, and keeps applying rules until reaching the actual words ("The", "cat", "sat").
• Characteristic:
• The process goes from the root of the tree to its leaves (the sentence words).
• It's good for predicting structures but can get stuck if multiple rules could match, possibly
requiring backtracking if a rule doesn't fit the input.
 BOTTOM-UP PARSING

• How it works:
• Bottom-up parsing starts from the words of the sentence (the leaves of the tree) and
attempts to combine them into larger phrases (like noun phrases or verb phrases)
using grammar rules, working up toward the root symbol.
• Example:
• Given "The cat sat," it first identifies "The" as a determiner and "cat" as a noun, then
combines them into a noun phrase (NP), then joins with "sat" (a verb) into a verb
phrase (VP), and finally combines NP and VP into a complete sentence (S).
• Characteristic:
• The process starts from the leaves and goes up to the root, often using a "shift-
reduce" mechanism (shift parts onto a stack, reduce them to larger units when rules
match).
 CONSTITUENCY PARSING

• Constituency parsing is about breaking a sentence into its

subparts—called constituents—using grammar rules, and
representing this as a tree.
• The main goal is to uncover how a sentence is structured in
terms of phrases (like noun phrases, verb phrases).
• Example: For "The cat sat," the tree would show that "The
cat" is a noun phrase (NP), "sat" is a verb phrase (VP), and
the overall sentence (S) consists of these two constituents.
 CONSTITUENCY PARSING

• Modelling:
• The parser uses a provided grammar (often a Context-Free
Grammar—CFG) with rules like S→NP VP, NP→Det N, etc.
to decide how to group the words.
• Both top-down and bottom-up parsers build these constituency
trees, but from opposite directions: top-down from the
sentence root to words, bottom-up from words up to the
sentence root
 BOTTOM-UP PARSER

• CYK, PCFG, and Shift-Reduce parsers are all bottom-

up parsing techniques—they build a parse tree starting
from the words (leaves) and work upward to the
sentence root, useful in NLP for constituency parsing.
• CYK,
• PCFG (Probabilistic Context Free Grammar),
• Shift Reduce Parser
CYK PARSER (COCKE-YOUNGER-KASAMI)
Thank you