Background

Question Answering system
for NTCIR QAC2
TAKAHASHI Tetsuro
Computational Linguistics Laboratory
NAIST

Efficient Information Access to hugeamount of text data on the www or inencyclopedias.
→ Question Answering
The Internet

When isHalloween?
Encyclopedia

COE technical presentation 2004/5/27

What is QA
Question AnsweringTo
To obtain
obtain appropriate
appropriate answers
answers forfor aa given
given
question
writteninnaturallanguagequestion written in natural language
Q: Who killed Abraham Lincoln?
A: John Wilkes Booth.

NTCIR
The NTCIR Workshop
A series of evaluation workshops
Designed to enhance research inInformation Access technologies

participants of NTCIR-4(2003-2004)
74 groups
From 10 countries

NTCIR
Tasks
Cross-Lingual Information Retrieval
Task
Patent Retrieval Task
Question Answering Challenge
Text Summarization Challenge
WEB Task

NTCIR QAC
Question Answering Challenge
The required answers are short answers consistingof a noun or noun phrase.
Target documents: Four years Japanesenewspaper articles.

Subtask1
Returns five possible exact answers or no-answer.

Subtask2
Returns only one set of answers or no-answer.

Subtask3
Returns all the possible answers for a series ofquestions.

1System Overview

System Overview
Question

Three stages
Question analysis
Passage retrieval
Answer selection

Passage retrieval

Question analysis

Two characteristics
Mediates the difference of expression using
paraphrasing.
Re-ranks answer candidates by structural
matching.

Answer seeking

Answer list

System Overview

Question analysis

Question

クローン羊のドリーが誕生したのはいつですか。
(When was the cloned sheep Dolly born?)

クローン羊のドリーが誕生したのはいつですか。
クローン羊のドリーが誕生したのはいつですか。
(When(Whenwaswasthethecloned
cloned sheep
sheepDolly
Dollyborn?)
born?)

Question Analysis

Passage retrieval

Question analysis

いつ => X (NE:DATE)(when => X(NE:DATE))

ルールベース

VP するのは X(NE:DATE) だ => X(NE:DATE) VPする
(the day VP is X(NE:DATE) => VP on X(NE:DATE)):

about
100 rules

Answer seeking

Answer list

クローン羊のドリーはX(NE:DATE)誕生した。
(The cloned sheep Dolly was born on X(DATE))

System Overview

Passage retrieval

Question

クローン羊のドリーが誕生したのはいつですか。
(When was the cloned sheep Dolly born?)

クローン羊のドリーが誕生したのはいつですか。
クローン羊のドリーが誕生したのはいつですか。
(When(Whenwaswasthethecloned
cloned sheep
sheepDolly
Dollyborn?)
born?)

Keyword extraction
Passage retrieval

Question analysis
クローン羊のドリーはX(NE:DATE)誕生した。
(The cloned sheep Dolly was born on X(DATE))

Answer seeking

Document retrieval
Passage retrieval

Answer list

2

Passage retrieval

Passage retrieval

クローン羊のドリーが誕生したのはいつですか。
(When was the cloned sheep Dolly born?)

クローン羊のドリーが誕生したのはいつですか。
(When was the cloned sheep Dolly born?)

Keyword extraction

keywords

cloned, sheep, Dolly, born

Document retrieval
Passage retrieval

