MODULE 5

CHAPTER
Pragmatic and
5 Discourse Processing
Syllabus
5.1 Discourse Reference Resolution, Reference Phenomena, Syntactic & Semantic constraint
on coherence; Anaphora Resolution using Hobbs and Cantering Algorithm.
5.2 Self-Leamingtopics: Discourse segmentation, Conference resolution.

5.1 Pragmatic Analysis. ****...5-2

5.2 Discourse Analysis. 5-2

5.3 Reference Resolution. 5-2

5.4 Reference Phenomena...

5.4.1 Type of Referring Expression.. 5-5

5.4.2 Types of Referents which Complicate the Reference Resolution... 5-8

5.5 Syntactic and Semantic Constraints on Coreference.. ******

5-10

5.6 Anaphora Resolution. ****** ****

5-14
5.6.1 Hobbs Algorithm.. .5-14

5.6.2 Centering Algorithm... .5-17

Chapter Ends.
Peamsene eseusees
Nature Language rocessing (MU - Sem 7- omp)
(Pragmatic& Discourse Proc.)...Page no. (5-22
5.1 PRAGMATIC ANALYSIS

A step in the intormation extraction from text is pragmatic analysis. In particular, its
the section on analysing a group of text structures to determine their true meaning or
the intended meaning.
The study of pragmatics, a branch of linguistics and semiotics, focuses on how context
affects meaning.
In contrast to semantics, which examines meaning that is "coded" or conventional in a
particular language, pragmatics investigates how the transmission of meaning
depends not only on the speaker's and listener's structural and linguistic knowledge
grammar, lexicon, etc.), but also on the context of the utterance, any prior knowledge
about those involved, the speaker's implied intent, and other elements.
For example, the semantic analysis meaning of the sentence "The Soldier fought like
a lion" yields the meaning that the soldier fought using the paws or bit using teeth!
Which not the intended meaning. The intended meaning here is to highlight the

ferociousness of the soldier.

Sarcasm identification or detection is one of the important application of pragmatic

analysis.

5.2 DISCOURSE ANALYsIS

events that take place at
Til now our mostly been drawn to linguistic
attention has
often consists of collocated, connected
the word or sentence level. Of course, language
unrelated utterances. Such a collection of
groupings of sentences rather than single,
Sentences is referred to as a discourse.
in linguistics refers to. Discourse analysis
is
in what the word discourse
anguage use
entals understanding social
practise of analysing texts or languages that
ne Dealing n-grams, tenses,
with morphemes,
eractions and text [Link] elements can be part of discourse analysis.
and
guistic features, page layouts,
One definition of discourse is a series of sentences.

5.3 REFERENCE RESOLUTION

in language. Think about the
occurrences
iscourse level is rich with

Conversation in the example, He looked at it for

dealership to check out an Acura Integra.
e n t to Bill's car

about an hour (5.1)

Tech-Neo Publications...A SACHIN SHAH Venture
(MU-New Syllabus w.e
w.e.f academic year 22-23) (M7-83)
Natural Language Processing (MU Sem 7-Comp) (Pragmatic &Discourse Proc.)..Page no. (5-31
What do pronouns like "he" and "it" mean? The reader might not have issue
deducino
that he refers to John and not Bill, and that it refers to the Integra and not Bill's
auta
business, but for a computer?
The mechanism through which speakers utilise terms like John' and 'he' in passage
5.1) to signify a person called John' is the subject of this section's consideration of
the reference problem. Reference Resolution is a process by which when speakers use
expressions like John' and he' in passage (5.1) to denote a person named John' this
relation is identified.
We must first clarify a few terms before we can continue further.

1. Referring Expression and Referent

A natural language expression used to perform reference is called a referring

expression, and the entity that is referred to is called the referent.

Example : The name John' and he' in passage (5.1) are referring expressions,
and John' the person is their referent.

As a convenient shorthand, we will sometimes speak of a referring expression

referring to a referent, e.g., we might say that he' refers to John' the person.

2. Corefer

If the same entity has been referred by two referring expressions then it is called
as Corefer.
Example: The name John' and he' are corefer in passage (5.1) as both are

referring to the person 'John'.

3. Antecedent

There is also a name for a referring expression that grants permission for the use
of another, similar to how mentioning the name John' permits John' the person
to be afterwards referred to by the pronoun he'.

We call the name John' the antecedent of he.

