< CBA to Paraphrasing & Nominalization, Dec. 2nd, 2010 >Typology of Paraphrases
and Approaches to Compute Them
Atsushi FUJITA
Future University Hakodate, JAPANhttp://paraphrasing.org/~fujita/ Intentional deﬁnition
e.g., LDOCE(v) to express in a shorter, clearer, or different way
what someone has said or written(n) a statement that expresses in a shorter, clearer, ordifferent way what someone has said or written2 Extensional deﬁnition

lexical, phrasal, sentential, discourse-level, ...
 covered all? well-organized?


The riddle is solved by me.

Employment showed a sharp decrease.

I solved the riddle.

Employment decreased sharply.

Emma burst into tears and he tried to comfort her.
Emma cried, and he tried to console her.
 Scope / boundaryNot precisely deﬁned

I want some fresh air.

My son eats eggplants.

Could you open the window?

My son likes eggplants.

3 Axes

Structure Required knowledge
 Application
 Sameness and diﬀerence of meaning Guidepost

To clarify how human beings process paraphrases
 To automate paraphrases (steadily)Clarify required resources for each type Modularize each type for selective use

Artiﬁcial, so not be crazy4 A survey

Share the idea
 Discuss the way of creating typology

e.g., Axes

Involve people for creating typologies

e.g., http://paraphrasing.org/paraphrase.html

5Outline
1.
2.
3.
4.
5.

Sameness of meaning
Linguistically-motivated typology
Paraphrases in apps
Computation
Future directions Semantics

Formal semantics
 Situation semantics
Discourse representation theory [Kamp, 81]
 Mental-space theory [Fauconnier, 85]

Lexical semantics
Frame semantics [Fillmore. 76]
 Lexical Conceptual Structure [Jackendoff, 90]
 Generative Lexicon [Pustejovsky, 95]7 A good subject

To think of equality
 Toward semantic computingHow to drive semantic frameworks

 Levels of sameness [Sato, 99]
 Pragmatic meaning Referential meaning Denotation8 Illocutionary / perlocutionary acts

I want some fresh air.
Could you open the window?
Hearerʼs interpretation
Speaker wants me to open
the window to get fresh air.
Various interpretation
But, only the speaker knows truth9 Coreference

Barça’s #10 scored no goal in the last El Clásico.
Lionel Messi scored no goal in the last match against Real Madrid.
in 2008-2011
Barçaʼs eye view

May not true in the other situatione.g., Ronaldinho, Riquelme, Rivaldo, ...
 e.g., against Barça, between Barça and Real

Discourse-levelincl. exophora Cognitive meaning [Milićević, 07]

10 Truth-value semantics

Tom bought a car from John.
John sold a car to Tom.
Can be carried out
Without referring to the communicative situation
 With linguistic knowledge (With world knowledge)Have diﬀerent connotation [Edmonds, 99][Inkpen+, 06]
Theme / Rheme
 Formality
 Emotion (attitude)

11 It supposes some diﬀerences(v) to express in a shorter, clearer, or different way
what someone has said or written(n) a statement that expresses in a shorter, clearer, ordifferent way what someone has said or written
Not exactly same meaning (synonym) [Clark, 92]
 But near-synonym [Edmonds, 99]

12

[Edmonds, 99]
ActivityACTOR

ATTRIBUTE

PersonDeviation

CORE denotation

ATTRIBUTE

Stupidity

ACTEE

Criticism

Misconception

ATTRIBUTE

Pejorative

CAUSE-OF

ACTOR

Severitylow

DEGREE“blunder”“error”

highlow

mediumhighConcreteness13 Whatʼs changed?

complex  simple
 verbose  clear
 marked  unmarked
 emotional  neutral Reasons why we paraphraseTo facilitate communication
For conﬁrmation
 For accelerating understanding

To strengthen the solidarity in a community
14 Linguistic variability in conveying a meaningrisk of receiving a severe wound
Variability
possibility to be seriously injured
Ambiguity
Mouse

Meaning

Linguistic exp.
15

 Relation between diﬀerent meanings

Mouton & Co. is the publisher
that published Noam Chomsky’s
Syntactic Structures in 1957.
Entailment

Inference

Textual inference
Textual entailment
The author of Syntactic Structures
is Noam Chomsky.
Mouton & Co. gained much with
Chomsky’s Syntactic Structures.

Meaning

Linguistic exp.
16 Not necessarily same meaningXY
Mouton & Co. is the publisher that published Noam
Chomsky’s Syntactic Structures in 1957.
The author of Syntactic Structures is Noam Chomsky.