・ Dolly the sheep clone dies young.
・ Dolly
the sheep
diesfamous
young.as the first・ Dolly
the sheep,
whoclonebecame・ Dolly
the sheep
diesfamous
young.as the first・ Dolly
thecloned
sheep,
whoclonebecamemammalto・ befromanadultdies
cell,young.
has died.
Dolly
sheepwhoclone
・ Dollythethesheep,
becamefamousthe first
mammalto becloned
from
an
adult
hasasdied.
・ The
news・ wasconfirmed
on Friday
by cell,the
RoslinDolly
sheep,
becamefamousas thefirst
mammaltothe
beclonedwho
froman adult
cell,
has
died.
・ The
news
was
confirmed
on Friday
bycreated
the Roslin
Institute,
theScottishresearch
centerwhich
mammaltobe confirmed
cloned
from
adult
cell,
died.
・ The
news
was
onan
Fridaybythehas
Roslinthe
Scottishresearch center
which
createdher. Institute,・ The news
was confirmed
Fridayby theRoslinthe Scottish
researchoncenter
which
createdher. Institute,・ A decision
was takento"euthanase"six-year-old
Institute,
theScottishresearch
center which createdher.
・A
decision
was taken
to "euthanase"six-year-old
Dolly
after
a veterinary
examination
showedthat
her.
・A
decision
was taken
to "euthanase"six-year-old
Dolly
after
a
veterinary
examination
showedthat
she had a progressivelunginstitute said・ A after
decision
wasdisease,takenexamination
tothe"euthanase"six-year-old
Dolly
a veterinary
showedthat
hada progressive
lung disease,
the institutesaid
in a shestatement.
Dolly
a veterinary
she
had aafter
progressive
lungexaminationdisease, the showed
institutethat
said
in a became
statement.
・ Dolly
thea firstmammallung
clonewhen theshe institute said
had
progressive
disease,in shea becamestatement.
Dolly
the first mammal clone when she
was ・bornon
1996.
in 5a Julystatement.
・born
Dolly
the first mammal clone when she
wason became
5 July
1996.
・ She
was
to thepublicthemammal
following
year.when she
・revealed
Dolly
became
the
first
clone
was
born
on
5 July
1996.
She
was
revealedtothe
thepublic thefollowing
・ Dr・Harry
Griffin,from
institute,
said:"Sheep year.
wasbornrevealedon 5 July
1996.
・Harry
She
was
tothe
theinstitute,public thefollowing
year.
・
Dr
Griffin,from
said:"Sheepcan live to ・11She
or 12
years
of agelung infections
wasGriffin,
revealed
to andthethe said:
followingyear.
・ DrtoHarry
thepublic
institute,"Sheepcan liveor 12yearsfromof ageandlung infections
are common
in 11
older
sheep,
particularly
those
・
Dr
Harry
Griffin,fromthe
institute,
said:"Sheepcan live toor 12yearsparticularlyof age andthoselung infections
are inside.
commonin 11
older
sheep,
housedlive to in
11olderor 12sheep,years ofage and lunginfections
arecancommonparticularly
thosehousedinside.
・ Speaking
to
BBC
News
on sheep,
Friday,particularlyProf
arecommon
in 24
older
those
housedinside.
・ Speaking
to
BBC
24 be
on theFriday,Prof
Wilmutsaid
Dolly'sbirthNewsshouldimportanthousedinside.
・ Speaking
to BBC
24 be
on theFriday,Prof
Wilmutsaid Dolly's
birthNewsshouldimportantissue.
・ Speaking
to BBCbirthNews
24 onbeFriday,Prof
Wilmutsaid Dolly's
shouldthe important
issue.
Wilmut said Dolly's birth should be the important
issue.
issue.

Passage retrieval
クローン羊のドリーが誕生したのはいつですか。
(When was the cloned sheep Dolly born?)

