< COLING 2008, Aug. 19th, 2008 >A Probabilistic Modelfor Measuring Grammaticality and Similarity
of Automatically Generated Paraphrasesof Predicate Phrases
Atsushi FUJITA and Satoshi SATO
Nagoya Univ., Japan

Overview
X show a A Y
Abstract pattern

X v(Y) adv(A)Paraphrase Generation(Instantiation)
Employment showsa sharp decrease

Employmentdecreases sharply

Paraphrase candidate
Grammaticality
 Similarity
Quality Measurement

Score (How likely to be paraphrase)2

Automatic Paraphrasing
Fundamental in NLP
Recognition: IR, IE, QA, Summarization
 Generation: MT, TTS, Authoring/Reading aidsParaphrase knowledge

Handcraft
Thesauri (of words) [Many work] Transformation rules [Mel’cuk+, 87] [Dras, 99] [Jacquemin, 99]Automatic acquisition
Anchor-based [Lin+, 01] [Szpektor+, 04]
 Aligning comparable/bilingual corpora [Many work]
3

Representation of Paraphrase Knowledge
XVY[Harris, 1957]
X’s V-ing of Y Nominalization

XVY

Y be V-PP by X

Passivization

X show a A Y

X v(Y) adv(A)Removing light-verb

Fully-abstracted

X wrote Y

X is the author of Y

X solves Y

X deals with Y

burst into tears
comfortcriedconsole[Lin+, 2001][Barzilay+, 2001]

Fully-lexicalized
4

Instantiating Phrasal Paraphrases
Over-generation leads to spurious instances
cf. filling arguments [Pantel+, 07] cf. applying to contexts [Szpektor+, 08]
X show a A Y

X v(Y) adv(A)Employment showsa sharp decrease
Statistics show a
gradual decline
The data show a
specific distribution

Employment
decreases sharply

OK

Statistics decline Not equivalent
gradually
The data distribute Not grammaticalspecifically5

Task Description
Measuring the quality of paraphrase candidate
Input: Automatically generated phrasal paraphrases
Employment showsa sharp decrease

Employment
decreases sharplyst

Output: Quality score [0,1]6Quality as Paraphrases
Three conditions to be satisfied
1. Semantically equivalent
2. Substitutable in some context
3. GrammaticalApproachesAcquisition of instances

1 and 2 are measured, assuming 3

Instantiation of abstract pattern (our focus)
1 and 2 are weakly ensured
 3 is measured, and 1 and 2 are reexamined

7

Outline
1.

Task Description

2. Proposed Model3.
4.

Experiments
ConclusionProposed Model
Assumptionss is given and grammatical s and t do not co-occurFormulation with a conditional probability

Grammaticality

Similarity

9Grammaticality Factor
Statistical Language Model

History ofStructured N-gram LM
 Normalized with length10Grammaticality Factor: Definition of Nodes
For JapaneseWhat present dependency parsers determine
Bunsetsu: {Content word} + {Function word} * Bunsetsu dependencies
kittoBunsetsu can be quite long (so not appropriate)kare wakyou nokaigini wa

surelyhe TOP today GEN meeting DAT TOP(He will surely not come to today’s meeting.)

u.

must.

kuru nai dacome NEG

EOS

11

Grammaticality Factor: MDS
Morpheme-based Dependency Structure [KURA, 01]
Node: Morpheme Edge:

Rightmost node → Head-word of its mother bunsetsu Other nodes → Succeeding node


kitto

kare wakyou nokaigi

ni wa

surelyhe TOP today GEN meeting DAT TOP(He will surely not come to today’s meeting.)

u.

must.

kuru nai dacome NEG

EOS

12

Grammaticality Factor: CFDSContent-Function-based Dependency Structure
Node: Sequence of content words or of function words
 Edge:Rightmost node → Head-word of its mother bunsetsu Other nodes → Succeeding node

kittokare wakyou nokaigi

ni-wa

kuru

nai-daro-u-.

surelyhe TOP today GEN meeting DAT-TOP(He will surely not come to today’s meeting.)

comeNEG-must-.

EOS13

Grammaticality Factor: Parameter Estimation
MLE for 1, 2, and 3-gram models
Mainichi(1.5GB)

Node Type # of alphabets
MDS
320,394
CFDS14,625,384
Bunsetsu
19,507,402

Linear interpolation of 3 models


Mixture weights were determined via an EMYomiuri
Asahi+(350MB)(180MB)
14

Similarity Factor
A kind of distributional similarity measure

