Computational Linguistics: Pragmatics and Formalisms
9/21/2024
CPSC503 Winter 2016
1
CPSC 503
Computational Linguistics
Intro to Pragmatics
Lecture 13
Giuseppe Carenini
9/21/2024
CPSC503 Winter 2016
2
Knowledge-Formalisms Map
(including probabilistic formalisms)
•
Logical formalisms
(First-Order Logics)
•
Thesaurus & corpus
based methods &
Neural models
Rule systems
(and prob. versions)
State Machines
(prob. versions)
Neural Models
Morphology
Syntax
Pragmatics
Discourse:
Monolog and
Dialogue
Semantics
AI planners
(HTN, MDPs+RL)
U
n
d
e
r
s
t
a
n
d
i
n
g
G
e
n
e
r
a
t
i
o
n
9/21/2024
CPSC503 Winter 2016
3
Today Feb 25
•
Brief Intro Pragmatics
•
Discourse
–
Monologue
–
Dialog
9/21/2024
CPSC503 Winter 2016
4
“Semantic” Analysis
Syntax-driven and Lexical
Semantic Analysis
Sentence
Literal
Meaning
Discourse
Structure
Meanings
of words
Meanings of
grammatical
structures
Context
Common-Sense
Domain knowledge
Intended meaning
Further
Analysis
I
N
F
E
R
E
N
C
E
Pragmatics
9/21/2024
CPSC503 Winter 2016
5
Semantic Analysis
Syntax-driven
Semantic Analysis
Sentence
Literal
Meaning
Discourse
Structure
Meanings
of words
Meanings of
grammatical
structures
Context
Common-Sense
Domain knowledge
Intended meaning
Further
Analysis
I
N
F
E
R
E
N
C
E
I am going to SFU on Tue
The garbage truck just left
Shall we meet on Tue?
What time is it?
9/21/2024
CPSC503 Winter 2016
6
Pragmatics: Example
(i) A: So can you please come over here again right
now
(ii) B: Well, I have to go to Edinburgh today sir
(iii) A: Hmm. How about this Thursday?
What information can we infer about the
context in which this (short and
insignificant) exchange occurred ?
9/21/2024
CPSC503 Winter 2016
7
Pragmatics: Conversational Structure
(i) A: So can you please come over here again
right now
(ii) B: Well, I have to go to Edinburgh today sir
(iii) A: Hmm. How about this Thursday?
Not the end of a conversation (nor the beginning)
Pragmatic knowledge: Strong expectations about
the structure of conversations
•
Pairs e.g., request <-> response
•
Closing/Opening forms
9/21/2024
CPSC503 Winter 2016
8
Pragmatics: Dialog Acts
•
A is
requesting
B to come at time of speaking,
•
B
implies he can’t
(or would rather not)
•
A
repeats the request
for some other time.
Pragmatic assumptions relying on:
•
mutual knowledge
(
B
knows that
A
knows that…)
•
co-operation
(must be a response… triggers inference)
•
topical coherence
(
who
should do
what
on Thur?)
(i) A: So can you please come over here again
right now?
(ii) B: Well, I have to go to Edinburgh today sir
(iii) A: Hmm. How about this Thursday?
9/21/2024
CPSC503 Winter 2016
9
Pragmatics: Specific Act (Request)
•
A wants B to come over
•
A believes it is possible for B to come over
•
A believes B is not already there
•
A believes he is not in a position to order B to…
Assumption:
A
behaving rationally and sincerely
(i) A: So can you please come over here again
right now
(ii) B: Well, I have to go to Edinburgh today sir
(iii) A: Hmm. How about this Thursday?
Pragmatic knowledge: speaker beliefs and
intentions underlying the
act of requesting
9/21/2024
CPSC503 Winter 2016
10
Pragmatics: Deixis
•
A assumes B knows where A is
•
Neither A nor B are in Edinburgh
•
The day in which the exchange is taking place is
not Thur., nor Wed. (or at least, so A believes)
Pragmatic knowledge: References to space and
time wrt space and time of speaking
(i) A: So can you please come over here again
right now
(ii) B: Well, I have to go to Edinburgh today sir
(iii) A: Hmm. How about this Thursday?
9/21/2024
CPSC503 Winter 2016
11
Today Feb 25
•
Brief Intro Pragmatics
•
Discourse
–
Monologue
–
Dialog
9/21/2024
CPSC503 Winter 2016
12
Discourse: Monologue
•
Monologues
as sequences of “sentences”
have
structure
•
Tasks:
Rhetorical (discourse) parsing
and generation
•
Key discourse phenomenon:
referring
expressions
(what
they
denote may
depend on previous discourse)
Task
:
Coreference resolution
(like sentences as sequences of words)
9/21/2024
CPSC503 Winter 2016
13
Discourse/Text Segmentation(1)
•
Simple approach:
–
linear (unable to identify hierarchical structure)
–
Subtopics, passages
UNSUPERVISED
•
Key idea:
lexical cohesion
(vs. coherence)
“There is not water on the moon. Andromeda
is covered by the moon.”
•
Discourse segments tend to be lexically
cohesive
•
Cohesion score drops on segment boundaries
9/21/2024
CPSC503 Winter 2016
14
Discourse/Text Segmentation(2)
SUPERVISED
•
Binary classifier (SVM, decision tree,…)
•
: make yes-no boundary decision between
any two sentences
features
•
Cohesion features (e.g., word overlap, word
cosine)
9/21/2024
CPSC503 Winter 2016
15
Sample Monologues: Coherence
H
o
u
s
e
-
A
i
s
a
n
i
n
t
e
r
e
s
t
i
n
g
h
o
u
s
e
.
I
t
h
a
s
a
c
o
n
v
e
n
i
e
n
t
l
o
c
a
t
i
o
n
.
E
v
e
n
t
h
o
u
g
h
h
o
u
s
e
-
A
i
s
s
o
m
e
w
h
a
t
f
a
r
f
r
o
m
t
h
e
p
a
r
k
,
i
t
i
s
c
l
o
s
e
t
o
w
o
r
k
a
n
d
t
o
a
r
a
p
i
d
t
r
a
n
s
p
o
r
t
a
t
i
o
n
s
t
o
p
.
It has a convenient location. It is close to work. Even
though house-A is somewhat far from the park,
house-
A is an interesting house. It is close to a rapid
transportation
stop.
9/21/2024
CPSC503 Winter 2016
16
Corresponding Text Structure
H
o
u
s
e
-
A
i
s
a
n
i
n
t
e
r
e
s
t
i
n
g
h
o
u
s
e
.
I
t
h
a
s
a
c
o
n
v
e
n
i
e
n
t
l
o
c
a
t
i
o
n
.
E
v
e
n
t
h
o
u
g
h
h
o
u
s
e
-
A
i
s
s
o
m
e
w
h
a
t
f
a
r
f
r
o
m
t
h
e
p
a
r
k
i
t
i
s
c
l
o
s
e
t
o
w
o
r
k
i
t
i
s
c
l
o
s
e
t
o
a
r
a
p
i
d
t
r
a
n
s
p
o
r
t
a
t
i
o
n
s
t
o
p
E
V
I
D
E
N
C
E
-
1
C
O
N
C
E
S
S
I
O
N
-
1
C
O
R
E
-
1
decomposition
ordering
rhetorical relations
RST
9/21/2024
CPSC503 Winter 2016
17
9/21/2024
CPSC503 Winter 2016
18
Parsing
H
o
u
s
e
-
A
i
s
a
n
i
n
t
e
r
e
s
t
i
n
g
h
o
u
s
e
.
I
t
h
a
s
a
c
o
n
v
e
n
i
e
n
t
l
o
c
a
t
i
o
n
.
E
v
e
n
t
h
o
u
g
h
h
o
u
s
e
-
A
i
s
s
o
m
e
w
h
a
t
f
a
r
f
r
o
m
t
h
e
p
a
r
k
i
t
i
s
c
l
o
s
e
t
o
w
o
r
k
i
t
i
s
c
l
o
s
e
t
o
a
r
a
p
i
d
t
r
a
n
s
p
o
r
t
a
t
i
o
n
s
t
o
p
decomposition
ordering
rhetorical relations
H
o
u
s
e
-
A
i
s
a
n
i
n
t
e
r
e
s
t
i
n
g
h
o
u
s
e
.
I
t
h
a
s
a
c
o
n
v
e
n
i
e
n
t
l
o
c
a
t
i
o
n
.
E
v
e
n
t
h
o
u
g
h
h
o
u
s
e
-
A
i
s
s
o
m
e
w
h
a
t
f
a
r
f
r
o
m
t
h
e
p
a
r
k
,
i
t
i
s
c
l
o
s
e
t
o
w
o
r
k
a
n
d
t
o
a
r
a
p
i
d
t
r
a
n
s
p
o
r
t
a
t
i
o
n
s
t
o
p
.
9/21/2024
CPSC503 Winter 2016
19
Generation
H
o
u
s
e
-
A
i
s
a
n
i
n
t
e
r
e
s
t
i
n
g
h
o
u
s
e
.
I
t
h
a
s
a
c
o
n
v
e
n
i
e
n
t
l
o
c
a
t
i
o
n
.
E
v
e
n
t
h
o
u
g
h
h
o
u
s
e
-
A
i
s
s
o
m
e
w
h
a
t
f
a
r
f
r
o
m
t
h
e
p
a
r
k
i
t
i
s
c
l
o
s
e
t
o
w
o
r
k
i
t
i
s
c
l
o
s
e
t
o
a
r
a
p
i
d
t
r
a
n
s
p
o
r
t
a
t
i
o
n
s
t
o
p
decomposition
ordering
rhetorical relations
GOAL: Convince hearer that she/he should look at House-A
H
o
u
s
e
-
A
i
s
a
n
i
n
t
e
r
e
s
t
i
n
g
h
o
u
s
e
.
I
t
h
a
s
a
c
o
n
v
e
n
i
e
n
t
l
o
c
a
t
i
o
n
.
E
v
e
n
t
h
o
u
g
h
h
o
u
s
e
-
A
i
s
s
o
m
e
w
h
a
t
f
a
r
f
r
o
m
t
h
e
p
a
r
k
,
i
t
i
s
c
l
o
s
e
t
o
w
o
r
k
a
n
d
t
o
a
r
a
p
i
d
t
r
a
n
s
p
o
r
t
a
t
i
o
n
s
t
o
p
.
9/21/2024
CPSC503 Winter 2016
20
Text Relations, Parsing and Generation
Parsing:
Given a monologue, determine its rhetorical
structure (semi-sup. [Marcu, ’00 and ‘02]) (
sup.
[Duverle & Prendinger ‘09])….
Our own work [CL,2015]
•
G
e
n
e
r
a
t
i
o
n
:
G
i
v
e
n
a
c
o
m
m
u
n
i
c
a
t
i
v
e
g
o
a
l
e
.
g
.
,
[
c
o
n
v
i
n
c
e
u
s
e
r
t
o
q
u
i
t
s
m
o
k
i
n
g
]
g
e
n
e
r
a
t
e
s
t
r
u
c
t
u
r
e
,
c
o
n
t
e
n
t
,
t
e
x
t
[
R
e
i
t
e
r
e
t
a
l
.
A
I
J
‘
0
3
]
.
G
e
n
e
r
a
t
i
o
n
o
f
t
e
x
t
u
a
l
s
u
m
m
a
r
i
e
s
f
r
o
m
n
e
o
n
a
t
a
l
i
n
t
e
n
s
i
v
e
c
a
r
e
d
a
t
a
[
P
o
r
t
e
t
e
t
a
l
.
A
I
J
‘
0
9
]
.
•
Rhetorical (coherence) Relations:
–
different proposals (typically 20-30 rels)
–
Elaboration, Contrast, Purpose
…
9/21/2024
CPSC503 Winter 2016
21
•
I saw
him
•
I passed
the course
•
I’d like
the red one
•
I disagree with
what you just said
•
That
caused the invasion
Reference
Language contains many references to
entities mentioned in previous sentences
(i.e., in the discourse context/model)
Two tasks
•
Anaphora/pronominal resolution
•
Co-reference resolution
9/21/2024
CPSC503 Winter 2016
22
Reference Resolution
Terminology
Referring expression
: NL expression used to
perform reference
Referent
: “entity” that is referred
Types of referring
expressions:
•
Indefinite NP (a, some, …)
•
Definite NP (the, … )
•
Pronouns (he, she, her,...)
•
Demonstratives (this, that,..)
•
Names
•
Inferrables
•
Generics
(see next)
Cont’ Referring Expressions
•
Inferrables
“ I almost bought a new car
today, but <
a door
> had a dent and <
the
engine
> was too noisy”
•
Generics
“I saw no less than 6 Ferraris
today. <
They
> are the coolest cars.”
9/21/2024
CPSC503 Winter 2016
23
9/21/2024
CPSC503 Winter 2016
24
Pronominal Resolution: “Simplest” Algorithm
•
Last object mentioned (correct gender/person)
–
John ate an apple.
He
was hungry.
•
He refers to John (“apple” is not a “he”)
–
Google is unstoppable.
They
have increased..
•
Selectional restrictions
–
John ate an apple in the store
.
It
was delicious.
[stores cannot be delicious]
It
was quiet.
[apples cannot be quiet]
•
Binding Theory constraints
–
Mary bought
herself
a new Ferrari
–
Mary bought
her
a new Ferrari
9/21/2024
CPSC503 Winter 2016
25
•
Some pronouns don’t refer to anything
–
It
rained
•
must check if verb has a dummy subject
Additional Complications
•
Evaluate “last object” mentioned using parse
tree, not literal text position
–
I went to the GAP, which is opposite to BR,
–
It
is a big store.
[GAP, not BP]
9/21/2024
CPSC503 Winter 2016
26
Focus
John is a good student
He goes to all his tutorials
He helped Sam with CS4001
He
wants to do a project for Prof. Gray
He
refers to John (not Sam)
9/21/2024
CPSC503 Winter 2016
27
Supervised Pronominal Resolution
Corpus annotated with co-reference relations
(all antecedents of each pronoun are marked)
•
What features ?
(U
1
)
John
saw
a nice Ferrari
in
the parking lot
(U
2
)
He
showed
it
to
Bob
(U
3
)
He
bought it
9/21/2024
CPSC503 Winter 2016
28
Need World Knowledge…
–
The police prohibited the fascists from
demonstrating because
they
feared violence.
vs
–
The police prohibited the fascists from
demonstrating because
they
advocated
violence.
Exactly the same syntax!
•
Not possible to resolve
they
without
detailed representation of world knowledge
about
feared violence
vs.
advocated violence
9/21/2024
CPSC503 Winter 2016
29
Coreference resolution
•
Decide whether any pair of NPs co-refer
•
Binary classifier again
NP
j
•
What features?
Same as for anaphora +
specific ones to deal
with definite and names. E.g.,
–
Edit distance
–
Alias (based on type – e.g., for PERSON: Dr. or
Chairman can be removed)
–
Appositive (“Mary, the new CEO, ….”
anaphor
antecedents
Coreference Resolution: State
the art
9/21/2024
CPSC503 Winter 2016
30
Neural Coreference Resolution Kevin Clark CS Stanford University - Report
9/21/2024
CPSC503 Winter 2016
31
Today Feb 25
•
Brief Intro Pragmatics
•
Discourse
–
Monologue
–
Dialog
9/21/2024
CPSC503 Winter 2016
32
Discourse: Dialog
•
Most fundamental form of language use
•
First kind we learn as children
Dialog can be seen as a sequence of
communicative actions of different kinds
(
dialog acts
) - (DAMSL 1997; ~20)
9/21/2024
CPSC503 Winter 2016
33
Dialog: two key tasks
•
(1) Dialog act interpretation:
identify the user dialog act
•
(2) Dialog management: (1) &
decide
what to say and when
9/21/2024
CPSC503 Winter 2016
34
Dialog Act Interpretation
•
What dialog act a given utterance is?
E.g., I’m having problems with the homework
•
Surface form is not sufficient!
–
Statement
- prof. should make a note of this,
perhaps make homework easier next year
–
Directive
- prof. should help student with the
homework
–
Information request
- prof should give student
the solution
9/21/2024
CPSC503 Winter 2016
35
Automatic Interpretation of
Dialog Acts
Logical formalisms
(First-Order Logics)
Morphology
Syntax
Pragmatics
Discourse and
Dialogue
Semantics
AI planners
Rule systems
(and prob. versions)
State Machines
(and prob. versions)
Plan-Inferential
Cue-based
9/21/2024
CPSC503 Winter 2016
36
Cue-Based: Key Idea
Words and collocations:
•
Please
and
would you
-> REQUEST
•
are you
and
is it
-> YES-NO-QUESTIONs
Conversational structure:
•
Yeah
following PROPOSAL -> AGREEMENT
•
Yeah
following INFORM -> BACKCHANNEL
Prosody:
Loudness or stress
yeah
->
AGREEMENT vs. BACKCHANNEL
9/21/2024
CPSC503 Winter 2016
37
Cue-Based model (1)
Each dialog act type (d) has its own
micro-grammar
which can be captured by N-gram models
Lexical:
given an utterance
W= w
1
…
w
n
for each
dialog act (d) we can compute
P(W|d)
Prosodic:
given an utterance
F= f
1
…
f
n
for each
dialog act (d) we can compute
P(F|d)
Annotated
Corpus
9/21/2024
CPSC503 Winter 2016
38
Cue-Based model (2)
Conversational structure: Markov chain
Annotated
Corpus
.8
.3
.7
.5
1
1
.2
.3
1
.2
Combine all info sources: HMM/CRF…
N-gram models!
9/21/2024
CPSC503 Winter 2016
39
Cue-Based model Summary
•
Start form
annotated corpus
(each utterance
labeled with appropriate dialog act)
•
For each dialog act type (e.g., REQUEST),
build
lexical
and
phonological
N-grams
•
Build
Markov chain for dialog acts
(to express
conversational structure)
9/21/2024
CPSC503 Winter 2016
40
Next class:
Tue
March 1
•
Project proposal
(
bring your write-up
to class
; 1-2
pages single project, 3-4 pages group project)
•
Project proposal Presentation
–
Approx 4 min presentation + 1 min for questions (8
mins over all if you are in a group)
–
For content, follow instructions at course project web
page
–
Bring 1 handout
to class for me
(
copy of your slides
)
–
Please
send me your presentation by NOON
(so that I
can have all the presentations on my laptop)
Assignment 3 will be posted soon (due March 11)
9/21/2024
CPSC503 Winter 2016
41
•
We have 20 readings overall
•
So one paper each
•
Fill out Google form asap, readings will be
assigned today
•
(if time - Show Course Web Page)
Reading Presentation Assignment
9/21/2024
CPSC503 Winter 2016
42
Knowledge-Formalisms Map
(including probabilistic formalisms)
•
Logical formalisms
(First-Order Logics)
•
Thesaurus & corpus
based methods
Rule systems
(and prob. versions)
State Machines
(and prob. versions)
Morphology
Syntax
Pragmatics
Discourse and
Dialogue
Semantics
AI planners
(MDPs Markov Decision
Processes)
U
n
d
e
r
s
t
a
n
d
i
n
g
G
e
n
e
r
a
t
i
o
n
9/21/2024
CPSC503 Winter 2016
43
Next Time: Natural Language
Generation
•
Read handout on NLG
•
Lecture will be about an NLG system
that I developed and tested
9/21/2024
CPSC503 Winter 2016
44
Today 27/10
•
Brief Intro Pragmatics
•
Discourse
–
Monologue
–
Dialog
9/21/2024
CPSC503 Winter 2016
45
Discourse: Dialog
•
Most fundamental form of language use
•
First kind we learn as children
Dialog can be seen as a sequence of
communicative actions of different kinds
(
dialog acts
) - (DAMSL 1997; ~20)
9/21/2024
CPSC503 Winter 2016
46
Dialog: two key tasks
•
(1) Dialog act interpretation:
identify the user dialog act
•
(2) Dialog management: (1) &
decide
what to say and when
9/21/2024
CPSC503 Winter 2016
47
Dialog Act Interpretation
•
What dialog act a given utterance is?
E.g., I’m having problems with the homework
•
Surface form is not sufficient!
–
Statement
- prof. should make a note of this,
perhaps make homework easier next year
–
Directive
- prof. should help student with the
homework
–
Information request
- prof should give student
the solution
9/21/2024
CPSC503 Winter 2016
48
Automatic Interpretation of
Dialog Acts
Logical formalisms
(First-Order Logics)
Morphology
Syntax
Pragmatics
Discourse and
Dialogue
Semantics
AI planners
Rule systems
(and prob. versions)
State Machines
(and prob. versions)
Plan-Inferential
Cue-based
9/21/2024
CPSC503 Winter 2016
49
Cue-Based: Key Idea
Words and collocations:
•
Please
and
would you
-> REQUEST
•
are you
and
is it
-> YES-NO-QUESTIONs
Conversational structure:
•
Yeah
following PROPOSAL -> AGREEMENT
•
Yeah
following INFORM -> BACKCHANNEL
Prosody:
Loudness or stress
yeah
->
AGREEMENT vs. BACKCHANNEL
9/21/2024
CPSC503 Winter 2016
50
Cue-Based model (1)
Each dialog act type (d) has its own
micro-grammar
which can be captured by N-gram models
Lexical:
given an utterance
W= w
1
…
w
n
for each
dialog act (d) we can compute
P(W|d)
Prosodic:
given an utterance
F= f
1
…
f
n
for each
dialog act (d) we can compute
P(F|d)
Annotated
Corpus
9/21/2024
CPSC503 Winter 2016
51
Cue-Based model (2)
Conversational structure: Markov chain
Annotated
Corpus
.8
.3
.7
.5
1
1
.2
.3
1
.2
Combine all info sources: HMM
N-gram models!
9/21/2024
CPSC503 Winter 2016
52
Cue-Based model Summary
•
Start form
annotated corpus
(each utterance
labeled with appropriate dialog act)
•
For each dialog act type (e.g., REQUEST),
build
lexical
and
phonological
N-grams
•
Build
Markov chain for dialog acts
(to express
conversational structure)
9/21/2024
CPSC503 Winter 2016
53
Dialog Managers in
Conversational Agents
•
Examples:
Airline travel info system,
restaurant/movie guide, email access by
phone
•
Tasks
–
Control flow of dialogue (turn-taking)
–
What to say/ask and when
9/21/2024
CPSC503 Winter 2016
54
Dialog Managers
Logical formalisms
(First-Order Logics)
Morphology
Syntax
Pragmatics
Discourse and
Dialogue
Semantics
AI planners
(and prob. versions)
Rule systems
(and prob. versions)
State Machines
(and prob. versions)
FSA
Template-Based
BDI
MDP
9/21/2024
CPSC503 Winter 2016
55
Plan Inferential (BDI) Pros/Cons
•
Powerful:
uses rich and sound knowledge
structures -> should enable modeling of
subtle indirect uses of dialog acts
•
Dialog acts are expressed as plan operators
involving belief, desire, intentions
9/21/2024
CPSC503 Winter 2016
56
FSA Dialog Manager: system
initiative
•
xxx
9/21/2024
CPSC503 Winter 2016
57
Template-based Dialog Manager (1)
•
GOAL: to allow more complex sentences that
provide more than one info item at a time
S
: How may I help you?
U
: I want to go from Boston to Baltimore on the 8th.
Slot
Optional questions
From_Airport
“From what city are you leaving?”
To_Airport
“Where are you going?”
Dept-Time
“When do you want to leave?”
Dept-Day
……………
…………
•
Interpretation: Semantic Grammars, semi-
HMM, Hidden-Understanding-Models (HUM)
9/21/2024
CPSC503 Winter 2016
58
Template-based Dialog Manager (2)
•
More than one template: e.g., car or hotel
reservation
•
User may provide information to fill slots
in different templates
•
A set of
production rules
fill slots
depending on input and determines what
questions should be asked next
E.g.,
IF user mention
car slot
and “most” of
air
slot
are filled
THEN ask about remaining car slots.
9/21/2024
CPSC503 Winter 2016
59
Markov Decision Processes [’02]
•
Common formalism in AI to model an
agent interacting with its environment.
•
States / Actions / Rewards
•
Application to dialog:
–
States
: slot in frame currently worked on,
ASR confidence value, number of questions
about slot,..
–
Actions
: questions types, confirmation types
–
Rewards
: user feedback, task completion
rate
9/21/2024
CPSC503 Winter 2016
60
BDI Dialog Manager
Sys to understand U2 needs model of
preconditions, effects, decomposition of:
–
meeting event (precon: be “there”)
-
fly-to plan (decomp: book-flight, take-flight)
-
Take-flight plan (effect: be “there”)
S1
: How may I help you?
U1
: I want to go to Pittsburgh in April.
S2
: And, what date in April do you want to travel?
U2
: Uh hmm I have a mtg. there on the 12
th
.
REQUEST
ACKNOWLEDGE
INFORM
REQUEST
9/21/2024
CPSC503 Winter 2016
61
BDI Dialog Manager
Sys to generate S2 needs model preconditions of:
-
Book-flight action (agent knows departure date and
time)
S1
: How may I help you?
U1
: I want to go to Pittsburgh in April.
S2
: And, what date in April do you want to travel?
U2
: Uh hmm I have a mtg. there on the 12
th
.
REQUEST
ACKNOWLEDGE
INFORM
REQUEST
Integrated with logic-based planning system
•
Understanding an utterance
: plan recognition
(recognize multiple goals)
•
Generating an utterance
: plan generation
(possibly) satisfying multiple goals
9/21/2024
CPSC503 Winter 2016
62
Designing Dialog Systems:
User-Centered Design
•
Early Focus on User and Task:
e.g., interview the users
•
Build Prototypes: Wizard-of-Oz
(WOZ) studies
Iterative Design
•
Evaluation
9/21/2024
CPSC503 Winter 2016
63
Next Time: Natural Language
Generation
•
Read handout on NLG
•
Lecture will be about an NLG system
that I developed and tested
9/21/2024
CPSC503 Winter 2016
64
Finish from (Oct 14)
•
Semantic Role Labeling
9/21/2024
CPSC503 Winter 2016
65
Semantic Role Labeling: Example
–
In 1979 ,
singer Nancy Wilson
HIRED
him
to
open her nightclub act
.
–
Castro
has swallowed his doubts and HIRED
Valenzuela
as
a cook
in his small restaurant .
Employer
Employee
Task
Position
Some roles.. (FrameNet for
hiring
frame)
•
DEF. Labeling phrases in a sentence with
semantic roles with respect to a target
word
9/21/2024
CPSC503 Winter 2016
66
Supervised Semantic Role Labeling
Typically framed as a
classification problem
since
[Gildea, Jurfsky 2002]
•
Train a classifier that for each predicate:
–
determine for each synt. constituent which
semantic role
(if any) it plays with respect to
the predicate
•
Train on a corpus annotated with relevant
constituent features
These include:
predicate, phrase type, head
word and its POS, path, voice, linear position……
and many others
9/21/2024
CPSC503 Winter 2016
67
Semantic Role Labeling: Example
[issued, NP, Examiner, NNP, NP
S
VP
VBD, active, before, …..]
ARG0
predicate, phrase type, head word and its POS, path, voice, linear position……
9/21/2024
CPSC503 Winter 2016
68
Supervised Semantic Role Labeling
(basic) Algorithm
1.
Assign
parse tree
to input
2.
Find all predicate-bearing words (PropBank,
FrameNet)
3.
For each predicate.: apply classifier to
each synt. constituent
Unsupervised Semantic Role Labeling:
bootstrapping [Swier, Stevenson ‘04]
9/21/2024
CPSC503 Winter 2016
69
Semantic Role Labeling
(state of the art systems)
A
S
S
E
R
T
A
u
t
o
m
a
t
i
c
S
t
a
t
i
s
t
i
c
a
l
S
E
m
a
n
t
i
c
R
o
l
e
T
a
g
g
e
r
T
o
w
a
r
d
s
r
e
f
e
r
e
n
c
e
:
R
o
b
u
s
t
S
e
m
a
n
t
i
c
R
o
l
e
L
a
b
e
l
i
n
g
S
a
m
e
e
r
P
r
a
d
h
a
n
,
W
a
y
n
e
W
a
r
d
a
n
d
J
a
m
e
s
H
.
M
a
r
t
i
n
C
o
m
p
u
t
a
t
i
o
n
a
l
L
i
n
g
u
i
s
t
i
c
s
S
p
e
c
i
a
l
I
s
s
u
e
o
n
S
e
m
a
n
t
i
c
R
o
l
e
L
a
b
e
l
i
n
g
,
V
o
l
.
3
4
,
N
o
.
2
,
p
p
.
2
8
9
-
3
1
0
,
2
0
0
8
.
I
l
l
i
n
o
i
s
S
e
m
a
n
t
i
c
R
o
l
e
L
a
b
e
l
e
r
(
S
R
L
)
(
M
a
c
h
i
n
e
L
e
a
r
n
i
n
g
a
n
d
I
n
t
e
g
e
r
L
i
n
e
a
r
P
r
o
r
g
a
m
m
i
n
g
)
Explore the world of computational linguistics through topics like pragmatics, formalisms, knowledge representation, state machines, neural models, semantics, and discourse analysis. Dive into the intricacies of language structures, meanings, and contextual inferences to unravel the complexities of human communication.
Uploaded on Sep 21, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CPSC 503 Computational Linguistics Intro to Pragmatics Lecture 13 Giuseppe Carenini 9/21/2024 CPSC503 Winter 2016 1
Knowledge-Formalisms Map (including probabilistic formalisms) U n d e r s t a n d i n g G e n e r a t i o n State Machines (prob. versions) Neural Models Morphology Syntax Rule systems (and prob. versions) Semantics (First-Order Logics) Thesaurus & corpus based methods & Neural models Logical formalisms Pragmatics Discourse: Monolog and Dialogue AI planners (HTN, MDPs+RL) 9/21/2024 CPSC503 Winter 2016 2
Today Feb 25 Brief Intro Pragmatics Discourse Monologue Dialog 9/21/2024 CPSC503 Winter 2016 3
Semantic Analysis Sentence Meanings of grammatical structures Syntax-driven and Lexical Semantic Analysis Meanings of words Literal Meaning I N F E R E N C E Common-Sense Domain knowledge Further Analysis Discourse Structure Context Intended meaning Pragmatics 9/21/2024 CPSC503 Winter 2016 4
Semantic Analysis I am going to SFU on Tue The garbage truck just left Sentence Meanings of grammatical structures Syntax-driven Semantic Analysis Meanings of words Literal Meaning I N F E R E N C E Common-Sense Domain knowledge Further Analysis Discourse Structure Context Intended meaning 9/21/2024 Shall we meet on Tue? What time is it? CPSC503 Winter 2016 5
Pragmatics: Example (i) A: So can you please come over here again right now (ii) B: Well, I have to go to Edinburgh today sir (iii) A: Hmm. How about this Thursday? What information can we infer about the context in which this (short and insignificant) exchange occurred ? 9/21/2024 CPSC503 Winter 2016 6
Pragmatics: Conversational Structure (i) A: So can you please come over here again right now (ii) B: Well, I have to go to Edinburgh today sir (iii) A: Hmm. How about this Thursday? Not the end of a conversation (nor the beginning) Pragmatic knowledge: Strong expectations about the structure of conversations Pairs e.g., request <-> response Closing/Opening forms 9/21/2024 CPSC503 Winter 2016 7
Pragmatics: Dialog Acts (i) A: So can you please come over here again right now? (ii) B: Well, I have to go to Edinburgh today sir (iii) A: Hmm. How about this Thursday? A is requesting B to come at time of speaking, B implies he can t (or would rather not) A repeats the request for some other time. Pragmatic assumptions relying on: mutual knowledge (B knows that A knows that ) co-operation (must be a response triggers inference) topical coherence (who should do what on Thur?) 9/21/2024 CPSC503 Winter 2016 8
Pragmatics: Specific Act (Request) (i) A: So can you please come over here again right now (ii) B: Well, I have to go to Edinburgh today sir (iii) A: Hmm. How about this Thursday? A wants B to come over A believes it is possible for B to come over A believes B is not already there A believes he is not in a position to order B to Pragmatic knowledge: speaker beliefs and intentions underlying the act of requesting Assumption: A behaving rationally and sincerely 9/21/2024 CPSC503 Winter 2016 9
Pragmatics: Deixis (i) A: So can you please come over here again right now (ii) B: Well, I have to go to Edinburgh today sir (iii) A: Hmm. How about this Thursday? A assumes B knows where A is Neither A nor B are in Edinburgh The day in which the exchange is taking place is not Thur., nor Wed. (or at least, so A believes) Pragmatic knowledge: References to space and time wrt space and time of speaking 9/21/2024 CPSC503 Winter 2016 10
Today Feb 25 Brief Intro Pragmatics Discourse Monologue Dialog 9/21/2024 CPSC503 Winter 2016 11
Discourse: Monologue Monologues as sequences of sentences have structure Tasks: Rhetorical (discourse) parsing and generation (like sentences as sequences of words) Key discourse phenomenon: referring expressions (what they denote may depend on previous discourse) Task: Coreference resolution 9/21/2024 CPSC503 Winter 2016 12
Sample Monologues: Coherence House-A is an interesting house. It has a convenient location. Even though house-A is somewhat far from the park, it is close to work and to a rapid transportation stop. It has a convenient location. It is close to work. Even though house-A is somewhat far from the park, house- A is an interesting house. It is close to a rapid transportation stop. 9/21/2024 CPSC503 Winter 2016 15
Corresponding Text Structure CORE EVIDENCE House-A interesting house. is an CORE-1 CONCESSION-1 EVIDENCE-1 It location. has a convenient it is close to a rapid transportation stop it is close to work Even somewhat far from the park though house-A is 9/21/2024 CPSC503 Winter 2016 ordering 16 decomposition rhetorical relations
Parsing House-A is an interesting house. It has a convenient location. Even though house-A is somewhat far from the park, it is close to work and to a rapid CORE EVIDENCE House-A interesting house. transportation stop. is an CORE-1 CONCESSION-1 EVIDENCE-1 It location. has a convenient it is close to a rapid transportation stop it is close to work Even somewhat far from the park though house-A is 9/21/2024 CPSC503 Winter 2016 ordering 18 decomposition rhetorical relations
Generation GOAL: Convince hearer that she/he should look at House-A House-A is an interesting house. It has a convenient location. Even though house-A is somewhat far from the park, it is close to work and to a rapid CORE EVIDENCE House-A interesting house. transportation stop. is an CORE-1 CONCESSION-1 EVIDENCE-1 It location. has a convenient it is close to a rapid transportation stop it is close to work Even somewhat far from the park though house-A is 9/21/2024 CPSC503 Winter 2016 ordering 19 decomposition rhetorical relations
Text Relations, Parsing and Generation Rhetorical (coherence) Relations: different proposals (typically 20-30 rels) Elaboration, Contrast, Purpose Parsing: Given a monologue, determine its rhetorical structure (semi-sup. [Marcu, 00 and 02]) (sup. [Duverle & Prendinger 09]) . Our own work [CL,2015] Generation: Given a communicative goale.g., [convince user to quit smoking] content, text [Reiter et al. AIJ 03]. Generation of textual summaries from neonatal intensive care data [Portet et al. AIJ 09]. [convince user to quit smoking]generate structure, 9/21/2024 CPSC503 Winter 2016 20
Reference Language contains many references to entities mentioned in previous sentences (i.e., in the discourse context/model) I saw him I passed the course I d like the red one I disagree with what you just said That caused the invasion Two tasks Anaphora/pronominal resolution 9/21/2024 Co-reference resolution CPSC503 Winter 2016 21
Reference Resolution Terminology Referring expression: NL expression used to perform reference Referent: entity that is referred Types of referring expressions: Indefinite NP (a, some, ) Definite NP (the, ) Pronouns (he, she, her,...) Demonstratives (this, that,..) Names Inferrables Generics (see next) 9/21/2024 CPSC503 Winter 2016 22
Cont Referring Expressions Inferrables I almost bought a new car today, but <a door> had a dent and <the engine> was too noisy Generics I saw no less than 6 Ferraris today. <They> are the coolest cars. 9/21/2024 CPSC503 Winter 2016 23
Pronominal Resolution: Simplest Algorithm Last object mentioned (correct gender/person) John ate an apple. He was hungry. He refers to John ( apple is not a he ) Google is unstoppable. They have increased.. Selectional restrictions John ate an apple in the store. It was delicious. [stores cannot be delicious] It was quiet. [apples cannot be quiet] Binding Theory constraints Mary bought herself a new Ferrari Mary bought her a new Ferrari 9/21/2024 CPSC503 Winter 2016 24
Additional Complications Some pronouns don t refer to anything It rained must check if verb has a dummy subject Evaluate last object mentioned using parse tree, not literal text position I went to the GAP, which is opposite to BR, It is a big store. [GAP, not BP] 9/21/2024 CPSC503 Winter 2016 25
Focus John is a good student He goes to all his tutorials He helped Sam with CS4001 He wants to do a project for Prof. Gray He refers to John (not Sam) 9/21/2024 CPSC503 Winter 2016 26
Supervised Pronominal Resolution Corpus annotated with co-reference relations (all antecedents of each pronoun are marked) What features ? (U1) John saw a nice Ferrari in the parking lot (U2) He showed it to Bob (U3) Hebought it 9/21/2024 CPSC503 Winter 2016 27
Need World Knowledge The police prohibited the fascists from demonstrating because they feared violence. vs The police prohibited the fascists from demonstrating because they advocated violence. Exactly the same syntax! Not possible to resolve they without detailed representation of world knowledge about feared violence vs. advocated violence 9/21/2024 CPSC503 Winter 2016 28
Coreference resolution Decide whether any pair of NPs co-refer Binary classifier again anaphor NPj antecedents What features? Same as for anaphora + specific ones to deal with definite and names. E.g., Edit distance Alias (based on type e.g., for PERSON: Dr. or Chairman can be removed) Appositive ( Mary, the new CEO, . 9/21/2024 CPSC503 Winter 2016 29
Coreference Resolution: State the art Neural Coreference Resolution Kevin Clark CS Stanford University - Report 9/21/2024 CPSC503 Winter 2016 30
Today Feb 25 Brief Intro Pragmatics Discourse Monologue Dialog 9/21/2024 CPSC503 Winter 2016 31
Discourse: Dialog Most fundamental form of language use First kind we learn as children Dialog can be seen as a sequence of communicative actions of different kinds (dialog acts) - (DAMSL 1997; ~20) Example: (i) A: So can you please come over here again right now (ii) B: Well, I have to go to Edinburgh today sir (iii) A: Hmm. How about this Thursday (vi) B: OK ACTION-DIRECTIVE REJECT-PART ACTION- DIRECTIVE ACCEPT 9/21/2024 CPSC503 Winter 2016 32
Dialog: two key tasks (1) Dialog act interpretation: identify the user dialog act (2) Dialog management: (1) & decide what to say and when 9/21/2024 CPSC503 Winter 2016 33
Cue-Based: Key Idea Words and collocations: Please and would you -> REQUEST are you and is it -> YES-NO-QUESTIONs Prosody: Loudness or stress yeah -> AGREEMENT vs. BACKCHANNEL Conversational structure: Yeah following PROPOSAL -> AGREEMENT Yeah following INFORM -> BACKCHANNEL 9/21/2024 CPSC503 Winter 2016 36
Cue-Based model (1) Each dialog act type (d) has its own micro-grammar which can be captured by N-gram models Split Corpus for d1 Corpus for dm N-gram models1 Annotated Corpus N-gram modelsm Lexical: given an utterance W= w1 wn for each dialog act (d) we can compute P(W|d) Prosodic: given an utterance F= f1 fn for each 9/21/2024 dialog act (d) we can compute P(F|d) CPSC503 Winter 2016 37
Cue-Based model (2) Conversational structure: Markov chain Annotated Corpus 1 1 d1 d3 1 .3 .8 d5 d2 .2 .2 .3 d4 .5 .7 Fi , Wi Combine all info sources: HMM/CRF ( | ) P i d d 1 i di-1 di d = ( P , | d ) P = W F d i W i i ( , | ) P W F i i i ( | ) ( | ) P F d i i i i Fi , Wi Fi , Wi N-gram models! 9/21/2024 CPSC503 Winter 2016 38
Cue-Based model Summary Start form annotated corpus (each utterance labeled with appropriate dialog act) For each dialog act type (e.g., REQUEST), build lexical and phonological N-grams Build Markov chain for dialog acts (to express conversational structure) Combine Markov Chain and N-grams into single model Now ( max arg D P D Sequences of sequences | , ) W F 9/21/2024 ..can be computed with CPSC503 Winter 2016 39
Assignment 3 will be posted soon (due March 11) Next class: Tue March 1 Project proposal (bring your write-up to class; 1-2 pages single project, 3-4 pages group project) Project proposal Presentation Approx 4 min presentation + 1 min for questions (8 mins over all if you are in a group) For content, follow instructions at course project web page Bring 1 handout to class for me (copy of your slides) Please send me your presentation by NOON (so that I can have all the presentations on my laptop) 9/21/2024 CPSC503 Winter 2016 40
Reading Presentation Assignment We have 20 readings overall So one paper each Fill out Google form asap, readings will be assigned today (if time - Show Course Web Page) 9/21/2024 CPSC503 Winter 2016 41
Knowledge-Formalisms Map (including probabilistic formalisms) U n d e r s t a n d i n g G e n e r a t i o n State Machines (and prob. versions) Morphology Syntax Rule systems (and prob. versions) Semantics (First-Order Logics) Thesaurus & corpus based methods Logical formalisms Pragmatics Discourse and Dialogue AI planners (MDPs Markov Decision Processes) 9/21/2024 CPSC503 Winter 2016 42
Next Time: Natural Language Generation Read handout on NLG Lecture will be about an NLG system that I developed and tested 9/21/2024 CPSC503 Winter 2016 43
Today 27/10 Brief Intro Pragmatics Discourse Monologue Dialog 9/21/2024 CPSC503 Winter 2016 44
Discourse: Dialog Most fundamental form of language use First kind we learn as children Dialog can be seen as a sequence of communicative actions of different kinds (dialog acts) - (DAMSL 1997; ~20) Example: (i) A: So can you please come over here again right now (ii) B: Well, I have to go to Edinburgh today sir (iii) A: Hmm. How about this Thursday (vi) B: OK ACTION-DIRECTIVE REJECT-PART ACTION- DIRECTIVE ACCEPT 9/21/2024 CPSC503 Winter 2016 45
Dialog: two key tasks (1) Dialog act interpretation: identify the user dialog act (2) Dialog management: (1) & decide what to say and when 9/21/2024 CPSC503 Winter 2016 46
Dialog Act Interpretation What dialog act a given utterance is? Surface form is not sufficient! E.g., I m having problems with the homework Statement - prof. should make a note of this, perhaps make homework easier next year Directive - prof. should help student with the homework Information request - prof should give student the solution 9/21/2024 CPSC503 Winter 2016 47
Automatic Interpretation of Dialog Acts State Machines (and prob. versions) Morphology Cue-based Syntax Rule systems (and prob. versions) Semantics Pragmatics Discourse and Dialogue Logical formalisms (First-Order Logics) Plan-Inferential AI planners 9/21/2024 CPSC503 Winter 2016 48
Cue-Based: Key Idea Words and collocations: Please and would you -> REQUEST are you and is it -> YES-NO-QUESTIONs Prosody: Loudness or stress yeah -> AGREEMENT vs. BACKCHANNEL Conversational structure: Yeah following PROPOSAL -> AGREEMENT Yeah following INFORM -> BACKCHANNEL 9/21/2024 CPSC503 Winter 2016 49
Cue-Based model (1) Each dialog act type (d) has its own micro-grammar which can be captured by N-gram models Split Corpus for d1 Corpus for dm N-gram models1 Annotated Corpus N-gram modelsm Lexical: given an utterance W= w1 wn for each dialog act (d) we can compute P(W|d) Prosodic: given an utterance F= f1 fn for each 9/21/2024 dialog act (d) we can compute P(F|d) CPSC503 Winter 2016 50
Cue-Based model (2) Conversational structure: Markov chain Annotated Corpus 1 1 d1 d3 1 .3 .8 d5 d2 .2 .2 .3 d4 .5 .7 Fi , Wi Combine all info sources: HMM ( | ) P i d d 1 i di-1 di d = ( P , | d ) P = W F d i W i i ( , | ) P W F i i i ( | ) ( | ) P F d i i i i Fi , Wi Fi , Wi N-gram models! 9/21/2024 CPSC503 Winter 2016 51
Cue-Based model Summary Start form annotated corpus (each utterance labeled with appropriate dialog act) For each dialog act type (e.g., REQUEST), build lexical and phonological N-grams Build Markov chain for dialog acts (to express conversational structure) Combine Markov Chain and N-grams into an HMM Sequences of sequences Now arg max D ( | , ) P D W F 9/21/2024 ..can be computed with CPSC503 Winter 2016 52
Dialog Managers in Conversational Agents Examples: Airline travel info system, restaurant/movie guide, email access by phone Tasks Control flow of dialogue (turn-taking) What to say/ask and when 9/21/2024 CPSC503 Winter 2016 53
Dialog Managers State Machines (and prob. versions) Morphology FSA Syntax Rule systems (and prob. versions) Semantics Template-Based Pragmatics Discourse and Dialogue Logical formalisms (First-Order Logics) BDI MDP AI planners (and prob. versions) 9/21/2024 CPSC503 Winter 2016 54
Plan Inferential (BDI) Pros/Cons Dialog acts are expressed as plan operators involving belief, desire, intentions Powerful: uses rich and sound knowledge structures -> should enable modeling of subtle indirect uses of dialog acts Time-consuming: To develop To execute Ties discourse processing with non- linguistic reasoning -> AI complete 9/21/2024 CPSC503 Winter 2016 55