Keyword extraction
・ Dolly the sheep clone dies young.
・ Dolly
the sheep
diesfamous
young.as the first・ Dolly
the sheep,
whoclonebecame・ Dolly
the sheep
diesfamous
young.as the first・ Dolly
thecloned
sheep,
whoclonebecamemammalto・ befromanadultdies
cell,young.
has died.
Dolly
sheepwhoclone
・ Dollythethesheep,
becamefamousthe first
mammalto becloned
from
an
adult
hasasdied.
・ The
news・ wasconfirmed
on Friday
by cell,the
RoslinDolly
sheep,
becamefamousas thefirst
mammaltothe
beclonedwho
froman adult
cell,
has
died.
・ The
news
was
confirmed
on Friday
bycreated
the Roslin
Institute,
theScottishresearch
centerwhich
mammaltobe confirmed
cloned
from
adult
cell,
died.
・ The
news
was
onan
Fridaybythehas
Roslinthe
Scottishresearch center
which
createdher. Institute,・ The news
was confirmed
oncenterFridayby theRoslinInstitute,
theScottishresearchwhich
createdher.
・ A decision
was taken"euthanase"six-year-old
Institute,the toScottishresearch
center which createdher.
・A
decision
was taken
to "euthanase"six-year-old
Dolly
after
a
veterinary
examination
showedthat
her.
・A
decision
was taken
to "euthanase"six-year-old
Dolly
after
a veterinary
examination
showedthat
she hada progressivelunginstitutesaid
・ A after
decision
wasdisease,takenexamination
tothe"euthanase"six-year-old
Dollyaveterinary
showedthat
had a progressive lung disease, the institute said
in a shestatement.
Dolly
a veterinary
she
had aafter
progressive
lungexaminationdisease, the showed
institutethat
said
in a became
statement.
・ Dolly
thea firstmammallung
clonewhen theshe institute said
had
progressive
disease,in shea becamestatement.
Dolly
the first mammal clone when she
was ・bornon
1996.
in 5a Julystatement.
・born
Dolly
the first mammal clone when she
wason became
5 July
1996.
・ She
was
to thepublicthemammal
following
year.when she
・revealed
Dolly
became
the
first
clone
was
born
on
5 July
1996.
She
was
revealedtothe
thepublic thefollowing
・ Dr・Harry
Griffin,from
institute,
said:"Sheep year.
wasbornrevealedon 5 July
1996.
・Harry
She
was
tothe
theinstitute,public thefollowing・ Drtofrom
said:"Sheep year.
can liveorGriffin,
12
years
of agelung infections
・11ShewasGriffin,
revealed
to andthepublicthe said:
following
year.
・
Dr
Harry
from
the
institute,"Sheepcan live toor 12yearsparticularlyof age andthoselung infections
are common
in 11
older
sheep,・ Dr
Griffin,fromofthe"SheepcanliveHarry
to
or 12
years
ageinstitute,andthoselungsaid:
infections
are inside.
commonin 11
older
sheep,
particularlyhousedlive to in
11olderor 12sheep,years ofage and lunginfections
arecancommonparticularly
thosehousedinside.
・ Speaking
to
BBC
News
on sheep,
Friday,particularlyProf
arecommon
in 24
older
those
housedinside.
・ Speaking
to
BBC
24 be
on theFriday,Prof
Wilmutsaid
Dolly'sbirthNewsshouldimportanthousedinside.
・ Speaking
to BBC
24 be
on theFriday,Prof
Wilmutsaid Dolly's
birthNewsshouldimportantissue.
・ Speaking
to BBCbirthNews
24 onbeFriday,Prof
Wilmutsaid Dolly's
shouldthe important
issue.
Wilmut said Dolly's birth should be the important
issue.
issue.

Document retrieval
Passage retrievalcloned, sheep, Dolly, born
DATE

Retrieved document