4. Anaphora and Anaphoric

Reference to an entity that has been already introduced into the discourseis
called anaphora, and the referring expression used is said to be
anaphoric.
Example: In passage (5.1), the pronouns 'he' and it are anaphoric. And, the name
John' is anaphora.

(MU-New Syllabus [Link] academic year 22-23) (M7-83) Tech-Neo Publications...A SACHIN SHAH Venu
!!! i l
l
D

il
Natural Language Processing (MU
Sem 7- Comp) (Pragmatic & Discourse Proc.)...Page no. (5-5)
5.4REFERENCE PHENOMENA
wwww.w.

offered by natural languages is quite extensi

The range of referential phenomena sive.
Five types of referring expression have been covered here, indefinite noun phrasas
es,
and names.
definite noun phrases, pronouns, demonstratives,

Additionally it is important to note the three types of referents which complicate the
reference resolution problem, inferrables, discontinuous sets and generics.

a5.4.1 Type of Referring Expression

There five types of referring expressions, indefinite noun phrases, definite noun
demonstratives, and names. Indefinite noun
phrases, pronouns,
phrases
1. Indefinite Noun Phrases Definite noun
Indefinite references bring unfamiliar entities to
phrases
the conversation environment. Pronouns
The determiner a' (or an') is used to indicate Demonstratives
indefinite references most frequently, although it
may also indicate by quantifiers like 'some' or even Names
the determiner this'. Fig 5.4.1:Types of Referring
Expressions
Example
I saw 'an' Acura Integra today. (5.2)

"Some' Acura Integras were being unloaded at the local dealership today. (6.3)

I saw this' awesome Acura Integra today. (5.4)

I am going to the dealership to buy 'an' Acura Integra today. (5.5)

These noun phrases elicit a representation for se
a new entity that fits the discou
model's definition.

There may be a
specific/non-specific ambiguity since the indefinite determinere r '
doesn't say whether the speaker has
can
identify the
object. Example (5.2) only
the specific reading since the speaker is that

specifically thinking of the Integra

she saw.

Drawback: On the other hand,

both interpretations are
plausible in phrase (5.5).
In other words, the speaker may already know which Integra she wants o1
may

simply be preparing to choose one she likes

(nonspecific).
(MU-New Syllabus w.e.f academic year 22-23) (M7-83)
Tech-Neo Publications...A SACHIN V e n t u r e

SH
Natural LanguageProcessing
(MU Sem 7-Comp) Pragmatic &Discourse Proc.)...Pageno. (5-5)

Solution to the problem: In some instances, a following referencing statement can

be used to distinguish between the readings; if the expression is definite, the reading
15
is particular (I hope they still have that option), and if it is indefinite, the reading
generic (I hope they have a car I like).

There are several exceptions to this rule, such as when definite expressions are
in particular modal circumstances (I'll parkit in my garage), this is
acceptable
compatible with the nonspecific reading.

2. Definite Noun Phrases

having a "definite
An entity that is identifiable to the hearer is referred to as

reference" when,
is therefore
) it has already been mentioned in the discourse context (and

represented in the discourse model),

Gi) is a part of the hearer's worldview,

or

uniqueness.
ii) the description itself implies the object's
Example
was white and needed
to be washed. (5.6)
I saw an Acura Integra today. The Integra'
car race in the US. (5.7)
The Indianapolis 500' is the most popular
500 was an Integra. (6.8)
The fastest car in the Indianapolis from the
referent may be determined
(6.6) showcases an example where the
Conversation context.
the hearer's set of
referent is identifiable from
.1) showcases an example where the
beliefs.
the referent is inherently
unique.
showcases an example where
model or the hearer's collection of
to note that
the discourse
e It is important a definite
noun in a sentence. In the
to
Odviews must be accessible in
order to refer
of the referent.
model representation
a discourse
d instance, it also evokes
3. Pronouns
reterence, as seen in example (5.9).
*Onominalization is another type of
P definite
and needed to be washed. (5.9)
*9aW an Acura Integra today.
It was white
restrictions
plete definite noun
than complet noun phrases,
phrase
Pronominal reference has more

