Proceedings of the Third NTCIR Workshop

NTT DATA Question-Answering Experimentat the NTCIR-3 QAC

Toru Takaki Yoshio Eriguchi
Research and Development Headquarters
NTT DATA Corporation
Kayabacho Tower Bldg., 1-21-2, Shinkawa,Chuo-ku, Tokyo 104-0033 Japan

ftakakit,eriguchiyg@nttdata.co.jp

Abstract

In this paper, we give an overview of our questionanswering system for the NTCIR-3 QAC. Our system
is based on an information-retrieval technique and an
information-extraction technique by pattern matching.
The system has three main stages: question analysis, passage retrieval, and answer extraction. In thepassage-retrieval stage, two types of retrieval method
are applied sequentially to narrow down the document
quantity for the following answer-extraction stage. We
have submitted our results for all three sub-tasks of the
NTCIR-3 QAC ocial runs.
Keywords: question answering, information retrieval,information extraction, passage retrieval, question analysis, pattern matching.
1 Introduction
Our participation in the NTCIR-3 Question and Answering Challenge (QAC) represents NTT DATA's
rst participation in NTCIR.
The question-answering approach - an applicationof "real" information retrieval rather than "document" retrieval - is a promising means of providing
a user with required information precisely and eciently. The goal of question-answering is that a system returns a concise package of information that answers the user's question through knowledge acquisition from a data source on the Internet or an intranet.
The Text REtrieval Conference (TREC) has set out
an English question-answering track each year from
TREC-8 in 1999 to TREC-2002 in 2002 [6,7]. We
participated in the TREC question-answering trackin 1999 and 2000, and have built an English questionanswering system [4,5].
The NTCIR-3 QAC is the rst evaluation workshop concerning large-scale question-answering using
Japanese [2]. We rebuilt our question-answering sys© 2003 National Institute of Informatics

tem for the Japanese language, and have submitted
the results for all three sub-tasks (task 1, 2, and 3) of
the NTCIR-3 QAC.
To perform these tasks, we constructed a questionanswering system by combining a traditional informationretrieval technique and an information-extraction technique. In this paper, we describe the processing of our
QA system, and discuss and analyze the evaluation results we obtained for the NTCIR-3 QAC ocial runs.

2 System overview
This section describes the processing of our QA system. The system was built by combining a fundamental information-retrieval system and an informationextraction system. The QA procedure consists of threemain components. First, we will explain the processing for each of these components and then will explain
the task-oriented processing for the sub-tasks.
The processing procedure is shown in Fig. 1. For
this system, we used only the Mainichi Newspapers(1998-1999) in the NTCIR-3 QAC document set as an
information source; other sources, such as an encyclopedia or external Web data, were not used.

(1) Question-analysis component
This component determines the answer categories thatmatch the inputted question.

(a) Answer-categories de nition
The answer categories are de ned using a three-level
hierarchical structure. In the top-level of the structure, where the answer categories have abstract answer types, we de ned ve categories: (1) Noun, (2)Non-noun, (3) Quantity, (4) Time, and (5) Unknown.
In the lower levels of the structure, the categories are
given more detailed answer-type de nitions. For example, second-level categories under the Noun cate-The Third NTCIR Workshop, Sep.2001 - Oct. 2002

Question

Noun
Non-Noun
QuantityTime
Unknown(1) Question Analysis

Answer category specification(2) Passage Retrieval

Query term extraction & weighting
Document Retrieval
Passage extraction
answer category

Newspaper Articles

passages

PersonOrganization
Structure
Location
LengthWeightWidth
Money
Temperature

Building
Tower
StationBridgeStation(3) Answer Extraction

Information extraction
Final answer phrase selection
Duplication answer deletion

AnswerFigure 1: Processing Proceduregory are Person, Organization, Structure, Location,etc. An example of answer-type categories is shown in
Fig. 2.