・・Dolly
Dollythethesheep
sheepclone
clonediesdiesyoungyoung. .
・・Dolly
Dollythethesheep,
sheep,who
whobecame
becamefamous
famousasasthe
thefirst
firstmammal
mammaltotobe
beclonedclonedfromfromananadult
adultcell,
cell,hashasdied.
died.
・・The
Thenews
newswaswasconfirmed
confirmedon
onFridayFridayby
bythe
theRoslin
RoslinInstitute,
Institute,thetheScottish
Scottishresearch
researchcenter
centerwhich
whichcreatedcreatedher.
her.
・・AAdecision
decisionwas
wastakentakentoto"euthanase""euthanase"six-year-old
six-year-oldDolly
Dollyafter
afteraaveterinary
veterinary
examination
examinationshowed
showedthat
thatsheshehadhadaaprogressive
progressivelung
lungdisease,disease,thetheinstituteinstitutesaid
said
ininaastatement.
statement.
・・Dolly
Dollybecame
becamethethefirst
firstmammal
mammalclone
clonewhen
whensheshewaswasborn
bornonon55July
July1996.
1996.
・・She
Shewaswasrevealed
revealedtotothe
thepublic
publicthe
thefollowing
followingyear.
year.
・・Dr
Harry
Griffin,fromthe
institute,
said:"Sheep
can
live
to
11
or
12
Dr Harry Griffin, from the institute, said: "Sheep can live to 11 or 12years
years
of
ofage
ageandandlunglunginfections
infectionsare
arecommon
commonininolder
oldersheep,
sheep,particularly
particularlythose
thosehousedinside.
housed inside.
・・Speaking
SpeakingtotoBBC
BBCNews
News24
24on
onFriday,Friday,Prof
ProfWilmut
Wilmutsaid
saidDolly's
Dolly'sbirth
birthshouldshouldbe
bethe
theimportant
importantissue.
issue.

cloned, sheep, Dolly, born

Document retrieval
Passage retrieval

Newspaper
articlesPassage retrieval
Retrieved document

cloned, sheep, Dolly, born, DATE

・・Dolly
Dollythethesheep
sheepclone
clonediesdiesyoungyoung. .
・・Dolly
Dollythethesheep,
sheep,who
whobecame
becamefamous
famousasasthe
thefirst
firstmammal
mammaltotobe
beclonedclonedfromfromananadult
adultcell,
cell,hashasdied.
died.
・・The
Thenews
newswaswasconfirmed
confirmedon
onFridayFridayby
bythe
theRoslin
RoslinInstitute,
Institute,thetheScottish
Scottishresearch
researchcenter
centerwhich
whichcreatedcreatedher.
her.
・・AAdecision
was
taken
to
"euthanase"six-year-old
Dolly
after
a
veterinary
decision was taken to "euthanase" six-year-old Dolly after a veterinary
examination
examinationshowed
showedthat
thatsheshehadhadaaprogressive
progressivelung
lungdisease,disease,thetheinstituteinstitutesaid
said
ininaastatement.
statement.
・・Dollybecamethefirstmammal
clone
when
she
was
born
on
5
July
1996.
Dolly became the first mammal clone when she was born on 5 July 1996.
・・She
Shewaswasrevealed
revealedtotothe
thepublic
publicthe
thefollowing
followingyear.
year.
・・Dr
DrHarry
HarryGriffin,
Griffin,fromfromthetheinstitute,institute,said:
said:"Sheep"Sheepcan
canlive
livetoto11
11or
or12
12years
years
of
ofage
ageandandlunglunginfections
infectionsare
arecommon
commonininolder
oldersheep,
sheep,particularly
particularlythose
thosehousedhousedinside.
inside.
・・Speaking
SpeakingtotoBBC
BBCNews
News24
24on
onFriday,Friday,Prof
ProfWilmut
Wilmutsaid
saidDolly's
Dolly'sbirth
birthshouldshouldbe
bethe
theimportant
importantissue.
issue.

Passage retrievalcloned, sheep, Dolly, born, DATE

Keyword extraction

20-best documents

Passage retrieval
クローン羊のドリーが誕生したのはいつですか。
(When was the cloned sheep Dolly born?)