activation or
salience for the referent in the
for the the
necessitating
essitating a high level of
discourse model._
MJ-New Sylabus w.e.f academic year 22-23) (M7-83)
Tech-Neo Publicatione.A SACHIN SHAH Venture
Natural Language Processing (MU- Sem 7-Comp) (Pragmatic & Discourse Proc.)..Page no. (5-7
While definite noun phrases can frequently refer further back, pronouns
ns tyni
typically
(but not always) refer to entities that were introduced no more than one or t
sentences before to the current discourse. This is illustrated by the difieron
ence
between sentences (5.10d) and (5.10d').

(5.10)
(a) John went to Bob's party, and parked next to a beautiful Acura Integra.

than hour.
(b) He went inside and talked to Bob for more an

(c) Bob told him that he recently got engaged.

(d) He also said that he bought it' yesterday.
d') He also said that he bought 'the Acura' yesterday.
The Integra no longer has the level of salience necessary to permit pronominal
reference by the time we get to the last sentence.

Cataphora: In cataphora, pronouns are mentioned before their referents are, as

in the following example (5.11). Here, it can be seen that the pronouns 'he' and t
both appear before the introduction of their respective referents.

Before he bought it, John checked over the Integra very carefully. (5.11)

Bound: Pronouns can be considered bound when they appear in quantified

contexts, as in the following example (5.12). Her' operates as a variable bound to
the quantified expression every woman when read in the appropriate way, rather
than referring to any particular woman in the context.

Every woman bought her Acura at the local dealership. (5.12)

4. Demonstratives

Simple definite pronouns like it function

differently than demonstraive
pronouns like this' and that. They may show up both by themselves and a
determiners, such as 'this Acura' and that Acura'.
The decision between two
demonstratives-this signalling proximity and
signalling distance-is typically connected to some idea of ical

proximity. Depending on the situational setting of the conversation

geograpnie
spatial distance might be calculated as in (5.13). participan
John shows Bob an Acura Integra and a Mazda
Miatal
.Bob (pointing): I like 'this' better than 'that.
(6.13)

(MU-New Syllabus w.e.f academic year 22-23)

(M7-83)
ITech-Neo Publications..A SACHIN SHAH Venture
Natural Language Processing(MU - Sem 7-Comp)
(Pragmatic &Discourse Proc.)...Page no.(5-8)
As an alternative, the discourse model's conceptual relations might be used to
symbolically understand distance. Consider the example (5.14).
Here, this one' relates to the Acura that was purchased yesterday (closer
temporal distance), and that one' refers to the Acura that was purchased five

years ago (greater temporal distance).

I bought an Integra yesterday. It's similar to the one I bought five years ago.
That one was really nice, but I like this one even better. (6.14)

5. Names
of
Names prevalent type of referring expression and include names persons,
are a

be used to refer to both new

organisations, and places. In the discourse, names may
and historical entities.

(5.15)
done him justice.
(a) Miss Woodhouse' certainly had not
from Amazon;
International Business Machines' sought patent compensation
(6)
BM had previously sued other companies

Complicate
5.4.2 Types of Referents which
the Reference Resolution

expression types,
Ater describing several referring
referent kinds Inferables
we will now focus on a few intriguing
more
reference resolution
problem
aE make the

challenging
1. Inferrables Discontinous sets
refers
In certain instances, a referring expression
rather than one
to an entity that has been implied Generics
in the text.
that has been xpressly
summoned

Such referents are called as Inferrables. which

Fig 54.2:Types of Referents
Complicate the Reference Resolution

Example but 'a door had a dent and the engine'

I almost Acura Integra today,
St bought an

Seemed noisy. (5.16)

SACHIN SHAH Venture
MU-New Svlabus w.e. Tech-Neo Publications..A
(M7-83)
ademic year 22-23)
Natural Language Processing (MU - Sem 7- Comp) (Pragmatic & Discourse Proc.)..Page no. (5-9)
Now, consider the expressions 'a door and "the engine. In a typical situation, the
indefinite noun phrase 'a door' would introduce a new door into the discourse contex
but in this instance, the hearer is to infer something additional: that it is not just y

door, but rather one of the doors of the Integra.

The definite noun phrase the engine is also typically used to denote the engine' that
has already been invoked or is otherwise easily recognised. Although 'the engine' of
the aforementioned Integra has not been stated clearly in this sentence, the hearer

infers that it is the referent.

The outcomes of processes that are described by utterances in : discourse can also be

specified by inferrables. Take into account the recipe's possible follow-ups (a-c) to

sentence (5.17).

(5.17)
Mix the flour, butter, and water.