Contextual feature set (F)BOW: Words surrounding s and t have similar distributions and t are semantically similar
MOD: s and t share a number of modifiers and modifieess and t are substitutable

15

Similarity Factor: Parameter Estimation
Employ Web snippets as an example collection
To obtain sufficient amount of feature info.
 Yahoo! JAPAN Web-search API‘‘Phrase search’’ 1,000 snippets (as much as possible)
16

Similarity Factor: Parameter Estimation (cont’d)
MLE

Based on snippets

Based on static corpus

Mainichi(1.5GB)

WebCP(42.7GB)[Kawahara+, 06]
17

Summary
What is taken into accountGrammaticality of t
 Similarity between s and tYou do not need to enumerate all the phrases


cf. P(ph | f), pmi(ph, f)

Options

Grammaticality

Similarity
max # of snippets(1,000 / 500)

MDS / CFDS

Mainichi / WebCP
BOW / MOD18

Outline
1.
2.

Task Description
Proposed Model3. Experiments
4.

Conclusion

Overview
X show a A Y
Abstract pattern

X v(Y) adv(A)Paraphrase Generation(Instantiation)
Employment showsa sharp decrease

Employmentdecreases sharply

Paraphrase candidate
Grammaticality
 Similarity
Quality Measurement

Score (How likely to be paraphrase)20

Test Data
Extract input phrases
1,000+ phrases × 6 basic phrase types
 Mainichi (1.5GB)
 Referring to structureTrans. Pat.
N:C:V ⇒ adv(V):vp(N)Gen. Func.
vp(N)Lex. Func.
adv(V)

Paraphrase generation [Fujita+, 07]176,541 candidates for 4,002 phrases

SamplingCandidates for 200 phrases
 Diverse cases (see column Y)
21Overview
X show a A Y
Abstract pattern

X v(Y) adv(A)Paraphrase Generation(Instantiation)
Employment showsa sharp decrease

Employment
decreases sharply

Paraphrase candidate
Grammaticality
 Similarity
Quality Measurement

Score (How likely to be paraphrase)22

Viewpoint
How well a system can rank a correct candidate first?
Models evaluated

Proposed model
All combination of options
 P(t) × P(f) × Feature set × max # of snippet
222+12Baselines

HAR: harmonic mean of BOW and MOD scores

Lin’s measure [Lin+, 01] α-skew divergence [Lee, 99]
 HITS

Similarity only
Grammaticality only23

Results (max 1,000 snippets)# of cases that gained positive judgmentsModels except CFDS+Mainichi << the best models
2 judges’ OK

1 or 2 judges’ OKStrictLenient
Model \ Feature
BOW MOD HAR BOW MOD HAR
CFDS+Mainichi 79
82
83 121 121 122
Lin79
88
88 116 128 1298489
89 121 128 128
α-skewHITS
84
119
XXX: best
XXX: significantly worse than the best (McNemer’s test, p<0.05)
24

Results (max 1,000 snippets, HAR)
Lenient precision and score
Best candidate

Relatively high score

High precision

Proposed

Proposed(similarity factor only)25

Considerations
Harnessing the Web led to accurate baselines
1. Looking up the Web … Feature retrieval+ Grammaticality check2. Comparing feature distributions … Similarity check

Two distinct viewpoints of similarity are combined
Constituent similarity:
Syntactic transformation + Lexical derivation [Fujita+, 07]Contextual similarity:
Bag of words / Bag of modifiers

Trans. Pat.
N:C:V ⇒ adv(V):vp(N)Gen. Func.
vp(N)Lex. Func.
adv(V)

26

Diagnosis shows the room of improvement
Grammaticality

MDS < CFDS

Similarity
max # of snippets(1,000 / 500 / 200 / 100)

Mainichi > WebCPBOW < MOD ≒ HAR

A2: MDS cannot capture
collocation of content words
A3: Combining with P(t)dismisses the advantage

A5: No significant difference(Even Web is not sufficient?)
A4: Linguistic tools are trainedon newspaper articles
27

Conclusion & Future work
Measuring the quality of paraphrase candidates
Input: Automatically generated phrasal paraphrases
Output: Quality score [0,1]Semantically equivalent Substitutable in some context
 Grammatical

Similarity
Grammaticality

Overall: 54-62% (cf. Lin/skew: 58-65%, HITS: 60%)
 Top 50: 80-92% (cf. Lin/skew: 90-98%, HITS: 70%)
Future work
Feature engineering (including parameter tuning) Application to non-productive paraphrases28