e.g., lexical entailment in WordNet [Miller+, 85]
marchwalk Troponymy

forgetknow Backward presupposition

has startedオ

started Temporal17 Not ensure even truth

Mouton & Co. is the publisher that published Noam
Chomsky’s Syntactic Structures in 1957.
Mouton & Co. gained much with Chomsky’s Syntactic Structures.
 But useful in some situations [Pantel+, 07]

My son eats eggplants.

Everything is imported to Japan.

My son likes eggplants.

Everything is eaten in Japan.

18

 Levels of sameness [Sato, 99]

Pragmatic meaning Referential meaning Denotation
 Related concepts
 Entailment: paraphrase  bi-directional entailment
 Inference: entailment
always-true inference19Outline
1.
2.
3.
4.
5.

Sameness of meaning
Linguistically-motivated typology
Paraphrases in apps
Computation
Future directions

 Names used in papers

Lexical / Phrasal
 Syntactic Sentential Classiﬁcation in [IWP, 2005]
 Phrase-level Sentence-level Discourse-levelNot necessarily atomic, because
methods and results are centered21 Focused on denotation


Explainable referring to
The given context
 Linguistic knowledge

Ignored diﬀerences in connotation

 5 types based on Inﬂuenced scope Generality (or productivity)

22

Discourse Clause separation (relative clause)Småland, which is located to the south-west of Stockholm,
is called “The Kingdom of Glass”. The reason is that there
are sixteen glass manufacturers in this area.
Småland is located to the south-west of Stockholm. It iscalled “The Kingdom of Glass”. The reason is that there
are sixteen glass manufacturers in this area.
 Conjunction replacement

Note down the number. Otherwise, you may forget it.
Note down the number. If not, you may forget it.

23

Discourse Cleft  non-cleft

It was his best suit that John wore to the dance last night.
John wore his best suit to the dance last night.
 Head-switch (clausal complement  modiﬁer)

The conference venue is the building whose roof is red.
The conference venue is the building with red roof.
 Move of negation

Your application is canceled if you do not reply.
Your application is not canceled if you reply.
 Embedded  coordinate, reordering, etc.
24Generalizable
X solve Y

Y is solved by X

X gives Y a fright

Y is frightened of X

X is in our favor

X is favorable to us

X show a sharp decrease

X decrease sharply

X be the author of Y

X wrote Y

X comfort Y

X console Y

pass awaydieburst into tears

cried

Non-generalizable
25

Syntax
 Inversion

If I had money enough, ...

Independent of thesucceeding clause

Had I money enough, ...
 Move of adverb

She can speak English fluently.
She can fluently speak English.
 Paraphrase of negation

He drank nothing but famous spirits.
All he drank were famous spirits.
 Less variation
26

Lexical Synonymy
 Not generalized at all Need to collect thoroughly
There’s a risk of receiving a severe wound.

N, AdjThere’s a possibility of receiving serious injure.
Emma burst into tears and he tried to comfort her.

V, VP

Emma cried, and he tried to console her.
Regards this as lexical?
Itʼs indecomposable any morelarge VP

Real Sociedad snapped a two-game losing streak.
Real Sociedad got points for the first time in three games.
27

Syn/LexSem Seems to be syntactic paraphraseBut have lexical constraints to some degree
John smeared paint on the wall.
John smeared the wall with paint.
Employment showed a decrease.
Employment decreased.



Required information


Lexico-semantic information
Fine-grained argument structure Lexical derivation, antonym, etc.
Selectional preference, collocation
28

[Levin, 93]
 Passive to active

 Dative alt.

The riddle is solved by him.

Bill sold a car to Tom.

He solved the riddle.

Bill sold Tom a car.

 Locative alt.

 Source alt.

John smeared paint on the wall.

The well gushed oil.

John smeared the wall with paint.

Oil gushed from the well.

 Reciprocal alt.

The car collided with the bicycle.
The car and the bicycle collided.

 Transitivity alt.

(entailment)
Janet broke the cup.
The cup broke.

29 Light-verb construction (N  V), A  Adv

Employment showed a sharp decrease.
Employment decreased sharply.
 Adj  V

I visited a priest in the old temple.
I visited a priest in the olden(ed) temple.
 Adj  N

I feel drowsy.
I have a drowsiness.

30

 Head-switch (NP), N  V

We need an improvement of recycling system.
We need an improved recycling system.
 Head-switch (VP), V  Adv, N  V