(a) Kneed the dough' until smooth and shiny.

(b) Spread the paste' over the blueberries.

(c)Stir the batter until all lumps are gone.

The words 'the dough' (a solid), batter (a liquid), and 'paste' (something in

between) can all be used to refer to the outcome of the acts in the first line, but

they all indicate distinct characteristics of this outcome.

2. Discontinuous Sets

is
Generally, 'they' and them' are examples of a plural referring expression that
sometimes used to refer to groups of items that are invoked collectively. Other
and
examples include another plural referring expression (their Acuras)
conjoined noun phrases (John and Mary), as shown in the following example,
John and Mary love their Acuras. They drive them all the time. (6.18)
However, plural references may also apply to groups of things that the texts
discontinuous phrases have referred to, as in the following example,

John has an Acura, and Mary has a Mazda. They drive them all the time. (519)
to
.Here, they' refer to John and Mary, and the Acura and the Mazda are referred
as them' in this sentence. Also, take note that the second line in this instance
will often be read pairwise or correspondingly, meaning that John drives tne

Acura and Mary drives the Mazda rather than both of them driving botn

automobiles.

(MU-New Syllabus w.e.f academic year 22-23) (M7-83) Tech-Neo Publications...A SACHIN SHAH Venture
 Language Procecessing (MU
Natural
Sem 7- Comp) (Pragmatic &Discourse Proc.)...Page no.(5-10)
3. Generics

The existence of generic reference

adds another layer of complexity to the
reference problem. Considering one (15.20).
I saw no less than 6 Acura
Integras today. "They' are the coolest cars. (5.20)
The most obvious reading here relates to the class of Integras as a whole rather
than the specific six Integras stated in the first phrase.

5.5 SYNTACTIC AND SEMANTIC CONSTRAINTS ON cOREFERENCE

*******

Any effective reference resolution method must include

the step of filtering the collection of potential referents Number
agreemet
based on a few reasonably rigid requirements. Here, we
Person and case
go through a few of these restrictions. agreemet
Gender
1. Number Agreement
agreement
It is necessary for referring statements and their
Syntactic
number; in English, this constraints
referents to have the same

references to the Selectional

entails differentiating between restrictions
singular and plural.
Fig. 5.5.1:Syntactic and Semantic
Constraints on Coreference

are categorised according to their number.

In Table No. 5.5.1, pronouns
Pronouns according to Number Agreement
Table 5.5.1:

Plural Unspecified
Singular
Them You
She, Her, He, Him, His,
It | We, Us, They,

Example on number agreement.

constraints
he following examples illustrate
(5.21)
dohn has a new Acura. Tt is red.
red. (5.22)
lohn has three: new Acuras. They' a r e
red. (5.23)
John has a new Acura. "They'
are

(5.24)
John Tt is red.
has three new Acuras.
(5.24) aare
correct whereas, (5.23) and
(5.22) are
Here, the examples (5.21)
and
should be
associated with plural and the terr
term
they' term
rect statements as the These to
s t a t e m e n t s violate the constraints.

0uld be associated with

singular.

MU-New Svllabus w.e.f Tech-Neo Publications...A SACHIN SHAH Venture

Ous W.e.f academic year 22-23) (M7-83)
acade
Natural Language Processing(MU-Sem 7 Comp) (Pragmatic&Discourse Proc.)...Page no.(5-11)
2. Person and Case Agreement

Three different person tenses are recognised in English: first, second, and third.
Also, due to case agreement, various pronoun forms may be necessary when used
in the subject position (nominative case, e.g, he, she, or they), object position
(accusative case, e g.. him, her, or they), and genitive position (genitive case, e.g.,
his Acura, her Acura, their Acura).
Table No. 5.5.2 depicts a division of pronoun categories according to person and
according to case agreement.
Table 5.5.2: Division of Pronoun Categories according to Person and case agreement

| First Second | Third

Nominative I, We You | He, She, They

Accusative Me, Us You Him, Her, Them

Genitive My, Our Your His, Her, Their

Example
You and I have Acuras. We' love them. (5.25)
John and Mary have Acuras. They' love them. (5.26)
John and Mary have Acuras. 'We' love them. (Where, We = John and Mary) 6.27)

You and I have Acuras. "They' love them. (Where, They = You and D (5.28)