(b) Answer-category speci cation
The answer-category speci cation is a processing stepin which a determination is made as to what type ofanswer is required for a given question. Characteristic
expressions in the question sentence are extracted using the pattern-matching engine and matched to corresponding answer types. The pattern-matching engine
uses manually created rule patterns that are de ned by
a combination of a morphological character sequence
and a part of speech [1].
When a question sentence is matched with a pattern, the answer category is determined by referring
to a table that de nes the correspondence between thepattern and a category, and a category score is given
for the pattern.
If the answer category of a detailed lower-level category is given, the categories of related higher-level
categories are also given as next-candidate types withthe lower category's score. If a question does notmatch any of the patterns, an "Unknown" category
is given.

(2) Passage-retrieval component
This component extracts the candidate passages containing answer phrases from the newspaper articles inthe data set. It performs the query-term-extraction,

Figure 2: Answer categories
document-retrieval, and passage-extraction processing.

(c) Important-question-phrase extraction
In this processing, the interrogative phrase is removed
from the original question sentence.

(d) Query-term extraction
Query terms for document retrieval are extracted
from the above question sentence. We implemented
two types of query-term-extraction sub-component:
QTE1 and QTE2.

QTE1 All the combination of sequential morphemes

is extracted as query terms. In some cases,
query terms may become quite long. Although
the number of query terms becomes sum of 1 ton when the number of morphemes is n, we used
only twenty selected terms with a low document
frequency as query terms.

QTE2 Only terms of a morpheme's combination withspeci c parts of speech, such as a noun and an
out-of-vocabulary word, are extracted as query
terms.

QTE2 is a query-term-extraction method that is
applied as part of the general-information retrieval.
Through the QTE1 method, a newspaper article that
includes a longer query term can be searched with ahigher score.
(e) Query-term weighting
When the parts of speech of the query terms are aproper noun and an out-of-vocabulary word, a higherscore is given to the query terms.

Proceedings of the Third NTCIR Workshop(f) Document Retrieval
Using the extracted query terms and their scores, thesystem searches newspaper articles in the databaseto nd documents that include the question's answer
phrase. We did a relevance ranking of the articles using the BM25 probabilistic retrieval formula [3], andused the ten top-ranked documents for the subsequent
processing.

(g) Passage extraction
Candidate passages that may include the answer are
speci ed and extracted from the top-ranked documents obtained in the previous step. Each passage
is given a score that depends on the importance ofthe query terms and the degree of concentration withwhich the terms appear [4].
Passages with a score above a set threshold become
candidate passages.

(3) Answer-extraction component
The answer-extraction component extracts a phrasethat matches the answer category from the obtained
candidate passage, and outputs the nal answer phrase.

(h) Information extraction
A phrase that belongs to the answer categories givenby the answer-categories speci cation is extracted
from the candidate passage. We use the same patternmatching engine as is used in the answer-categories
speci cation to extract an answer phrase. The answerextraction-pattern rules for each answer category werecreated manually.
When the answer category is "Unknown", a proper
noun is generally extracted as the answer phrase.
The extracted answer-candidate phrases are givenscores that are calculated using the answer category'sscore and the passage score. Thus, even identicalphrases can have di erent phrase scores depending on
the extracted candidate passage.

Ext racted phrase
Passage ID
scoreorange981212999-071 5.0
apple
990207888-003 4.0
apple
990905777-024 3.5
Ext racted phrase
appleorangesummed score
7.5
5.0

Figure 3: Phrase selection
the output order of the answer phrases is basedon the summed scores.
An example of phrase selection is shown in Fig.
3. Three answer phrases are extracted in this example. The phrase "apple" is extracted from two separate passages.
When using the ANS1 method, which outputs inthe order of the answer phrase score given for eachpassage, the rst answer phrase would be "orange"
and the second would be "apple". On the other hand,with the ANS2 method, where the scores of an identical answer phrase are summed, the rst answer phrase
would be "apple".

(j) Duplication-answer deletion
The system does not output the same answer phrase
within the question sentence.