Keyword extraction
・ Dolly the sheep clone dies young.
・ Dolly
the sheep
diesfamous
young.as the first・ Dolly
the sheep,
whoclonebecame・ Dolly
the sheep
diesfamous
young.as the first・ Dolly
thecloned
sheep,
whoclonebecamemammalto・ befromanadultdies
cell,young.
has died.
Dolly
sheepwhoclone
・ Dollythethesheep,
becamefamousthe first
mammalto becloned
from
an
adult
hasasdied.
・ The
news・ wasconfirmed
on Friday
by cell,the
RoslinDolly
sheep,
becamefamousas thefirst
mammaltothe
beclonedwho
froman adult
cell,
has
died.
・ The
news
was
confirmed
on Friday
bycreated
the Roslin
Institute,
theScottishresearch
centerwhich
mammaltobe confirmed
cloned
from
adult
cell,
died.
・ The
news
was
onan
Fridaybythehas
Roslinthe
Scottishresearch center
which
createdher. Institute,・ The news
was confirmed
Fridayby theRoslinthe Scottish
researchoncenter
which
createdher. Institute,・ A decision
was takento"euthanase"six-year-old
Institute,
theScottishresearch
center which createdher.
・A
decision
was taken
to "euthanase"six-year-old
Dolly
after
a veterinary
examination
showedthat
her.
・A
decision
was taken
to "euthanase"six-year-old
Dolly
after
a
veterinary
examination
showedthat
she had a progressivelunginstitute said・ A after
decision
wasdisease,takenexamination
tothe"euthanase"six-year-old
Dolly
a veterinary
showedthat
hada progressive
lung disease,
the institutesaid
in a shestatement.
Dolly
a veterinary
she
had aafter
progressive
lungexaminationdisease, the showed
institutethat
said
in a became
statement.
・ Dolly
thea firstmammallung
clonewhen theshe institute said
had
progressive
disease,in shea becamestatement.
Dolly
the first mammal clone when she
was ・bornon
1996.
in 5a Julystatement.
・born
Dolly
the first mammal clone when she
wason became
5 July
1996.
・ She
was
to thepublicthemammal
following
year.when she
・revealed
Dolly
became
the
first
clone
was
born
on
5 July
1996.
She
was
revealedtothe
thepublic thefollowing
・ Dr・Harry
Griffin,from
institute,
said:"Sheep year.
wasbornrevealedon 5 July
1996.
・Harry
She
was
tothe
theinstitute,public thefollowing
year.
・
Dr
Griffin,from
said:"Sheepcan live to ・11She
or 12
years
of agelung infections
wasGriffin,
revealed
to andthethe said:
followingyear.
・ DrtoHarry
thepublic
institute,"Sheepcan liveor 12yearsfromof ageandlung infections
are common
in 11
older
sheep,
particularly
those
・
Dr
Harry
Griffin,fromthe
institute,
said:"Sheepcan live toor 12yearsparticularlyof age andthoselung infections
are inside.
commonin 11
older
sheep,
housedlive to in
11olderor 12sheep,years ofage and lunginfections
arecancommonparticularly
thosehousedinside.
・ Speaking
to
BBC
News
on sheep,
Friday,particularlyProf
arecommon
in 24
older
those
housedinside.
・ Speaking
to
BBC
24 be
on theFriday,Prof
Wilmutsaid
Dolly'sbirthNewsshouldimportanthousedinside.
・ Speaking
to BBC
24 be
on theFriday,Prof
Wilmutsaid Dolly's
birthNewsshouldimportantissue.
・ Speaking
to BBCbirthNews
24 onbeFriday,Prof
Wilmutsaid Dolly's
shouldthe important
issue.
Wilmut said Dolly's birth should be the important
issue.
issue.

cloned, sheep, Dolly, born, DATE

Document retrieval
Passage retrieval

Newspaper
articles10-beset passages
・ Dolly became the first mammal clone when she
・ Dollybecamefirst mammal clone when she
wasborn on5 Julythe
1996.
・ Dollybecamefirst mammal clone when she
wasbornrevealedon
5 Julytothe
1996.
・ She
was
the public
the following
year. she・ Dollybecamefirst mammalclone whenwasbornrevealedon
5 Julytothe
1996.
・ She
was
the public the following year.
was wasbornrevealedon 5 Julyto1996.
・ She
the public the following year.
・ She was revealed to the public the following year.

