< IJCNLP 2008, Jan. 10th, 2008 >Computing Paraphrasability of Syntactic Variants
Using Web Snippets
Atsushi FUJITA and Satoshi SATO
Nagoya Univ., Japan

Automatic Paraphrasing
Fundamental in NLP
Recognition: IR, IE, QA, Multi-Doc.Summarization
 Generation: MT, TTS, Authoring aidsResources requiredHandcrafted knowledge
Thesauri [Many work] Transformation rules [Mel’cuk+, 87] [Dras, 99] [Jacquemin, 99]Automatic knowledge acquisition
Distributional similarity [Lin+, 01] [Szpektor+, 04]
 Aligning comparable/bilingual corpora [Many work]
2Paraphrase Knowledge
Template-like representation


Lexical paraphrases
X wrote Y

X is the author of Y

X solves Y

X deals with Y

Morpho-syntactic paraphrases (syntactic variants)
XVY

Y be v(Z)-PP by X

X show a A YPassivization

X v(Y) adv(A)Lack of applicability conditions

Removing light-verb

incorrect results3

Task Description
Computing paraphrasability between phrases


Input: automatically generated paraphrase candidates


Pair of original and generated phrases (s and t)
We hurry checking it

We check it in a hurrystOutput: paraphrasability score [0,1]Is t grammatical ?
 Does t hold if s holds ? (semantic equivalence or inclusion) Is t syntactically substitutable for s in some context ?
4Issues and Solutions
How to measure similarity between phrases ?
Contextual similarity: distributional similarity

Bag of words / Bag of dependency relations

Constituent similarity: handling syntactic variants

Syntactic transformation + Lexical derivation

How to deal with data sparseness problem ?
Collect example sentences of phrases from Web snippetsAssessing grammaticality

5Outline
1.

Task Description

2.

Paraphrases Handled

3.

Proposed Method
Experiments
Discussion
Conclusion

4.
5.
6.

Paraphrases of Predicate Phrases
Symmetricvs.

Asymmetric

X change Y

X modify Y

X sprint

Equivalent / Inclusion / Entailment vs.
X change Y
X sprint

X modify Y
X run

X run

Inference

X married Y

X dated Y

X snore Y

X sleep Y

Lexicalvs.

Morpho-syntactic

X change Y

X modify Y

X show a A Y

X v(Y) adv(A)7

Paraphrases Handled
Morpho-syntactic paraphrases (syntactic variants)
Syntactic transformation + Lexical derivation
Constituent similarity is guaranteed a little
 e.g. Head-switching, Light-verb construction, Category-shiftClimate is in our favor

Climate is favorable for us

We hurry checking it

We check it in a hurry

Predicate phrases of Japanese
kakunin-oisogu

checking-ACC
to hurry
to hurry checking it

isoidekakunin-suruin a hurry to checkto check it in a hurry8Syntactic Variant Generator for Japanese
kakunin : o : isogu
NC V

checking: ACC: to hurry[Fujita+, 07]

Trans. Pat.
N:C:V ⇒ adv(V):vp(N)adv(isogu) : vp(kakunin)
Lex. Func.
adv(V)
isoide{v(kakunin) : genVoice() : genTense()}Lex. Func.
v(N)kakunin-suru

Gen. Func.
vp(N)Gen. Func.
genVoice()

Gen. Func.
genTense(){φ, reru/rareru, seru/saseru}{φ, ta/da}

isoide : {kakunin-suru : {φ, reru/rareru, seru/saseru} : {φ, ta/da}}9

Outline

2.

Task Description
Paraphrases Handled

3.

Proposed Method

4.

Experiments
Discussion
Conclusion

1.

5.
6.

Overviews kakunin-o

isogu

CandidateGeneration

kakunin-suru t

isoideto hurry checking it

to check it in a hurry

1.Snippet
RetrievalSnippets

1.SnippetRetrieval

AnchorSnippets

mimoto2.Feature
Extraction

identity

Features2.Feature
Extraction

Features3.Paraphrasability
Computation

Paraphrasability score Par (s⇒t)
11

Step 1. Snippet Retrieval``Phrase search’’
Yahoo! JAPAN Web-search API
 500 top snippets
12

Step 2. Feature Extraction
HITS: # of pages Yahoo! API returns


Larger HITSt is more likely grammatical

BOW: content words around the phrase in snippets
BOWs surrounding s and t have similar distributions and t are semantically similar

MOD: modifiers and modifiees of the phrase in snippetss and t share a number of modifiers and modifieess and t are syntactically substitutable
13

Extracting MOD Features
Modifier / modifiee chunk (bunsetsu)
Relation types (Depend / Appositive / Parallel) Base form of the head-word (content word) Some types of functional words (if any)

yotei-daSentence within snippet(dependency tree)

kenshou-suru
saigen-sei-ojikken-kekka-no
kare-nokuwashiku

Given phrase

Modifiee/D: yoteiFeatures(plan)

Modifier/D: kuwashii(in detail)

Modifier/D: kare_no(his)(I am) planning to verify the reproducibility of his experimental result in detail.

14

Step 2. Feature Extraction (Anc)
Source-focused feature extraction

1. Determine anchor a which strongly associates with s

Noun which most frequently modifies s (one of MOD features)semi-oukaberu

smile-ACC to show
be smilingdoriburu-deamanmenfrom ear to ear

