Vidyavardhini’s College of Engineering & Technology

Department of Computer Engineering

CSDC7013:Natural Language Processing (NLP)

Module 1. Pragmatics & Discourse Processing

Code/Sub: - CSDC7013/ NLP /VII

By Prof. Sridhar

1
 Course Objectives
• To define natural language processing and to learn
various stages of natural language processing.
• To describe basic concepts and algorithmic
description of the main language levels:
Morphology, Syntax, Semantics, and Pragmatics
&Discourse analysis.
• To design and implement various language models
and POS tagging techniques.
• To design and implement applications based on
natural language processing.
 Course Outcomes
• Identify Challenges of NLP and ambiguities in
natural language.
• Apply Morphological analysis approaches on the
given data.
• Apply Syntactic analysis approaches on the given
data.
• Apply Semantic Analysis techniques on the given
data.
• Apply Pragmatic and Discourse Analysis
techniques on the given data.
• Design NLP based application.
 Topics
• Discourse: Reference Resolution
• Coreference Resolution
• Syntactic & Semantic Constraints on
Coreference
• Anaphora Resolution using Hobbs Algorithm
• Anaphora Resolution using Centering Algorithm
 Introduction: Pragmatic Analysis(PA)
• Pragmatics deals with how meaning is constructed and
interpreted in context. It explores:
• Speech Acts: Actions performed via utterances (e.g., requests,
promises, apologies).
• Implicature: Meaning implied but not explicitly stated. For
instance, saying "It's cold in here" might imply a request to close
a window.
• Deixis: Words whose meaning depends on context (e.g., "here,"
"there," "you").
• Presupposition: Assumptions the speaker believes to be true
(e.g., "Even John passed the exam" presupposes that passing
the exam was difficult).
• Politeness Theory: How speakers manage face (self-image) in
interactions, using strategies like indirect requests to maintain
social harmony.
 Discourse: Reference Resolution
• Discourse analysis studies how language is used in texts and
conversations to construct meaning across larger stretches
than single sentences.
• Discourse analysis may be defined as the process of
determining contextual information that is useful for
performing other tasks, such as anaphora resolution (AR), NER
etc.
• Reference may be defined as the linguistic expression to
denote an entity or individual.
• Reference Resolution: Interpretation of the sentences from
any discourse in terms of to know who or what entity is
being talked about.
 Discourse: Reference Resolution
• Discourse Reference Resolution : is a linguistic process where
one word in a sentence or discourse may refer to another word
or entity. The task of resolving such references is known as
Reference Resolution.
• Major problems in NLP is discourse processing − building
theories and models of how utterances stick together to form
coherent discourse.
• Actually, the language always consists of collocated, structured
and coherent groups of sentences rather than isolated and
unrelated sentences.
• These coherent groups of sentences are referred to as
discourse.
 Concept of Cohesion
• Cohesion and coherence are two essential concepts in
discourse analysis
• Cohesion: Cohesion refers to the grammatical and
lexical links within a text that tie sentences together,
creating a surface-level flow.

• It’s about the actual words and structures used to

connect ideas, ensuring that one part of the text
logically follows another.
 Concept of Cohesion