He hurried to check it.
He checked it in a hurry.
 Move of quantiﬁer

We performed two transactions in this morning.
We performed transactions twice in this morning.

31 A linguistically motivated typology[A] Extra-sentential
Cohesion
Generality[B] Extra-clausal[C] Pure syntactic[D] Morpho-syntactic paraphrase[E] Lexical (word, phrasal)
Denotation # of Instances Focused on denotation
 Atomicity
 Scope Generality
32 On the typologyLess [C] Pure syntactic paraphrases

After all, inter-clausal vs intra-clausal (within a VP)

Treatment of indecomposable ones

 Lexical semantics for [D] FrameNet [Baker+, 98]
 VerbNet [Kipper+, 00]
 Lexical Conceptual Structure [Jackendoff, 91]
 Generative Lexicon [Pustejovsky, 95]

33

Outline
1.
2.
3.
4.
5.

Sameness of meaning
Linguistically-motivated typology
Paraphrases in apps
Computation
Future directions

Paraphrase Generation
Writing aid
Reading aid
Post-process
for MT

Consumedby human

Pre-process
for TTS

Pre-process
for MT

Summarization

Consumedby machine

Multi-document
summarization

Look up TM

QA

IR

IE

DM

inside of MT

Paraphrase Recognition35

 Target types of paraphrases
 Diﬀerences accepted Connotation
Theme/Rheme
 Formality
 Emotion (attitude)

Denotation
Entailment
 Inference Full-auto / consumed by human36 Multi-document summarization [Barzilay, 03]37 Pre-edit for machine translation [Shirai+, 98]

データは無料で配布する予定だ
MT system*The data is a plan that distributes freely.

我々は + データを無料で配布する + つもりだ
MT system

We plan to distribute the data freely.

Not only paraphrase, but also anaphora resolution
 Entailment / inference cannot be not applied

38 Data mining

Summary of events [Izumi+, 10]
Light-verb construction
 Keep factuality, but not some aspectual info.


try to get the first prize≠

get the first prize≠

began to repair
repaired=

has started
startedCollecting instances of plausible events
Discover unknown unknowns [Torisawa+, 08]
 Build statement maps [Murakami+, 09]39 Writing aid (information dispatching aid)Showing alternatives [Max+, 08]

Easier, clearer, more-decorative, etc.

Automatic rewriteNormalization of speciﬁc documentse.g., technical manuals, health reports

 Reading aid (information consuming aid)

Simplifying texts [Carroll+, 98][Canning+, 99][Inui+, 03]
 Adding explanatory information

e.g., gloss of words, related terms

40 Text simpliﬁcation for reading aid [Inui+, 03]41

 Typology and modularization are necessary

IR IE DM MT Writing Reading[A] Extra-sentential[B] Extra-clausal[C] Pure syntactic[D] Morpho-syntactic[E] Lexical
Focus
Formality
EmotionEntailment
Inference42

Outline
1.
2.
3.
4.
5.

Sameness of meaning
Linguistically-motivated typology
Paraphrases in apps
Computation
Future directions

Phase 1. Knowledge development

Acquisition

Handcrafting patterns
 Automatic acquisition (corpus, Web)

Phase 2. Use of knowledge

Recognition
Generation

Segmentation and disambiguation
 Applicability check in the given context
Grammaticality
 Semantic appropriateness Equivalency of meaningPhase 3. Tuning for apps
e.g., simpliﬁcation, reduction of homonyms, etc.
44Paraphrase Acquisition
1st phase towardautomatic paraphrasing Handcrafting patterns

Transformation rules [Mel’cuk+, 87][Dras, 99][Jacquemin, 99]
 Thesaurus (of words) [A lot of work] Automatic acquisition
 Distributional similarity in a single corpus[Lin+, 01][Torisawa, 01][Hagiwara+, 06], etc.
 Alignment of parallel/comparable/bilingual corpus[Barzilay+, 01][Shinyama+, 02][Pang+, 03][Ibrahim+, 03][Dolan+, 04][Bannard+, 05], etc.
 From the Web [Szpektor+, 04]
 Implicit modeling Statistical translation model [Quirk+, 04][Bannard+, 05]
 Tree kernel [Collins+, 01][Takahashi, 05]

46

[A-D]
 For a sentenceTransformation grammar [Harris, 81]

NP1 V1 (+AUX) V2 (-AUX) NP2 Active  Passive
 NP2 V1 BE V2-PP by NP1
 Meaning-text Theory [Mel’čuk+, 87]
X


I
Y


Oper1(S0(X))
I

