Module 5: Discourse and Reference Resolution

1. Fundamental Concepts

1.1 Discourse
Discourse refers to a connected sequence of linguistic units (sentences, utterances, or larger text segments) that
form a meaningful communication. It goes beyond individual sentences to analyze how multiple sentences
relate to each other to convey meaning in context.

Key aspects:

Studies how sentences combine to form coherent text

Examines linguistic structures larger than single sentences

Analyzes how context affects meaning interpretation

Essential for understanding natural language communication

1.2 Coherence
Coherence is the quality that makes a text semantically meaningful and logically connected. A coherent text has
ideas that flow naturally and relate to each other in understandable ways.

Characteristics:

Logical flow of ideas

Clear relationships between sentences

Unified topic or theme

Meaningful connections that readers can infer

1.3 Cohesion
Cohesion refers to the linguistic devices that create surface connections between sentences in a text. It's the
grammatical and lexical linking that holds a text together.

Ways to achieve cohesion:

Reference: Using pronouns, demonstratives (this, that, these, those)

Substitution: Replacing one word with another (do, so, one)

Ellipsis: Omitting repeated elements

Conjunction: Using connecting words (and, but, however, therefore)

Lexical cohesion: Repetition, synonyms, related words

1.4 Importance of Discourse Analysis in NLP

Discourse analysis is crucial for:

Machine Translation: Understanding context improves translation accuracy

Text Summarization: Identifying main topics and their relationships

Question Answering: Resolving references to provide accurate answers

Dialogue Systems: Maintaining conversation context and coherence

Information Extraction: Understanding how entities relate across sentences

Sentiment Analysis: Tracking opinion changes throughout text

Text Generation: Producing coherent and natural-sounding text

2. Reference Phenomenon

2.1 Referring Expressions and Referents

Referring Expression: A linguistic expression used to identify or refer to an entity in the discourse. Examples
include pronouns (he, she, it), proper names (John, Microsoft), definite descriptions (the president, the blue car).

Referent: The actual entity in the world or discourse model that a referring expression points to. It's what the
expression refers to.

Example: In "John bought a car. He drove it home."

"He" is a referring expression → referent is John

"it" is a referring expression → referent is the car

2.2 Five Types of Referring Expressions

1. Indefinite Noun Phrases: Introduce new entities into discourse
Use articles: a, an, some

Example: "A student entered the room"

Signals new information to the listener

2. Definite Noun Phrases: Refer to entities assumed known to the listener

Use article: the

Example: "The student asked a question"

Presupposes entity exists and is identifiable

3. Pronouns: Short forms replacing noun phrases

Personal: he, she, it, they

Possessive: his, her, its, their

Demonstrative: this, that, these, those

Example: "She answered it carefully"

4. Demonstratives: Point to specific entities with spatial/temporal distance

Proximal: this, these (near speaker)

Distal: that, those (far from speaker)

Example: "This book is mine; that one is yours"

5. Proper Names: Unique identifiers for specific entities

People: Alice, Dr. Smith

Places: London, Stanford University

Organizations: Google, United Nations

Example: "Microsoft announced new features"

2.3 Special Uses

Inferable/Bridging References: References that can be inferred from context

Example: "John bought a car. The engine was powerful."

"The engine" is inferable because cars have engines

Generic References: Refer to entire classes or types

Example: "The lion is a dangerous animal"

Refers to lions in general, not a specific lion

Non-referential Uses: Expressions that don't refer to specific entities

Expletive "it": "It is raining"

Expletive "there": "There are three books on the table"

 These have grammatical function but no specific referent

3. Anaphora and Reference Resolution

3.1 Anaphora Resolution
Anaphora: A linguistic expression that refers back to a previously mentioned entity (the antecedent).

Anaphora Resolution: The process of determining what an anaphoric expression refers to. It involves
identifying the correct antecedent for pronouns and other referring expressions.

Example: "Sarah went to the store. She bought milk."

Anaphor: "She"

Antecedent: "Sarah"

Task: Determine that "She" = "Sarah"

3.2 Anaphora vs. Cataphora

Anaphora: Refers backward to a previously mentioned entity

Example: "When Sarah arrived, she was tired."

"she" refers back to "Sarah"

Cataphora: Refers forward to an entity mentioned later

Example: "When she arrived, Sarah was tired."

"she" refers forward to "Sarah"

Less common than anaphora

3.3 Two Reference Resolution Tasks

1. Pronominal Anaphora Resolution (Pronoun Resolution)
Finding antecedents for pronouns (he, she, it, they)

Most common reference resolution task

Example: "John met Mary. He greeted her."

2. Co-reference Resolution
Identifying all expressions that refer to the same entity