kakeagaru

saido

dribble-withto run
to overlap by dribbling

to go upside

2. Retrieve snippets for s AND a and t AND a 3. Extract BOW and MOD features from those snippets
15

Step 3. Paraphrasability Computation
Lin: Lin’s measure [Lin+, 01]

Fs, Ft : Feature sets for s and t
 w(x, f) : Weight of feature f in Fx (frequency in snippets)
skew: α-skew divergence [Lee, 99]

Ps = P(f | s), Pt = P(f | t)
 α : approximation degree of KL divergence [0,1]16Summary
Features: Contextual features of entire phrase
c.f. Marginal features [Torisawa, 06] [Pantel+, 07]
 BOW, MOD

Weight of features: Frequency in snippets
c.f. pair-wise MI [Lin+, 01] [Pantel+, 07] c.f. Relative Focus Feature [Geffet+, 05]
DS measures
Lin’s measure (symmetric) [Lin+, 01] α-skew divergence (asymmetric) [Lee, 99]
17Outline

3.

Task Description
Paraphrases Handled
Proposed Method

4.

Experiments

5.

Discussion
Conclusion

1.
2.

6.

Setup: Candidate Generation
6 basic phrase types
Most frequent 1,000+ phrases for each type
Mainichi newspaper corpus (1991-2005, 1.5GB)
 Referring to dependency trees


Syntactic variant generator for Japanese [Fujita+, 07]
Trans. Pat.
N:C:V ⇒ adv(V):vp(N)Gen. Func.
vp(N)Lex. Func.
adv(V)

19

Examples of Phrases
N:C:V

N:C:Adv:V

kakunin-o isogu

kentou-ochecking-ACC to hurry
to hurry checking it

consideration-ACC further
to take consideration further

N1:N2:C:V

sarani susumeru
to go ahead

N:C:Adj

songai-baisho-o motomeru

nodo-ga itai

damage-reparation-ACC
to demand
to demand reparation for damage

throat-NOM be painful
to have a sore throat

N:C:V1:V2

toukei-o

Adj:N:C:Vtori-hajimeru

statistics-ACC to take-to start
to start collect statistics

takai hyouka-oukeru

highassessment-ACC to receive
to be rated high20

Setup: Computing Paraphrasability Scores
15 measures:
Proposed: {HITS,{BOW,MOD,HAR}×{Lin,skew}}×{Nor,Anc}
 BL (Mainichi): HITS using 1.5GB newspaper corpus
21

Evaluation 1: Ev.GenQuestionCan a correct paraphrase have the highest score among
candidates for a source phrase ?

Judgment (2 assesors)
For 200 input, the best candidates of 15 models

22

Results 1: Ev.Gen
Mainichi << *.HITS
*.BOW.* < *.MOD.**.HAR.*

Web enables us to compute paraphrasability accurately

Candidates with higher scores are more likely correcte.g. Lenient Prec. over 93% (th=0.5)

Nor.X.*

Anc.X.* (discuss later)

1 or 2 judges’ OK
2 judges’ OK

23

Evaluation 2: Ev.Rec
Question

How is the method useful for collecting paraphrase
instances ?

Judgment (2 assesors)

200 best candidates for each of 15 models

24

Results 2: Ev.Rec
Mainichi*.HITS << *.BOW.**.MOD.**.HAR.*DS measures outperformed HITS Lenient Prec. almost reach a ceiling

Nor.X.*

Anc.X.* again

Anchor selection might be inappropriate 2 or more content words make s rarely ambiguous

25

Results 2: Ev.Rec
Remaining problems
Dropping N1 from N1:N2:C:V


Typically functions as generalization
yagai-konsato
outdoors-concert



konsatoo concert

N1 sometimes plays as the semantic head of N1:N2

shukketsu-taryou-de shibou-suru
blood loss-plenty-ABL
die due to heavy blood lossto dietaryou-deshibou-suru

x loss-plenty-ABL to die(*) die due to plentySolutions:Semantic parsing, Phrase boundary detection, etc.
26

Outline

4.

Task Description
Paraphrases Handled
Proposed Method
Experiments

5.

Discussion

6.

Conclusion

1.
2.
3.

Discussion: Issues Addressed
Measurement of paraphrasability between phrases

Reasonably nice (Ev.Gen: over 65%, Ev.Rec: over 96%)
Combining constituent and contextual similarities

Room for improvement
Feature selection [Hagiwara+, 08] Feature weighting [Lin+, 01] [Geffet+, 05]
Data sparseness problem
Not perfectly solved
 TSUBAKI offers larger number of snippets [Shinzato+, 08]
28

Discussion: Technical Issues
Coverage
For 50% input, no candidate is output
 More robust generation systemTo generate a wider range of paraphrases
 To handle other types of phrases with less human-laborPortability
90% of candidates are filtered out due to 0 HITS
 Use SLMs to prune incorrect candidates before querying
29Conclusion
Computing paraphrasability between phrases


Input: paraphrase candidates
Automatically generated
 Syntactic variants
 Predicate phrases in Japanese

Output: paraphrasability score [0,1]Is t grammatical ?
 Does t hold if s holds ? (semantic equivalence or inclusion) Is t syntactically substitutable for s in some context ?
Proposed method achieved reasonable results
Ev.Gen: over 65% (over 93% w/ th=0.5), Ev.Rec: over 96%30