Backgroundthe accessibility to Web documents
most part of information on WWW is transferred by text

A Method for Resolving
Japanese Zero Pronouns

Toward intelligent treatment of text data
we are working on natural language processing (NLP)
Development of NLP techniques
Machine translation, information extraction

Ryu IIDA
Computational Linguistics Lab.
ryu-i@is.naist.jp

The process which crosses sentence boundaries,
such as anaphora resolution, remains a major obstacle
to further improvements[COE technical presentation, 24 August 2004]

2Motivation

Zero pronouns resolution

Developing the performance of anaphora resolution
suitable for real world applications

In Japanese, anaphors are omitted
because of speaker ’ s and hearer ’s recognition

Anaphora resolution

antecedent

process tracking entities in text

トムは ジョンにその本をあげた。
Tom-wa John-ni the book-o gave
(Tom gave the book John)

antecedent

Tom gave John the book.
Then, he went back to the school.

Zero pronoun(anaphor)

その後、(φガ) 学校に 戻った。
Then, φ-ga school- ni went-back(Then, φ went back to the school)

anaphor

Detecting antecedents against anaphors

3

Previous work

Challenging issue

Two approaches to anaphora resolution
Rule-based approach

Achieving a good union between theoretical linguistic
findings and corpus-based empirical methods[Mitkov 97, Baldwin 95, Nakaiwa 96, Okumura 95, Murata 97]

Many attempted to encode linguistic cues into rules
Problem:
Furthermanualinfluenced
refinement
needed inTheory
this study
This wassignificantly
byisCentering
butWalker
it will etbeal.prohibitively
costly[Grosz 95,94, Kameyama,86]
Best-achieved performance in MUC:
(Message Understanding Conference)

4

Precision roughly 70%
Recallroughly 60%

Corpus-based machine learning approach[Aoneand These
Bennettprevious
95, Soon work
et al. tend
01, Ngtoand
Problem:lackCardie
an 02, Seki 02]
Cost effective
appropriate reference to the theoretical
They haveachieved
a performancecomparable
to best performing
linguistic
work
on coherence
and coreference
rule-based systems

561

Statistical approaches [Soon et al. ‘01, Ng and Cardie ‘02]

Statistical approaches [Soon et al. ‘01, Ng and Cardie ‘02]
antecedent

Reach a level of performance comparable to state-of-theart rule-based systems[MUC-6]

A federal judge in Pittsburgh issued a temporary restraining
order preventing Trans World Airlines from buying
additional shares of USAir Group Inc. 〇The order, requested in a suit filed by USAir , dealt another×blow to TWA's bid to buy the company
for $52 a share.

Recast the task of anaphora resolution as a sequence ofclassification problems

×anaphor

the task is to classify these pairs of noun phrases into
positive or negative
positive instance: Pair of an anaphor and the antecedent
negative instance: Pairs of an anaphor and the NPs locatedbetween the anaphor and the antecedent
USAir Group Inc

USAirpositiveorderUSAirnegative

suit

USAir

negative

outputclass

7

Statistical approaches [Soon et al. ‘01, Ng and Cardie ‘02]
Test Phase [Ng and Cardie, 02]

Statistical approaches [Soon et al. ‘01, Ng and Cardie ‘02]
Feature set [Ng and Cardie 02]
USAir Group Inc

USAir

order

USAir

suit

USAir

candidates

positive POS
DEMONSTRATIVE
negative STRING_MATCH
negative NUMBER
GENDERSEM_CLASSDISTANCE
SYNTACTIC ROLE

features

NP2
NP3
NP5
NP6
NP7
NP8

A drawback of the previous statistical models

anaphorfeatures

Glendorashe

positive

Positive and negative
instances may have theidentical feature vector

antecedent-2.5

NP6POS
Prop_Noun
PronounNE
SEM_CLASSSENT_DIST: Noun: Yes: No: PERSON: Person:0POS
Prop_Noun
PronounNE
SEM_CLASSSENT_DIST: Noun: Yes: No: PERSON: Person:0

Slightly better than best-performing rule- based model at MUC-7

10Proposed model

Sarah went downstairs and received another curious shock, forwhen Glendora flapped into the dining room in her home madeThe previous models do not capture
moccasins, Sarah asked her when she had brought coffee to her
local said
context
appropriatelyroom, and Glendora
she hadn't.

negative

1.5
1.5-0.3

Precision 78.0%, Recall 64.2%
9

she-0.4

Input each pair of given anaphor
Selectthebest-scoredcandidateandone ofthesecandidates
toas the output
the decision tree