Groups referring expressions into co-reference chains

Handles pronouns, definite NPs, proper names

Example: "Apple Inc. released a new iPhone. The company's stock rose."

4. Co-reference Resolution

4.1 Co-reference Chain

A co-reference chain (or equivalence class) is a set of all referring expressions in a text that refer to the same
entity.

Example: "Barack Obama was born in Hawaii. The president served two terms. He left office in 2017."

Co-reference chain: {Barack Obama, The president, He} → all refer to the same person

Importance:

Essential for text understanding and information extraction

Enables tracking entities throughout documents

Critical for question answering and summarization

Helps resolve ambiguity in natural language

4.2 Features for Co-reference Resolution

1. Number Agreement: Singular anaphors match singular antecedents

"The student... he/she" ✓

"The students... he/she" ✗

2. Person Agreement: Match grammatical person (1st, 2nd, 3rd)

Maintain consistency in person reference

3. Gender Agreement: Match gender characteristics

"The woman... she" ✓

"The woman... he" ✗

4. Semantic Type/Entity Type: Match semantic categories

Person pronouns for people: "John... he"

Object pronouns for things: "car... it"

Organization names with "it" or "they"

5. Syntactic Constraints: Structural rules

Binding theory constraints

C-command relationships in syntax trees

6. Distance/Recency: Prefer closer antecedents

More recent mentions are more likely antecedents

Measure in sentences or clauses

7. Grammatical Role: Subject preference

Subjects are more likely antecedents than objects

Example: "John told Bill that he won" → "he" likely = John

8. Salience/Givenness: More prominent entities preferred

Entities in focus are more likely referents

Repeated mentions increase salience

9. Selectional Restrictions: Verb-argument compatibility

"The rock ate dinner" → unlikely, rocks don't eat

Semantic plausibility constraints

10. Parallelism: Similar syntactic positions

Same grammatical role in parallel structures

"John likes Mary, and Bill likes her too"

5. Algorithms for Anaphora Resolution

5.1 Hobbs Algorithm

A syntax-based algorithm for pronominal anaphora resolution that searches parse trees for antecedents.

Algorithm Steps:

1. Begin at the NP node immediately dominating the pronoun

2. Go up the tree to the first NP or S node

 3. Traverse the tree breadth-first, left-to-right, proposing NPs as antecedents

4. If no antecedent found, move to the previous sentence

5. Traverse that sentence's parse tree from top

6. Propose NPs in breadth-first order

7. Apply filtering constraints (number, gender agreement)

8. Select first compatible NP as antecedent

Characteristics:

Uses syntactic parse tree structure

Implements left-to-right, breadth-first search

Incorporates recency preference

Simple but effective baseline

Requires accurate syntactic parsing

Example Application: For "John drove to the store. He bought milk":

1. Parse both sentences

2. Search for antecedent of "He"

3. Traverse previous sentence tree

4. Find "John" as compatible masculine singular NP

5. Return "John" as antecedent

5.2 Centering Algorithm

A discourse-based approach that tracks focus/center of attention across sentences.

Key Concepts:

Centers:

Cb (Backward-looking center): Most salient entity from previous utterance

Cp (Preferred center): Most salient entity in current utterance

Cf (Forward-looking centers): Ranked list of entities in current utterance

Transitions: Relationships between consecutive utterances

1. Continue: Same Cb, same Cp (most coherent)

2. Retain: Same Cb, different Cp

3. Smooth-Shift: Different Cb, Cb = Cp

4. Rough-Shift: Different Cb, Cb ≠ Cp (least coherent)

Algorithm:

1. Identify all entities in utterance

2. Rank by grammatical role (Subject > Object > Others)

3. Determine Cb from previous utterance

4. Calculate transition type

5. Prefer continuations that maintain centers

6. Resolve pronouns to entities maintaining coherence

Example:
 S1: "John went to the bank"
Cf: {John, bank}, Cp: John

S2: "He deposited money"

Cb: John, Cf: {He, money}, Cp: He

Transition: Continue (coherent)

"He" resolves to John

5.3 Features for Pronominal Anaphora Resolution

When resolving pronouns to potential referents, consider:

1. Morphological Agreement:
Number (singular/plural)

Gender (masculine/feminine/neuter)

Person (1st/2nd/3rd)

2. Syntactic Features:
Grammatical role (subject/object)

Binding constraints

Syntactic parallelism

3. Semantic Features:
Semantic type compatibility

Selectional restrictions

World knowledge

4. Distance Features:
Sentence distance

Clause distance

Number of intervening NPs

5. Salience Features:
Grammatical role prominence

Repeated mentions

Position in discourse

6. Contextual Features:
Topic continuity

Discourse structure