(4) Task-oriented component
In addition to the processing components explained
above, we implemented task-oriented processing components. We explain each component here with respect to its sub-task characteristics.

(k) Passage retrieval by phrase structure (PRPS)

This is the processing that determines which phrases
will be output from among the extracted answercandidate phrases as a nal answer. We implemented
two types of selection sub-components: ANS1 andANS2.

We prepared another passage-retrieval component toimplement a passage-retrieval method that retrieves
similar passages with regard to the relationships between terms determined through syntactic analysis.
The syntax of the question sentence and each newspaper article is analyzed using the Kurohashi-Nagao
Parser (KNP). This method was applied to task 1 andtask 2.

based on the score given to each phrase in eachpassage. The same answer phrase is output only
once.

(l) Query-term extraction for series
questions (QTESQ)(i) Final-answer phrase selection

ANS1 The output order of the answer phrases is

ANS2 The scores of an identical answer phrase thatappears in di erent passages are summed andTask 3 is question answering for a series of questions
that are assumed to be continuously input.

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

Table 2: Evaluation results for task 1 for NTCIR-3 QAC ocial questions
Run name

MRR

NDQAS11NDQAS12NDQAS13
NDQAS14

0.362
0.313
0.404
0.436

1st
53
47
63
70

#Q at answer rank#Q
2nd 3rd 4th 5th not found Best
23 10
8
4
97
70
19
5
6
7
111
63
22
7
7
3
93
79
21
9
3
4
88
84

#Q

#Q

91
75
102
107

80
64
91
96

 Ave > Ave

Table 3: Evaluation results for tasks 2 and 3 for NTCIR-3 QAC ocial questions
Run nameFM

NDQAS21 0.149
NDQAS31 0.144#Q at FM range

0.8 0.6 0.4 0.2 >0
7
0

16
0

24
0

Table 1: Applied components
Task No
1
1
1
1
2
3

Run name Applied components
NDQAS11 QTE1+ANS1
NDQAS12 QTE1+ANS1+PRPS
NDQAS13 QTE1+ANS2
NDQAS14 QTE2+ANS2
NDQAS21 QTE1+ANS1+PRPS
NDQAS31 QTE1+ANS1+QTESQ

For such a task, it is necessary to use the information obtained for previous questions to get answers.
In our system, we use query terms that combine theterms extracted from the present question and theterms extracted from the previous question.

3 Experimental Results
In this section, we discuss the results of experimental
evaluations that used the data set of the NTCIR-3
QAC formal run.

3.1 Experimental conditions
In each task, the question-answering processing of theformal run's question was performed by choosing appropriate processing components. The list of appliedcomponents is shown in Table 1. When the number of
NDQAS12 output answers was less than ve, the output of NDQAS11 was added behind the NDQAS12
answers.

3.2 Experimental results
The numbers of questions for the evaluation of tasks
1, 2, and 3 were 195, 200, and 40, respectively. (Although the number of released questions for task 1 was

61
17

62
18

=0
138
22

#Q
Best
40
14

#Q

#Q

87
30

10
0

 Ave > Ave

200, ve questions that had no correct answer were excepted from the evaluation.) The evaluation measures
were the mean reciprocal rank (MRR) in task 1, andthe F-measure (FM) in tasks 2 and 3. The evaluation
results for task 1 are shown in Table 2, and those fortasks 2 and 3 are shown in Table 3.
We submitted two results for task 1 (NDQAS11
and NDQAS12) and one result for each of tasks 2 and 3(NDQAS21 and NDQAS31, respectively). Each task's
average evaluation value for the formal run was 0.303(task 1, MRR), 0.141 (task 2, FM), and 0.107 (task
3, FM). The questions where there was a large di erence in the evaluation value between our results andthe average are shown in Table 4 (best) and Table 5(worst).

3.3 Processing result for each component
Here, we analyze the processing of each component
based on the result for NDQAS11 in task 1.