3System Overview

Answer seeking
Passages
Passages
Passages
w5

Question

Paraphrased
Question

w5
w3 w5
w4
w3 w4
w3 w4
w1 w2
w1 w2
w1 w2

w5
w3
w1

w4

w2

matching

Passage retrieval

Question analysis

・ Dolly became the first mammal clone when she
・ Dolly became the first mammal clone when she
was・born
5 July 1996.
Dollyonbecame
the first mammal clone when she
was born on 5 July 1996.
・ She
revealed
to thepublic the following year.
waswasborn
on 5 July
1996.
・ She was revealed to the public the following year.
・ She was revealed to the public the following year.

Bag-of-words matchingansweransweranswercandidatecandidatecandidate

クローン羊のドリーはX(NE:DATE)誕生した。
(The cloned sheep Dolly was born on X(DATE))

Verifies and re-ranks answer
candidates using structural
information.

Structural matching

Answer seeking
Answer list

Answer list

Answer seeking

System Overview

Answer seeking
paraphrasing
q_21

Passages
Passages
Passages
w5

p1_1

q_22

q_2

q_23

w5
w3 w5
w4
w3 w4
w3 w4
w1 w2
w1 w2
w1 w2

Questionparaphrase space

matching

q_1

Gives score to every word according
to keywords, answer type and theirproximity.

a1

p1_11

p1_2

p1_12

p1_3

Paraphrased
Question

Passage retrieval

Question analysis

w5
w3
w1

w4

w2

・ Dolly became the first mammal clone when she
・ Dolly became the first mammal clone when she
was・born
5 July 1996.
Dollyonbecame
the first mammal clone when she
was born on 5 July 1996.
・ She
revealed
to thepublic the following year.
waswasborn
on 5 July
1996.
・ She was revealed to the public the following year.
・ She was revealed to the public the following year.

クローン羊のドリーはX(NE:DATE)誕生した。
(The cloned sheep Dolly was born on X(DATE))

Answer seeking

Answer list

Answer list

Evaluation and Result

Evaluation and Result

Subtask 1 (200 questions)

Subtask 1 (200 questions)
MRR−re-ranking＋re-ranking− paraphrasing

0.340

0.311

＋ paraphrasing

0.341

0.310

RRi =

1
Ranki

∑ RR
n

MRR =

i =1

n

i

1: 2002
2: 5 July 1996
3: Friday
4: 1996
5: 2 years ago

MRR−re-ranking＋re-ranking− paraphrasing

0.340

0.311

＋ paraphrasing

0.341

0.310

RRi =

1
Ranki

∑ RR
n

MRR =

i =1

i

1: 2002
2: 5 July 1996
3: Friday
4: 1996
5: 2 years ago

RRi =

1
2

n

4

Evaluation and Result

Evaluation and Result

Subtask 2 (200 questions)
Mean F-value−re-ranking＋re-ranking− paraphrasing

0.219

0.185

＋ paraphrasing

0.220

0.185

2 × Recalli × Precisioni
F − valuei =Recalli + Precisioni∑ F - valuenMean F − value =i =1Re-ranking had a negative effect.
Other way to combine structural
information.

Effect of paraphrasing wasextremely small.
Investigation of paraphrasing rules
for question answeringinRelated work

Conclusion

Structural matching
Ittycheriah 2001, Kiyota 2002
used information of syntactic structure
as a score to be appended

as a penalty
The penalty was too strict, since question
key words appeared in positions isolated
from the answer in many passages.

Question answering system
Mediates the difference of expression using
paraphrasing.
Re-ranks answer candidates by structural
matching.

Evaluation
Re-ranking had a negative effect.
Effect of paraphrasing was extremely small.

Future work
Investigation of paraphrasing rules forquestion answering.

5