Focus tracking

6. Reference Operations and Discourse Model

6.1 Discourse Model Operations

Introduction: Adding new entities to the discourse model

Indefinite NPs typically introduce entities

"A student asked a question" → adds student and question

Direct Reference: Referring to existing entities

Definite NPs and pronouns

"The student waited" → refers to known student

Inferential Reference: Accessing entities through bridging

Related entities inferred from context

"John bought a car. The steering wheel was damaged"

Entity Tracking: Maintaining entity states

Updates properties and relationships

Tracks entity salience over discourse

6.2 Relationships in Discourse Model

Identity: Multiple expressions refer to same entity

Part-Whole: Meronymic relationships (car → engine)

Set-Membership: Entity belongs to a set

Attributive: Property relationships

Event-Participant: Entities involved in events

7. Discourse Structures

7.1 Rhetorical Structure Theory (RST)

A theory describing hierarchical organization of texts through rhetorical relations between text spans.

Core Concepts:

Nucleus: Central, more essential text span

Satellite: Supporting, less essential text span

Relations: Connect nucleus and satellite or multiple nuclei

Common RST Relations:

Multinuclear Relations (equal importance):

1. Sequence: Chronological order of events

2. Contrast: Opposing or differing situations

3. Joint: Elements at same level without specific relation

4. List: Enumeration of items

Nucleus-Satellite Relations:

1. Elaboration: Satellite provides details about nucleus

"John is tall. He is 6'5" tall."

2. Background: Satellite provides context for nucleus

"Before the meeting started, John reviewed notes."

3. Evidence: Satellite supports nucleus with proof

"Climate is changing. Temperatures have risen 2°C."

4. Cause: Satellite causes nucleus situation

"Because it rained, the match was cancelled."

5. Result: Nucleus results from satellite

"It rained heavily, so the streets flooded."

6. Purpose: Satellite describes nucleus's goal

"She studied hard to pass the exam."

7. Condition: Satellite specifies condition for nucleus

 "If it rains, the event will be postponed."

8. Concession: Satellite acknowledges contrary position

"Although tired, she continued working."

9. Justification: Satellite justifies nucleus claim

"We should leave now, since traffic gets heavy."

10. Evaluation: Satellite assesses nucleus

"The plan worked well, which was fortunate."

RST Tree Structure:

Hierarchical tree representation

Leaves are elementary discourse units (EDUs)

Internal nodes represent relations

Captures document coherence structure

7.2 Other Discourse Structures

Grosz and Sidner Theory:

Three components: linguistic structure, intentional structure, attentional state

Focus spaces track discourse entities

Hierarchical organization of discourse segments

Penn Discourse TreeBank (PDTB):

Lexically grounded approach

Discourse connectives signal relations

Four relation types: Temporal, Contingency, Comparison, Expansion

Topic Segmentation:

Dividing text into topically coherent segments

Linear or hierarchical segmentation

Applications in summarization and retrieval

8. Discourse Segmentation

8.1 Types of Segmentation Methods

1. Lexical Cohesion Methods:

Based on word repetition and semantic similarity

TextTiling algorithm

Segments where lexical cohesion drops

Uses sliding windows to detect boundaries

2. Cue Phrase-Based Methods:

Uses explicit discourse markers

Three stages:
1. Cue phrase identification: Detect markers (however, therefore, first, next)

2. Relation classification: Determine relationship type

3. Segment attachment: Attach segments based on relations

Markers signal shifts or continuations

3. Machine Learning Methods:

Supervised learning with annotated data

Features: lexical, syntactic, semantic

Classification or sequence labeling

Can combine multiple information sources

4. Topic Modeling Methods:

Latent Dirichlet Allocation (LDA)

Detect topic changes for boundaries

Unsupervised approach

Good for long documents

8.2 Cue-Phrase Based Coherence Extraction

Three Stages:

Stage 1: Cue Phrase Detection

Identify discourse markers in text

Examples: however, moreover, first, in conclusion

Build lexicon of cue phrases

Disambiguate multi-purpose words

Stage 2: Relation Identification

Classify relationship signaled by cue

Categories: contrast, elaboration, temporal, causal

Use cue phrase semantics

Consider syntactic context

Stage 3: Structure Building

Construct hierarchical discourse structure

Attach segments based on relations

Build discourse tree

Validate coherence

9. Lexical Resources for NLP

9.1 WordNet
Structure:

Lexical database of English

Groups words into synonym sets (synsets)

Represents concepts, not just words

Relations: hypernymy, hyponymy, meronymy, antonymy

Applications:

Word sense disambiguation

Semantic similarity calculation

Information retrieval
 Text classification

Question answering

Example:

Synset: {car, auto, automobile, machine, motorcar}

Hypernym: vehicle

Meronym: engine, wheel

9.2 PropBank
Structure:

Adds semantic role labels to Penn Treebank

Verb-centric annotation

Numbered arguments (ARG0, ARG1, etc.)

Framesets for different verb senses

Semantic Roles:

ARG0: Agent (typically subject)

ARG1: Patient/Theme (typically object)

ARG2-5: Verb-specific roles

ARGM: Modifiers (location, time, manner)

Applications:

Semantic role labeling

Information extraction

Question answering

Machine translation

Example: "John broke the window with a hammer"

broke.01: ARG0=John, ARG1=window, ARG2=hammer

9.3 FrameNet
Structure:

Frame semantics approach

Frames represent conceptual scenarios

Frame elements are participant roles

Lexical units evoke frames

Components:

Frames: Conceptual structures (Commerce_buy)

Frame Elements: Roles (Buyer, Goods, Seller)

Lexical Units: Words evoking frame (buy, purchase, acquire)

Applications:

Semantic parsing

Information extraction

Textual entailment
 Paraphrase detection

Example: Commerce_buy frame:

Elements: Buyer, Seller, Goods, Money

Verbs: buy, purchase, acquire

"Mary bought a book from John for $20"

10. Text Processing Techniques

10.1 Porter Stemmer

Definition: Algorithm for removing common morphological endings from English words.

Key Features:

Five phases with multiple rules

Removes suffixes step-by-step

Measures word size before removing suffix

Handles various suffix patterns

Benefits:

Reduces vocabulary size

Groups related words

Improves information retrieval

Fast and simple

Language-specific (English)

Limitations:

Over-stemming: "universe" → "univers"

Under-stemming: keeps some variants separate

Not linguistically motivated

Produces non-words

Not reversible

Example:

connection → connect

connections → connect

connected → connect

connecting → connect

10.2 Lemmatization Approaches

Lemmatization reduces words to their dictionary form (lemma) using vocabulary and morphological analysis.

Eight Approaches:

1. Dictionary-Based Lookup:

Use pre-built dictionary mapping

Fast but limited coverage

Example: "better" → "good"

2. Rule-Based:
 Hand-crafted morphological rules

Language-specific patterns

Example: Remove "-ing", "-ed" with vowel doubling rules

3. Morphological Analysis:

Analyze word structure (prefix, root, suffix)

Linguistic understanding

Example: "unhappiness" → "un-happy-ness" → "happy"

4. Machine Learning:

Train models on annotated data

Learn patterns from examples

Handles exceptions well

5. WordNet-Based:

Use WordNet lemma information

Considers POS tags

High accuracy for covered words

6. Finite-State Transducers:

Model morphological processes

Bidirectional mapping

Efficient computation

7. Hybrid Approaches:

Combine dictionary + rules + ML

Fallback mechanisms

Better coverage and accuracy

8. Neural Network Approaches:

Sequence-to-sequence models

Character-level processing

Learn from large corpora

Handle rare words better

Lemmatization vs Stemming:

Lemmatization produces valid words

Considers POS context

More accurate but slower

Better for understanding tasks

11. Industry Applications of Co-reference Resolution

11.1 Use Cases

1. Question Answering Systems:

Resolve pronouns in questions and answers

Track entities across multiple sentences

 "Who is the CEO of Apple? When did he start?"

2. Information Extraction:

Extract entity relationships across documents

Build knowledge graphs

Merge information about same entity

3. Text Summarization:

Maintain entity references in summaries

Avoid ambiguous pronouns

Create coherent condensed text

4. Machine Translation:

Preserve reference relationships

Handle dropped pronouns (pro-drop languages)

Maintain discourse coherence

5. Chatbots and Dialogue Systems:

Track conversation history

Resolve references to previous utterances

Maintain context across turns

6. Search Engines:

Improve query understanding

Return relevant documents

Handle pronoun queries

7. Content Recommendation:

Understand user interests across mentions

Track entities in user history

Improve personalization

8. Healthcare Systems:

Link patient mentions in medical records

Track symptoms and treatments

Support clinical decision-making

9. Legal Document Analysis:

Track parties across contracts

Identify entity mentions

Support e-discovery

10. Social Media Analysis:

Track trending entities

Sentiment analysis about entities

Event detection and tracking

Summary
This module covers the essential aspects of discourse processing and reference resolution in NLP.
Understanding how texts maintain coherence, how references work, and how to resolve them computationally is
fundamental for building systems that truly understand natural language in context. The combination of
linguistic theory (RST, centering theory) and practical algorithms (Hobbs, machine learning approaches)
provides both theoretical foundation and implementation strategies for these challenging problems.