• Key concepts of cohesion include:
• Reference: Referring back or forward to something already
mentioned or yet to be mentioned in the discourse.
• Anaphora: Referring back (e.g., "John left. He forgot his keys.").
• Cataphora: Referring forward (e.g., "When he arrived, John
found the house empty.").

• Substitution: Replacing a word or phrase with another (e.g., “I

need a pen. Do you have one?”).

• Ellipsis: Omitting a word or phrase that is understood from the

context (e.g., "Do you want tea or coffee?" — "I'll have coffee
[omitted 'I'll have coffee']").
 Concept of Cohesion
• Key concepts of cohesion include:
• Conjunction: Using linking words to connect clauses or
sentences.
• Additive: and, moreover, besides
• Adversative: but, however, on the other hand
• Causal: because, therefore, so
• Temporal: then, next, finally
• Lexical Cohesion: Using related words or repetition to maintain
continuity.
• Repetition: Repeating the same word (e.g., “The dog barked. The
dog ran away.”).
• Synonymy: Using synonyms or near-synonyms (e.g., “The dog
barked. The canine ran away.”).
• Collocation: Words that often occur together (e.g., "bread and
butter").
 Concept of Coherence
• Coherence is a key property of any well-organized text.
• Coherence, is about the logical and meaningful flow of
ideas.
• It’s not about the explicit linguistic links but rather how
well the ideas fit together and make sense as a whole.
• Coherence reflects the deeper, underlying relationships
between parts of the discourse.
• can help document a set of sentences into a logically
consistent order, which is at the core of many text-
synthesis tasks such as text generation and multi-
document summarization.
 Concept of Coherence
• Factors contributing to coherence:
• Logical Sequence: The ideas must be arranged in a way that
they make logical sense.
• For example, a narrative must have events that follow a logical
timeline.
• Consistency of Topic: The text should remain focused on a
central theme or topic. Sudden shifts without explanation can
break coherence.
• Relevance: The content should be relevant to the overall
purpose of the discourse. Irrelevant information disrupts
coherence.
• Inferred Meaning: The reader or listener often needs to infer
relationships between ideas even when they are not explicitly
stated.
• For instance, in a story, readers infer that one event caused
another even if it's not directly stated.
• Cohesive Example:
• "Mary went to the store because she needed to buy
groceries. When she arrived, she realized that the store
was closed.“

• Coherent Example:
• "Mary went to the store to buy groceries. However, when
she arrived, she realized the store was closed. Feeling
frustrated, she decided to return home and order
groceries online."
• Cohesion vs. Coherence:
• A text can be cohesive without being coherent.
• For example, a series of sentences might have
appropriate linking words, but if the ideas are
jumbled or don't make sense together, the text lacks
coherence.
• Conversely, a text can be coherent but not heavily
cohesive.
• In casual speech, for instance, people may jump from
one idea to another without using formal cohesive
devices, yet their meaning can still be understood.
 • Coherence Vs Cohesion
Coherence Cohesion
Very general principle of Formal linguistic features Ex.
interpretation of language in Repetitions, reference
context
Fewer formal language features. Semantic relationship between
Ex. Vocabulary choice sentences and within sentences.
Relationship deals with text as a Determines by lexically and
whole grammatically over interessnetial
relationships.
Based on sematic relationships More recognizable
 Discourse Structure
• Discourse structure is a term used to describe the
way in which an entire text is organized –
• for example, how language is used in a poem, in a
newspaper article, or in a speech designed to read
aloud.

• Useful in information retrieval, text summarization

and information extraction kind of applications.
 Discourse Segmentation
• Techniques to separate documents into passages
include:
• 1. Rule based systems on clue words & phrases
• 2. Probabilistic techniques to separate fragments &
identify discourse segments
• Text Tilting algorithm uses cohesion to identify
segments, assuming that each segment exhibits lexical
cohesion within the segment, but not cohesive across
different segments:
• Lexical Cohesion Score:- average similarity of words
within a segment.
• Identify boundaries by the difference of cohesion
scores.
 Building Hierarchical Discourse Structure
• For example
• S1 − Ram went to the bank to deposit money.

• S2 − He then took a train to Shyam’s cloth shop.

• S3 − He wanted to buy some clothes.

• S4 − He do not have new clothes for party.

• S5 − He also wanted to talk to Shyam regarding his health.

Building Hierarchical Discourse Structure
 Coreference Resolution
• Coreference resolution is the task of finding all
expressions that refer to the same entity in a
text.
• For example: “I”, “my”, and “she” belong to
the same cluster and “Joe” and “he” belong to
the same cluster.
• Algorithms which resolve coreferences
commonly look for the nearest preceding
mention that is compatible with the referring
expression.
 Reference Resolution

• Reference: the process by which speakers use expressions

to denote an entity.
• Referring expression: expression used to perform
reference .
• Referent: the entity that is referred to.
• Coreference: referring expressions that are used to refer to
the same entity.
• Anaphora: reference to a previously introduced entity.
 Reference Resolution
• Discourse Model
It contains representations of the entities that have been
referred to in the discourse and the relationships in which
they participate.

• Two components required by a system to produce and

interpret referring expressions.
– A method for constructing a discourse model that
evolves dynamically.
– A method for mapping between referring expressions
and referents.
 Reference Phenomena
Five common types of referring expression
Type Example
Indefinite noun phrase I saw a Ford Escort today.
Definite noun phrase I saw a Ford Escort today. The Escort was white.
Pronoun I saw a Ford Escort today. It was white.
Demonstratives I like this better than that.
One-anaphora I saw 6 Ford Escort today. Now I want one.

Three types of referring expression that complicate the reference resolution

Type Example
Inferrables I almost bought a Ford Escort, but a door had a dent.
Discontinuous Sets John and Mary love their Escorts. They often drive them.
Generics I saw 6 Ford Escorts today. They are the coolest cars.
 Constraints (for English)
• Number Agreement:
– To distinguish between singular and plural references.
– Examples:
• 1. Singular: Ex. : The cat runs quickly.
• The cat (singular subject) agrees with runs (singular verb).
• 2. Plural: Ex.: The cats run quickly.
• The cats (plural subject) agrees with run (plural verb).

• This rule applies to pronouns as well:

• 3. Singular Pronoun Agreement: Ex.: She is going to the store.
• She (singular pronoun) agrees with is (singular verb).
• 4. Plural Pronoun Agreement: Ex. : They are going to the store.
• They (plural pronoun) agrees with are (plural verb).
 Constraints (for English)
• Gender Agreement:
• Gender Agreement refers to ensuring that pronouns and
sometimes verbs or adjectives agree with the gender of the
noun they refer to.
• In English, gender distinctions typically apply to male, female,
and non-personal (objects or animals, often referred to as it).
– To distinguish male, female, and non-personal genders.
• Example:
• John has a new car. It is attractive. [It = the new car]
• He is reading his book. He (male pronoun) agrees with his
(possessive pronoun).
• She is reading her book. She (female pronoun) agrees with her
(possessive pronoun).
• The book is on the table. It belongs to him.It (neutral pronoun)
refers to the book (non-personal).
• They are reading their book. They (singular, gender-neutral) agrees
with their (possessive).
 Constraints (for English)
• Person and Case Agreement:
– To distinguish between three forms of person;
– To distinguish between subject position, object position,
and genitive position.

– Ex. "I gave you my book, and he gave her his, but they
didn’t give us theirs.“

– First Person:I (subject), my (possessive), us (object)

– Second Person:you (object)
– Third Person:he (subject), her (object), his (possessive),
they (subject), theirs (possessive pronoun)
 Constraints (for English)
• Syntactic Constraints:
– Syntactic Constraints refer to the grammatical rules
that govern the relationship between a referring
expression (like a pronoun) and its antecedent (the
noun or noun phrase it refers to).
– These constraints ensure that a pronoun or other
referring expression is clearly connected to the correct
antecedent.
– Example
– John saw himself in the mirror.
• John is the antecedent of himself, and both are in the
same clause
– John bought himself a new car. [himself=John]
• John bought him a new car. [him≠John]
 Constraints (for English)
• Selectional Restrictions: refer to the semantic
constraints that a verb places on its arguments (such
as its subject, object, etc.).
• restrictions are based on the meaning of the verb,
which limits the types of nouns or noun phrases that
can logically serve as its arguments.

– A verb places restrictions on its arguments.

• John parked his Acura in the garage. He had
driven it around for hours. [it=Acura,
it≠garage];
• I picked up the book and sat in a chair. It broke.
 Constraints (for English)
• Selectional Restrictions:
• Examples of Selectional Restrictions:
• 1. Animate vs. Inanimate Subjects: Some verbs require their
subject to be an animate (living) entity.
• Example (Correct):
• The dog barks.
• Barks requires an animate subject, and the dog is
animate.
• Example (Incorrect):
• The rock barks.
• Barks cannot take the rock as a subject because a rock
is inanimate, and barking is an action only animate
beings can perform.
 Constraints (for English)
• Selectional Restrictions:
• 2. Human vs. Non-human Subjects: Certain verbs are
semantically restricted to human subjects.
• Example (Correct):
• John thinks about the problem.
• Thinks requires a subject capable of cognition (typically
human or sentient beings), and John is a human.
• Example (Incorrect):
• The chair thinks about the problem.
• Thinks cannot logically have the chair as a subject
because chairs do not have the capacity for cognition.
 Constraints (for English)
• Selectional Restrictions:
• 3. Concrete vs. Abstract Objects
• Some verbs require their object to be something concrete
(physically tangible) or abstract (intangible), depending on the
verb’s meaning.
• Example (Correct):
• She kicked the ball.
• Kicked requires a concrete object (something that can
be physically kicked), and the ball is a physical object.
• Example (Incorrect):
• She kicked an idea.
• Kicked cannot logically have an idea as its object
because ideas are abstract and cannot be physically
kicked.
 Constraints (for English)
• Selectional Restrictions:
• 4. Appropriate Objects for Verbs of Consumption
• Verbs that describe acts of consumption (e.g., eat, drink)
require an object that can be consumed.
• Example (Correct):
• He drank the water.
• Drank requires an object that can be consumed as a
liquid, and the water fits.
• Example (Incorrect):
• He drank the chair.
• Drank cannot logically have the chair as an object
because chairs are not consumable.
 Constraints (for English)
• Selectional Restrictions:
• 5. Physical vs. Non-physical Objects for Verbs of Sensation
• Verbs related to sensory perception (e.g., see, hear, feel) often
have restrictions on the types of objects they can take.
• Example (Correct):
• She saw the car.
• Saw requires an object that can be visually perceived,
and the car fits.
• Example (Incorrect):
• She saw the sound.
• Saw cannot take the sound as an object because sounds
cannot be visually perceived.
Anaphora resolution
• Anaphora resolution is the process of finding an
anaphor's antecedent.
• Example: The car is falling apart, but it still works.
• Here "it" is the anaphor and "The car" is the
antecedent. This is an example of pronominal
anaphora, or anaphora where the anaphor is a
pronoun.
 Hobbs’ algorithm
• Hobbs’ algorithm: discourse analysis, is primarily associated
with the task of resolving referential ambiguities, such as
determining what a pronoun or noun phrase refers to in a
given context.
• provides a way to handle coreference resolution, which is
essential for understanding the relationships between entities
in text.
• Centering Theory: Hobbs’ algorithm is influenced by
centering theory, which focuses on maintaining a coherence in
discourse by keeping track of the "center" of attention in
conversation.
• Simple syntax-based algorithm for 3rd person anaphoric
pronouns
• Hobb’s Algorithm relies on
→ Syntactic parser
→ Morphological number and Gender Checker
 Hobbs’ algorithm
• Simple syntax-based algorithm for 3rd person anaphoric
pronouns

• Hobb’s Algorithm relies on

→ Syntactic parser
→ Morphological number and Gender Checker

• Searches syntax trees of current and preceding sentences in

breadth-first, left to right manner. Stops when it finds
matching NP.
 Hobbs’ algorithm
• Step 1: Parse the Sentence
• - Input: Syntactic parse tree of the sentence to resolve.
• - Example: 'John met Bill. He is happy.’
• Step 2: Begin at the Pronoun:
• - Find the pronoun or noun phrase needing resolution.
• - Example: 'He' in 'He is happy.’
• Step 3: Move Upwards in the Tree
• - Trace backward to the next higher node in the tree.
• Step 4: Search Left Branches
• - Explore left branches for potential antecedents.
• - Left branches contain earlier entities.
 Hobbs’ algorithm
• Step 5: Traverse to the Previous Sentence
• - If no antecedent is found, move to the previous sentence.
• - Repeat the search process in the previous sentence's tree.
• Step 6: Apply Constraints
• - Eliminate unlikely candidates based on rules.
• - Consider gender and number agreement.
• Step 7: Select the Most Likely Antecedent
• - Prefer the most local candidate (closest in proximity).
• - If multiple candidates exist, choose the most relevant one.
• Step 8: Continue the Search if Needed
• - If no antecedent is found, search further sentences.
• - Consider less preferred interpretations if needed.
 Practice Example: Hobb’s Alg.
• Mary met Susan. She told her about the
project.
 Practice Example: Hobb’s Alg.
• “John Saw Bill when he was walking his dog.”
Centering Theory
Introduction:

 Anaphora resolution is the task of determining the

antecedent (the noun or noun phrase that a pronoun
refers to) in a discourse.

 Centering Theory, which is a discourse coherence

framework introduced by Grosz, Joshi, and Weinstein
in the 1990s.
Centering Theory
Basic ideas:

 Focus of Attention: Centering theory assumes that at

any point in a discourse, there are a limited number
of entities that the speaker is focused on.

 Coherence of Discourse: The transitions between

sentences are governed by the entities that are
mentioned or implied, which provides coherence to
the discourse.
Centering Algorithm for Anaphora Resolution
algorithm uses below principles to resolve anaphoric
references:

 Identify discourse entities: In each sentence,

determine all potential referring expressions (e.g.,
pronouns, definite descriptions).

 Determine Cb and Cf: For each utterance, identify the

backward-looking center (Cb) and the forward-
looking centers (Cf).
Centering Algorithm for Anaphora Resolution
algorithm uses below principles to resolve anaphoric
references:

 Rank the Cf: Give priority to entities in subject

position, grammatical prominence, and salience in
discourse.

 Resolve anaphora: If a pronoun is encountered,

resolve it to the most prominent entity that fits the
grammatical and semantic constraints from the Cf
list.
Centering Algorithm: Types of Transitions
algorithm considers the transitions between two
utterances:

 Continue: If the Cb of the current utterance is the

same as that of the previous utterance, and the
current Cp is also the same as the Cb.
 Retain: If the Cb of the current utterance is the same
as the previous utterance but the Cp is different.
 Smooth Shift: If the Cb changes, but the Cp is
maintained.
 Rough Shift: If both the Cb and Cp change.
Centering Algorithm: example 1
Consider the following discourse:

1. John went to the store.

2. He bought some bread.
• In sentence 1, "John" is the only entity, and hence
becomes both the Cb and Cp.
• In sentence 2, "He" refers back to "John", so
"John" remains the Cb, and "bread" is added to
the Cf list.
 By following the transitions and maintaining the Cb
and Cp, the algorithm can resolve the pronoun
"He" to "John".
 Centering Algorithm: example 2

Consider the following discourse:Simple Pronoun Resolution

1. Mary saw a dog.
2. She gave it some food.
• S1: "Mary" and "a dog" are introduced as forward-
looking centers (Cf). "Mary" is in subject position and is
the most salient entity, making her the preferred center
(Cp).
• S2: "She" refers to "Mary," making "Mary" the
backward-looking center (Cb). The pronoun "it" refers to
"a dog," another entity from the previous sentence's Cf
list.
• Transition: This is a Continue transition, as the
backward-looking center (Cb) stays the same ("Mary")
between the sentences, ensuring discourse coherence.
 Centering Algorithm: example 3

Consider the following discourse: Change in Subject

1. Alice picked up the phone.
2. Then, Bob called her.
❑ Analysis: Sentence 1: "Alice" is the subject and is placed
in the forward-looking centers (Cf), with "the phone" as
another potential entity in the Cf list. "Alice" becomes
the preferred center (Cp).
❑ Sentence 2: "Bob" is the new subject, introduced as the
new Cp. "Her" refers to "Alice," who is the backward-
looking center (Cb) from the previous sentence.
❑ Transition: This is a Retain transition, where the
backward-looking center (Cb) stays the same ("Alice"),
but the preferred center (Cp) shifts to "Bob."
 Centering Algorithm: example 4

Ex4: Rough Shift (Pronoun Referring to a New Entity)

1. The president met with the advisor..
2. He discussed the plan in detail.
❑ Analysis: Sentence 1: "The president" and "the advisor"
are introduced as the forward-looking centers (Cf). "The
president" is the preferred center (Cp) as the subject.
❑ Sentence 2: "He" could refer to either "the president" or
"the advisor." In this case, let's assume that "he" refers
to "the advisor."
❑ Transition: This is a Rough Shift, as both the backward-
looking center (Cb) and preferred center (Cp) change.
The shift happens when "he" now refers to "the advisor,"
moving the discourse focus away from "the president."
 Centering Algorithm: Practice 1

Ex5: Pronoun Refers to a Salient Entity

1. Sarah invited her friends over for dinner.
2. They enjoyed the food.
 Centering Algorithm: Practice 1

Ex5: Pronoun Refers to a Salient Entity

1. Sarah invited her friends over for dinner.
2. They enjoyed the food.
❑ Analysis: Sentence 1: "Sarah" and "her friends" are
introduced as forward-looking centers (Cf). Since "Sarah"
is the subject, she is the preferred center (Cp).
❑ Sentence 2: "They" refers to "her friends," as it is a plural
pronoun. "They" becomes the new backward-looking
center (Cb), while the food ("the food") is introduced as
another forward-looking center."
❑ Transition: This is a Retain transition because the Cb
shifts from "Sarah" to "her friends," while there is a new
focus on a different subject in the next utterance."
Centering Algorithm: Practice 2

Ex6: Two Potential Antecedents

1. Tom gave Jerry a book.
2. He was very grateful.
 Centering Algorithm: Practice 2

Ex6: Two Potential Antecedents

1. Tom gave Jerry a book.
2. He was very grateful.
❑ Analysis: Sentence 1: Both "Tom" and "Jerry" are
introduced as forward-looking centers (Cf), with "Tom" as
the preferred center (Cp) since he is the subject.
❑ Sentence 2: "He" can refer to either "Tom" or "Jerry," but
pragmatics suggests that "He" refers to "Jerry" (the
recipient) since the phrase "very grateful" fits Jerry’s role
better.
❑ Transition: Smooth Shift because the focus moves from
"Tom" (Cp of Sentence 1) to "Jerry" (Cb and Cp of
Sentence 2).
 Centering Algorithm: Practice 3

Ex7: Singular vs. Plural Pronouns

1. The children went to the park.

2. They played on the swings.
 Centering Algorithm: Practice 3

Ex7: Singular vs. Plural Pronouns

1. The children went to the park.
2. They played on the swings.
❑ Analysis: Sentence 1: "The children" is introduced as the
forward-looking center (Cf) and is the subject, making it
the preferred center (Cp).
❑ Sentence 2: "He" can refer to either "Tom" or "Jerry," but
pragmatics suggests that "He" refers to "Jerry" (the
recipient) since the phrase "very grateful" fits Jerry’s role
"They" refers back to "the children," so "the children" is
the backward-looking center (Cb), and "the swings"
becomes a new entity in the Cf list.
❑ Transition: This is a Continue transition because the Cb
("the children") remains the same across the two
sentences, and the focus of the discourse doesn’t shift.
Definitions
Utterance – A sentence in the context of a discourse.
Center – An entity referred to in the discourse (our
discourse referents).
Forward looking centers – An utterance Un is assigned
a set of centers Cf(Un) that are referred to in Un
(basically, the drefs introduced / acccessed in a
sentence).
Backward looking center – An utterance Un is assigned
a single center Cb(Un), which is equal to one of the
centers in Cf(Un-1)Cf(Un).
If there is no such center, Cb(Un) is NIL.
Ranking of forward looking
centers
 Cf(Un) is an ordered set.

 Its order reflects the prominence of the centers in

the utterance.

 The ordering (ranking) is done primarily according

to the syntactic position of the word in the
utterance (subject > object(s) > other).

 The prominent center of an utterance, Cp(Un), is the

highest ranking center in Cf(Un).
Ranking of forward looking
centers
 Think of the backward looking
center Cb(Un) as the current topic.

 Think of the preferred center Cp(Un)

as the potential new topic.
Another example
 U1. John drives a Ferrari.

 U2. He drives too fast.

 U3. Mike races him often.

 U4. He sometimes beats him.

Let’s see what the centers are…
 U1. John drives a Ferrari.
Cb(U1) = NIL (or: John). Cf(U1) = (John, Ferrari)

 U2. He drives too fast.

Cb(U2) = John. Cf(U2) = (John)

 U3. Mike races him often.

Cb(U3) = John. Cf(U3) = (Mike, John)

 U4. He sometimes beats him.

Cb(U4) = Mike. Cf(U4) = (Mike, John)
Let’s see what the transitions
are…
 U1. John drives a Ferrari.
Cb(U1) = John. Cf(U1) = (John, Ferrari)

 U2. He drives too fast. (continuation)

Cb(U2) = John. Cf(U2) = (John)

 U3. Mike races him often. (retaining)

Cb(U3) = John. Cf(U3) = (Mike, John)

 U4. He sometimes beats him. (shifting-1)

Cb(U4) = Mike. Cf(U4) = (Mike, John)
 Centering rules in discourse
1. If some element of Cf(Un-1) is realized
as a pronoun in Un, then so is Cb(Un).

2. Continuation is preferred over

retaining, which is preferred over
shifting-1, which is preferred over
shifting:
Cont >> Retain >> Shift-1 >> Shift
Violation of rule 1
 Assuming He in utterance U1 refers to
John…

 U1. He has been acting quite odd.

 U2. He called up Mike Yesterday.
 U3. John wanted to meet him
urgently.
In more detail …
 U1. He has been acting quite odd.
Cb(U1) = John. Cf(U1) = (John)

 U2. He called up Mike Yesterday.

Cb(U2) = John. Cf(U2) = (John, Mike)

 U3. John wanted to meet him urgently.

Cb(U3) = John. Cf(U3) = (John, Mike)
Compare the two discourses we started with:

 U1. John went to his favorite music store to buy a

piano.
 U2. He had frequented the store for many years.
 U3. He was excited that he could finally buy a piano.
 U4. He arrived just as the store was closing for the
day.

 U1. John went to his favorite music store to buy a

piano.
 U2. It was a store John had frequented for many years.
 U3. He was excited that he could finally buy a piano.
 U4. It was closing just as John arrived.
Transitions for the 1st discourse
 U1. John went to his favorite music store to buy a piano.
Cb(U1) = John. Cf(U1) = (John, store, piano).

 U2. He had frequented the store for many years.

Cb(U2) = John. Cf(U2) = (John, store). CONT

 U3. He was excited that he could finally buy a piano.

Cb(U3) = John. Cf(U3) = (John, piano). CONT

 U4. He arrived just as the store was closing for the day.
Cb(U4) = John. Cf(U4) = (John, store). CONT
Transitions for the 2nd discourse
 U1. John went to his favorite music store to buy a
piano. Cb(U1) = John. Cf(U1) = (John, store, piano).

 U2. It was a store John had frequented for many

years.
Cb(U2) = John. Cf(U2) = (store, John). RETAIN

 U3. He was excited that he could finally buy a piano.

Cb(U3) = John. Cf(U3) = (John, piano). CONT

 U4. It was closing just as John arrived.

Cb(U4) = John. Cf(U4) = (store, John). RETAIN
Practice Examples- Hobb’s Alg

 Steps of Hobbs' Algorithm

1. Parse the sentence into a syntactic tree.
2. Begin at the pronoun node.
3. Move up the tree until you find the first NP or S
node.
4. Go down the left branch and find a potential
antecedent.
5. If found, mark it. If not, move up and repeat.
6. Traverse other clauses and sentences if
needed.
Practice Examples- Hobb’s Alg

 Example 1:
 Sentence: John went to the park with Bill. He
played football.
1. Identify the pronoun in question.
2. Follow Hobbs' algorithm step-by-step to
resolve it.
Practice Examples- Hobb’s Alg

 Example 2:
 Sentence: Susan told Mary that she won the
award.

1. Identify the pronoun in question.

2. Follow Hobbs' algorithm step-by-step to
resolve it.
Practice Examples- Hobb’s Alg

 Example 3:
 Sentence: The manager called the employee
because he wanted to discuss the project.

1. Identify the pronoun in question.

2. Follow Hobbs' algorithm step-by-step to
resolve it.
Practice Examples- Centering Alg.

 Steps of the Centering Algorithm:

1. Identify discourse segments: Break down
the discourse into sentences or utterances.
2. Assign entities to the centers:
1.Backward-looking center (Cb): Refers to the entity
carried over from the previous sentence, representing
the topic or focus.
2.Forward-looking centers (Cf): List of entities that
could be referenced in the next utterance, ranked by
salience.
Practice Examples- Centering Alg.

 Steps of the Centering Algorithm:

3. Determine transitions between
utterances:
1.Continue: The most prominent entity
remains the same in both sentences.
2.Retain: The backward-looking center stays
the same, but the sentence shifts the focus
to a new entity.
3.Shift: The backward-looking center changes
completely, indicating a topic shift.
Practice Examples- Centering Alg.

 Steps of the Centering Algorithm:

 Transition Types:
• Continue: Cb remains the same, and the
subject continues as the topic.
• Smooth-shift: The backward-looking center
changes, but the most prominent forward-
looking center is retained.
• Rough-shift: A new entity takes over the
discourse without any continuity.
Practice Examples- Centering Alg.

 Example 1:
 Sentences:
S1: John went to the store.
S2: He bought some milk.
Practice Examples- Centering Alg.

•Discourse Segment: Break the sentences into two utterances:

•Utterance 1: "John went to the store."
•Utterance 2: "He bought some milk."
•Centering (Cb, Cf) assignment:
•S1:
•Cb (Backward-looking center): None (since this is the first sentence).
•Cf (Forward-looking centers): {John, store}.
•S2:
•Cb: John (assuming “He” refers to John).
•Cf: {John, milk}.
•Transition:Cb remains the same from S1 to S2 (John).
•Transition type: Continue (because John is the focus in both
sentences).
Practice Examples- Centering Alg.

 Example 2:
 Sentences:
Sentences:S1: The cat chased the mouse.
 S2: It ran up the tree.
Practice Examples- Centering Alg.

 Discourse Segment:
 Two utterances:
 Utterance 1: "The cat chased the mouse.“
 Utterance 2: "It ran up the tree.
 "Centering (Cb, Cf) assignment:
 S1:Cb: None.
 Cf: {cat, mouse}.
 S2:Cb: Could be the cat or the mouse, but let’s
assume "It" refers to the mouse (since the
second sentence describes an escape).
 Cf: {mouse, tree}.
Practice Examples- Centering Alg.

 "Centering (Cb, Cf) assignment:

 S1:Cb: None.
 Cf: {cat, mouse}.
 S2:Cb: Could be the cat or the mouse, but let’s
assume "It" refers to the mouse (since the second
sentence describes an escape).
 Cf: {mouse, tree}.
 Transition:
 Cb shifts from no Cb in S1 to "mouse" in S2.
 Transition type:
 Smooth-shift (the shift to the mouse is smooth
because it's ranked highly in the previous sentence’s
forward-looking centers).
 apply the Centering Algorithm to the
following sentences:
 Sentences:
S1: The boy found a puppy.
S2: He took it home.
• Identify the Cb and Cf for each sentence.
• Determine the type of transition between
S1 and S2.
Thank You