II

Y

S0(X)

VP 
Light-verb construction

Various types of rules [Takahashi+, 01]47

[E] Near-synonyms: words within the same synset
e.g., WordNet [Miller+, 85]02526085: achieve, accomplish, attain, reach
05793554: basis, base, cornerstone, foundation, ...
achieve  accomplishbase  basis

Just near-synonym [Clark, 92]
Subtle diﬀerence [Edmonds, 99]
 Static synonymy apart from context [Fujita+, 00]How to enlarge thesaurus?
Neologisms
google (v)  search Web using Google Named entities


Future University Hakodate  FUN

48

[B-E] Distributional hypothesis [Harris, 64]

Semantically similar words tend to appear in similar
contexts.
 e.g., VP  NP [Lin+, 01][Torisawa, 02]subj- commission- committee- government
- he
-I
-…

find

obj

a solution

Compute similarity
mod

to

pcomp

- strike- civil war- crisis- problem- situation
-…

subj

- commission- clout- government
- he
- she
-…

solve

obj

- problem- crisis- mystery- woe- crime-…

X find a solution to Y  X solve 49
Y[B-E]
 With multiple-sequence alignment

Multiple verbalizations of proofs [Barzilay+, 03] Multiple translations [Pang+, 03]flattenedtolevelled’sdetroit
*e*

Begin

a

*e*
building*e*building
blastedindetroit*e*toleveled
*e*

End

*e*

razed

was

groundtheleveled

into

ashes

down

reducedtorubble50

[B-E] News articles reporting the same event

Named entities as anchor [Shinyama+, 02]
minimal paraphrase

in Hong Kong
two more people

LOCATION-node
NUMBER-node
predicate-nodeinsubject

have diedobjecttwo more deathobjectthe government

subject

Hong Kong

subject

has announced

reported
51

[B-E]
 Phrases translated into the same phraseTranslation table of SMT [Bannard+, 05]

what is more, the relevant cost dynamic is completely under control
im ubrigen ist die diesbezugliche kostenentwicklung vollig unter kontrolle
wir sind es den steuerzahlern schuldig die kosten unter kontrolle zu haben
we owe it to the taxpayers to keep the costs in checkunder control

in check52

[C-E]
Generalizable
X solve Y

Y is solved by X

X gives Y a fright

Y is frightened of X

X is in our favor

X is favorable to us

X show a sharp decrease

X decrease sharply

X be the author of Y

X wrote Y

X comfort Y

X console Y

pass awaydieburst into tears

cried

Generate& Validate

Collect

Non-generalizable53

[D] Generation of knowledge [Fujita+, 07;08]


Syntactic transformation + Lexical derivation

X solve Y

XVY

Y is solved by X

Y be V-PP by X

X gives Y a fright

X give Y a Z

Y is frightened of X

Y be v(Z)-PP of X

X is in our favor

X be in Z’s Y

X is favorable to us

X be adj(Y) to Z

X show a sharp decrease

X show a A Y

X decrease sharply

X v(Y) adv(A)generate
instancesvalidate54 IssuesHow to cover various types of paraphrases?
 e.g., knock oﬀ each type (typology-based) Current status

Type
Handcraft[A] Extra-sentential○[B] Extra-clausal○[C] Pure syntactic○[D] Morpho-syntactic△[E] LexicalーManageable

Too noisy

Corpus
Combi
ー
ー
△
ー
Promising
△
ー
△
○
○
ー
Low coverage
Promising55

Phase 1. Knowledge development

Acquisition

Handcrafting patterns
 Automatic acquisition (corpus, Web)

Phase 2. Use of knowledge

Recognition
Generation

Segmentation and disambiguation
 Applicability check in the given context
Grammaticality
 Semantic appropriateness Equivalency of meaningPhase 3. Tuning for apps
e.g., simpliﬁcation, reduction of homonyms, etc.
56

 Paraphrase recognition/identiﬁcationGiven pair of linguistic expressions  label


Theme of machine learning research

give an advice,

give a copy

copy

make a copy,,

advisecopy

 Paraphrase generation
 Numerous outputs

investigate the cause of a fire


{＝, }

incl. unseen expressions＝≠＝
investigate why there was a fire
investigate what started a fire
make an investigation
into the cause of a fire57

Paraphrase Generation
Example of 2nd phase towardautomatic paraphrasingParaphrase
Knowledge

Step 1.
Candidate generation

Statistical
統計モデル
Models
統計モデル
Step 2. Assessment
Rules
59