Here, the examples (5.25) and (5.26) follow the person and case agreement constraints
whereas, (5.27) and (5.28) do not follow these constraints.

3. Gender Agreement

The gender implied by the referring statement must likewise be accepted by the
referents. English third person pronouns differentiate between the genders of male,
female, and nonpersonal, although unlike many other languages, the first two only apply
to living objects. Table No. 5.5.3 illustrate the pronouns under these gender categories.
Table 5.5.3: Pronouns under Gender Categories

Masculine Feminine Nonpersonal

He, Him, His | She, Her It

(MU-New Syllabus w.e.f academic year 22-23) (M7-83) Tech-Neo Publications...A SACHIN SHAH Venture
 Processing (MU Sen 7-Comp) (Pragmatic&Discourse Proc.)..Page no. (5-12)
-

Language
Natural

Example

John has an Acura. "He' is attractive. (Where, he = John, not the Acura) (5.29)
John has an Acura. Tt is attractive. (Where, it = the Acura, not John) 5.30)
4. Syntactic Constraints

their syntactic
When two referential expressions are used in the same sentence,
limit reference
interactions with potential antecedent noun phrases may potentially
relations.

Example
subject to the constraints indicated
The pronouns in all of the following sentences are

in brackets.
J o h n bought 'himself a new Acura. (himself =John) (5.31)

John bought him'a new Acura. (him John) 6.32)

