Transcript Interpretation as Abduction

Interpretation as
Abduction
Maurizio Atzori
[email protected]
Interpretation as Abduction (1993)
Jerry R. Hobbs, Mark Stickel,
Douglas Appelt, and Paul Martin
1
Summary
Abduction in NLP
 The TACITUS Project


The Abductive Commonsense Inference
Text Understanding System
Weighted Abduction
 Some Local Pragmatics

2
What is abduction?

Deduction
A, A  B
B

Induction
A(a1), A(a2),..., B(a1), B(a2), B(a3),...
" x . A(x)  B(x)

Abduction is inference to the best
explanation
B, A  B
A
3
Logic as the Language of Thought

The six keys of Cognitive processes



Conjunction of concepts (P  Q)
Modus Ponens
Recognition of Obvious Contradictions




Predicate-Argument Relations
We can relate different concept together
Universal Instantiation
In other words: First-order logic!

With no double negations or contrapositives
4
Nonmonotonic Logic as the
Reasoning of Thought
Monotonic logic:
 Nonmonotonic:


KB╞ A  KBX ╞ A
KB╞ A  KBX ╞ A
E.g.: negation as failure

KB




bird(x)  abnormal_bird(x) fly(x)
pinguin(x)  abnormal_bird(x)
bird(a)
fly(a) ? true
KB = KB  {pinguin(a)}
fly(a) ? false
5
Discourse Understanding

People understand discourse because they
know so much



How is knowledge used in the interpretation of
discourse?
We need to build a KB of commonsense and
domain knowledge
Local pragmatics




Reference resolution
Interpretation of compound nominals
Syntactic/lexical ambiguity
Metonymy resolution
6
Sentence Interpretation

Prove the logical form of the sentence
Together with the constraints that
predicates impose on their arguments
 Allowing for coercions

Merging redundancies where possible
 Making assumptions where necessary

7
Concrete Example
A cargo train running from Lima to Lorohia was derailed before
dawn today after hitting a dynamite charge.
Inspector Eulogio Flores died in the explosion.
The police reported that the incident took place past midnight in
the Carahuaichi-Jaurin area.





Incident: Location
Incident: Type
Physical Target: Description
Physical Target: Effect
Human Target: Name
Peru: Carahuaichi-Jaurin (area)
Bombing
“cargo train”
Some damage: “cargo train”
“Eulogio Flores”
8
Concrete Example: Inferences
Hitting a dynamite charge = booming
 The target = train that hit the charge
 The human target = in the explosion
 Incident = hitting of the dynamite
charge


In order to get the location
9
TACITUS

Syntactic analysis / Semantic translation
component (DIALOGIC)

Obtained mergin a large grammar of English with
a semantic translator for all the rules (DIAGRAM
Project, Linguistic String Project)


Pragmatic component


Produce a logical form of the sentence (no KB)
Produces an elaborated logical form: inferences,
assumptions, coreferences are explicited (KB)
Task component

Outputs the desired answer (e.g. diagnosis or
database entries)
10
Most- or least-specific abduction?

In many AI application, “most-specific
abduction” is used


E.g.:
In NLP application:

Sometimes “least-specific abduction” is better


E.g. “fluid”: we don’t want to abduce “lube oil”
Sometimes “most-specific” is better

E.g. “alarm sounded. Flow obstructed” and “the
alarm is for the lube oil pressure”: we want to
abduce that the flow is of “lube oil”
11
Weighted Abduction: desiderata

A new abduction scheme (3 features)
1.
2.
3.
Goals should be assumable
Assumption at various levels of specificity
Redundacy of text should be taken into
account (yielding more economic proofs)
12
Weighted Abduction: solution
1.
Every conjunct in the logical form of the
sentence is given an assumability cost
2.
If cost(Q)=c then cost(P1) is w1c
If ($...,x,y,...) ...,q(x)20,q(y)10,...
3.
Then ($...,x,...) ...,q(x)10,...
leading to minimality through redundancies

Eg.
13
Weighted Abduction: examples

How much does it cost to prove Q?

C, or 0.6 if we already know P1 or P2
Cost(Q1)=$10
Cost(Q2)=$10

Q1? Least-specific: $10