Paraphrase
Knowledge

Step 1.
Candidate generation

 TransferApproach to MT in ʼ70〜ʼ80
Assume compositionality
 Substitute parts of input structure Transducer Accept sequence (structure is encoded)60

[A-E][Takahashi+, 01]
PAST
X2

COP
THEME

X3

only

COMP

spiritsdrinkfamous

X4
X5

X1(Particle: は)(Particle: の)

(VMS)

(V)

(COP: だ)

X6

X4

(Particle: だけ)

X7

X5

(N)

X9
X7

X8

(AUX: ない)

(VMS)

PAST

(V)

(Particle: しか)

NEG

(N)

drink

NOM

All he drank were famous spirits.

He

He drank nothing but famous spirits.

NOM

only

He

spirits
famous61 At the (shallow) syntax level

Minimal standard for various apps
 Backed up by matured parsing technology
 Many acquisition methods work at the same level Discussion
 How wide range can be realized at this level?
 How semantic constraints are incorporated?
e.g., lexical semantics for [D] Leave until the assessment step?


62

[Fujita+, 04]
BECOMEBECOMEBE WITH

BE WITH[Ken] zMOVE FROM TO

NOM[inspiration] y [film] x
ACC[Ken] z[Ken] z[film] x[Ken] y

NOM

ACC

DAT

to receive
Ken-NOM

Semantic transfer

ACT ON

Syntactic transfer

inspiration-ACC
film-DATKen receives an inspiration from the film.

to inspire-PASSIVE-???????
KenKen-NOM???
filmfilm-DAT???

Ken is inspired by the film.

63 Recovering meaning using GL frameworkComputing metonymy and default[Vila+, soon]

John began the book.
John began reading the book.
book
ARGSTR =ARG1 = x: info
ARG2 = y: physobj
info・physobj

QUALIA=

FORMAL =
TELIC
=
=
AGENT

hold(y, x)read(e1, w, x.y)write(e2, z, x.y)64 Because knowledge is static

Grammaticality
 Semantic appropriateness Equivalency of meanings in the context
 Filtering, correction, ranking

Rule-based Statistical
approachStatistical
統計モデル
Models
統計モデル
Step 2. Assessment
Rules
65

[Takahashi+, 01]
PAST
Conjugation

COP
THEME

only

COMP

spiritsdrinkfamousPAST

NEG-conj

NEG

Topicalization
TOP

NOM

All he drank were famous spirits.

He

He drank nothing but famous spirits.

drink
NOM

only

He

spirits
famous66

 Grammaticality: statistical language modelCollocation

e.g., <V, Slot, N> [Fujita+, 04][Pantel+, 07]

Global grammaticality of sentences [Wan, 05]

 Semantic appropriateness Compare gloss and context [Okamoto+, 03]
 Equivalency of meanings in the context
 Suitability for the given context[Pantel+, 07][Szpektor+, 08]67

 Decoding from latticeMultiple-sequence alignment [Barzilay+, 03]

Learn whole sentence

Statistical machine translation [Quirk+, 04]Use learned phrase table

flattenedtolevelled’sdetroit
*e*

Begin

a

*e*
building*e*building
blastedindetroit*e*toleveled
*e*

End

*e*

razed

was

groundtheleveled

into

ashes

down

reducedtorubble68 Application of knowledge to a certain context

Inﬂuence of paraphrase to the context
 How to deal with generality and idiosyncrasy?
 Two approaches

Transfer + assessment
 Transducer Viewpoints of assessment

Grammaticality
Discussed
 Semantic appropriateness Equivalency of meanings in contextNot yet explored69

Outline
1.
2.
3.
4.
5.

Sameness of meaning
Linguistically-motivated typology
Paraphrases in apps
Computation
Future directions

Phase 1. Knowledge development
How to cover various types of paraphrases?
 Not enough

Need a formalism and a resource repository

Phase 2. Use of knowledge

How to deal with generality and idiosyncrasy?
 Some levels on grammaticality  More studies on “paraphrase in context”

We ask users in generation-type apps

Phase 3. Tuning for apps

How to selectively use each type of paraphrases?
 No cross-application platform. Modularization!!
71 Establishing the way to compile the typology
incl. infrastructure: community, portal

 Parallelism
散歩に出かける

take a walk

散歩する

walk

faire une promenade
dar un paseo

promenerpasear72

Thank you
Acknowledgment
My ex-supervisor: Prof. Kentaro INUIMy ex-boss: Prof. Satoshi SATO
http://paraphrasing.org/~fujita/