Bill) (5.33)
John said that Bill bought 'him'a new Acura. (him
Acura. (himself= Bill) (5.34)
John said that Bill bought himself a new

Acura. (He # John and he # John) (5.35)

He' said that he' bought John a new

and themselves'. A reflexive

Reflexive pronouns in English include himself, herself,
immediate sentence (5.31), but a
that contains it
corefers with the subject of the most
this subject, to greatly simplify the issue (5.32).
nonreflexive cannot corefer with
the reverse reference pattern is evident between
Examples (5.33) and (5.34), in which
the pronoun and the subject of the higher
phrase, demonstrate that this rule only
immediate clause. John, on the other hand, cannot
applies to the subject of the most
the most recent sentence o r with a higher-levell
corefer with either the subject of
subject (5.35).
and
just apply to a referring expression
a certain
These syntactic restrictions don't
also forbid coreference between the two.
potential antecedent noun phrase; they
antecedents that can be used to signify the
regardless of whether there are any other

same item.
like "him, generally, would be able to corefer
or
example, a nonreflexive pronoun
sentence as it does in example (5.36), but it is not
with the subject of the preceding
the coreterential pronoun he' in the
POSsible in example (5.37) due to the presence ot
second clause.
Bill bought 'him' a n e w Acura. (him =
John) (6.36)
John wanted a n e w car.
new Acura. (he =
John, him T.
He' bought 'him'
a *

dohn wanted a n e w car.

6.37)

(MU-New syllabu Tech-Neo Publications...A SACHIN SHAH Venture

Yabus w.e.f academic year 22-23) (M7-83)
Natural Language Processing (MU Sem 7- Comp) (Pragmatic &Discourse Proc.)..Page no. (5-131

simplify the problem too much in a number of ware

The criteria discussed above And
they do not apply in many situations. In truth, the facts become extremely comnl.
plex

upon closer examination. In fact, it seems implausible that mere syntactic relations
ns
could adequately explain all of the evidence.
appear in the same syntactic arrangements, tho
For example, even though they
reflexive himself and the nonreflexive "him in sentences18.43) and (18.44)
respectively, can both relate to the subject John.
John set the pamphlets about Acuras next to himself. (himself = John) (5.38)

John set the pamphlets about Acuras next to him. (him

=
John) (5.39)

5. Selectional Restrictions
Referents may be dropped due to selectional restrictions that a verb imposes on
its arguments, as in the following example (5.40).
John parked his Acura in the garage. He had driven it around for hours. (5.40)

Here, the term it be compared to either the Acura or the garage. The
might
direct object of the verb 'drive', however, must be a vehicle that can be driven,
such as a car, truck, or bus, and cannot be a garage. As a result, 'the Acura' is the

only potential referent because the pronoun appears as the object of drive. It is
feasible that a real-world NLP system might have a set of selectional constraints
that were very extensive for the verbs in its lexicon.

However, in the of metaphors, restrictions

case on selection can be broken. For
example, take a look at (5.41).
John bought a new Acura. It drinks gasoline like you would not believe. (5.41)
in this
Although the verb 'drink' doesn't frequently relate to inanimate objects,
context, it can be used to refer to a brand-new Acura.
are far
Also, more general semantic constraints might also be in force, but they
more challenging to represent thoroughly. Take for example the passage(6.4
car
John parked his Acura in the garage. It is incredibly messy, with old bike and
parts lying around everywhere. (5.42)
John parked his Acura in downtown Beverly Hills. It is incredibly messy,
old bike and car parts lying around everywhere. 5.43)
In 5.42) as a car is probably too small to have bike and automobile parts
around "everywhere" therefore the garage is almost surely the intena
reference it' in this case.
of
In order to resolve this reference, a system must be aware of the normal sva the
automobiles, garages, and the typical kinds of stuff one may find in each. hthat
a
other hand, one's familiarity with Beverly Hills might lead them to believe
the Acura is the passage's reference to that city (5.43).

Venture

(MU-New Syllabus w.e.f academic year 22-23) (M7-83) Tech-Neo Publications...A SACHIN SHAH
 Vatura Language Procecessing (MU Sem 7-Comp) Pragmatic & Discourse Proc.)...Page no. (5-14)
ANAPHORA RESOLUTION **

In this section two algorithms will be

presented from anaphora resolution.
5.6.1 Hobbs Algorithm
One method for pronoun resolving is the Hobbs algorithm. The syntactic parse tree ot
the sentences forms the foundation of the
algorithm.
Consider the (5.44) Jack and Jill example to better grasp the concept and how we as
humans attempt to resolve the pronoun "his."

Jack and Jill went up the hill, To fetch a pail of water. Jack fell down and broke "his'
crown, And Jill came tumbling after. (5.44)
Here, Jack, Jill, hill, water, and crown are the potential resolution candidates for

pronoun 'his'.
the
Why, then, did we not consider the crown as a potential remedy? Perhaps because
initial
word his' was followed by the noun crown'. The Hobbs algorithm's
must always be confined to the left of the
presumption states that the referent search
target, eliminating the crown.
referents?
I f so, are Jill, water, or hill potential
that 'his' might not be referring to her'. The
But since Jill is a girl, we are aware

typically used to refer to male or female

etc. are
pronouns 'he', his', she', her,
to refer to inanimate objects. This characteristic,
animate objects, while it is used
rules out the possibilities Jill, hill,
of and water.
referred as gender agreement,
and entities that are closest to
referenced with pronouns,
Only a few sentences can be
than those that are farther awav, Tt
the referring word are more significant
Recency property is the name given to
with Jack as the only option.
ultimately left us

this property.
embed intelligence (using
the Hobbs algorithm) in
explore how we can
Now, let's the task of pronoun resolution now that
common sense
to accomplish
0Dots that lack resolve pronouns.
how humans digest text and
we have
a better grasp of

Algorithmn the algorithm makes use of

It is when resolving pronouns,

portant to note that, the previo
previous sections. The pronoun to be
s in the
mentioned
syntactic straints as
to and including the current
sentences up to
of the
solved and the
the syntactic parse
Hobbs algorithm.
the
e Serveas theinput to Tech-Neo Publications..A SACHIN SHAH Venture
New Syllabusv 22-23) (M7-83)
w.e.f academic year
 Natural Language Processing (MU -Sem 7-Comp) (Pragmatic &Discourse Proc.)..Page no. (5-15
Fig 5.6.1 details the Hobbs algorithm.
Construot a parse tree and ldentfy the
pronoun for oo-reference reeolution
www.w w.w

move up the tree to the first

NP' or 'S', call
t as 'X and call path to it as p

8earch left-to-nght below the X and left

of p' and propose any 'NP" node which has
an 'NP" or 'S' between it and 'X

If X
is highest 'S ifXle an NP If Xis an
node in sentence

search previous trees, search below 'X to

And 'p' does not
in order of recency, right of 'p', left-to-right,
pass through an 'N-bar
left-to-right, that X breadth-firts, but not
breadth-first, proposing going
NPs immediately dominates through any 'NP', or
propose 'X
encountered 'S', proposing 'NP
encountered
search below 'X to
Go up to first 'NP" or 'S
left of 'p', left-to-right,
node encountered,
and call this 'X, breadth-first,
and path to it p' proposing 'NP
encountered

Satisfied
No
with
Answer?

Yes

Answer
Fig 5.6.1 :Hobbs Algorithm
Example
Let's look at two sentences:
(5.45)
Sentence 1(S1):Jack is an engineer.
Sentence 2 (S2): Jill likes him.
(MU-New Syllabus w.e.f academic year
22-23) (M7-83) Tech-Neo Publications... ASACHIN SHAH
Venu
 LanguageProcessing (MU
Natural -

Sem 7-Comp) (Pragmatic &Discourse Proc.)...Page no. (5-16)

S

S1

NP P
NP
Jack
Jill
NP
NP
S
likes PRP
Det
him
an
engineer

Fig. 5.6.2:Parse Tree for the given sentences

The problem identified is to resolve the pronoun him'.

Based on the algorithm

Go back from him' to PRP' to NP and this 'NP will be called as * and the path
1
him' to PRP to NP' as p'.

2. As there is no path to the left of p', we again go back from NP' to VP to s2,

which is our new *.

Due to the syntactic restrictions imposed by Binding theory, it does not, however,
3.
nonreflexive cannot refer to the
study that branch. According to binding theory,
a

clause in which However, a reflexive

it appears.
subject of the most immediate
can. Reflexive words include
such like himself, herself, themselves, etc. So, we
becomes my new *.
again go backwards to 'S',
4. From S we move to 'S1,
which is our new XK. 4
S2
Now we have encountered

NP when search the path. NP VP NP

This NP does not violate Jack Jill

NP
any constraints hence, this
18 out solution or answer. likes PRP
Det
That is, the him' in the
Baven sentences refers to an engineer him
Jack' Fig.5.6.3 : Resolution Path

'him'.
ig 5.6.3 sho resolution path for the pronoun
Shows the pronoun

MU-Nelew Syllabus (M7-83)

Tech-Neo Publications...A SACHIN SHAH Venture
w.e.f ademic year 22-23)
Natural Language Processing (MU - Sem 7- Comp) (Pragmatic &Discourse Proc.)..Page no. (5-171

5.6.2 Centering Algorithmn

An explicit discourse model representation is not used by the Hobbs algorithm

that explicitly represents a

Centering theory, in contrast, is a family of models
discourse model and also makes the claim that at any given point in the discourse,

and that this object should be distinguished from all

only one entity is being "focused"
other entities that have been evoked.

There two main representations tracked in the Centering

are
theory discoursemodel.
utterances. The Backward
In what follows, take U, and Un1 to be two adjacent
looking center of Un. denoted as C,(U,), represents the entity currently being focused
on Forward looking in the discourse after U, is interpreted. The forward looking
ordered list containing the entities
centers Un, denoted as Cf (U,), form an
of
mentioned in Un, all of which could serve as the Cb
of the following utterance. In fact,
element of CE (U,) mentioned in U
CpUn+ 1) is by definition the most highly ranked
first utterance in a discourse is undefined.) As
for how the entities
+1 (The Ch of the
sake we can use the grammatical role
in the Cr (U,) are ordered, for simplicity's
hierarchy below.

nominal object >indirect object or oblique >

Subject> existential predicate
>

demarcated adverbial PP

We call thehighest rank forward looking center as Cp (preferred center).

are determined by the algorithm based on the
The preferred referents of pronouns
relationships between the
forward and backward looking centres in neighbouring
phrases. According to
the link between C(Un+ 1), ChUn), and Cp (Un + 1, four
intersentential interactions between a pair ofutterances Un and Un +1 are specified

these are depicted in Fig 5.6.4.

Ch (Un+1) =C,(U,) Ch=(Un+1)#CpU)

Or undefined Ch(U,)

Ch (Un+ 1)= Cp(Un +1 Continue Smooth-Shift

Ch=(Un+ 1)+ C,(Un+1 Retain Rough-Shift
Fig. 5.6.4 : Transitions

Following rules are to be followed:

then
Rule 1: If any element of Cr (U,) is realized by a pronoun in utterance Un + 1

ChUn+1 must be realized as a pronoun also.

Tech-Neo Publications..A SACHIN SHAH V
enture

(MU-New Syllabus w.e.f academic year 22-23) (M7-83)

Nature
Language rocessing (MU -
Sem
7-Comp) (Pragmatic & Discourse Proc.)...Page no.(5-18)
Rule 2: Transition states are ordered. Continue is preferred to Retain is preferred to
Smooth-Shift is preferred to Rough-Shift.

The algorithm is defined as follows.

arrangement of rererene
1. Create potential C-Ce pairings for every conceivable
assignments.

Use constraints, such as selectional limitations, centering rules, and syntactie

2.
coreference requirements, to narrow the results.

3 Order by transitional phrases

and
(gender, number, syntactic,
If Rule 1 and other coreference requirements
referents that are assigned
selectional restrictions) are not broken, the pronominal
Rule [Link] us step through
are those that produce
the most desired relation in
the algorithm.
assage (21.66) to illustrate
5.46)
at the used car dealership. (U1)
John saw a beautiful 1961 Ford Falcon

He showed it to Bob. (U;)

He bought it. (U3)

order the Cf, for sentence U1
we get:
role hierarchy to
Using the grammatical
dealership)
C (U1):1John, Ford,
C, (U):John
C (U1): undefined
interchangeable
with John, and it, which is
is
he pronouns he', which are presentin sentence Ug. John is
Ford or the dealership,
nterchangeable with the
because he' is
the highest-ranking Cr (U1) member mentionedi
bU) by definition referent of it,
For each potential
referent for he').
(Since he' is the only possible
would be as follows if we
2 we
The assignments
the ensuing transitions are
compared.

presume it' pertains to the Falcon:

Ce Ug): John, Ford, Bob)