anaphorModel (decision tree)

Sarah-1.1

We
Ng and Cardie ’s model as
NP4refer to-1.0
the baseline-3.5
of our empirical evaluation

training (C4.5)[Kameyama 98]

extract NPs-2.0

NP1

candidateanaphor
先行詞候補照応詞
Organization:1
先行詞候補 Prp_noun:1 Organization:1
照応詞
SENT_DIST:0
Person:1
ハ:1
Person:1
ハ:1
SENT_DIST:0 positive
Person:1
ハ:1
Person:1
SENT_DIST:0 negative
negative
Pronoun:0
Pronoun:0 ハ:1 STR_MATCH:0
Pronoun:0
Pronoun:1
Pronoun:0
Pronoun:1

antecedent

811Inspired by Centering Theory that captures the local
contextual factors
Improve the search algorithm: tournament model
A new model which makes pair-wise comparisons between
candidates

122

Centering Theory [Grosz `95]

Tournament model
What we want to do is to answer a question which is more
likely to be coreferent, Sarah or Glendora

Capturing the salience of sentences
Topic > Subj > I-obj > Obj > Others
Sarah went downstairs and received another curious shock, forwhen Glendora flapped into the dining room in her home mademoccasins, Sarah asked her when she had brought coffee to herroom, and Glendora said she hadn't.

Conduct a tournament consisting of a series of matches inwhich candidates compete with each other

Sarah went downstairs and received another curious shock,
Salience: CHAIN(Cb = Cp = Sarah)……

Sarah went downstairs
downstairs and received another curious shock, forwhen Glendora ×
flapped into ×
thedining
dining room in her home mademoccasins,
Sarah asked
× Sarah〇 her when she had brought coffee to herroom, and〇 Glendora said
〇 she hadn't.

Match victory is determined by a pairwise comparison
between candidates as a binary classification problem
Most likely candidate is selected through a single-elimination
tournament of matchestransition

she hadn't.
Salience: CHAIN(Cb = Cp = Glendora)

antecedent

Glendora
13

Tournament model

Training instancesfeatures

Training Phase

Tournament modelclassnIn the tournament, the correct
antecedent NP5 must prevail over any of
the other four candidates

NP1

NP5ANP

right

NP4NP5ANP

rightnExtract four training instances

NP5

NP7

ANP

left

nInduce a pairwise classifier from a set of
extracted training instances

NP5

NP8

ANP

left

nThe classifier classifies a given pair ofcandidates into left or rightthe right hand side of a given
pair wins (is more likely to bethe antecedent)

14

1.

Test Phase2.

the first match is arranged
between the nearest candidates(NP7 and NP8)
each of the following matchesarranged in turn between thewinner (NP8) of the previous
match and a new challenger(NP5)

antecedent
NP1

NP2

NP3NP4NP5NP6NP7NP8

coreferent

ANP

NP1

NP5NP5

NP6NP7NP8ANP
anaphorbeginning of
document

16

Experiments

3. the winner is next matched against
the next challenger (NP4)
4. this process is repeated until thelast one participate
5. the model selects the candidatethat prevails through the final roundas the answer

antecedent

NP4

coreferent
15

Test Phase

NP3

anaphorbeginning of
document

Tournament model

NP2

Empirical evaluation on Japanese zero pronouns
resolution
Comparison among three models
1. Rule-based model [Nariyama `02]
2. Previous statistical model (baseline model)[Ng and Cardie `02]

NP1

NP2

NP3

NP4

NP5

coreferent
beginning ofdocument

NP6NP7NP8

3. Tournament model (proposed model)

ANPanaphor17

18

3

Method

Results

Data
Zero pronouns tagged JapaneseGDA
newspaper article corpus

Tournamentmodel (proposed)

MUC-6

Texts

： 2,17660

Sentences
Tags of anaphoric relation：24,475： 2,781

8,946

75.1%
65.7%

As a preliminarily test, only resolving subject zeroanaphors, 2,781 instances in total

Rule-basedmodel

Conduct five fold cross-validation on that data set withsupport vector machinesprevious statisticalmodel (baseline)

45.6%

1920Conclusions
Our concern is achieving a good union between theoreticallinguistic findings and corpus-based empirical methods

We presented a trainable anaphora resolution model thatis designed to incorporate contextual cuesby means of a tournament-based search algorithm
Future work
In Japanese zero-anaphora resolution,
1. Identification of relations between the topic and subtopics
2. Analysis of complex and quoted sentences
3. Refinement of the treatment of selectional restrictions
214