Q1  Q2? Most-specific! $18 instead of $20!
14
Weighted Abduction: “et cetera”
 (" x)

It is abductively unuseful


 (" x)

lube-oil(x)  fluid(x)
“Flow obstructed. Metal particles in lube oil filter”
($ x) lube-oil(x) but we cannot infer fluid(x) 
fluid(x)  lube-oil(x)
It “works” but we haven’t such an axiom

 (" x)
It is false!
fluid(x)  etc1(x)  lube-oil(x)

etc(x) is something like “abnormal” (special) fluid

It can only be assumed, never proved
15
Local Pragmatics Phenomena

Definite Reference
I bought a new car last week. The car is already giving me trouble.
I bought a new car last week. The vehicle is already giving me trouble.
I bought a new car last week. The engine is already giving me trouble.
The engine of my new car is already giving me trouble.

KB


(" x) car(x)  vehicle(x)
(" x) car(x)  ($ x) vehicle(x)
16
Lexical Ambiguity
John wanted a loan. He went to the bank.
 KB
bank1(x)  bank(x)
“banca”
 bank2(x)  bank(x)
“riva”
 loan(y)  financial-institution(x)  issue(x,y)
 financial-institution(x)  etc1(x)  bank1(x)


river(z)  bank2(x)  borders(x,z)
17
Lexical Ambiguity: Abduction
...  bank(x)  ...
bank1(x)  bank(x)
financial-institution(x)  etc1(x)  bank1(x)
loan(y)  financial-institution(x)  issue(x,y)
loan(L)
18
Compound Nominals
Turpentine jar.


($ x, y) turpentine(y)  jar(x)  nn(y, x)
KB
(" y) liquid(y)  etc1(y)  turpentine(y)
 (" e1, x, y) function(e1, x)  contain’(e1, x, y)
 liquid(y)  etc2 (e1, x, y)  jar(x)



If the function of something is to contain liquid, then it may
be a jar
(" e1, x, y) contain’(e1, x, y)  nn(y, x)
19
Compound Nominals: Abduction
turpentine(y)  nn(y, x)  jar(x)
liquid(y)  etc1(y)  turpentine(y)
contain’(e1, x, y)  nn(y, x)
liquid(y)  function(e1, x)  contain’(e1, x, y)  etc2 (e1, x, y)  jar(x)
20
Other Local Pragmatics

Exploiting Redundancy


Coreference Problems
Distinguishing the Given and the New
21
Integration with other approaches
Interpretation as abduction
 Parsing as deduction


It becomes possible to integrate syntax,
semantics and pragmatics in a very
thorough and elegant way.
22
Applications

Text understanding

TACITUS Project at SRI




Equipment failure reports
Naval operations reports
Terrorist reports
Question Answering!

FALCON’s postprocessor makes use of this
abductive framework

Select the right answer among some candidate
documents
23
References (1/3)
Hobbs, Jerry R., 2001. Abduction in Natural Language
Understanding, to appear in L. Horn and G. Ward (eds.),
Handbook of Pragmatics, Blackwell
 Thomason, Richmond H., and Jerry R. Hobbs, 1997.
Interrelating Interpretation and Generation in an Abductive
Framework, Proceedings, AAAI Fall Symposium

Workshop on Communicative Action in Humans and
Machines, Cambridge, Massachusetts, November 1997,
pp. 97-105
 Hobbs, Jerry R., 1992. Metaphor and Abduction, in A.
Ortony, J. Slack, and O. Stock, eds., Communication from
an Artificial Intelligence Perspective: Theoretical and
Applied Issues, Springer-Verlag, Berlin, pp. 35-58. Also
published as SRI Technical Note 508, SRI International,
Menlo Park, California. August 1991
24
References (2/3)
Hobbs, Jerry R., Douglas E. Appelt, John Bear, Mabry
Tyson, and David Magerman, 1991. The TACITUS
System: The MUC-3 Experience, SRI Technical Note 511,
SRI International, Menlo Park, California. November 1991
 Stickel, M.E., 1991. A Prolog-like inference system for
computing minimum-cost abductive explanations in
natural-language interpretation. Annals of Mathematics
and Artificial Intelligence 4 (1991), 89-106
 Hobbs, Jerry R., and Megumi Kameyama, 1990.
Translation by Abduction, in H. Karlgren, ed.,
Proceedings, Thirteenth International Conference on
Computational Linguistics, Helsinki, Finland, Vol. 3, pp.
155-161, August, 1990

25
References (3/3)
Tyson, Mabry, and Jerry R. Hobbs, 1990. DomainIndependent Task Specification in the TACITUS Natural
Language System, Technical Note 488, Artificial
Intelligence Center, SRI International, May 1990
 Hobbs, Jerry R., 1990. An Integrated Abductive
Framework for Discourse Interpretation, Proceedings,
AAAI Spring Symposium on Abduction, Stanford,
California, March 1990
 Hobbs, Jerry R., 1989. The Use of Abduction in Natural
Language Processing, Proceedings, Nagoya International

Symposium on Knowledge Information and Intelligent
Communication, Nagoya, Japan, November 1989

Hobbs, Jerry R., and Paul Martin 1987. Local Pragmatics.
Proceedings, International Joint Conference on Artificial 26
Intelligence, pp. 520-523. Milano, Italy, August 1987.