Cp Ug): John
Ch Ug):John

SACHIN SHAH Venture

Tech-Neo Publications...A
MUNew Sy us w.e.f academic year 22-23)
(M7-83)
 Natural Language Processing (MU - Sem 7-Comp) (Pragmatic & Discourse Proc.)..Page no. (5.1au
9
undefined)
Result:Continue (C,(U2)= C%(U2); Ch(U)
If we assume it refers to the dealership, the assignments would be:

CrU2): tJohn, dealership, Bob

CPU):John
ChU):John
Result: Continue (C,(U2)= C%(U2); C,(U1) undefined)
Since both options lead to a Continue transition, the algorithm is unable to determine
which should be chosen. We will assume for the purposes of example that ties are
broken in terms of the ranking on the prior Cf list. As a result, we will assume that
refers to the Falcon rather than the dealership, maintaining the first choice above's

representation of the current discourse model.

. While it is compatible with the Ford in sentence U3, he is compatible with either John
or Bob. If we take him to mean John, then John is ChU), and the tasks wouldbe

Cr U3): 1John, Ford)

Cp (U3)John
C U3): John
Result: Continue (Cp (U3)=©%(U3)=C%(U2))
. I f we assume he refers to Bob, then Bob is Cb{U3) and the assignments wouldbe:

C (Us): Bob, Ford)

Cp (Us): Bob

Cb Ug): Bob
Result: Smooth-Shift (C(U3)=©% (Ua); C%(U3)6=Ch (U2))
Since a Continue is preferred to a Smooth-Shift per Rule 2, John is correctly taken t
be the referent.

The key salient factors that the centering algorithm implicitly takes into account a
are

for the
the preferences repeated mentions, recency, and grammatical roles. Since
resulting transition type determines the final reference assignments, the
grammatical role hierarchy only indirectly influences salience.
In particular, ifthe former results in a more highly ranked transition, a referent
low-ranking grammatical role will be preferred to one in a more highly ra
nked

position.
(MU-New Syllabus w.e.f academic year 22-23) (M7-83) V e n t u r e

Tech-Neo Publications..A SACHIN SHAH

Natural Languag Processing (MU Sem 7-Comp) (Pragmatic &Discourse Proc.)..Page no.(5-20)
Consequently, the centering algorith1m can mistakenly resolve a pronoun to a

referent with low salience. For illustration's sake (5.47),

Bob opened up a new dealership last week. John took a look at the Fords in his lot. He
ended up buying one. (6.47)

The third sentence's subject pronoun, "he," will be assigned to Bob by the centering
method because Bob is Ch(U2), whereas John will be assigned if John is C(U2),
resulting in a Smooth-Shift relation.
On the other hand, John will be accurately designated as the referent by the Hobbs
The like the Hobbs algorithm, needs both
algorithm. centering algorithm,
morphological gender detectors anda complete syntactic parse.

As a model of entity coherence, centering theory also has implications for other
discourse applications, such as summarization.

Chapter Ends..

DOO