Ab

duction

in

Natural

Language

Understanding

Jerry

R.

Hobbs

Articial

In

telligence

Cen

ter

SRI

In

ternational

1

Language

and

Kno

wledge

W

e

are

able

to

understand

language

so

w

ell

b

ecause

w

e

kno

w

so

m

uc

h.

When

w

e

read

the

sen

tence

(1)

John

dro

v

e

do

wn

the

street

in

a

car.

w

e

kno

w

immediately

that

the

driving

and

hence

John

are

in

the

car

and

that

the

street

isn't.

W

e

attac

h

the

prep

ositional

phrase

to

the

v

erb

\dro

v

e"

rather

than

to

the

noun

\street".

This

is

not

syn

tactic

kno

wledge,

b

ecause

in

the

syn

tactically

similar

sen

tence

(2)

John

dro

v

e

do

wn

a

street

in

Chicago.

it

is

the

street

that

is

in

Chicago.

Therefore,

a

large

part

of

the

study

of

language

should

b

e

an

in

v

estigation

of

the

question

of

ho

w

w

e

use

our

kno

wledge

of

the

w

orld

to

understand

discourse.

This

question

has

b

een

examined

primarily

b

y

researc

hers

in

the

eld

of

articial

in

telligence

(AI),

in

part

b

ecause

they

ha

v

e

b

een

in

terested

in

linking

language

with

actual

b

eha

vior

in

sp

ecic

situations,

whic

h

has

led

them

to

an

attempt

to

represen

t

and

reason

ab

out

fairly

complex

w

orld

kno

wledge.

In

this

c

hapter

I

describ

e

ho

w

a

particular

kind

of

reasoning,

called

abduction,

pro-

vides

a

framew

ork

for

addressing

a

broad

range

of

problems

that

are

p

osed

in

discourse

and

that

require

w

orld

kno

wledge

in

their

solutions.

I

rst

defend

rst-order

logic

as

a

mo

de

of

represen

tation

for

the

information

con

v

ey

ed

b

y

sen

tences

and

the

kno

wledge

w

e

bring

to

the

discourses

w

e

in

terpret,

but

with

one

ca

v

eat:

Reasoning

m

ust

b

e

defeasible.

I

discuss

sev

eral

w

a

ys

that

defeasible

inference

has

b

een

formalized

in

AI,

and

in

tro

duce

ab

duction

as

one

of

those

metho

ds.

Then

in

successiv

e

sections

I

sho

w

ho

w

v

arious

problems

in

local

pra

gma

tics,

suc

h

as

reference

resolution,

meton

ym

y

,

in

terpreting

comp

ound

nominals,

and

w

ord

sense

disam

biguation

can

b

e

solv

ed

via

ab

duction;

ho

w

this

pro

cessing

can

b

e

em

b

edded

in

an

ab

ductiv

e

pro

cess

for

recognizing

the

syn

tactic

structure

of

sen

tences;

ho

w

this

in

turn

can

b

e

em

b

edded

in

a

pro

cess

for

recognizing

the

structure

of

discourse;

and

1

ho

w

these

can

all

b

e

in

tegrated

with

the

recognition

of

the

sp

eak

er's

plan.

I

close

with

a

discussion

of

some

of

the

principal

outstanding

researc

h

issues.

2

Logic

as

the

Language

of

Though

t

A

v

ery

large

b

o

dy

of

w

ork

in

AI

b

egins

with

the

assumptions

that

information

and

kno

wl-

edge

should

b

e

represen

ted

in

rst-order

logic

and

that

reasoning

is

theorem-pro

ving.

On

the

face

of

it,

this

seems

implausible

as

a

mo

del

for

p

eople.

It

certainly

do

esn't

seem

as

if

w

e

are

using

logic

when

w

e

are

thinking,

and

if

w

e

are,

wh

y

are

so

man

y

of

our

though

ts

and

actions

so

illogical?

In

fact,

there

are

psyc

hological

exp

erimen

ts

that

purp

ort

to

sho

w

that

p

eople

do

not

use

logic

in

thinking

ab

out

a

problem

(e.g.,

W

ason

and

Johnson-Laird

1972).

I

b

eliev

e

that

the

claim

that

logic

is

the

language

of

though

t

comes

to

less

than

one

migh

t

think,

ho

w

ev

er,

and

that

th

us

it

is

more

con

tro

v

ersial

than

it

ough

t

to

b

e.

It

is

the

claim

that

a

broad

range

of

cognitiv

e

pro

cesses

are

amenable

to

a

high-lev

el

description

in

whic

h

six

k

ey

features

are

presen

t.

The

rst

three

of

these

features

c

haracterize

prop

osi-

tional

logic

and

the

next

t

w

o

rst-order

logic.

I

will

express

them

in

terms

of

\concepts",

but

one

can

just

as

easily

substitute

prop

ositions,

neural

elemen

ts,

or

a

n

um

b

er

of

other

terms.

Conjunction:

There

is

an

additiv

e

eect

(P

^

Q)

of

t

w

o

distinct

concepts

(P

and

Q)

b

eing

activ

ated

at

the

same

time.

Mo

dus

P

onens:

The

activ

ation

of

one

concept

(P

)

triggers

the

activ

ation

of

another

concept

(Q)

b

ecause

of

the

existence

of

some

structural

relation

b

et

w

een

them

(P

Q).

Recognition

of

Ob

vious

Con

tradictions:

The

recognition

of

con

tradictions

in

general

is

undecidable,

but

w

e

ha

v

e

no

trouble

with

the

easy

ones,

for

example,

that

cats

aren't

dogs.

Predicate-Argumen

t

Relations:

Concepts

can

b

e

related

to

other

concepts

in

sev-

eral

dieren

t

w

a

ys.

F

or

example,

w

e

can

distinguish

b

et

w

een

a

dog

biting

a

man

(bite(D

;

M

))

and

a

man

biting

a

dog

(bite(M

;

D

)).

Univ

ersal

Instan

tiation

(or

V

ariable

Binding):

W

e

can

k

eep

separate

our

kno

wl-

edge

of

general

(univ

ersal)

principles