(1) Question-analysis component
In the answer-category speci cation, 126 of 200 questions were correctly assigned to a category other than
"Unknown" in task 1. The number of questions assigned to the "Unknown" category was 55 (28%).
Many of the "Unknown" category questions had
a question expression such as "〜は何ですか" (Whatis/are ...?) and "〜は何といいますか" (What is/are ...
called?). The correct category for these questions
could not be determined through the interrogative
pattern rule only, and the answer category-judging
pattern for these questions was not yet de ned in oursystem.
Another question expression "〜はどこですか" also
led to many errors. The meaning of such a question

Proceedings of the Third NTCIR Workshop

Table 4: Best results and questions
Q No.

MRR
Ave.
1.000
0.100
1.000
0.167
1.000
0.217

NDQAS11

1
2
3

1067
1105
1172

4

1030

1.000

0.232

5

1180

1.000

0.236

1

1104

2
3

NDQAS12
1.000

Ave.
0.089

1055
1170

1.000
1.000

0.113
0.217

4

1172

1.000

0.217

5

1154

1.000

0.222

Question
Di .
0.900 What is absolute zero in centigrade?
0.833 What are the sequels to J.K. Rowlings Harry Potter and the Sorcerers Stone?
0.783 Who is the TV personality who got married saying that she felt a trembling
beam, beep, beep, beep?
0.768 What is the name of the government agency that oversees nancial businesses
and that became independent from the Ministry of Finance?
0.764 What is the name of the publishing house that publishes a magazine titledShukan Nichiroku 20 Seiki (Weekly Daily Records of the 20th Century)?
Di .
0.911 With which company did the automatic transmission manufacturer Jatco,
whose shares owned by Matsuda were all purchased by Nissan Motor, merge?
0.887 For which television drama did Koki Mitani write his rst script?
0.783 Where is the rst store which Costco, a major US supermarket chain, opened
in Japan?
0.783 Who is the TV personality who got married saying that she felt a trembling
beam, beep, beep, beep?
0.778 What planet is Europa a satellite of?

cannot be speci ed from only the expression, and acommon problem was that questions asking for an"Organization" name were categorized as "Location"questions in our system.

(2) Passage-retrieval component
In the passage-retrieval component, after the number of articles was narrowed down in the documentretrieval stage, more detailed passage-selection processing was done. We analyzed whether documentsor passages that included a correct answer were correctly searched in the document-retrieval and passageextraction stages.
Figure 6 shows the number of questions for which
we could retrieve a document/passage that included
the correct answer at a cuto point when N topranked document/passages were output. In the experiment, the candidate passage was chosen from the
top ten documents from the result of the documentretrieval stage and for 176 questions (90.3%) we could
retrieve a document that included the correct answer.
Moreover, in the passage extraction, the rates at cuto points of 10 and 100 passages were about 80% and90%, respectively. Thus, the passage-retrieval component worked well for most questions.

(3) Answer-extraction component
The answer-extraction stage extracted a correct answer phrase for 168 questions, but the answer phrases
for 71 questions were given a low phrase score, so thesequestions were not output within the nal answer.
Furthermore, seven questions had errors caused bya shortage of extraction patterns or an error regarding

the extraction character sequence length. For example, when the correct answer was "9.79 seconds", thesystem output only "9 seconds".
For 13 other questions, the system output answer
phrases that had the same meanings within the setof nal answer to each question (e.g., "Tokyo Disneyland" and "TDL").
When NDQAS11 was compared with NDQAS13
using the other answer extraction component, NDQAS13
output the exactly correct answer phrase. This suggests that the use of phrase information obtained frommany passages enables more correct answering of thequestions.

4 SummaryIn this paper, we have explained the processing of ourquestion-answering system, and brie y discussed andanalyzed our evaluation results. In the NTCIR-3
QAC, we applied a question-answering approach basedon a combination of an information-retrieval techniqueand an information-extraction technique.
Our experimental results suggest that applying a
conventional information-retrieval technique allowed
us to e ectively extract documents and passages that
included a correct answer. However, questions canvary in many ways, and our system did not respondadequately with regard to our present answer-categoryspeci cation module to some questions. The largescale Japanese question-answering test was built for
the rst time for the NTCIR-3 QAC, so further development of the question-answering technology is expected in the future.

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