(\All

men

are

mortal")

and

our

kno

wledge

of

their

instatiations

for

particular

individuals

(\So

crates

is

a

man"

and

\So

crates

is

mortal").

An

y

plausible

prop

osal

for

a

language

of

though

t

m

ust

ha

v

e

at

least

these

features,

and

once

y

ou

ha

v

e

these

features

y

ou

ha

v

e

rst-order

logic.

Note

that

in

this

list

there

are

no

complex

rules

for

double

negations

or

for

con

tra-

p

ositiv

es

(if

P

implies

Q

then

not

Q

implies

not

P

).

In

fact,

most

of

the

psyc

hological

exp

erimen

ts

purp

orting

to

sho

w

that

p

eople

don't

use

logic

really

sho

w

that

they

don't

2

use

the

con

trap

ositiv

e

rule

or

that

they

don't

handle

double

negations

w

ell.

If

the

tasks

in

those

exp

erimen

ts

w

ere

recast

in

to

problems

in

v

olving

the

use

of

mo

dus

p

onens,

no

one

w

ould

think

to

do

the

exp

erimen

ts

b

ecause

it

is

ob

vious

that

p

eople

w

ould

ha

v

e

no

trouble

with

the

task.

As

an

aside,

let

me

men

tion

that

man

y

researc

hers

in

linguistics

and

in

kno

wledge

represen

tation

mak

e

use

of

higher-order

logic.

It

is

straigh

tforw

ard,

through

v

arious

kinds

of

reication,

to

recast

these

logics

in

to

rst-order

logic,

and

in

view

of

the

resulting

simplication

in

c

haracterizing

the

reasoning

pro

cess,

there

are

v

ery

go

o

d

reasons

to

do

so

(Hobbs

1985a).

There

is

one

further

prop

ert

y

w

e

need

of

the

logic

if

w

e

are

to

use

it

for

represen

ting

and

reasoning

ab

out

commonsense

w

orld

kno

wledge|defeasibilit

y

or

nonmonotonicit

y

.

3

Nonmonotonic

Logic

The

logic

of

mathematics

is

monotonic,

in

that

once

w

e

kno

w

the

truth

v

alue

of

a

state-

men

t,

nothing

else

w

e

learn

can

c

hange

it.

Virtually

all

commonsense

kno

wledge

b

ey

ond

mathematics

is

uncertain

or

defeasible.

Whatev

er

general

principles

w

e

ha

v

e

are

usually

only

true

most

of

the

time

or

true

with

high

probabilit

y

or

true

unless

w

e

disco

v

er

evi-

dence

to

the

con

trary

.

It

is

almost

alw

a

ys

p

ossible

that

w

e

ma

y

ha

v

e

to

c

hange

what

w

e

b

eliev

ed

to

b

e

the

truth

v

alue

of

a

statemen

t

up

on

gaining

more

information.

Almost

all

commonsense

kno

wledge

should

b

e

tagged

with

\insofar

as

I

ha

v

e

b

een

able

to

determine

with

m

y

limited

access

to

the

facts

and

m

y

limited

resources

for

reasoning."

The

logic

of

commonsense

kno

wledge

m

ust

b

e

nonmonotonic.

The

dev

elopmen

t

of

nonmonotonic

logics

has

b

een

a

ma

jor

fo

cus

in

AI

researc

h

(Gins-

b

erg

1987).

One

early

attempt

in

v

olv

ed

\negation

as

failure"

(Hewitt

1972);

w

e

assume

that

not

P

is

true

if

w

e

fail

to

pro

v

e

that

P

.

Another

early

nonmonotonic

logic

(Mc-

Dermott

and

Do

yle

1980)

had

rules

of

the

form

\If

P

is

true

and

Q

is

consisten

t

with

ev

erything

else

w

e

kno

w,

then

tak

e

Q

to

b

e

true."

Probably

the

most

thoroughly

in

v

estigated

nonmonotonic

logic

w

as

that

dev

elop

ed

b

y

McCarth

y

(1980).

He

in

tro

duced

abnormality

conditions

whic

h

the

reasoner

then

minimized.

F

or

example,

the

general

fact

that

birds

y

is

expressed

(3)

(8

x)bir

d(x)

^

:ab

1

(x)

f

l

y

(x)

That

is,

if

x

is

a

bird

and

not

abnormal

in

a

w

a

y

sp

ecic

to

this

rule,

then

x

ies.

F

urther

axioms

migh

t

sp

ell

out

the

exceptions:

(4)

(8

x)peng

uin(x)

ab

1

(x)

That

is,

p

enguins

are

abnormal

in

the

w

a

y

sp

ecic

to

the

\birds

y"

rule.

Then

to

dra

w

conclusions

w

e

minimize,

in

some

fashion,

those

things

w

e

tak

e

to

b

e

abnormal.

If

all

w

e

kno

w

ab

out

Tw

eet

y

is

that

he

is

a

bird,

then

w

e

assume

he

is

not

abnormal,

and

th

us

w

e

conclude

he

can

y

.

If

w

e

subsequen

tly

learn

that

Tw

eet

y

is

a

p

enguin,

w

e

retract

the

assumption

that

he

is

not

abnormal

in

that

w

a

y

.

3

A

problem

arises

with

this

approac

h

when

w

e

ha

v

e

man

y

axioms

with

dieren

t

abnor-

malit

y

conditions.

There

ma

y

b

e

man

y

w

a

ys

to

minimize

the

abnormalities,

eac

h

leading

to

dieren

t

conclusions.

This

is

illustrated

b

y

an

example

that

is

kno

wn

as

the

Nix

on

dia-

mond

(Reiter

and

Criscuolo

1981).

Supp

ose

w

e

kno

w

that

generally

Quak

ers

are

pacists.

W

e

can

write

this

as

(5)

(8

x)Quak

er

(x)

^

:ab

2

(x)

pacif

ist(x)

Supp

ose

w

e

also

kno

w

that

Republicans

are

generally

not

pacists.

(6)

(8

x)R epubl

ican(x)

^

:ab

3

(x)

:pacif

ist(x)

Then

what

do

w

e

conclude

when

w

e

learn

that

Nixon

is

b

oth

a

Quak

er

and

a

Republican?

Assuming

b

oth

abnormalit

y

conditions

results

in

a

con

tradiction.

If

w

e

tak

e

ab

2

to

b

e

false,

w

e

conclude

Nixon

is

a

pacist.

If

w

e

tak

e

ab

3

to

b

e

false,

w

e

conclude

Nixon

is

not

a

pacist.

Ho

w

do

w

e

c

ho

ose

b

et

w

een

the

t

w

o

p

ossibilities?

Researc

hers

ha

v

e

made

v

arious

suggestions

for

ho

w

to

think

ab

out

this

problem

(e.g.,

Shoham

1987).

In

general,

some

sc

heme

is

needed

for

c

ho

osing

among

the

p

ossible

com

binations

of

assumptions.

In

recen

t

y

ears

there

has

b

een

considerable

in

terest

in

AI

in

the

reasoning

pro

cess

kno

wn

as

ab

duction,

or

inference

to

the

b

est

explanation.

As

it

is

normally

conceiv

ed

in

AI,

it

can

b

e

view

ed

as

one

v

ariet

y

of

nonmonotonic

logic.

4

Ab

duction

The

simplest

w

a

y

to

explain

ab

duction

is

b

y

comparing

it

with

t

w

o

w

ords

it

rh

ymes

with|deduction

and

induction.

In

deduction,

from

P

and

P

Q,

w

e

conclude

Q.

In

induction,

from

P

and

Q,

or

more

lik

ely

a

n

um

b

er

of

instances

of

P

and

Q

together

with

other

considerations,

w

e

conclude

P

Q.

Ab

duction

is

the

third

p

ossibilit

y

.

F

rom

an

observ

able

Q

and

a

general

principle

P

Q,

w

e

conclude

that

P

m

ust

b

e

the

underlying

reason

that

Q

is

true.

W

e

assume

P

b

ecause

it

explains

Q.

Of

course,

there

ma

y

b

e

man

y

suc

h

p

ossible

P

's,

some

con

tradictory

with

others,

and

therefore

an

y

metho

d

of

ab

duction

m

ust

include

a

metho

d

for

ev

aluating

and

c

ho

osing

among

alternativ

es.

A

t

a

rst

cut,

supp

ose

in

trying

to

explain

Q

w

e

kno

w

P

^

R

Q

and

w

e

kno

w

R .

Then

R

pro

vides

partial

evidence

that

Q

is

true,

making

the

assumption

of

P

more

reasonable.

In

addition,

if

w

e

are

seeking

to

explain

t

w

o

things,

Q

1

and

Q

2

,

then

it

is

reasonable

to

fa

v

or

assuming

a

P

that

explains

b

oth

of

them

rather

than

a

dieren

t

explanation

for

eac

h.

The

conclusions

w

e

dra

w

in

this

w

a

y

are

only

assumptions

and

ma

y

ha

v

e

to

b

e

retracted

later

if

w

e

acquire

new,

con

tradictory

information.

That

is,

this

metho

d

of

reasoning

is

nonmonotonic.

Ab

duction

has

a

history

.

Prior

to

the

late

sev

en

teen

th

cen

tury

science

w

as

view

ed

as

deductiv

e,

at

least

in

the

ideal.

It

w

as

felt

that,

on

the

mo

del

of

Euclidean

geometry

,

one

should

b

egin

with

prop

ositions

that

w

ere

self-eviden

t

and

deduce

whatev

er

consequences

one

could

from

them.

The

mo

dern

view

of

scien

tic

theories,

probably

b

est

expressed

b

y

Lak

atos

(1970),

is

quite

dieren

t.

One

tries

to

construct

abstract

theories

from

whic

h

4

observ

able

ev

en

ts

can

b

e

deduced

or

predicted.

There

is

no

need

for

the

abstract

theories

to

b

e

self-eviden

t,

and

they

usually

are

not.

It

is

only

necessary

for

them

to

predict

as

broad

a

range

as

p

ossible

of

the

observ

able

data

and

for

them

to

b

e

\elegan

t",

whatev

er

that

means.

Th

us,

the

mo

dern

view

is

that

science

is

fundamen

tally

ab

ductiv

e.

W

e

seek

hidden

principles

or

causes

from

whic

h

w

e

can

deduce

the

observ

able

evidence.

This

view

of

science,

and

hence

the

notion

of

ab

duction,

can

b

e

seen

rst,

insofar

as

I

am

a

w

are,

in

some

passages

in

Newton's

Principia

(1934

[1686]).

A

t

the

end

of

Principia,

in

a

justication

for

not

seeking

the

cause

of

gra

vit

y

,

he

sa

ys,

\And

to

us

it

is

enough

that

gra

vit

y

do

es

really

exist,

and

act

according

to

the

la

ws

whic

h

w

e

ha

v

e

explained,

and

abundan

tly

serv

es

to

accoun

t

for

all

the

motions

of

the

celestial

b

o

dies,

and

of

our

sea."

(Newton

1934:547)

The

justication

for

gra

vit

y

(P

)

and

its

la

ws

(P

Q)

is

not

in

their

self-eviden

tial

nature

but

in

what

they

accoun

t

for

(Q).

In

the

eigh

teen

th

cen

tury

,

the

German

philosopher

Christian

W

ol

(1963

[1728])

sho

ws,

to

m

y

kno

wledge,

the

earliest

explicit

a

w

areness

of

the

imp

ortance

of

ab

ductiv

e

reasoning.

He

presen

ts

almost

the

standard

Euclidean

accoun

t

of

certain

kno

wledge,

but

with

an

imp

ortan

t

pro

vision

in

his

recognition

of

the

inevitabilit

y

and

imp

ortance

of

h

yp

otheses:

Philosoph

y

m

ust

use

h

yp

otheses

insofar

as

they

pa

v

e

the

w

a

y

to

the

disco

v

ery

of

certain

truth.

F

or

in

a

philosophical

h

yp

othesis

certain

things

whic

h

are

not

rmly

established

are

assumed

b

ecause

they

pro

vide

a

reason

for

things

whic

h

are

observ

ed

to

o

ccur.

No

w

if

w

e

can

also

deduce

other

things

whic

h

are

not

observ

ed

to

o

ccur,

then

w

e

ha

v

e

the

opp

ortunit

y

to

either

observ

e

or

exp

erimen

tally

detect

things

whic

h

otherwise

w

e

migh

t

not

ha

v

e

noticed.

In

this

w

a

y

w

e

b

ecome

more

certain

as

to

whether

or

not

an

ything

con

trary

to

exp

erience

follo

ws

from

the

h

yp

othesis.

If

w

e

deduce

things

whic

h

are

con

trary

to

exp

erience,

then

the

h

yp

othesis

is

false.

If

the

deductions

agree

with

exp

erience,

then

the

probabilit

y

of

the

h

yp

othesis

is

increased.

And

th

us

the

w

a

y

is

pa

v

ed

for

the

disco

v

ery

of

certain

truth.

(W

ol

1963:67)

He

also

recognizes

the

principle

of

parsimon

y:

\If

one

cannot

necessarily

deduce

from

a

h

yp

othesis

the

things

for

whic

h

it

is

assumed,

then

the

h

yp

othesis

is

spurious."

(W

ol

1963:68)

Ho

w

ev

er,

he

views

h

yp

otheses

as

only

pro

visional,

a

w

aiting

deductiv

e

pro

of.

The

term

\ab

duction"

w

as

rst

used

b

y

C.

S.

Pierce

(e.g.,

1955).

His

denition

of

it

is

as

follo

ws:

(7)

The

surprising

fact,

Q,

is

observ

ed;

But

if

P

w

ere

true,

Q

w

ould

b

e

a

matter

of

course,

Hence,

there

is

reason

to

susp

ect

that

P

is

true.

(Pierce

1955:151)

(He

actually

used

A

and

C

for

P

and

Q.)

Pierce

sa

ys

that

\in

pure

ab

duction,

it

can

nev

er

b

e

justiable

to

accept

the

h

yp

othesis

otherwise

than

as

an

in

terrogation",

and

that

\the

whole

question

of

what

one

out

of

a

n

um

b

er

of

p

ossible

h

yp

otheses

ough

t

to

b

e

en

tertained

b

ecomes

purely

a

question

of

econom

y

."

That

is,

there

m

ust

b

e

an

ev

aluation

sc

heme

for

c

ho

osing

among

p

ossible

ab

ductiv

e

inferences.

The

earliest

form

ulation

of

ab

duction

in

articial

in

telligence

w

as

b

y

Morgan

(1971).

He

sho

w

ed

ho

w

a

complete

set

of

truth-preserving

rules

for

generating

theorems

could

b

e

turned

in

to

a

complete

set

of

falseho

o

d-preserving

rules

for

generating

h

yp

otheses.

5

The

rst

use

of

ab

duction

in

an

AI

application

w

as

b

y

P

ople

(1973),

in

the

con

text

of

medical

diagnosis.

He

ga

v

e

the

form

ulation

of

ab

duction

sk

etc

hed

ab

o

v

e

and

sho

w

ed

ho

w

it

can

b

e

implemen

ted

in

a

theorem-pro

ving

framew

ork.

Literals

(or

prop

ositions)

that

are

\abandoned

b

y

deduction

in

the

sense

that

they

fail

to

ha

v

e

successor

no

des"

(P

ople

1973:150)

are

tak

en

as

the

candidate

h

yp

otheses.

That

is,

one

tries

to

pro

v

e

the

symptoms

and

signs

exhibited

and

the

parts

of

a

p

oten

tial

pro

of

that

cannot

b

e

pro

v

en

are

the

candidate

h

yp

otheses.

Those

h

yp

otheses

are

b

est

that

accoun

t

for

the

most

data,

and

in

service

of

this

principle,

he

in

tro

duced

factoring

or

syn

thesis,

whic

h

attempts

to

unify

goal

literals.

Hyp

otheses

where

this

is

used

are

fa

v

ored.

That

is,

that

explanation

is

b

est

that

minimizes

the

n

um

b

er

of

causes.

W

ork

on

ab

duction

in

articial

in

telligence

w

as

reviv

ed

in

the

1980s

at

sev

eral

sites.

Reggia

and

his

colleagues

(e.g.,

Reggia

et

al.,

1983;

Reggia

1985)

form

ulated

ab

ductiv

e

inference

in

terms

of

parsimonious

co

v

ering

theory

.

Charniak

and

McDermott

(1985)

pre-

sen

ted

the

basic

pattern

of

ab

duction

and

then

discussed

man

y

of

the

issues

in

v

olv

ed

in

trying

to

decide

among

alternativ

e

h

yp

otheses

on

probabilistic

grounds.

Co

x

and

Pietrzyk

o

wski

(1986)

presen

t

a

form

ulation

in

a

theorem-pro

ving

framew

ork

that

is

v

ery

similar

to

P

ople's,

though

apparen

tly

indep

enden

t.

It

is

esp

ecially

v

aluable

in

that

it

con-

siders

ab

duction

abstractly

,

as

a

mec

hanism

with

a

v

ariet

y

of

p

ossible

applications,

and

not

just

as

a

handmaiden

to

diagnosis.

Josephson

and

Josephson

(1994)

pro

vide

a

comprehensiv

e

treatmen

t

of

ab

duction,

its

philosophical

bac

kground,

its

computational

prop

erties,

and

its

utilization

in

AI

applica-

tions.

I

ha

v

e

indicated

that

the

practice

of

science

is

fundamen

tally

ab

ductiv

e.

The

extension

of

ab

duction

to

ordinary

cognitiv

e

tasks

is

v

ery

m

uc

h

in

line

with

the

p

opular

view

in

cognitiv

e

science

that

p

eople

going

ab

out

in

the

w

orld

trying

to

understand

it

are

scien

tists

in

the

small.

This

view

can

b

e

extended

to

natural

language

understanding|in

terpreting

discourse

is

coming

up

with

the

b

est

explanation

for

what

is

said.

The

rst

app

eal

to

something

lik

e

ab

duction

that

I

am

a

w

are

of

in

natural

language

understanding

w

as

b

y

Grice

(1967,

1989),

when

he

in

tro

duced

the

notion

of

conversa-

tional

implica

ture

to

handle

examples

lik

e

the

follo

wing:

(8)

A:

Ho

w

is

John

doing

on

his

new

job

at

the

bank?

B:

Quite

w

ell.

He

lik

es

his

colleagues

and

he

hasn't

em

b

ezzled

an

y

money

y

et.

Grice

argues

that

in

order

to

see

this

as

coheren

t,

w

e

m

ust

assume,

or

dra

w

as

a

con

v

er-

sational

implicature,

that

b

oth

A

and

B

kno

w

that

John

is

dishonest.

Although

he

do

es

not

sa

y

so,

an

implicature

can

b

e

view

ed

as

an

ab

ductiv

e

mo

v

e

for

the

sak

e

of

ac

hieving

the

b

est

in

terpretation.

Lewis

(1979)

in

tro

duces

the

notion

of

a

ccommod

a

tion

in

con

v

ersation

to

explain

the

phenomenon

that

o

ccurs

when

y

ou

\sa

y

something

that

requires

a

missing

presupp

osi-

tion,

and

straigh

ta

w

a

y

that

presupp

osition

springs

in

to

existence,

making

what

y

ou

said

acceptable

after

all."

The

hearer

accommo

dates

the

sp

eak

er.

Thomason

(1990)

argued

that

Grice's

con

v

ersational

implicatures

are

based

on

Lewis's

rule

of

accommo

dation.

W

e

migh

t

sa

y

that

implicature

is

a

pro

cedural

c

haracterization

6

of

something

that,

at

the

functional

or

in

teractional

lev

el,

app

ears

as

accommo

dation.

Implicature

is

the

w

a

y

w

e

do

accommo

dation.

In

the

middle

1980s

researc

hers

at

sev

eral

sites

b

egan

to

apply

ab

duction

to

natural

language

understanding

(Norvig

1983,

1987;

Wilensky

1983;

Wilensky

et

al.

1988;

Char-

niak

and

Goldman

1988,

1989;

Hobbs

et

al.

1988;

Hobbs

et

al.

1993).

A

t

least

in

the

last

case

the

recognition

that

implicature

w

as

a

use

of

ab

duction

w

as

a

k

ey

observ

ation

in

the

dev

elopmen

t

of

the

framew

ork.

Norvig,

Wilensky

,

and

their

asso

ciates

prop

osed

an

op

eration

called

concretion,

one

of

man

y

that

tak

e

place

in

the

pro

cessing

of

a

text.

It

is

a

\kind

of

inference

in

whic

h

a

more

sp

ecic

in

terpretation

of

an

utterance

is

made

than

can

b

e

sustained

on

a

strictly

logical

basis"

(Wilensky

et

al.

1988:50).

Th

us,

\to

use

a

p

encil"

generally

means

to

write

with

a

p

encil,

ev

en

though

one

could

use

a

p

encil

for

man

y

other

purp

oses.

Charniak

and

his

asso

ciates

also

dev

elop

ed

an

ab

ductiv

e

approac

h

to

in

terpretation.

Charniak

(1986)

expressed

the

fundamen

tal

insigh

t:

\A

standard

platitude

is

that

under-

standing

something

is

relating

it

to

what

one

already

kno

ws.

:

:

:

One

extreme

example

w

ould

b

e

to

pro

v

e

that

what

one

is

told

m

ust

b

e

true

on

the

basis

of

what

one

already

kno

ws.

:

:

:

W

e

w

an

t

to

pro

v

e

what

one

is

told

given

c

ertain

assumptions."

(Charniak

1986:585)

Charniak

and

Goldman

dev

elop

ed

an

in

terpretation

pro

cedure

that

incremen

tally

built

a

b

elief

net

w

ork

(P

earl

1988),

where

the

links

b

et

w

een

the

no

des,

represen

ting

inuences

b

et

w

een

ev

en

ts,

w

ere

determined

from

axioms

expressing

w

orld

kno

wledge.

They

felt

that

one

could

mak

e

not

unreasonable

estimates

of

the

required

probabilities,

giving

a

principled

seman

tics

to

the

n

um

b

ers.

The

net

w

orks

w

ere

then

ev

aluated

and

am

biguities

w

ere

resolv

ed

b

y

lo

oking

for

the

highest

resultan

t

probabilities.

Stic

k

el

in

v

en

ted

a

metho

d

called

weighted

abduction

(Stic

k

el

1988;

Hobbs

et

al.

1993)

that

builds

the

ev

aluation

criteria

in

to

the

pro

of

pro

cess.

Briey

,

prop

ositions

to

b

e

pro

v

ed

are

giv

en

an

assumption

cost|what

y

ou

will

ha

v

e

to

pa

y

to

assume

them.

When

w

e

bac

k

c

hain

o

v

er

a

rule

of

the

form

P

Q,

the

cost

is

passed

bac

k

from

Q

to

P

,

according

to

a

w

eigh

t

asso

ciated

with

P

.

Generally

,

P

will

cost

more

to

assume

than

Q,

so

that

short

pro

ofs

are

fa

v

ored

o

v

er

long

ones.

But

if

partial

evidence

is

found,

for

example,

if

P

^

R

Q

and

w

e

can

pro

v

e

R ,

then

it

will

cost

less

to

assume

P

than

to

assume

Q,

and

w

e

get

a

more

sp

ecic

in

terpretation.

In

addition,

if

w

e

need

to

pro

v

e

Q

1

and

Q

2

and

P

implies

b

oth,

then

it

will

cost

less

to

assume

P

than

to

assume

Q

1

and

Q

2

.

This

feature

of

the

metho

d

allo

ws

us

to

exploit

the

implicit

redundancy

inheren

t

in

natural

language

discourse.

W

eigh

ted

ab

duction

suggests

a

simple

w

a

y

to

incorp

orate

the

uncertain

t

y

of

kno

wl-

edge

in

to

the

axioms

expressing

the

kno

wledge.

Prop

ositions

can

b

e

assumed

at

a

cost.

Therefore,

w

e

can

ha

v

e

prop

ositions

whose

only

role

is

to

b

e

assumed

and

to

levy

a

cost.

F

or

example,

let's

return

to

the

rule

that

birds

y

.

W

e

can

express

it

with

the

axiom

(9)

(8

x)[bir

d(x)

^

etc

1

(x)

f

l

y

(x)]

That

is,

if

x

is

a

bird

and

some

other

unsp

ecied

conditions

hold

for

x

(etc

1

(x)),

then

x

ies.

The

predicate

etc

1

enco

des

the

unsp

ecied

conditions.

There

will

nev

er

b

e

a

w

a

y

to

pro

v

e

it;

it

can

only

b

e

assumed

at

cost.

The

cost

of

etc

1

will

dep

end

in

v

ersely

on

the

7

certain

t

y

of

the

rule

that

birds

y

.

It

will

cost

to

use

this

rule,

but

the

lo

w

est-cost

pro

of

of

ev

erything

w

e

are

trying

to

explain

ma

y

nev

ertheless

in

v

olv

e

this

rule

and

hence

the

inference

that

birds

y

.

W

e

kno

w

that

p

enguins

don't

y:

(10)

(8

x)[peng

uin(x)

:f

l

y

(x)]

If

w

e

kno

w

Tw

eet

y

is

a

p

enguin,

w

e

kno

w

he

do

esn't

y

.

Th

us,

to

assume

etc

1

is

true

of

Tw

eet

y

w

ould

lead

to

a

con

tradiction,

so

w

e

don't.

The

relation

b

et

w

een

the

etc

predicates

and

the

abnormalit

y

predicates

of

McCarth

y's

nonmonotonic

logic

is

ob

vious:

etc

1

is

just

:ab

1

.

The

framew

ork

of

\In

terpretation

as

Ab

duction"

(IA)

(Hobbs

et

al.

1993)

follo

ws

di-

rectly

from

this

metho

d

of

ab

ductiv

e

inference,

and

it

is

the

IA

framew

ork

that

is

presen

ted

in

the

remainder

of

this

c

hapter.

Whereas

in

Norvig

and

Wilensky's

w

ork,

ab

duction

or

concretion

w

as

one

pro

cess

among

man

y

in

v

olv

ed

in

natural

language

understanding,

in

the

IA

framew

ork

ab

duction

is

the

whole

story

.

Whereas

in

Charniak

and

Goldman's

w

ork,

sp

ecic

pro

cedures

in

v

olving

ab

duction

are

implemen

ted

to

solv

e

sp

ecic

in

terpretation

problems,

in

the

IA

framew

ork

there

is

only

one

pro

cedure|ab

duction|that

is

used

to

explain

or

pro

v

e

the

logical

form

of

the

text,

and

the

solutions

to

sp

ecic

in

terpretation

problems

fall

out

as

b

ypro

ducts

of

this

pro

cess.

It

should

b

e

p

oin

ted

out

that

in

addition

to

what

is

presen

ted

b

elo

w

there

ha

v

e

b

een

a

n

um

b

er

of

other

researc

hers

who

ha

v

e

used

ab

duction

for

v

arious

natural

language

understanding

problems,

including

Nagao

(1989)

for

resolving

syn

tactic

am

biguit

y

,

Dasigi

(1988)

for

resolving

lexical

am

biguit

y

,

Ra

yner

(1993)

for

asking

questions

of

a

database,

Ng

and

Mo

oney

(1990)

and

Lascarides

and

Ob

erlander

(1992)

for

recognizing

discourse

structure,

McRo

y

and

Hirst

(1991)

for

making

repairs

in

presupp

osition

errors,

App

elt

and

P

ollac

k

(1990)

for

recognizing

the

sp

eak

er's

plan,

and

Harabagiu

and

Moldo

v

an

(1998)

for

general

text

understanding

using

W

ordNet

as

a

kno

wledge

base.

5

In

terpretation

as

Ab

duction

In

the

IA

framew

ork

w

e

can

describ

e

v

ery

concisely

what

it

is

to

in

terpret

a

sen

tence:

(11)

Pro

v

e

the

logical

form

of

the

sen

tence,

together

with

the

selectional

constrain

ts

that

predicates

imp

ose

on

their

argumen

ts,

allo

wing

for

co

ercions,

Merging

redundancies

where

p

ossible,

Making

assumptions

where

necessary

.

By

the

rst

line

w

e

mean

\pro

v

e,

or

deriv

e

in

the

logical

sense,

from

the

predicate

calcu-

lus

axioms

in

the

kno

wledge

base,

the

logical

form

that

has

b

een

pro

duced

b

y

syn

tactic

analysis

and

seman

tic

translation

of

the

sen

tence."

In

a

discourse

situation,

the

sp

eak

er

and

hearer

b

oth

ha

v

e

their

sets

of

priv

ate

b

eliefs,

and

there

is

a

large

o

v

erlapping

set

of

m

utual

b

eliefs.

An

utterance

liv

es

on

the

b

oundary

b

et

w

een

m

utual

b

elief

and

the

sp

eak

er's

priv

ate

b

eliefs.

It

is

a

bid

to

extend

the

area

of

8

m

utual

b

elief

to

include

some

priv

ate

b

eliefs

of

the

sp

eak

er's.

It

is

anc

hored

referen

tially

in

m

utual

b

elief,

and

when

w

e

succeed

in

pro

ving

the

logical

form

and

the

constrain

ts,

w

e

are

recognizing

this

referen

tial

anc

hor.

This

is

the

giv

en

information,

the

denite,

the

presupp

osed.

Where

it

is

necessary

to

mak

e

assumptions,

the

information

comes

from

the

sp

eak

er's

priv

ate

b

eliefs,

and

hence

is

the

new

information,

the

indenite,

the

asserted.

Merging

redundancies

is

a

w

a

y

of

getting

a

minimal,

and

hence

a

b

est,

in

terpretation.

Merging

redundancies

and

minimizing

the

assumptions

result

naturally

from

the

metho

d

of

w

eigh

ted

ab

duction.

6

Ab

duction

and

Lo

cal

Pragmatics

Lo

cal

pragmatics

encompasses

those

problems

that

are

p

osed

within

the

scop

e

of

individual

sen

tences,

ev

en

though

their

solution

will

generally

require

greater

con

text

and

w

orld

kno

wledge.

Included

under

this

lab

el

are

the

resolution

of

coreference,

resolving

syn

tactic

and

lexical

am

biguit

y

,

in

terpreting

meton

ym

y

and

metaphor,

and

nding

sp

ecic

meanings

for

v

ague

predicates

suc

h

as

in

the

comp

ound

nominal.

Consider

a

simple

example

that

con

tains

three

of

these

problems.

(12)

The

Boston

oÆce

called.

This

sen

tence

p

oses

at

least

three

lo

cal

pragmatics

problems,

the

problems

of

resolving

the

reference

of

\the

Boston

oÆce",

expanding

the

meton

ym

y

to

\[Some

p

erson

at]

the

Boston

oÆce

called",

and

determining

the

implicit

relation

b

et

w

een

Boston

and

the

oÆce.

Let

us

put

these

problems

aside

for

the

momen

t,

ho

w

ev

er,

and

in

terpret

the

sen

tence

according

to

the

IA

c

haracterization.

W

e

m

ust

pro

v

e

ab

ductiv

ely

the

logical

form

of

the

sen

tence

together

with

the

constrain

t

\call"

imp

oses

on

its

agen

t,

allo

wing

for

a

co

ercion.

That

is,

w

e

m

ust

pro

v

e

ab

ductiv

ely

the

expression

(ignoring

tense

and

some

other

complexities)

(13)

(9

x;

y

;

z

;

e)cal

l

0

(e;

x)

^

per

son(x)

^

r

el

(x;

y

)

^

oÆc

e(y

)

^

B

oston(z

)

^

nn(z

;

y

)

That

is,

there

is

a

calling

ev

en

t

e

b

y

x

where

x

is

a

p

erson.

x

ma

y

or

ma

y

not

b

e

the

same

as

the

explicit

sub

ject

of

the

sen

tence,

but

it

is

at

least

related

to

it,

or

co

ercible

from

it,

represen

ted

b

y

r

el

(x;

y

).

y

is

an

oÆce

and

it

b

ears

some

unsp

ecied

relation

nn

to

z

whic

h

is

Boston.

per

son(x)

is

the

requiremen

t

that

cal

l

0

imp

oses

on

its

agen

t

x.

(Briey

,

p(x)

means

p

is

true

of

x,

and

p

0

(e;

x)

means

that

e

is

the

ev

en

tualit

y

of

p's

b

eing

true

of

x.

See

Hobbs

(1985a)

for

explication

of

and

justication

for

this

st

yle

of

logical

form.

The

predicate

r

el

is

for

accomo

dating

meton

ym

y

.

Ho

w

it

is

in

tro

duced

is

discussed

in

the

next

section.

The

in

teresting

and

imp

ortan

t

question

of

what

sp

ecic

relations

can

instan

tiate

it

is

b

ey

ond

the

scop

e

of

this

c

hapter.)

The

sen

tence

can

b

e

in

terpreted

with

resp

ect

to

a

kno

wledge

base

of

m

utual

kno

wledge

that

con

tains

the

follo

wing

facts:

(14)

B

oston(B

1

)

that

is,

B

1

is

the

cit

y

of

Boston.

9

(15)

oÆc

e(O

1

)

^

in(O

1

;

B

1

)

that

is,

O

1

is

an

oÆce

and

is

in

Boston.

(16)

per

son(J

1

)

that

is,

John

J

1

is

a

p

erson.

(17)

w

or

k

-f

or

(J

1

;

O

1

)

that

is,

John

J

1

w

orks

for

the

oÆce

O

1

.

(18)

(8

y

;

z

)in(y

;

z

)

nn(z

;

y

)

that

is,

if

y

is

in

z

,

then

z

and

y

are

in

a

p

ossible

comp

ound

nominal

relation.

(19)

(8

x;

y

)w

or

k

-f

or

(x;

y

)

r

el

(x;

y

)

that

is,

if

x

w

orks

for

y

,

then

y

can

b

e

co

erced

in

to

x.

Giv

en

these

axioms,

the

pro

of

of

all

of

the

logical

form

is

straigh

tforw

ard

except

for

the

conjunct

cal

l

0

(e;

x).

Hence,

w

e

assume

that;

it

is

the

new

information

con

v

ey

ed

b

y

the

sen

tence.

This

in

terpretation

is

illustrated

in

the

pro

of

graph

of

Figure

1,

where

a

rectangle

is

dra

wn

around

the

assumed

literal

cal

l

0

(e;

x).

Suc

h

pro

of

graphs

pla

y

the

same

role

in

in

ter-

pretation

as

parse

trees

pla

y

in

syn

tactic

analysis.

They

are

pictures

of

the

in

terpretations,

and

w

e

will

see

sev

eral

suc

h

diagrams

in

this

c

hapter.

No

w

notice

that

the

three

lo

cal

pragmatics

problems

ha

v

e

b

een

solv

ed

as

a

b

y-pro

duct.

W

e

ha

v

e

resolv

ed

\the

Boston

oÆce"

to

O

1

.

W

e

ha

v

e

determined

the

implicit

relation

in

the

comp

ound

nominal

to

b

e

in.

And

w

e

ha

v

e

expanded

the

meton

ym

y

to

\John,

who

w

orks

for

the

Boston

oÆce,

called."

F

or

an

illustration

of

the

resolution

of

lexical

am

biguit

y

,

consider

an

example

from

Hirst

(1987):

(20)

The

plane

taxied

to

the

terminal.

The

w

ords

\plane",

\taxied",

and

\terminal"

are

all

am

biguous.

Supp

ose

the

kno

wledge

base

consists

of

the

follo

wing

axioms:

(21)

(8

x)air

pl

ane(x)

pl

ane(x)

or

an

airplane

is

a

plane.

(22)

(8

x)w

ood-smoother

(x)

pl

ane(x)

or

a

w

o

o

d

smo

other

is

a

plane.

(23)

(8

x;

y

)mov

e-on-g

r

ound(x;

y

)

^

air

pl

ane(x)

taxi(x;

y

)

or

for

an

airplane

x

to

mo

v

e

on

the

ground

to

y

is

for

it

to

taxi

to

y

.

(24)

(8

x;

y

)r

ide-in-cab(x;

y

)

^

per

son(x)

taxi(x;

y

)

10

Logical

F

orm:

cal

l

0

(e;

x)

^

per

son(x)

^

r

el

(x;

y

)

^

oÆc

e(y

)

^

B

oston(z

)

^

nn(z

;

y

)

Kno

wledge

Base:

per

son(J

1

)

C

C

C

C

C

C

O

w

or

k

-f

or

(x;

y

)

r

el

(x;

y

)

6

w

or

k

-f

or

(J

1

;

O

1

)

6

oÆc

e(O

1

)

Æ

B

oston(B

1

)

in(y

;

z

)

nn(z

;

y

)

Æ

in(O

1

;

B

1

)

6

Figure

1:

In

terpretation

of

\The

Boston

oÆce

called."

or

for

a

p

erson

x

to

ride

in

a

cab

to

y

is

for

x

to

taxi

to

y

.

(25)

(8

y

)air

por

t-ter

minal

(y

)

ter

minal

(y

)

or

an

airp

ort

terminal

is

a

terminal.

(26)

(8

y

)computer

-ter

minal

(y

)

ter

minal

(y

)

or

a

computer

terminal

is

a

terminal.

(27)

(8

z

)air

por

t(z

)

(9

x;

y

)air

pl

ane(x)

^

air

por

t-ter

minal

(y

)

or

airp

orts

ha

v

e

airplanes

and

airp

ort

terminals.

The

logical

form

of

the

sen

tence

will

b

e,

roughly

,

(28)

(9

x;

y

)pl

ane(x)

^

taxi(x;

y

)

^

ter

minal

(y

)

The

minimal

pro

of

of

this

logical

form

will

in

v

olv

e

assuming

the

existence

of

an

airp

ort,

deriving

from

that

the

airplane,

and

th

us

the

plane,

and

the

airp

ort

terminal,

and

th

us

the

terminal,

assuming

x

is

mo

ving

on

the

ground

to

y

,

and

recognizing

the

redundancy

11

Logical

F

orm:

pl

ane(x)

^

taxi(x;

y

)

^

ter

minal

(y

)

Kno

wledge

Base:

6

air

pl

ane(x)

pl

ane(x)

@

@

@

@

@

@

@

@

@

I

mov

e-on-g

r

ound(x;

y

)

^

air

pl

ane(x)

taxi(x;

y

)

S

S

S

S

S

S

S

S

S

S

S

S

o

air

por

t-ter

minal

(y

)

ter

minal

(y

)

S

S

S

S

S

S

S

S

S

o

>

6

air

por

t(z

)

air

pl

ane(x)

^

air

por

t-ter

minal

(y

)

w

ood-smoother

(x)

pl

ane(x)

r

ide-in-cab(x;

y

)

^

per

son(x)

taxi(x;

y

)

computer

-ter

minal

(y

)

ter

minal

(y

)

Figure

2:

In

terpretation

of

\The

plane

taxied

to

the

terminal."

of

the

airplane

with

the

one

in

that

reading

of

\taxi".

This

in

terpretation

is

illustrated

in

Figure

2.

Another

p

ossible

in

terpretation

w

ould

b

e

one

in

whic

h

w

e

assumed

that

a

w

o

o

d

smo

other,

a

ride

in

a

taxi,

and

a

computer

terminal

all

existed.

It

is

b

ecause

w

eigh

ted

ab

duction

fa

v

ors

merging

redundancies

that

the

correct

in

terpretation

is

the

one

c

hosen.

That

in

terpretation

allo

ws

us

to

minimize

the

assumptions

w

e

mak

e.

7

Syn

tax

b

y

Ab

duction

In

Hobbs

(1998)

an

extensiv

e

subset

of

English

grammar

is

describ

ed

in

detail,

largely

fol-

lo

wing

P

ollard

and

Sag's

(1994)

Head-Driv

en

Phrase

Structure

Grammar

but

cast

in

to

the

IA

framew

ork.

In

this

treatmen

t,

the

predicate

S

y

n

is

used

to

express

the

relation

b

et

w

een

a

string

of

w

ords

and

the

ev

en

tualit

y

it

con

v

eys.

Certain

axioms

in

v

olving

S

y

n,

the

com-

position

axioms,

describ

e

ho

w

the

ev

en

tualit

y

con

v

ey

ed

emerges

from

the

concatenation

of

strings.

Other

axioms,

the

lexical

axioms,

link

S

y

n

predications

ab

out

w

ords

with

the

corresp

onding

logical-form

fragmen

ts.

There

are

also

al

terna

tion

axioms

whic

h

12

alter

the

places

in

the

string

of

w

ords

where

predicates

nd

their

argumen

ts.

In

this

c

hapter,

a

simplied

v

ersion

of

the

predicate

S

y

n

will

b

e

used.

W

e

will

tak

e

S

y

n

to

b

e

a

predicate

of

sev

en

argumen

ts.

(29)

S

y

n(w

;

e;

f

;

x;

a;

y

;

b)

w

is

a

string

of

w

ords.

e

is

the

ev

en

tualit

y

describ

ed

b

y

this

string.

f

is

the

category

of

the

head

of

the

phrase

w

.

If

the

string

w

con

tains

the

logical

sub

ject

of

the

head,

then

the

argumen

ts

x

and

a

are

the

empt

y

sym

b

ol

\

".

Otherwise,

x

is

a

v

ariable

refering

to

the

logical

sub

ject

and

a

is

its

category

.

Similarly

,

y

is

either

the

empt

y

sym

b

ol

or

a

v

ariable

refering

to

the

logical

ob

ject

and

b

is

either

the

empt

y

sym

b

ol

or

the

category

of

the

logical

ob

ject.

F

or

example,

(30)

S

y

n(\reads

a

no

v

el";

e;v;

x;n;

;

)

sa

ys

that

the

string

of

w

ords

\reads

a

no

v

el"

is

a

phrase

describing

an

ev

en

tualit

y

e

and

has

a

head

of

category

v

erb.

Its

logical

ob

ject

\a

no

v

el"

is

in

the

string

itself,

so

the

last

t

w

o

argumen

ts

are

the

empt

y

sym

b

ol.

Its

logical

sub

ject

is

not

part

of

the

string,

so

the

fourth

argumen

t

is

the

v

ariable

x

standing

for

the

logical

sub

ject

and

the

fth

argumen

t

sp

ecies

that

the

phrase

describing

it

m

ust

ha

v

e

a

noun

as

its

head.

In

Hobbs

(1998)

the

full

S

y

n

predicate

con

tains

argumen

t

p

ositions

for

further

complemen

ts

and

ller-gap

information,

and

the

category

argumen

ts

can

record

syn

tactic

features

as

w

ell.

Tw

o

of

the

most

imp

ortan

t

comp

osition

axioms

are

the

follo

wing:

(31)

(8

w

1

;

w

2

;

x;

a;

e;

f

)S

y

n(w

1

;

x;

a;

;

;

;

)

^

S

y

n(w

2

;

e;

f

;

x;

a;

;

)

S

y

n(w

1

w

2

;

e;

f

;

;

;

;

)

(8

w

1

;

w

2

;

e;

f

;

x;

a;

y

;

b)S

y

n(w

1

;

e;

f

;

x;

a;

y

;

b)

^

S

y

n(w

2

;

y

;

b;

;

;

;

)

S

y

n(w

1

w

2

;

e;

f

;

x;

a;

;

)

The

rst

axiom

corresp

onds

to

the

traditional

\S

!

NP

VP"

rule.

It

sa

ys

that

if

w

1

is

a

string

describing

an

en

tit

y

x

and

headed

b

y

a

w

ord

of

category

a

and

w

2

is

a

string

describing

ev

en

tualit

y

e,

headed

b

y

a

w

ord

of

category

f

,

and

lac

king

a

logical

sub

ject

x

of

category

a,

then

the

concatenation

w

1

w

2

is

a

string

describing

ev

en

tualit

y

e

and

headed

b

y

a

w

ord

of

category

f

.

The

second

axiom

corresp

onds

to

the

traditional

\VP

!

V

NP"

rule.

It

sa

ys

that

if

w

1

is

a

string

describing

ev

en

tualit

y

e,

headed

b

y

a

w

ord

of

category

f

,

and

lac

king

a

logical

sub

ject

x

of

category

a

and

a

logical

ob

ject

y

of

category

b

and

w

2

is

a

string

describing

an

en

tit

y

y

and

headed

b

y

a

w

ord

of

category

b,

then

the

concatenation

w

1

w

2

is

a

string

describing

ev

en

tualit

y

e,

headed

b

y

a

w

ord

of

category

f

,

and

lac

king

a

logical

sub

ject

x

of

category

a,

but

not

lac

king

a

logical

ob

ject.

A

t

ypical

lexical

axiom

is

the

follo

wing:

(32)

(8

e;

x;

y

)past(e)

^

r

ead

0

(e;

x;

y

)

^

per

son(x)

^

text(y

)

S

y

n(\read";

e;v;

x;n;

y

;n)

That

is,

if

e

is

the

ev

en

tualit

y

in

the

past

of

a

p

erson

x

reading

a

text

y

,

then

the

v

erb

\read"

can

b

e

used

to

describ

e

e

pro

vided

noun

phrases

describing

x

and

y

are

13

found

in

the

appropriate

places,

as

sp

ecied

b

y

comp

osition

axioms.

Lexical

axioms

th

us

enco

de

the

logical

form

fragmen

t

corresp

onding

to

a

w

ord

(past(e)

^

r

ead

0

(e;

x;

y

)),

selectional

constrain

ts

(per

son(x)

and

text(y

)),

the

sp

elling

(or

in

a

more

detailed

accoun

t,

the

phonology)

of

the

w

ord

(\read"),

its

category

(v

erb),

and

the

syn

tactic

constrain

ts

on

its

complemen

ts

(that

x

and

y

m

ust

come

from

noun

phrases).

The

lexical

axioms

constitute

the

in

terface

b

et

w

een

syn

tax

and

w

orld

kno

wledge;

kno

wledge

ab

out

reading

is

enco

ded

in

axioms

in

v

olving

the

predicate

r

ead

0

,

whereas

kno

wledge

of

syn

tax

is

enco

ded

in

axioms

in

v

olving

S

y

n,

and

these

t

w

o

are

link

ed

here.

In

terpreting

a

sen

tence

W

is

then

pro

ving

the

expression

(33)

(9

e)S

y

n(W

;

e;v;

;

;

;

)

i.e.,

pro

ving

that

W

is

headed

b

y

a

v

erb,

describ

es

some

ev

en

tualit

y

e,

and

is

complete

in

that

it

do

es

not

lac

k

a

logical

sub

ject

and

logical

ob

ject.

The

parse

of

the

sen

tence

is

found

b

ecause

comp

osition

axioms

are

used

in

the

pro

of.

The

logical

form

is

generated

b

ecause

that

part

of

the

pro

of

b

ottoms

out

in

lexical

axioms.

The

lo

cal

pragmatics

problems

are

solv

ed

b

ecause

that

logical

form

is

then

pro

v

ed.

That

is,

in

the

course

of

pro

ving

that

a

string

of

w

ords

is

a

grammatical,

in

terpretable

sen

tence,

the

in

terpretation

pro

cess

bac

k

c

hains

through

comp

osition

axioms

to

lexical

axioms

(the

syn

tactic

pro

cessing)

and

then

is

left

with

the

logical

form

of

the

sen

tence

to

b

e

pro

v

ed.

A

pro

of

of

this

logical

form

w

as

the

IA

c

haracterization

of

the

in

terpretation

of

a

sen

tence

giv

en

in

the

previous

section.

The

pro

of

graph

of

the

syn

tactic

part

of

the

in

terpretation

of

\John

read

Ulysses"

is

sho

wn

in

Figure

3.

Note

that

kno

wledge

that

John

is

a

p

erson

and

Ulysses

is

a

text

is

used

to

establish

the

selectional

constrain

ts

asso

ciated

with

\read".

In

Hobbs

(1998)

there

are

ab

out

a

dozen

comp

osition

axioms,

corresp

onding

to

similar

rules

in

P

ollard

and

Sag

(1994).

There

is

one

lexical

axiom

for

ev

ery

w

ord

sense

and

sub

categorization

pattern;

the

lexical

axioms

constitute

the

lexicon.

There

are

also

a

n

um

b

er

of

alternation

axioms

that

handle

suc

h

things

as

passiv

e

constructions.

These

axioms

alter

the

order

of,

or

otherwise

mo

dify

,

the

argumen

ts

of

the

predicate

asso

ciated

with

a

construction's

head.

Meton

ymic

co

ercion

relations

can

b

e

in

tro

duced

b

y

means

of

an

alternation

axiom

of

the

form

(34)

S

y

n(w

;

e;

f

;

x

0

;

a;

y

;

b)

^

r

el

(x

0

;

x)

S

y

n(w

;

e;

f

;

x;

a;

y

;

b)

That

is,

a

w

ord

or

phrase

w

lo

oking

for

a

sub

ject

referring

to

x

0

can

b

e

used

to

describ

e

the

same

situation

if

its

sub

ject

refers

to

x

instead,

where

x

is

related

to

x

0

b

y

a

co

ercion

relation

r

el

.

As

presen

ted

so

far,

ab

duction

pla

ys

no

role

in

this

enco

ding

of

syn

tactic

kno

wledge.

Syn

tactic

pro

cessing

is

just

logical

deduction.

The

principal

adv

an

tage

of

the

framew

ork

is

that

it

allo

ws

syn

tactic

analysis

to

b

e

done

with

other

in

terpretion

pro

cesses

in

a

uni-

form

framew

ork.

In

addition,

v

arious

sorts

of

ungrammaticalit

y|telegraphic

discourse,

disuencies,

scram

bling|can

b

e

handled

b

y

means

of

assumptions.

14

6

6

6

6

6

6

6

@

@

I

H

H

H

H

Y

per

son(x)

past(e)

S

y

n(\John";

x;n;

;

;

;

)

J

ohn

0

(e

1

;

x)

S

y

n(\John

read

Ulysses";

e;v;

;

;

;

)

S

y

n(\read

Ulysses";

e;v;

x;n;

;

)

S

y

n(\read";

e;v;

x;n;

y

;n)

S

y

n(\Ulysses";

y

;n;

;

;

;

)

r

ead

0

(e;

x;

y

)

nov

el

(y

)

U

l

y

sses

0

(e

2

;

y

)

text(y

)

Figure

3:

P

arse

of

\John

read

Ulysses."

In

this

section

w

e

ha

v

e

recast

the

problem

of

in

terpreting

a

sen

tence

as

one

of

pro

ving

that

the

string

of

w

ords

is

a

grammatical,

in

terpretable

sen

tence.

Lo

cal

pragmatics

is

subsumed

under

that

c

haracterization

in

the

w

ord

\in

terpretable".

It

is

w

ell

kno

wn

that

there

are

in

teractions

b

et

w

een

syn

tactic

pro

cessing

and

pragmatics.

By

solving

b

oth

problems

with

one

pro

of

and

c

ho

osing

among

pro

ofs

b

y

means

of

a

common

ev

aluation

metric,

w

e

can

mo

del

those

in

teractions.

Sometimes

less

fa

v

ored

solutions

will

b

e

c

hosen

in

eac

h

part

of

the

pro

of

b

ecause

that

results

in

the

lo

w

est-cost

pro

of

o

v

erall.

In

the

next

section

w

e

will

see

ho

w

this

picture

can

b

e

em

b

edded

in

an

ev

en

larger

picture.

8

Recognizing

Discourse

Structure

When

t

w

o

segmen

ts

of

discourse

are

adjacen

t,

that

v

ery

adjacency

con

v

eys

information.

Eac

h

segmen

t,

insofar

as

it

is

coheren

t,

con

v

eys

information

ab

out

a

situation

or

ev

en

tu-

alit

y

,

and

the

adjacency

of

the

segmen

ts

con

v

eys

the

suggestion

that

the

t

w

o

situations

are

related

in

some

fashion,

or

are

parts

of

larger

units

that

are

related.

P

art

of

what

it

is

to

understand

a

discourse

is

to

disco

v

er

what

that

relation

is.

Ov

erwhelmingly

,

the

relations

that

obtain

b

et

w

een

discourse

segmen

ts

are

based

on

causal,

similarit

y

,

or

gure-ground

relations

b

et

w

een

the

situations

they

con

v

ey

.

W

e

can

th

us

dene

a

n

um

b

er

of

coherence

rela

tions

in

terms

of

the

relations

b

et

w

een

the

situations.

This

will

not

b

e

explored

further

here,

but

it

is

describ

ed

in

greater

detail

in

Kehler

(this

v

olume).

Here

it

will

b

e

sho

wn

ho

w

this

asp

ect

of

discourse

structure

can

b

e

15

built

in

to

the

ab

duction

framew

ork.

Supp

ose

w

1

and

w

2

are

t

w

o

adjacen

t

segmen

ts

of

discourse

and

that

w

1

w

2

is

their

concatenation.

If

S

eg

ment(w

;

e)

sa

ys

that

the

string

w

is

a

coheren

t

segmen

t

of

discourse

describing

the

ev

en

tualit

y

e

and

C

oher

enceR el

(e

1

;

e

2

;

e)

sa

ys

that

there

is

a

coherence

relation

b

et

w

een

e

1

and

e

2

and

that

the

com

bination

of

the

t

w

o

con

v

eys

e,

then

w

e

can

express

the

basic

comp

osition

rule

for

discourse

as

(35)

(8

w

1

;

w

2

;

e

1

;

e

2

;

e)S

eg

ment(w

1

;

e

1

)

^

S

eg

ment(w

2

;

e

2

)

^

C

oher

enceR el

(e

1

;

e

2

;

e)

S

eg

ment(w

1

w

2

;

e)

That

is,

when

w

e

com

bine

t

w

o

coheren

t

segmen

ts

of

discourse

with

a

coherence

relation

w

e

get

a

coheren

t

segmen

t

of

discourse.

By

applying

this

successiv

ely

to

a

stretc

h

of

discourse,

w

e

get

a

tree-lik

e

structure

for

the

whole

discourse.

This

pro

cess

b

ottoms

out

in

sen

tences,

after

whic

h

syn

tactic

rules

tell

us

the

structure

and

meaning

of

the

string

of

w

ords.

This

is

captured

b

y

the

rule

(36)

(8

w

;

e)S

y

n(w

;

e;v;

;

;

;

)

S

eg

ment(w

;

e)

That

is,

a

grammatical

sen

tence

con

v

eying

e

is

a

coheren

t

segmen

t

of

discourse

con

v

eying

e.

In

the

previous

section

the

solution

to

lo

cal

pragmatics

problems|pro

ving

the

logical

form|w

as

em

b

edded

in

the

problem

of

nding

the

syn

tactic

structure

of,

or

parsing,

a

sen

tence.

These

t

w

o

axioms

no

w

em

b

ed

parsing

the

sen

tence

in

the

problem

of

recognizing

the

discourse

structure

of

the

whole

text.

If

W

is

a

text,

then

in

terpreting

W

is

a

matter

of

pro

ving

that

it

is

a

coheren

t

segmen

t

of

discourse

con

v

eying

some

ev

en

tualit

y

e:

(37)

(9

e)S

eg

ment(W

;

e)

No

w

let

us

consider

an

example.

Explanation

is

a

coherence

relation,

and

a

rst

appro

ximation

of

a

denition

of

the

Explanation

relation

w

ould

b

e

that

the

ev

en

tualit

y

describ

ed

b

y

the

second

segmen

t

causes

the

ev

en

tualit

y

describ

ed

b

y

the

rst:

(38)

(8

e

1

;

e

2

)cause(e

2

;

e

1

)

C

oher

enceR el

(e

1

;

e

2

;

e

1

)

That

is,

if

what

is

describ

ed

b

y

the

second

segmen

t

could

cause

what

is

describ

ed

b

y

the

rst

segmen

t,

then

there

is

a

coherence

relation

b

et

w

een

the

segmen

ts.

In

explanations,

what

is

explained

is

the

dominan

t

segmen

t

(the

nucleus

in

the

terms

of

Rhetorical

Struc-

ture

Theory

(Mann

and

Thompson

1986)),

so

it

is

e

1

that

is

describ

ed

b

y

the

comp

osed

segmen

t.

Hence,

the

third

argumen

t

of

Coher

enc

eR

el

is

e

1

.

Consider

a

v

ariation

on

a

classic

example

of

pronoun

resolution

diÆculties

from

Wino-

grad

(1972):

(39)

The

p

olice

prohibited

the

w

omen

from

demonstrating.

They

feared

violence.

Ho

w

do

w

e

kno

w

\they"

in

the

second

sen

tence

refers

to

the

p

olice

and

not

to

the

w

omen?

As

in

Section

6,

w

e

will

ignore

this

lo

cal

pragmatics

problem

and

pro

ceed

to

in

terpret

the

text

b

y

ab

duction.

T

o

in

terpret

the

text

is

to

pro

v

e

ab

ductiv

ely

the

expression

16

(40)

(9

e)S

eg

ment(\The

p

olice

:

:

:

violence.",

e)

This

in

v

olv

es

pro

ving

that

eac

h

sen

tence

is

a

segmen

t,

b

y

pro

ving

they

are

grammatical,

in

terpretable

sen

tences,

and

pro

ving

there

is

a

coherence

relation

b

et

w

een

them.

T

o

pro

v

e

they

are

sen

tences,

w

e

w

ould

tap

in

to

an

expanded

v

ersion

of

the

sen

tence

grammar

of

Section

7.

This

w

ould

b

ottom

out

in

the

logical

forms

of

the

sen

tences,

via

the

lexical

axioms,

and

th

us

require

us

to

pro

v

e

ab

ductiv

ely

those

logical

forms.

One

w

a

y

to

pro

v

e

there

is

a

coherence

relation

b

et

w

een

the

sen

tences

is

to

pro

v

e

there

is

an

Explanation

relation

b

et

w

een

them

b

y

sho

wing

there

is

a

causal

relation

b

et

w

een

the

ev

en

tualities

they

describ

e.

After

bac

k-c

haining

in

this

manner,

w

e

are

faced

with

pro

ving

the

expression

(41)

(9

e

1

;

p;

d;

w

;

e

2

;

y

;

v

;

z

)pol

ice(p)

^

pr

ohibit

0

(e

1

;

p;

d)

^

demonstr

ate

0

(d;

w

)

^

cause(e

2

;

e

1

)

^

f

ear

0

(e

2

;

y

;

v

)

^

v

iol

ent

0

(v

;

z

)

That

is,

there

is

a

prohibiting

ev

en

t

e

1

b

y

the

p

olice

p

of

a

demonstrating

ev

en

t

d

b

y

the

w

omen

w

.

There

is

a

fearing

ev

en

t

e

2

b

y

someone

y

(\they")

of

violence

v

b

y

someone

z

.

The

fearing

ev

en

t

e

2

causes

the

prohibiting

ev

en

t

e

1

.

This

expression

is

just

the

(simplied)

logical

forms

of

the

t

w

o

sen

tences,

plus

the

h

yp

othesized

causal

relation

b

et

w

een

them.

Supp

ose,

plausibly

enough,

w

e

ha

v

e

in

our

kno

wledge

base

the

follo

wing

axioms:

(42)

(8

e

2

;

y

;

v

)f

ear

0

(e

2

;

y

;

v

)

(9

d

2

)disw

ant

0

(d

2

;

y

;

v

)

^

cause(e

2

;

d

2

)

That

is,

if

e

2

is

a

fearing

b

y

y

of

v

,

then

that

will

cause

the

state

d

2

of

y

not

w

an

ting

or

\disw

an

ting"

v

.

(43)

(8

d;

w

)demonstr

ate

0

(d;

w

)

(9

v

;

z

)cause(d;

v

)

^

v

iol

ent

0

(v

;

z

)

That

is,

demonstrations

cause

violence.

(44)

(8

d;

v

;

d

2

;

y

)cause(d;

v

)

^

disw

ant

0

(d

2

;

y

;

v

)

(9

d

1

)disw

ant

0

(d

1

;

y

;

d)

^

cause(d

2

;

d

1

)

That

is,

if

someone

y

disw

an

ts

v

and

v

is

caused

b

y

d,

then

that

will

cause

y

to

disw

an

t

d

as

w

ell.

If

y

ou

don't

w

an

t

the

eect,

y

ou

don't

w

an

t

the

cause.

(45)

(8

d

1

;

p;

d)disw

ant

0

(d

1

;

p;

d)

^

author

ity

(p)

(9

e

1

)pr

ohibit

0

(e

1

;

p;

d)

^

cause(d

1

;

e

1

)

That

is,

if

those

in

authorit

y

disw

an

t

something,

that

will

cause

them

to

prohibit

it.

(46)

(8

e

1

;

e

2

;

e

3

)cause(e

1

;

e

2

)

^

cause(e

2

;

e

3

)

cause(e

1

;

e

3

)

That

is,

cause

is

transitiv

e.

(47)

(8

p)pol

ice(p)

author

ity

(p)

17

S

eg

ment(\The

p

olice

:

:

:

violence.";

e

1

)

6

C

oher

enceR el

(e

1

;

e

2

;

e

1

)

A

A

A

A

A

K

S

eg

ment(\The

p

olice

:

:

:

demonstrating.";

e

1

)

S

eg

ment(\They

:

:

:

violence.";

e

2

)

6

6

S

y

n(\The

p

olice

:

:

:

demonstrating.";

e

1

;v;

;

;

;

)

S

y

n(\They

feared

violence.";

e

2

;v;

;

;

;

)

6

cause(e

2

;

e

1

)

6

A

A

A

K

pr

ohibit

0

(e

1

;

p;

d)

cause(d

1

;

e

1

)

cause(e

2

;

d

1

)

y

=

p

6

*

@

@

@

@

I

6

author

ity

(p)

disw

ant

0

(d

1

;

y

;

d)

cause(d

2

;

d

1

)

Æ

6

*

A

A

A

A

K

6

6

pol

ice(p)

disw

ant

0

(d

2

;

y

;

v

)

cause(d;

v

)

cause(e

2

;

d

2

)

v

iol

ent

0

(v

;

z

)

Æ

3

1

@

@

@

@

@

@

@

I

Æ

6

demonstr

ate

0

(d;

w

)

f

ear

0

(e

2

;

y

;

v

)

Figure

4:

In

terpretation

of

\The

p

olice

prohibited

the

w

omen

from

demonstrating.

They

feared

violence."

18

That

is,

the

p

olice

are

in

authorit

y

.

F

rom

these

axioms,

w

e

can

pro

v

e

all

of

the

ab

o

v

e

logical

form

except

the

prop

ositions

pol

ice(p),

demonstr

ate

0

(d;

w

),

and

f

ear

0

(f

;

y

;

v

),

whic

h

w

e

assume.

This

is

illustrated

in

Figure

3.

Notice

that

in

the

course

of

doing

the

pro

of,

w

e

unify

y

with

p,

th

us

resolving

the

problematic

pronoun

reference

that

originally

motiv

ated

this

example.

\They"

refers

to

the

p

olice.

One

can

imagine

a

n

um

b

er

of

v

ariations

on

this

example.

If

w

e

had

not

included

the

axiom

that

demonstrations

cause

violence,

w

e

w

ould

ha

v

e

had

to

assume

the

violence

and

the

causal

relation

b

et

w

een

demonstrations

and

violence.

Moreo

v

er,

other

coherence

relations

migh

t

b

e

imagined

here

b

y

constructing

the

surrounding

con

text

in

the

righ

t

w

a

y

.

It

could

b

e

follo

w

ed

b

y

the

sen

tence

\But

since

they

had

nev

er

demonstrated

b

efore,

they

did

not

kno

w

that

violence

migh

t

result."

In

this

case,

the

second

sen

tence

w

ould

pla

y

a

sub

ordinate

role

to

the

third,

forcing

the

resolution

of

\they"

to

the

w

omen.

Eac

h

example,

of

course,

has

to

b

e

analyzed

on

its

o

wn,

and

c

hanging

the

example

c

hanges

the

analysis.

In

Winograd's

original

v

ersion

of

this

example,

(48)

The

p

olice

prohibited

the

w

omen

from

demonstrating,

b

ecause

they

feared

violence.

the

causalit

y

w

as

explicit,

th

us

eliminating

the

coherence

relation

as

a

source

of

am

biguit

y

.

The

literal

cause(e

2

;

e

1

)

w

ould

b

e

part

of

the

logical

form.

Winograd's

con

trasting

text,

in

whic

h

\they"

is

resolv

ed

to

the

w

omen,

is

(49)

The

p

olice

prohibited

the

w

omen

from

demonstrating,

b

ecause

they

adv

o

cated

violence.

Here

w

e

w

ould

need

the

facts

that

when

one

demonstrates

one

adv

o

cates

and

that

adv

o-

cating

something

tends

to

bring

it

ab

out.

Then

sho

wing

a

causal

relation

b

et

w

een

the

clauses

will

result

in

\they"

b

eing

iden

tied

with

the

demonstrators.

9

Recognizing

the

Sp

eak

er's

Plan

As

presen

ted

so

far,

understanding

discourse

is

seeing

the

w

orld

of

the

text

as

coheren

t,

whic

h

in

turn

in

v

olv

es

viewing

the

con

ten

t

of

the

text

as

observ

ables

to

b

e

explained.

The

fo

cus

has

b

een

on

the

information

con

v

ey

ed

explicitly

or

implicitly

b

y

the

discourse.

W

e

can

call

this

the

inf

orma

tional

accoun

t

of

a

discourse.

But

utterances

are

em

b

edded

in

the

w

orld

as

w

ell.

They

are

pro

duced

to

realize

a

sp

eak

er's

in

ten

tion,

or

more

generally

,

they

are

actions

in

the

execution

of

a

sp

eak

er's

plan

to

ac

hiev

e

some

goal.

The

description

of

ho

w

a

discourse

realizes

the

sp

eak

ers'

goals

ma

y

b

e

called

the

intentional

accoun

t

of

the

discourse.

Let

us

consider

the

in

ten

tional

accoun

t

from

the

broadest

p

ersp

ectiv

e.

An

in

telligen

t

agen

t

is

em

b

edded

in

the

w

orld

and

m

ust,

at

eac

h

instan

t,

understand

the

curren

t

situation.

The

agen

t

do

es

so

b

y

nding

an

explanation

for

what

is

p

erceiv

ed.

Put

dieren

tly

,

the

agen

t

m

ust

explain

wh

y

the

complete

set

of

observ

ables

encoun

tered

constitutes

a

coheren

t

situation.

Other

agen

ts

in

the

en

vironmen

t

are

view

ed

as

in

ten

tional,

that

is,

as

planning

19

mec

hanisms,

and

this

means

that

the

b

est

explanation

of

their

observ

able

actions

is

most

lik

ely

to

b

e

that

the

actions

are

steps

in

a

coheren

t

plan.

Th

us,

making

sense

of

an

en

vironmen

t

that

includes

other

agen

ts

en

tails

making

sense

of

the

other

agen

ts'

actions

in

terms

of

what

they

are

in

tended

to

ac

hiev

e.

When

those

actions

are

utterances,

the

utterances

m

ust

b

e

understo

o

d

as

actions

in

a

plan

the

agen

ts

are

trying

to

eect.

That

is,

the

sp

eak

er's

plan

m

ust

b

e

recognized|the

in

ten

tional

accoun

t.

Generally

,

when

a

sp

eak

er

sa

ys

something

it

is

with

the

goal

of

the

hearer

b

elieving

the

con

ten

t

of

the

utterance,

or

thinking

ab

out

it,

or

considering

it,

or

taking

some

other

cog-

nitiv

e

stance

to

w

ard

it.

Let

us

subsume

all

these

men

tal

terms

under

the

term

\cognize".

Then

w

e

can

summarize

the

relation

b

et

w

een

the

in

ten

tional

and

informational

accoun

ts

succinctly

in

the

follo

wing

form

ula:

(50)

in

ten

tional-accoun

t

=

g

oal

(A;

cog

niz

e(B

;

informational-accoun

t)

The

sp

eak

er

ostensibly

has

the

goal

of

c

hanging

the

men

tal

state

of

the

hearer

to

include

some

men

tal

stance

to

w

ard

the

con

ten

t

c

haracterized

b

y

the

informational

accoun

t.

Th

us,

the

informational

accoun

t

is

em

b

edded

in

the

in

ten

tional

accoun

t.

When

w

e

reason

ab

out

the

sp

eak

er's

in

ten

tion,

w

e

are

reasoning

ab

out

ho

w

this

goal

ts

in

to

the

larger

picture

of

the

sp

eak

er's

ongoing

plan.

W

e

are

asking

wh

y

the

sp

eak

er

seems

to

b

e

trying

to

get

the

hearer

to

b

eliev

e

this

particular

con

ten

t.

The

informational

accoun

t

explains

the

situation

describ

ed

in

the

discourse;

the

in

ten

tional

accoun

t

explains

wh

y

the

sp

eak

er

c

hose

to

con

v

ey

this

information.

The

(defeasible)

axiom

that

encapsulates

this

is

(51)

(8

s;

h;

e

1

;

e;

w

)g

oal

(s;

e

1

)

^

cog

niz

e

0

(e

1

;

h;

e)

^

S

eg

ment(w

;

e)

utter

(s;

h;

w

)

That

is,

normally

if

a

sp

eak

er

s

has

a

goal

of

the

hearer

h

cognizing

a

situation

e

and

w

is

a

string

of

w

ords

that

con

v

eys

e,

then

s

will

utter

w

to

h.

W

e

app

eal

to

this

axiom

to

in

terpret

the

utterance

as

an

in

ten

tional

comm

unicativ

e

act.

That

is,

if

y

ou

(U

)

utter

to

me

(I

)

a

string

of

w

ords

(W

),

then

to

explain

this

observ

able

ev

en

t,

I

ha

v

e

to

pro

v

e

(52)

utter

(U;

I

;

W

)

and

I

b

egin

to

do

so

b

y

bac

k

c

haining

on

the

ab

o

v

e

axiom.

Reasoning

ab

out

the

sp

eak

er's

plan

is

a

matter

of

establishing

the

rst

t

w

o

prop

ositions

in

the

an

teceden

t

of

the

axiom.

Determining

the

informational

con

ten

t

of

the

utterance

is

a

matter

of

establishing

the

third,

as

describ

ed

in

the

previous

sections.

The

t

w

o

sides

of

the

pro

of

inuence

eac

h

other

since

they

share

v

ariables

and

since

minimalit

y

results

when

b

oth

are

explained

and

when

they

share

prop

ositions.

Both

the

in

ten

tional

and

informational

accoun

ts

are

necessary

.

The

informational

ac-

coun

t

is

needed

b

ecause

w

e

ha

v

e

no

direct

access

to

the

sp

eak

er's

plan.

W

e

can

only

infer

it

from

history

and

b

eha

vior.

The

con

ten

t

of

the

utterance

is

often

the

b

est

evi-

dence

of

the

sp

eak

er's

in

ten

tion,

and

often

the

in

ten

tion

is

no

more

than

to

con

v

ey

that

particular

con

ten

t.

On

the

other

hand,

the

in

ten

tional

accoun

t

is

necessary

in

cases

lik

e

pragmatic

ellipsis,

where

the

informational

accoun

t

is

highly

underdetermined

and

the

global

in

terpretation

is

primarily

shap

ed

b

y

our

b

eliefs

ab

out

the

sp

eak

er's

plan.

20

P

erhaps

most

in

teresting

are

cases

of

gen

uine

conict

b

et

w

een

the

t

w

o

accoun

ts.

The

informational

accoun

t

do

es

not

seem

to

b

e

true,

or

it

seems

to

run

coun

ter

to

the

sp

eak

er's

goals

for

the

hearer

to

come

to

b

eliev

e

it,

or

it

ough

t

to

b

e

ob

vious

that

the

hearer

already

do

es

b

eliev

e

it.

T

autologies

are

an

example

of

the

last

of

these

cases|tautologies

suc

h

as

\b

o

ys

will

b

e

b

o

ys,"

\fair

is

fair,"

and

\a

job

is

a

job."

Norvig

and

Wilensky

(1990)

cite

this

gure

of

sp

eec

h

as

something

that

should

cause

trouble

for

an

ab

duction

approac

h

that

seeks

minimal

explanations,

since

the

minimal

explanation

is

that

they

just

express

a

kno

wn

truth.

Suc

h

an

explanation

requires

no

assumptions

at

all.

In

fact,

the

phenomenon

is

a

go

o

d

example

of

wh

y

an

informational

accoun

t

of

discourse

in

terpretation

has

to

b

e

em

b

edded

in

an

in

ten

tional

accoun

t.

Let

us

imagine

t

w

o

paren

ts,

A

and

B,

sitting

in

the

pla

yground

and

talking.

(53)

A:

Y

our

Johnn

y

is

certainly

acting

up

to

da

y

,

isn't

he?

B:

Bo

ys

will

b

e

b

o

ys.

In

order

to

a

v

oid

dealing

with

the

complications

of

plurals

and

tense

in

this

example,

let

us

simplify

B's

utterance

to

(54)

B:

A

b

o

y

is

a

b

o

y

.

Sev

eral

informational

accoun

ts

of

this

utterance

are

p

ossible.

The

rst

is

the

Literal

Extensional

In

terpretation.

The

rst

\a

b

o

y"

in

tro

duces

a

sp

ecic,

previously

uniden

tied

b

o

y

and

the

second

sa

ys

ab

out

him

that

he

is

a

b

o

y

.

The

second

informational

accoun

t

is

the

Literal

In

tensional

In

terpretation.

The

sen

tence

expresses

a

trivial

implicativ

e

re-

lation

b

et

w

een

t

w

o

general

prop

ositions|boy

(x)

and

boy

(x).

The

third

is

the

Desired

In

terpretation.

The

rst

\a

b

o

y"

iden

ties

the

t

ypical

mem

b

er

of

a

class

whic

h

Johnn

y

is

a

mem

b

er

of

and

the

second

con

v

eys

a

general

prop

ert

y

,

\b

eing

a

b

o

y",

as

a

w

a

y

of

con

v

eying

a

sp

ecic

prop

ert

y

,

\misb

eha

ving",

whic

h

is

true

of

mem

b

ers

of

that

class.

More

precisely

,

the

logical

form

of

the

sen

tence

can

b

e

written

as

follo

ws:

(55)

(9

e

1

;

e

2

;

x;

y

;

z

;

w

)boy

0

(e

1

;

x)

^

r

el

(z

;

x)

^

be(z

;

w

)

^

r

el

(w

;

y

)

^

boy

0

(e

2

;

y

)

The

sen

tence

expresses

a

be

relation

b

et

w

een

t

w

o

en

tities,

but

either

or

b

oth

of

its

argu-

men

ts

ma

y

b

e

sub

ject

to

co

ercion.

Th

us,

w

e

ha

v

e

in

tro

duced

the

t

w

o

r

el

relations.

The

logical

form

can

b

e

giv

en

the

tortured

paraphrase,

\z

is

w

,

where

z

is

related

to

x

whose

b

o

y-ness

is

e

1

and

w

is

related

to

y

whose

b

o

y-ness

is

e

2

."

The

required

axioms

are

as

follo

ws:

Ev

erything

is

itself:

(56)

(8

x)be(x;

x)

Implication

can

b

e

expressed

b

y

\to

b

e":

(57)

(8

e

1

;

e

2

)impl

y

(e

1

;

e

2

)

be(e

1

;

e

2

)

Implication

is

reexiv

e:

(58)

(8

e)impl

y

(e;

e)

21

Bo

ys

misb

eha

v

e:

(59)

(8

e

1

;

x)boy

0

(e

1

;

x)

(9

e

3

)misbehav

e

0

(e

3

;

x)

^

impl

y

(e

1

;

e

3

)

Misb

eha

v

ers

are

often

b

o

ys:

(60)

(8

e

3

;

x)misbehav

e

0

(e

3

;

x)

^

etc

1

(x)

(9

e

2

)boy

0

(e

2

;

x)

Iden

tit

y

is

a

p

ossible

co

ercion

relation:

(61)

(8

x)r

el

(x;

x)

An

en

tit

y

can

b

e

co

erced

in

to

a

prop

ert

y

of

the

en

tit

y:

(62)

(8

e;

x)boy

0

(e;

x)

r

el

(e;

x)

(8

e;

x)misbehav

e

0

(e;

x)

r

el

(e;

x)

Note

that

w

e

ha

v

e

axioms

in

b

oth

directions

relating

b

o

ys

and

misb

eha

ving;

in

Hobbs

et

al.

(1993)

the

general

w

a

y

of

expressing

axioms

is

with

biconditionals

and

etc

predicates.

The

axioms

with

the

co

ercion

relation

r

el

in

the

consequen

t

b

egin

to

sp

ell

out

the

range

of

p

ossible

in

terpretations

for

r

el

.

No

w

the

Literal

Extensional

In

terpretation

is

established

b

y

taking

the

t

w

o

co

ercion

relations

to

b

e

iden

tit

y

,

taking

be

to

b

e

expressing

iden

tit

y

,

and

assuming

boy

(e

1

;

x)

(or

equiv

alen

tly

,

boy

(e

2

;

y

)).

In

the

Literal

In

tensional

In

terpretation,

z

is

iden

tied

with

e

1

,

w

is

iden

tied

with

e

2

,

and

boy

0

(e

1

;

x)

and

boy

0

(e

2

;

y

)

are

tak

en

to

b

e

the

t

w

o

co

ercion

relations.

Then

e

2

is

iden

tied

with

e

1

and

be(e

1

;

e

1

)

is

in

terpreted

as

a

consequence

of

impl

y

(e

1

;

e

1

).

Again,

boy

(e

1

;

x)

is

assumed.

In

the

Desired

In

terpretation,

the

rst

co

ercion

relation

is

tak

en

to

b

e

boy

0

(e

1

;

x),

iden-

tifying

z

as

e

1

.

The

second

co

ercion

relation

is

tak

en

to

b

e

misbehav

e

0

(e

3

;

y

),

iden

tifying

w

as

e

3

.

If

etc

1

(y

)

is

assumed,

then

misbehav

e

0

(e

3

;

y

)

explains

boy

(e

2

;

y

).

If

boy

(e

1

;

x)

is

assumed,

it

can

explain

misbehav

e

0

(e

3

;

y

),

iden

tifying

x

and

y

,

and

also

impl

y

(e

1

;

e

3

).

The

latter

explains

be(e

1

;

e

3

).

Considering

the

informational

accoun

t

alone,

the

Literal

Extensional

In

terpretation

is

minimal

and

hence

w

ould

b

e

fa

v

ored.

The

Desired

In

terpretation

is

the

w

orst

of

the

three.

But

the

Literal

Extensional

and

In

tensional

In

terpretations

lea

v

e

the

fact

that

the

utterance

o

ccurred

unaccoun

ted

for.

In

the

in

ten

tional

accoun

t,

this

is

what

w

e

need

to

explain.

The

explanation

w

ould

run

something

lik

e

this:

B

w

an

ts

A

to

b

eliev

e

that

B

is

not

resp

onsible

for

Johnn

y's

misb

eha

ving.

Th

us,

B

w

an

ts

A

to

b

eliev

e

that

Johnn

y

misb

eha

v

es

necessarily

.

Th

us,

giv

en

that

Johnn

y

is

necessarily

a

b

o

y

,

B

w

an

ts

A

to

b

eliev

e

that

Johnn

y's

b

eing

a

b

o

y

implies

that

he

misb

eha

v

es.

Th

us,

B

w

an

ts

to

con

v

ey

to

A

that

b

eing

a

b

o

y

implies

misb

eha

ving.

Th

us,

giv

en

that

b

o

y-ness

implies

misb

eha

ving

is

a

p

ossible

in

terpretation

of

a

b

o

y

b

eing

a

b

o

y

,

B

w

an

ts

to

sa

y

to

A

that

a

b

o

y

is

a

b

o

y

.

22

The

con

ten

t

of

the

utterance

under

the

Literal

Extensional

and

In

tensional

In

terpre-

tations

do

not

lend

themselv

es

to

explanations

for

the

fact

that

the

utterance

o

ccurred,

whereas

the

Desired

In

terpretation

do

es.

The

requiremen

t

for

the

globally

minimal

ex-

planation

in

an

in

ten

tional

accoun

t,

that

is,

the

requiremen

t

that

b

oth

the

con

ten

t

and

the

fact

of

the

utterance

m

ust

b

e

explained,

forces

us

in

to

an

in

terpretation

of

the

con-

ten

t

that

w

ould

not

b

e

fa

v

ored

in

an

informational

accoun

t

alone.

W

e

are

forced

in

to

an

in

terpretation

of

the

con

ten

t

that,

while

not

optimal

lo

cally

,

con

tributes

to

a

global

in

terpretation

that

is

optimal.

10

Relation

to

Relev

ance

Theory

One

of

the

other

principal

con

tenders

for

a

theory

of

ho

w

w

e

understand

extended

discourse

is

Relev

ance

Theory

(R

T)

(Sp

erb

er

and

Wilson

1986).

In

fact,

the

IA

framew

ork

and

R

T

are

v

ery

close

to

eac

h

other

in

the

pro

cessing

that

w

ould

implemen

t

them.

In

R

T,

the

agen

t

is

in

the

situation

of

ha

ving

a

kno

wlege

base

K

and

hearing

a

sen

tence

with

con

ten

t

Q.

F

rom

K

and

Q

a

new

set

R

of

inferences

can

b

e

dra

wn:

(63)

K ;

Q

`

R

R

T

sa

ys

that

the

agen

t

striv

es

to

maximize

R

in

an

appropriately

hedged

sense.

An

immediate

consequence

of

this

is

that

insofar

as

w

e

are

able

to

pragmatically

strengthen

Q

b

y

means

of

axioms

of

the

form

(64)

P

Q

then

w

e

are

getting

a

b

etter

R ,

since

P

implies

an

ything

that

Q

implies,

and

then

some.

In

the

IA

framew

ork,

w

e

b

egin

with

pragmatic

strengthening.

The

task

of

the

agen

t

is

to

explain

the

general

Q

with

the

more

sp

ecic

P

.

This

means

that

an

ything

done

in

the

IA

framew

ork

ough

t

to

carry

o

v

er

without

c

hange

in

to

R

T.

Muc

h

of

the

w

ork

in

R

T

dep

ends

primarily

or

solely

on

pragmatic

strengthening,

and

where

this

is

the

case,

it

can

immediately

b

e

incorp

orated

in

to

the

IA

framew

ork.

F

rom

the

p

oin

t

of

view

of

IA,

p

eople

are

going

through

the

w

orld

trying

to

gure

out

what

is

going

on.

F

rom

the

p

oin

t

of

view

of

R

T,

they

are

going

through

the

w

orld

trying

to

learn

as

m

uc

h

as

they

can,

and

guring

out

what

is

going

on

is

in

service

of

that.

The

IA

framew

ork

has

b

een

w

ork

ed

out

in

greater

detail

formally

and,

I

b

eliev

e,

has

a

more

comp

elling

justication|explaining

the

observ

ables

in

our

en

vironmen

t.

But

a

great

deal

of

excellen

t

w

ork

has

b

een

done

in

R

T,

so

it

is

useful

to

kno

w

that

the

t

w

o

framew

orks

are

almost

en

tirely

compatible.

11

Researc

h

Issues

In

the

examples

giv

en

in

this

pap

er,

I

ha

v

e

ca

v

alierly

assumed

the

most

con

v

enien

t

axioms

w

ere

in

the

kno

wledge

base

that

w

as

b

eing

used.

But

of

course

it

is

a

serious

researc

h

issue

ho

w

to

construct

a

kno

wledge

base

prior

to

seeing

the

discourses

it

will

b

e

used

for

in

terpreting.

I

b

eliev

e

there

is

a

principled

metho

dology

for

deciding

what

facts

should

23

go

in

to

a

kno

wledge

base

(Hobbs

1984),

and

there

are

previous

and

ongoing

eorts

to

construct

a

kno

wledge

base

of

the

required

sort.

F

or

example,

W

ordNet

(Miller

1995),

while

shallo

w

and

lac

king

the

required

formalit

y

,

is

v

ery

broad,

and

attempts

ha

v

e

b

een

made

to

emplo

y

it

as

a

kno

wledge

base

in

text

understanding

(Harabagiu

and

Moldo

v

an

1998).

F

rameNet

(Bak

er

et

al.

1998)

is

a

more

recen

t

eort

aimed

at

deep

er

inference,

but

it

is

not

y

et

as

broad.

The

eorts

of

Hobbs

et

al.

(1986),

recen

tly

resumed,

are

deep

er

y

et

but

v

ery

m

uc

h

smaller

in

scop

e.

Cyc

(Guha

and

Lenat

1990)

is

b

oth

broad

and

deep,

but

it

is

not

clear

ho

w

useful

it

will

b

e

for

in

terpreting

discourse

(e.g.,

Mahesh

et

al.

1996).

In

an

y

case,

progress

in

b

eing

made

on

sev

eral

fron

ts.

Another

issue

I

w

as

silen

t

ab

out

in

presen

ting

the

examples

w

as

exactly

what

the

measure

is

that

decides

among

comp

eting

in

terpretations.

In

some

of

the

examples,

factors

suc

h

as

redundancy

in

explanation

and

the

co

v

erage

of

the

explanations

w

ere

app

ealed

to

as

criteria

for

c

ho

osing

among

them.

But

this

w

as

not

made

precise.

Charniak

and

Shimon

y

(1990)

w

en

t

a

long

w

a

y

in

setting

the

w

eigh

ting

criteria

on

a

rm

mathematical

foundation,

in

terms

of

probabilities.

But

w

e

still

do

not

ha

v

e

v

ery

m

uc

h

exp

erience

in

seeing

ho

w

the

metho

d

w

orks

out

in

practice.

My

feeling

is

that

no

w

the

task

is

to

build

up

a

large

kno

wledge

base

and

do

the

necessary

empirical

studies

of

attempting

to

pro

cess

a

large

n

um

b

er

of

texts

with

resp

ect

to

the

kno

wledge

base.

That

of

course

requires

the

kno

wledge

base.

I

ha

v

e

written

in

this

c

hapter

only

ab

out

in

terpretation,

not

ab

out

generation.

It

is

an

in

teresting

question

whether

generation

can

b

e

done

in

the

same

framew

ork.

A

t

the

most

abstract

lev

el,

it

seems

it

should

b

e

p

ossible.

In

terpreting

a

string

of

w

ords

W

w

as

describ

ed

as

pro

ving

the

expression

(65)

(9

e)S

eg

ment(W

;

e)

It

should

b

e

p

ossible

corresp

ondingly

to

c

haracterize

the

pro

cess

of

describing

a

situation

E

as

the

pro

cess

of

pro

ving

the

expression

(66)

(9

w

)S

eg

ment(w

;

E

)

Preliminary

explorations

of

this

idea

are

describ

ed

in

Thomason

and

Hobbs

(1997),

but

these

are

only

preliminary

.

The

in

v

estigation

of

quan

tit

y

implicatures

should

probably

b

e

lo

cated

at

the

lev

el

of

in

teractions

b

et

w

een

in

terpretation

and

generation.

The

sen

tence

(67)

John

has

three

c

hildren.

is

usually

not

said

when

John

has

more

than

three

c

hildren,

ev

en

though

it

is

still

true

in

those

circumstances.

The

hearer's

reasoning

w

ould

go

something

lik

e

this:

The

sp

eak

er

said

U

1

,

whic

h

could

mean

either

M

1

or

M

2

.

But

she

probably

means

M

1

,

b

ecause

if

she

had

mean

t

M

2

,

she

probably

w

ould

ha

v

e

said

U

2

.

Also

lo

cated

in

this

area

is

the

problem

of

ho

w

sp

eak

ers

are

able

to

co-construct

a

single

coheren

t

segmen

t

of

discourse,

and

sometimes

a

single

sen

tence,

across

sev

eral

con

v

ersational

turns

(e.g.,

Wilk

es-Gibbs

1986).

Learning

is

another

imp

ortan

t

researc

h

issue.

An

y

framew

ork

that

has

am

bitions

of

b

eing

a

serious

cognitiv

e

mo

del

m

ust

supp

ort

an

approac

h

to

learning.

In

the

IA

24

framew

ork,

what

is

learned

is

axioms.

A

set

of

axioms

can

b

e

augmen

ted

incremen

tally

via

the

follo

wing

incremen

tal

c

hanges:

in

tro

ducing

a

new

predicate

whic

h

is

a

sp

ecialization

of

an

old

one,

increasing

the

arit

y

of

a

predicate,

adding

a

prop

osition

to

the

an

teceden

t

of

an

axiom,

and

adding

a

prop

osition

to

the

consequen

t

of

an

axiom.

But

the

details

of

this

idea,

e.g.,

when

an

axioms

should

b

e

c

hanged,

ha

v

e

not

y

et

b

een

w

ork

ed

out.

Finally

,

there

should

b

e

a

plausible

realization

of

the

framew

ork

in

some

kind

of

neural

arc

hitecture.

The

SHR

UTI

arc

hitecture

dev

elop

ed

b

y

Shastri

and

his

colleagues

(e.g.,

Shastri

and

Ajjanagade

1993)

lo

oks

v

ery

promising

in

this

regard.

The

v

ariable

binding

required

b

y

rst-order

logic

is

realized

b

y

the

sync

hronized

ring

of

neurons,

and

the

w

eigh

ting

sc

heme

in

the

ab

duction

metho

d

is

realized

b

y

means

of

v

ariable

strengths

of

activ

ation.

But

again,

details

remain

to

b

e

w

ork

ed

out.

Ac

kno

wledgemen

ts

This

material

is

based

in

part

on

w

ork

supp

orted

b

y

the

National

Science

F

oundation

and

Adv

anced

Researc

h

Pro

jects

Agency

under

Gran

t

Num

b

er

IRI-9304961

(In

tegrated

T

ec

hniques

for

Generation

and

In

terpretation),

and

b

y

the

National

Science

F

oundation

under

Gran

t

Num

b

er

IRI-9619126

(Multimo

dal

Access

to

Spatial

Data).

An

y

opinions,

ndings,

and

conclusions

or

recommendations

expressed

in

this

c

hapter

are

those

of

the

author

and

do

not

necessarily

reect

the

views

of

the

National

Science

F

oundation.

References

[1]

App

elt,

Douglas

E.,

and

Martha

E.

P

ollac

k,

1990.

\W

eigh

ted

Ab

duction

for

Plan

Ascription",

T

ec

hnical

Note

491,

SRI

In

ternational,

Menlo

P

ark,

California,

Ma

y

1990.

[2]

Bak

er,

Collin

F.,

Charles

J.

Fillmore,

and

John

B.

Lo

w

e,

1998.

\The

Berk

eley

F

rameNet

pro

ject",

in

Pr

o

c

e

e

dings,

Thirt

y-Sixth

Ann

ual

Meeting

of

the

Asso

ciation

for

Computational

Linguistics,

pp.

86-90,

Mon

treal,

Canada,

August

1998.

[3]

Charniak,

Eugene,

1986.

\A

Neat

Theory

of

Mark

er

P

assing",

Pr

o

c

e

e

dings,

AAAI-86,

Fifth

National

Confer

enc

e

on

A

rticial

Intel

ligenc

e,

Philadelphia,

P

ennsylv

ania,

pp.

584-588.

[4]

Charniak,

Eugene,

and

Rob

ert

Goldman,

1988.

\A

Logic

for

Seman

tic

In

terpretation",

Pr

o

c

e

e

dings,

26th

A

nnual

Me

eting

of

the

Asso

ciation

for

Computational

Linguistics,

pp.

87-94,

Bualo,

New

Y

ork,

June

1988.

[5]

Charniak,

Eugene,

and

Rob

ert

Goldman,

1989.

\A

Seman

tics

for

Probabilistic

Quan

tier-F

ree

First-Order

Languages,

with

P

articular

Application

to

Story

Under-

standing",

Pr

o

c

e

e

dings,

Eleventh

International

Joint

Confer

enc

e

on

A

rticial

Intel

li-

genc

e,

pp.

1074-1079.

Detroit,

Mic

higan.

August

1989.

[6]

Charniak,

Eugene,

and

Drew

McDermott,

1985.

Intr

o

duction

to

A

rticial

Intel

ligenc

e.

Reading,

Mass.:

Addison-W

esley

Publishing

Co.

25

[7]

Charniak,

Eugene,

and

Solomon

E.

Shimon

y

,

1990.

\Probabilistic

Seman

tics

for

Cost

Based

Ab

duction",

T

ec

hnical

Rep

ort

CS-90-02,

Departmen

t

of

Computer

Science,

Bro

wn

Univ

ersit

y

,

F

ebruary

1990.

[8]

Co

x,

P

.

T.,

and

T.

Pietrzyk

o

wski,

1986.

\Causes

for

Ev

en

ts:

Their

Computa-

tion

and

Applications",

Pr

o

c

e

e

dings,

Eigh

th

In

ternational

Conference

on

Automated

Deduction(CADE-8),

pp.

608-621,

Oxford,

England.

[9]

Dasigi,

V

en

u

R.,

1988.

Wor

d

Sense

Disambiguation

in

Descriptive

T

ext

Interpr

eta-

tion:

A

Dual-R

oute

Parsimonious

Covering

Mo

del

(do

ctoral

dissertation),

T

ec

hnical

Rep

ort

TR-2151,

Departmen

t

of

Computer

Science,

Univ

ersit

y

of

Maryland,

College

P

ark,

Decem

b

er,

1988.

Also

published

as

T

ec

hnical

Rep

ort

WSU-CS-90-03,

Depart-

men

t

of

Computer

Science

and

Engineering,

W

righ

t

State

Univ

ersit

y

,

Da

yton,

Ohio.

[10]

Ginsb

erg,

Matthew

L.,

editor,

1987.

R

e

adings

in

Nonmonotonic

R

e

asoning,

Morgan

Kaufmann

Publishers,

Inc.,

Los

Altos,

California.

[11]

Grice,

H.

P

.,

1967.

\Logic

and

Con

v

ersation",

William

James

Lectures,

Harv

ard

Uni-

v

ersit

y

,

man

uscript.

[12]

Grice,

H.

P

.,

1989.

\Logic

and

Con

v

ersation",

in

Studies

in

the

Ways

of

Wor

ds,

Harv

ard

Univ

ersit

y

Press,

Cam

bridge,

MA,

pp.

22-40.

[13]

Guha,

R.

V.,

and

Douglas

B.

Lenat,

1990.

\Cyc:

A

Midterm

Rep

ort",

AI

Magazine,

V

ol.

11,

No.

3,

pp.

32-59.

[14]

Harabagiu,

Sanda,

and

Dan

Moldo

v

an,

1998.

\Kno

wledge

Pro

cessing

on

an

Extended

W

ordNet",

in

C.

F

ellbaum,

ed.,

Wor

dNet:

A

n

Ele

ctr

onic

L

exic

al

Datab

ase,

pp.

379-405.

MIT

Press,

1998.

[15]

Hewitt,

Carl

E.,

1972.

\Description

and

Theoretical

Analysis

(using

sc

hemas)

of

PLANNER:

A

Language

for

Pro

ving

Theorems

and

Manipulating

Mo

dels

in

a

Rob

ot",

T

ec

hnical

Rep

ort

TR-258,

AI

Lab

oratory

,

Massac

h

usetts

Institute

of

T

ec

hnology

,

Cam-

bridge,

MA.

[16]

Hirst,

Graeme,

1987.

Semantic

Interpr

etation

and

the

R

esolution

of

A

mbiguity,

Cam-

bridge

Univ

ersit

y

Press,

Cam

bridge,

England.

[17]

Hobbs,

Jerry

R.,

1984.

\Sublanguage

and

Kno

wledge",

T

ec

hnical

Note

329,

Articial

In

telligence

Cen

ter,

SRI

In

ternational,

Menlo

P

ark,

California,

June

1984.

[18]

Hobbs,

Jerry

R.

1985.

\On

tological

Promiscuit

y

."

Pr

o

c

e

e

dings,

23r

d

A

nnual

Me

eting

of

the

Asso

ciation

for

Computational

Linguistics,

pp.

61-69.

Chicago,

Illinois,

July

1985.

[19]

Hobbs,

Jerry

R.

1998.

\The

Syn

tax

of

English

in

an

Ab

ductiv

e

F

ramew

ork".

Av

ailable

at

http://www.isi.edu/discour

se-i

nfe

renc

e/c

hapt

er4.

pdf

.

26

[20]

Hobbs,

Jerry

R.,

William

Croft,

T

o

dd

Da

vies,

Douglas

Edw

ards,

and

Kenneth

La

ws,

1986.

\Commonsense

Metaph

ysics

and

Lexical

Seman

tics",

Pr

o

c

e

e

dings,

24th

A

nnual

Me

eting

of

the

Asso

ciation

for

Computational

Linguistics,

New

Y

ork,

June

1986.,

pp.

231-240.

[21]

Hobbs,

Jerry

R.,

Mark

Stic

k

el,

P

aul

Martin,

and

Douglas

Edw

ards,

1988.

\In

terpre-

tation

as

Ab

duction",

Pr

o

c

e

e

dings,

26th

A

nnual

Me

eting

of

the

Asso

ciation

for

Compu-

tational

Linguistics,

pp.

95-103,

Bualo,

New

Y

ork,

June

1988.

[22]

Hobbs,

Jerry

R.,

Mark

Stic

k

el,

Douglas

App

elt,

and

P

aul

Martin,

1993.

\In

terpreta-

tion

as

Ab

duction",

A

rticial

Intel

ligenc

e,

V

ol.

63,

Nos.

1-2,

pp.

69-142.

[23]

Josephson,

John

R.

and

Susan

G.

Josephson,

1990.

A

b

ductive

Infer

enc

e:

Computa-

tion,

Philosophy,

T

e

chnolo

gy,

Cam

bridge,

England.

[24]

Lak

atos,

Imre,

1970.

\F

alsication

and

the

Metho

dology

of

Scien

tic

Researc

h

Pro-

grammes",

in

Criticism

and

the

Gr

owth

of

Know

le

dge,

ed.

Imre

Lak

atos

and

Alan

Mus-

gra

v

e.

Cam

bridge

Univ

ersit

y

Press,

Cam

bridge,

England,

pp.

91-196.

[25]

Lascarides,

Alex,

and

Jon

Ob

erlander,

1992.

\Ab

ducing

T

emp

oral

Discourse",

in

R.

Dale,

E.

Ho

vy

,

D.

Rosner,

and

O.

Sto

c

k,

eds.,

Asp

e

cts

of

A

utomate

d

Natur

al

L

anguage

Gener

ation,

Springer,

Berlin,

pp.

167{182.

[26]

Lewis,

Da

vid,

1979.

\Scorek

eeping

in

a

Language

Game,"

Journal

of

Philosophic

al

L

o

gic,

V

ol.

6,

pp.

339-59.

[27]

Mahesh,

Ka

vi,

Sergei

Niren

burg,

Jim

Co

wie,

and

Da

vid

F

arw

ell,

1996.

\An

Assess-

men

t

of

Cyc

for

Natural

Language

Pro

cessing",

T

ec

hnical

Rep

ort

MCSS-96-302,

Com-

puting

Researc

h

Lab

oratory

,

New

Mexico

State

Univ

ersit

y

,

Las

Cruces,

NM,

Septem

b

er

1996.

[28]

Mann,

William,

and

Sandra

Thompson,

1986,

\Relational

Prop

ositions

in

Discourse",

Disc

ourse

Pr

o

c

esses,

V

ol.

9,

No.

1,

pp.

57-90.

[29]

McCarth

y

,

John,

1980.

\Circumscription:

A

F

orm

of

Nonmonotonic

Reasoning",

A

r-

ticial

Intel

ligenc

e,

V

ol.

13,

pp.

27-39.

Reprin

ted

in

M.

Ginsb

erg,

ed.,

R

e

adings

in

Nonmonotonic

R

e

asoning,

pp.

145-152,

Morgan

Kaufmann

Publishers,

Inc.,

Los

Altos,

California.

[30]

McDermott,

Drew,

and

John

Do

yle,

1980.

\Non-monotonic

Logic

I",

A

rticial

Intel-

ligenc

e,

V

ol.

13,

Nos.

1,2.

pp.

41-72.

April

1980.

[31]

McRo

y

,

Susan,

and

Graeme

Hirst,

1991.

\An

Ab

ductiv

e

Accoun

t

of

Repair

in

Con-

v

ersation",

Working

Notes,

AAAI

F

all

Symp

osium

on

Discourse

Structure

in

Natural

Language

Understanding

and

Generation,

Asilomar,

California,

No

v

em

b

er

1991,

pp.

52-57.

[32]

Miller,

George

A.,

1995.

\W

ordNet:

A

Lexical

Database

for

English",

Communic

a-

tions

of

the

A

CM,

V

ol.

38,

No.

11,

p.

3941,

No

v

em

b

er

1995.

27

[33]

Morgan,

Charles

G.,

1971.

\Hyp

othesis

Generation

b

y

Mac

hine",

A

rticial

Intel

li-

genc

e,

V

ol.

2,

pp.

179-187.

[34]

Nagao,

Katashi,

1989.

\Seman

tic

In

terpretation

Based

on

the

Multi-W

orld

Mo

del",

In

Pr

o

c

e

e

dings

of

the

Eleventh

International

Confer

enc

e

on

A

rticial

Intel

ligenc

e

,

pp.

1467-1473,

Detroit,

Mic

higan.

[35]

Newton,

Isaac,

1934

[1686].

Mathematic

al

Principles

of

Natur

al

Philosophy,

V

ol.

1:

The

Motion

of

Bo

dies,

and

V

ol.

2:

The

System

of

the

World,

translated

b

y

Andrew

Motte

and

Florian

Ca

jori,

Univ

ersit

y

of

California

Press,

Berk

eley

,

California.

[36]

Ng,

Hw

ee

T

ou

and

Ra

ymond

J.

Mo

oney

,

1990.

\The

Role

of

Coherence

in

Ab

ductiv

e

Explanation".

Pr

o

c

e

e

dings,

Eigh

th

National

Conference

on

Articial

In

telligence,

pp.

337-342,

Boston,

MA,

August

1990.

[37]

Norvig,

P

eter,

1983.

\F

rame

Activ

ated

Inferences

in

a

Story

Understanding

Pro-

gram",

Pr

o

c

e

e

dings

of

the

8th

International

Joint

Confer

enc

e

on

A

rticial

Intel

ligenc

e,

Karlsruhe,

W

est

German

y

,

pp.

624-626.

[38]

Norvig,

P

eter,

1987.

\Inference

in

T

ext

Understanding",

Pr

o

c

e

e

dings,

AAAI-87,

Sixth

National

Confer

enc

e

on

A

rticial

Intel

ligenc

e,

pp.

561-565,

Seattle,

W

ashington,

July

1987.

[39]

Norvig,

P

eter,

and

Rob

ert

Wilensky

,

1990.

\A

Critical

Ev

aluation

of

Commensurable

Ab

duction

Mo

dels

for

Seman

tic

In

terpretation",

in

H.

Karlgren,

ed.,

Pr

o

c

e

e

dings,

Thir-

teen

th

In

ternational

Conference

on

Computational

Linguistics,

Helsinki,

Finland,

V

ol.

3,

pp.

225-230,

August,

1990.

[40]

P

earl,

Judea,

1988.

Pr

ob

abilistic

R

e

asoning

in

Intel

ligent

Systems:

Networks

of

Plau-

sible

Infer

enc

e,

Morgan

Kaufmann

Publishers,

Inc.,

San

Mateo,

California.

[41]

Pierce,

Charles

Sanders,

1955.

\Ab

duction

and

Induction",

in

Justus

Buc

hler,

editor,

Philosophic

al

Writings

of

Pier

c

e,

pp.

150-156,

Do

v

er

Bo

oks,

New

Y

ork.

[42]

P

ollard,

Carl,

and

Iv

an

A.

Sag,

1994.

He

ad-Driven

Phr

ase

Structur

e

Gr

ammar,

Uni-

v

ersit

y

of

Chicago

Press

and

CSLI

Publications.

[43]

P

ople,

Harry

E.,

Jr.,

1973,

\On

the

Mec

hanization

of

Ab

ductiv

e

Logic",

Pr

o

c

e

e

dings,

Thir

d

International

Joint

Confer

enc

e

on

A

rticial

Intel

ligenc

e,

pp.

147-152,

Stanford,

California,

August

1973.

[44]

Ra

yner,

Mann

y

,

1993.

A

b

ductive

Equivalential

T

r

anslation

and

its

applic

ation

to

Nat-

ur

al

L

anguage

Datab

ase

Interfacing,

Ph.D.

thesis,

Ro

y

al

Institute

of

T

ec

hnology

,

Sto

c

k-

holm,

Septem

b

er

1993.

[45]

Reggia,

James

A.,

1985.

\Ab

ductiv

e

Inference",

in

K.

N.

Karna,

editor,

Pr

o

c

e

e

dings

of

the

Exp

ert

Systems

in

Government

Symp

osium,

pp.

484-489,

IEEE

Computer

So

ciet

y

Press,

New

Y

ork.

28

[46]

Reggia,

James

A.,

Dana

S.

Nau,

and

P

earl

Y.

W

ang,

1983.

\Diagnostic

Exp

ert

Sys-

tems

Based

on

a

Set

Co

v

ering

Mo

del",

International

Journal

of

Man-Machine

Studies,

V

ol.

19,

pp.

437-460.

[47]

Reiter,

Ra

ymond,

and

Gio

v

anni

Criscuolo,

1981.

\On

In

teracting

Defaults",

Pr

o-

c

e

e

dings,

Sev

en

th

In

ternational

Join

t

Conference

on

Articial

In

telligence,

pp.

270-276,

V

ancouv

er,

BC,

August

1981.

[48]

Shastri,

Lok

endra,

and

V

enk

at

Ajjanagadde,

1993.

\F

rom

Simple

Asso

ciations

to

Sys-

tematic

Reasoning:

A

Connectionist

Represen

tation

of

Rules,

V

ariables

and

Dynamic

Bindings

Using

T

emp

oral

Sync

hron

y",

Behavior

al

and

Br

ain

Scienc

es,

V

ol.

16,

pp.

417-

494.

[49]

Shoham,

Y

oa

v,

1987.

\Nonmonotonic

Logics:

Meaning

and

Utilit

y",

Pr

o

c

e

e

dings,

International

Joint

Confer

enc

e

on

A

rticial

Intel

ligenc

e,

pp.

388-393.

Milano,

Italy

,

August

1987.

[50]

Sp

erb

er,

Dan,

and

Deirdre

Wilson,

1986.

R

elevanc

e:

Communic

ation

and

Co

gnition,

Harv

ard

Univ

ersit

y

Press,

Cam

bridge,

Massac

h

usetts.

[51]

Stic

k

el,

Mark

E.,

1988.

\A

Prolog-lik

e

Inference

System

for

Computing

Minim

um-

Cost

Ab

ductiv

e

Explanations

in

Natural-Language

In

terpretation",

Pr

o

c

e

e

dings

of

the

International

Computer

Scienc

e

Confer

enc

e-88,

pp.

343{350,

Hong

Kong,

Decem

b

er

1988.

Also

published

as

T

ec

hnical

Note

451,

Articial

In

telligence

Cen

ter,

SRI

In

terna-

tional,

Menlo

P

ark,

California,

Septem

b

er

1988.

[52]

Thomason,

Ric

hmond

H.,

1990.

\Accommo

dation,

Meaning,

and

Implicature:

In

ter-

disciplinary

F

oundations

for

Pragmatics",

in

Intentions

in

Communic

ation,

P

.

Cohen,

J.

Morgan,

and

M.

P

ollac

k,

editors,

Bradford

Bo

oks

(MIT

Press),

Cam

bridge,

Mas-

sac

h

usetts,

pp.

325-364.

[53]

Thomason,

Ric

hmond

H.,

and

Jerry

R.

Hobbs,

1997.

\In

terrelating

In

terpretation

and

Generation

in

an

Ab

ductiv

e

F

ramew

ork",

Pr

o

c

e

e

dings,

AAAI

F

all

Symp

osium

W

ork-

shop

on

Comm

unicativ

e

Action

in

Humans

and

Mac

hines,

Cam

bridge,

Massac

h

usetts,

No

v

em

b

er

1997,

pp.

97-105.

[54]

W

ason,

P

.

C.,

and

Philip

Johnson-Laird,

1972.

Psycholo

gy

of

R

e

asoning:

Structur

e

and

Content,

Harv

ard

Univ

ersit

y

Press,

Cam

bridge,

MA.

[55]

Wilensky

,

Rob

ert,

1983.

Planning

and

Understanding:

A

Computational

Appr

o

ach

to

Human

R

e

asoning,

Addison-W

esley

,

Reading,

Massac

h

usetts.

[56]

Wilensky

,

Rob

ert,

Da

vid

N.

Chin,

Marc

Luria,

James

Martin,

James

Ma

yeld,

and

Dek

ai

W

u,

1988.

\The

Berk

eley

UNIX

Consultan

t

Pro

ject",

Computational

Linguistics,

v

ol.

14,

no.

4,

Decem

b

er

1988,

pp.

35-84.

[57]

Wilk

es-Gibbs,

Deanna,

1986.

\Collab

orativ

e

Pro

cesses

of

Language

Use

in

Con

v

er-

sation",

Ph.

D.

dissertation,

Departmen

t

of

Psyc

hology

,

Stanford

Univ

ersit

y

.

Stanford,

California.

29

[58]

Winograd,

T

erry

,

1972.

Understanding

Natur

al

L

anguage,

Academic

Press,

New

Y

ork.

[59]

W

ol,

Christian,

1963

[1728].

Pr

eliminary

Disc

ourse

on

Philosophy

in

Gener

al,

R.

J.

Blac

kw

ell

(trans.),

Bobbs-Merrill,

Indianap

olis

IN.

30