Table 5: Worst results and questions
Q No.
1
2

1058
1136

3
4
5
5

1125
1119
1114
1131

1

1131

2
3
4
5

1037
1079
1100
1128

0.000
0.000

MRR
Ave.
0.817
0.816

Di .
-0.817-0.816

0.000
0.000
0.000
0.000

0.766
0.764
0.734
0.734

-0.766-0.764-0.734-0.734

0.000

Ave.
0.734

Di .
-0.734

0.000
0.000
0.000
0.000

0.689
0.566
0.545
0.485

-0.689-0.566-0.545-0.485NDQAS11NDQAS12

Question
Who are the Japanese laureates for the Nobel Prize for Physics?
When will the Law for Recycling of Speci ed Kinds of Home Appliances
become e ective?
In which two countries was the FIFA World Cup 2002 held?
Which country owns the space station Mir?
Who bombed Yugoslavia?
Which nuclear powers signed the Protocol to the Treaty on the Southeast Asia
Nuclear-Weapon-Free Zone?
Which nuclear powers signed the Protocol to the Treaty on the Southeast Asia
Nuclear-Weapon-Free Zone?
When did the i-mode services start?
Which world chess champion had a match against IBMs Deep Blue in 1997?
When was iMac rst launched in Japan?
Who won the French Open Tennis Womens Singles Championship after aninterval of three years?

Table 6: Accuracy of Document retrieval and Passage selection
Cuto point at
x documents/passages
1
2
3
4
5
10
20
30
50
100

#Q including relevant
document/phrase at cuto point
Document retrieval Passage selection
119 (61.0%)
83 (42.6%)
137 (70.3%)
110 (56.4%)
150 (76.9%)
126 (64.6%)
158 (81.0%)
139 (71.3%)
163 (83.6%)
142 (72.8%)
176 (90.3%)
157 (80.5%)185 (94.9%)
168 (86.2%)
185 (94.9%)
172 (88.2%)
189 (96.9%)
174 (89.2%)
191 (97.9%)
178 (91.3%)

References[1] Y. Eriguchi, T. Kitani: NTT Data Description of
the Erie System Used for MUC-6, In Proceedingsof Tipster Text Program (Phase II), pp. 469-470,
1996.
[2] J. Fukumoto and T. Kato: An Overview of Question and Answering Challenge (QAC) of the Next
NTCIR Workshop. In Proceedings of the Sec-In Proceedings of the Eighth Text Retrieval Conference (TREC-8), pages 523-530, 2000. NIST Spe-cial Publication 500-246.

[5] T. Takaki: NTT DATA TREC-9 Question Answering Track Report. In Proceedings of the Ninth
Text Retrieval Conference (TREC-9), pages 399406, 2001. NIST Special Publication 500-249.

ond NTCIR Workshop on Research in Chinese &Japanese Text Retrieval and Text Summarization,[6] E.M. Voorhees, The TREC-8 Question Answering Track Report. In Proceedings of the Eighth
Text Retrieval Conference (TREC-8), pages 77-82,
2000. NIST Special Publication 500-246.

[3] S. E. Robertson and S. Walker: Okapi/ Keenbow at TREC-8. In Proceedings of the Eighth Text
Retrieval Conference (TREC-8), pages 151-161,
2000. NIST Special Publication 500-246.

[7] E.M. Voorhees: Overview of the TREC-9 Question Answering Track. In Proceedings of the Ninth
Text Retrieval Conference (TREC-9), pages 71-79,
2001. NIST Special Publication 500-249.

pp.375-377, 2001.

[4] T. Takaki: NTT DATA: Overview of system approach at TREC-8 ad hoc and question answering.