Answer Validation by Keyword Association
Masatsugu Tonoike, Takehito Utsuro and Satoshi Sato
Graduate school of Informatics, Kyoto University
Yoshida-Honmachi, Sakyo-ku 606-8501 Kyoto, JAPAN{tonoike,utsuro,sato}@pine.kuee.kyoto-u.ac.jp
Abstract
Answer validation is a component of question
answering system, which selects reliable answer
from answer candidates extracted by certain
methods. In this paper, we propose an approachof answer validation based on the strengths oflexical association between the keywords extracted from a question sentence and each answer candidate. The proposed answer validation process is decomposed into two steps: theﬁrst is to extract appropriate keywords from aquestion sentence using word features and thestrength of lexical association, while the second
is to estimate the strength of the association
between the keywords and an answer candidate
based on the hits of search engines. In the result of experimental evaluation, we show that agood proportion (79%) of a multiple-choice quiz
“Who wants to be a millionaire” can be solvedby the proposed method.

1

Introduction

The technology of searching for the answer ofa question written in natural language is called“Question Answering”(QA), and has gotten alot of attention recently. Research activities of
QA have been promoted through competitions
such as TREC QA Track (Voorhees, 2004) and
NTCIR QAC (Fukumoto et al., 2004). Question answering systems can be decomposed into
two steps: ﬁrst step is to collect answer candidates, while the second is to validate each of
those candidates. The ﬁrst step of collecting answer candidates has been well studied so far. Its
standard technology is as follows: ﬁrst, the answer type of a question, such as LOCATION or
PERSON, is identiﬁed. Then, the documents
which may contain answer candidates are retrieved by querying available document set with
queries generated from the question sentence.
Finally, named entities which match the answer
type of the question sentence are collected fromthe retrieved documents as answer candidates.
In this paper, we focus on the second step of
how to validate an answer candidate. Several

answer validation methods have been proposed.
One of the well-known approaches is that basedon deep understanding of text (e.g. Moldovan
et al. (2003)). In the approach of answer validation based on deep understanding, ﬁrst a question and the paragraph including an answer candidate are parsed and transformed into logicalforms. Second, the validity of the answer candidate is examined through logical inference. One
drawback of this approach is that it requires arich set of lexical knowledge such as WordNet
and world knowledge such as the inference ruleset. Consequently, this approach is computationally expensive. In contrast, in this paper,
we propose another approach of answer validation, which is purely based on the estimation of the strengths of lexical association between the keywords extracted from a question
sentence and each answer candidate. One underlying motivation of this paper is to examine the eﬀectiveness of quite low level semantic
operation such as measuring lexical association
against knowledge rich NLP tasks such as answer validation of question answering. Surprisingly, as we show later, given multiple-choices as
answer candidates of a question, a good proportion of a certain set of questions can be solved
by our method based on lexical association.
In our framework of answer validation by keyword association (in the remaining of this paper,
we call the notion of the lexical association introduced above as “keyword association”), theanswer validation process is decomposed into
two steps: the ﬁrst step is to extract appropriate keywords from a question sentence, while
the second step is to estimate the strength of
the association between the keywords and an
answer candidate. We propose two methods forthe keyword selection step: one is by a small
number of hand-crafted rules for determining
word weights based on word features, while theother is based on search engine hits. In the second step of how to validate an answer candidate,
the web is used as a knowledge base for estimating the strength of the association between theextracted keywords and an answer candidate.

Its basic idea is as follows: the stronger the association between the keywords and an answer
candidate, the more frequently they co-occur on
the web. In this paper, we introduce several
measures for estimating the strength of the association, and show their eﬀectiveness throughexperimental evaluation.
In this paper, in order to concentrate on theissue of answer validation, but not the whole QA
processes, we use an existing multiple-choice
quiz as the material for our study. The multiplechoice quiz we used is taken from “Who wants tobe a millionaire”. “Who wants to be a millionaire” is a famous TV show, which originated in
the United Kingdom and has been localized in
more than ﬁfty countries. We used the Japaneseversion, which is produced by Fuji Television
Network, Inc.. In the experimental evaluation,
about 80% of the questions of this quiz can besolved by the proposed method of answer validation by keyword association.
Section 2 introduces the idea of question answering by keyword association. Section 3 describes how to select keywords from a question
sentence. Section 4 describes how to select theanswer of multiple-choice questions. Section 5
describes how to integrate the procedures of
keyword selection and answer selection. Section 6 presents the results of experimental evaluations. Section 7 compares our work with several related works Section 8 presents our conclusion and future works.

2

Answer Validation by Keyword
Association

2.1

Keyword Association

Here is an example of the multiple-choice quiz.
Q1: Who is the director of “American Graﬃti”?
a: George Lucasb: Steven Spielberg
c: Francis Ford Coppola
d: Akira Kurosawa
Suppose that you do not know the correct answer and try to ﬁnd it using a search engine
on the Web. The simplest way is to input thequery “American Graﬃti” to the search engine
and skim the retrieved pages. This strategy assumes that the correct answer may appear on
the page that includes the keyword “American
Graﬃti”. A little cleverer way is to consider thenumber of pages that contain both the keyword
and a choice. This number can be estimated

Table 1: Hits of Keywords and the Choices for
the Question Q1 (X:“American Graﬃti”)
Y (choice)“George Lucas”“Steven Spielberg”“Francis Ford Coppola”“Akira Kurosawa”

hits(X and Y )15,500
5,220
4,800
836

from the hits of a search engine when you input a conjunct query “American Graﬃti” and“George Lucas”. Based on this assumption, it isreasonable to hypothesize that the choice which
has the largest hits is the answer. For the above
question Q1, this strategy works. Table 1 shows
the hits of the conjunct queries for each of the
choices. We used “google1 ” as a search engine.
Here, let X be the set of keywords, Y be thechoice. Function hits is deﬁned as follows.
hits(X) ≡ hits(x1 AND x2 AND · · · AND xn )where
X = {x1 , x2 , . . . , xn }The conjunct query with “George Lucas”, whichis the correct answer, returns the largest hits.
Here, the question Q1 can be regarded as aquestion on the strength of association between
keyword and an choice, and converted into thefollowing form.
Q1 : Select the one that has the strongest association with “American Graﬃti”.
a: George Lucasb: Steven Spielberg
c: Francis Ford Coppola
d: Akira Kurosawa
We call this association between the keyword
and the choice as keyword association.
2.2 How to Select Keywords
It is important to select appropriate keywords
from a question sentence. Consider the following question.
Q2: Who is the original author of the famous
movie “Lord of the Rings”?
a: Elijah Woodb: JRR Tolkien
c: Peter Jacksond: Liv Tyler
The numbers of hits are shown in Table 2. Here,let X be “Lord of the Rings”, X  be “Lord of the1

http://www.google.com

Table 2: Hits of Keywords and the Choices
for the Question Q2 (X:“Lord of the Rings”,
X  :“Lord of the Rings” and “original author”)
Y (choice)“Elijah Wood”“JRR Tolkien”“Peter Jackson”“Liv Tyler”

hits(X and Y )682,000
652,000
1,140,000
545,000hits(X  and Y )
213
702
340
106

keywords and Y be the choice. In this paper,
we call the hits of a conjunct query consistingof keywords X and a choice Y , which is normalized by the hits of X, as forward association
F A(X, Y ). We also call the hits of a conjunctquery X and Y , which is normalized by the hitsof Y , as backward association BA(X, Y ).
F A(X, Y ) = hits(X ∪ {Y })/hits(X)BA(X, Y ) = hits(X ∪ {Y })/hits({Y })Rings” and “original author”. When you selectthe title of this movie “Lord of the Rings” as a
keyword, the choice with the maximum hits is“Peter Jackson”, which is not the correct answer “JRR Tolkien”. However, if you select“Lord of the Rings” and “original author” askeywords, this question can be solved by selecting the choice with maximum hits. Therefore,
it is clear from this example that how to selectappropriate keywords is important.

Note that when X is ﬁxed, F A(X, Y ) is proportional to hits(X ∪ {Y }).
Let’s go back to Q3. In this case, the choicewith the maximum BA is correct. Some questions may solved by referring to F A, while others may be solved only by referring to BA.
Therefore, it is inevitable to invent a mechanism which switches between F A and BA.

2.3

Based on the observation of Sections 2.1 ∼ 2.3,
the following three questions must be addressedby answer validation based on keyword association.

Forward and Backward Association

For certain questions, it is not enough to generate a conjunct query consisting of some keywords and a choice, and then to simply selectthe choice with maximum hits. This section introduces more sophisticated measures for selecting an appropriate answer. Consider the following question.

2.4• How to select appropriate keywords from aquestion sentence.
• How to identify the correct answer considering forward and/or backward association.

Q3: Where is Pyramid?
a: Canadab: Egyptc: Japand: China
The numbers of hits are shown in Table 3. In
this case, given a conjunct query consisting ofa keyword “Pyramid” and a choice, the choicewith the maximum hits, i.e., “Canada” is not
the correct answer “Egypt”. Why could not thisquestion be solved? Let us consider the hits ofthe choices alone. The hits of the atomic query“Canada” is about seven times larger than thehits of the atomic query “Egypt”. With this observation, we can hypothesize that the hits of a
conjunct query “Pyramid” and a choice are affected by the hits of the choice alone. Therefore
some normalization might be required.
Based on the analysis above, we employ the
metrics proposed by Sato and Sasaki (2003).
Sato and Sasaki (2003) has proposed two metrics for evaluating the strength of the relationof two terms. Suppose that X be the set of

Summary• How many questions can be solved by thisstrategy based on keyword association.

3

Keyword Selection

This section describes two methods for selecting
appropriate keywords from a question sentence:
one is based on the features of each word, theother based on hits of a search engine.
First, all the nouns are extracted from thequestion sentence using a Japanese morphological analyzer JUMAN(Kurohashi and Nagao,1999) and a Japanese parser KNP(Kurohashi,1998). Here, when the sequence of nouns constitute a compound, only the longest compoundis extracted and their constituent nouns are notextracted. Let N denote the set of those extracted nouns and compounds, from which keywords are selected. In the following, the searchengine “goo2 ” is used for obtaining the numberof hits.
2

http://www.goo.ne.jp

Table 3: Hits of Keywords and the Choices for the Question Q3
X(keyword)
PyramidY(choice)
Canada
Egypt
Japan
China

3.1

hits(X)
3,170,000
hits(Y )100,000,000
14,500,000
63,100,000
53,600,000

hits(Y and X)
334,000
325,000
246,000
225,000

Keyword Selection Based on Word
FeaturesIn this method, keywords are selected by thefollowing procedure:
1. If the question sentence contains n quotations with quotation marks ‘「’ and ‘」’,
those n quoted strings are selected as keywords.
2. Otherwise:
2-1. According to the rules for word
weights in Table 4, weights are assigned to each element of the keyword
candidate set N .
2-2. Select the keyword candidate with the
maximum weight and that with thesecond maximum weight.
2-3. i. If the hits of AND search of those
two keyword candidates are 15 ormore, both are selected as keywords.
ii. Otherwise, select the one with the
maximum weight.
Let k denote the set of the selected keywords(k ⊆ N ), we examine the correctness of k as
follows. Let c denote a choice, cF1 A (k) the
choice with the maximum F A(k, c), and cBA
1 (k)the choice with the maximum BA(k, c), respectively.
cF1 A (k) = argmax F A(k, c)
c

cBA
1 (k)

= argmax BA(k, c)cHere, we regard the selected keywords k to becorrect if either cF1 A (k) or cBA
1 (k) is correct.
Against the development set which is to be introduced in Section 6.1, the correct rate of the
keywords selected by the procedure above is
84.5%.

FA(X, Y )
0.105
0.103
0.0776
0.0710BA(X, Y )0.00334
0.02240.003900.00420

Table 4: Rules for Word Weights
rulen-th segment
stopword
quoted by quotation marks「」
person nameverbal nouns (‘sahen’-verb stem)
word which expresses relation
Katakana
name of an award
name of an era
name of a country
numberhits > 1000000
and consists of one charactermarked by a topic maker andname of a jobhits > 100000
hits < 10000
number of characters = 1
number of characters = 2
number of characters = 3
number of characters = 4
number of characters ≥ 5weight(1 +0.01 × n)
0
3
3
0.5
2
2
2
0.5
0.5
3
0.9
0.1
0.2
1.1
0.2
0.25
0.5
1.1
1.2

3.2

Keyword Selection Based on Hitsof Search Engine
3.2.1 Basic Methods
First, we introduce several basic methods forselecting keywords based on hits of a search engine. Let 2N denote the power set of N , where aset of keywords k is an element of 2N (k ∈ 2N ).
Let k̂ denote the selected set of keywords and ĉthe selected choice.
The ﬁrst method is to simply select the pairof k̂, ĉ which gives the maximum hits as below:k̂, ĉ = argmax hits(k ∪ {c})c, k∈2N

Against the development set, the correct rate of
the choice which is selected by this method is35.7%.
In a similar way, another method which se-lects the maximum F A or BA can be given as
below:

Table 5: Evaluation of Keyword Association
Ratios (precision/coverage)(%)

k̂, ĉ = argmax F A(k ∪ {c})c, k∈2N

k̂, ĉ = argmax BA(k ∪ {c})c, k∈2N

Their correct rates are 71.3% and 36.1%, respectively.
3.2.2 Keyword Association Ratio
Next, we introduce more sophisticated methods which use the ratio of maximum and second maximum associations such as F A or BA.
The underlying assumption of those methods
are that: the greater those ratios are, the morereliable is the selected choice with the maximum
F A/BA. First, we introduce two methods: F A
ratio and BA ratio.
F A ratio This is the ratio of F A of the choicewith second maximum F A over one with maximum F A. F A ratio is calculated by the following procedure.
1. Select the choices with maximum F A andsecond maximum F A.
2. Estimate the correctness of the choice withmaximum F A by the ratio of their F As.
The set k̂ of keywords and the choice ĉ to be
selected by F A ratio are expressed as below:k̂ = argminĉ =cF2 A (k)k∈2NFAc1 (k̂)F A(k, cF2 A (k))
F A(k, cF1 A (k))= arg-secondmax F A(k, c)cwhere arg-secondmaxc is deﬁned as a function
which selects c with second maximum value.
Similarly, the method based on BA ratio is
given as below:
BA ratiok̂ = argmin
ĉ =
cBA
2 (k)

k∈2N
BA
c1 (k̂)BA(k, cBA
2 (k))BA(k, cBA
1 (k))= arg-secondmax BA(k, c)cUnlike the methods based on F A ratio and
BA ratio, the following two methods consider
both F A and BA. The motivation of those two
methods is to regard the decision by F A and
BA to be reliable if F A and BA agree on selecting the choice.

ratio

FA
BA

max and second max
FABA
63.1/100 70.6/95.0
75.8/93.2 67.6/100

BA ratio with maximum and second maximum F A
k̂ = argmin
ĉ =

k∈2N
cF1 A (k̂)

BA(k, cF2 A (k))
BA(k, cF1 A (k))

F A ratio with maximum and second maximum BAk̂ = argmin
ĉ =

k∈2N
cBA
1 (k̂)F A(k, cBA
2 (k))F A(k, cBA
1 (k))

Coverages and precisions of these four methods
against the development set are shown in Table 5. Coverage is measured as the rate of questions for which the ratio is less than or equal to
13 . Precisions are measured as the rate of questions for which the selected choice ĉ is the correct answer, over those covered questions. The
method having the greatest precision is BA ratio with maximum and second maximum F A.
In the following sections, we use this ratio as
the keyword association ratio. Table 6 farther
examines the correlation of the range of the ratio and the coverage/precision. When the ratio
is less than or equal to 0.25, about 60% of thequestions are solved with the precision close to90%. This threshold of 0.25 is used in the Section 5 when integrating the keyword association
ratio and word weights.

4

Answer Selection

In this section, we explain a method to identify
the correct answer considering forward and/or
backward association. After selecting keywords,
the following numbers are obtained by a searchengine.
• Hits of the keywords X: hits(X)• Hits of the choice Y : hits({Y })3

For the ratios considering both F A and BA, theratio greater than 1 means that F A and BA disagree on
selecting the choice.

Table 6: Evaluation of Keyword Association
Ratio: BA ratio of F A max and second-max
ratio
0≤ 0.01≤ 0.1≤ 0.25≤ 0.5≤ 0.75≤1# of questions
coverageprecision
18.9% (163/888)
89.6% (146/163)
21.5% (191/888)
89.5% (171/191)
40.5% (360/888)
87.5% (315/360)
60.4% (536/888) 86.9% (466/536)
78.0% (693/888)
81.6% (566/693)
87.2% (774/888)
78.4% (607/774)
93.2% (828/888)
75.8% (628/828)

Table 7: Precision of Answer Selection (withkeyword selection by word weights)
methodmax F Amax BA
selection rule

Table 8: Evaluation of Each Answer Selection
Rule (with keyword selection by word weights)
rule
1
2∼6
total
2
3
4
5
6
7

• Hits of the conjunct query:hits(X ∪ {Y })Then for each choice Y , F A and BA are calculated. As introduced in section 3, cF1 A (k) denotes the choice whose F A value is highest, andcBA
1 (k) the choice whose BA value is highest.
What has to done here is to decide which of
cF1 A (k) and cBA
1 (k) is correct.
After manually analyzing the search engine
hits against the development set, we handcrafted the following rules for switching between
cF1 A (k) and cBA
1 (k).
FA
1. if cF1 A (k) = cBA
1 (k) then c1 (k)F A(k,cBA (k))

2. else if F A(k,c1F A (k)) ≥ 0.8 then cBA
1 (k)1

F A(k,cBA (k))
3. else if F A(k,c1F A (k)) ≤ 0.2 then cF1 A (k)1BA(k,cF A (k))

1
≥ 0.53 then cF1 A (k)4. else if BA(k,cBA(k))

F A(k,cBA (k))
6. else if F A(k,c1F A (k)) ≥ 0.6 then cBA
1 (k)
1

5

4

Four questions are excluded because hits of the conjunct query hits(X ∪ {Y }) were 0

-

cBA
1 (k)
A
cF
1 (k)
FA
c1 (k)
cBA
1 (k)
cBA
1 (k)
A
cF
1 (k)

precision
88.5% (479/541)
60.3% (207/343)
77.6% (686/884)
65.3% (32/49)
61.8% (68/110)
53.6% (37/69)
60.3% (35/58)
66.7% (12/18)
59.0% (23/39)

Total Procedure of Keyword
Selection and Answer Selection

Finally, the procedures of keyword selection andanswer selection presented in the previous sections are integrated as given below:

7. else cF1 A (k)Table 7 shows the results of evaluating precision of answer selection methods against the development set, when the keywords are selectedbased on word weights in Section 3.1. In thetable, in addition to the result of answer selection rules above, the results with baselines of
selecting the choice with maximum F A or BA
are also shown. It is clear from the table thatthe answer selection rules described here significantly outperforms those baselines.
For each of the answer selection rules, Table 8 shows its precision. In the development
set4 , there are 541 questions (about 60%) whereanswerA
BA
cF
1 (k) = c1 (k)cF1 A (k) and cBA
1 (k) are identical, and the 88.5%of the selected choices are correct. This result shows that more than half of the questions
cF1 A (k) is equal to cBA
1 (k) and about 90% of
these questions can be solved. This result showsthat whether F A and BA agree or not is very
important and is crucial for reliably selecting
the answer.

1

5. else if hits(k) ≥ 1300 then cBA
1 (k)precision
70.8%
67.6%
77.3%

1. If ratio ≤ 0.25:
Use the set of keywords selected by BA ratio with maximum and second maximum
F A. The choice to be selected is the one
with maximum BA.
2. Otherwise:
Use the set of keywords selected by word
weights. Answer selection is done by theprocedure of Section4.

6

Evaluation

6.1 Data Set
In this research, we used the card game version of “クイズ＄ミリオネア (Who wants to be amillionaire)”, which is sold by Tomy Company,

LTD. It has 1960 questions, which are classiﬁed into ﬁfteen levels according to the amountof prize money. Each question has four choices.
All questions are written in Japanese. The followings give a few examples.

Table 9: The number of questions per prize
money amountprize money amount(yen)
10,00020,00030,00050,000100,000
150,000
250,000
500,000
750,000
1,000,000
1,500,000
2,500,000
5,000,000
7,500,000
10,000,000
total

10,000 yen level[A39] エジプトやケニアなどの国がある
大陸はどこ？
(Which continent are Egypt and
Kenya located in?)A. アフリカ大陸 (Africa)
B. ユーラシア大陸 (Eurasia)
C. 北アメリカ大陸 (North America)
D. 南アメリカ大陸 (South America)[Correct Answer: アフリカ大陸]
1,000,000 yen level[J39] コロンブスが新大陸発見の航海をしたときに乗っていた船の名前は何？
(What is the name of the ship in which
Columbus was sailing when he discovered a new continent?)
A. アトランティス号 (Atlantis)
B. アルゴ号 (Argo)
C. サンタマリア号 (Santa Maria)
D. ノーチラス号 (Nautilus)[Correct Answer: サンタマリア号]
10,000,000 yen level[O4] 夏期オリンピック大会で参加国数が初めて１００ヶ国を越えた大会はどれ？
(In which summer Olympics did thenumber of participating countries ﬁrst
exceed 100?)
A. ローマ五輪 (Rome Olympics)
B. 東京五輪 (Tokyo Olympics)
C. メキシコ五輪 (Mexico Olympics)
D. ミュンヘン五輪 (Munich Olympics)[Correct Answer: メキシコ五輪]
We divide questions of each level into two
halves: ﬁrst of which is used as the development set and the second as the test set. We
exclude questions with superlative expressions(e.g., Out of the following four countries, selectthe one with the maximum number of states.)or negation (e.g., Out of the following four colors, which is not used in the national ﬂag ofFrance.) because they are not suitable for solving by keyword association. Consequently, thedevelopment set comprises 888 questions, while
the test set comprises 906 questions. The number of questions per prize money amount isshown in Table 9.

# of questions
full dev test
160
71
74
160
71
77
160
67
70
160
75
71
160
73
73
160
76
72
160
71
77
160
74
77
160
78
71
160
73
76
120
53
58
90
38
42
70
30
32
50
24
21
30
14
15
1960 888 906

We compare the questions of “Who wants tobe a millionaire” with those of TREC 2003 QA
track and those of NTCIR4 QAC2 task. The
questions of “Who wants to be a millionaire”
are all classiﬁed as factoid question. They correspond to TREC 2003 QA track factoid component. The questions of NTCIR4 QAC2 arealso all classiﬁed as factoid question. We compare bunsetsu 5 count of the questions of “Whowants to be a millionaire” with word count of
the questions of TREC 2003 QA track factoid
component and bunsetsu count of the questionsof NTCIR4 QAC2 Subtask1. The questionsof “Who wants to be a millionaire” consist of
7.24 bunsetsu on average, while those of TREC
2003 QA track factoid component consist of 7.76
words on average, and those of NTCIR4 QAC2
Subtask1 consist of 6.19 bunsetsu on average.
Therefore, it can be concluded that the questions of “Who wants to be a millionaire” arenot shorter than those of TREC 2003 QA track
and those of NTCIR4 QAC2 task.
6.2 Results
Against the development and the test sets,
Table 10 shows the results of evaluating thetotal procedure of keyword selection and answer selection presented in Section 5. The table also shows the performance of baselines:
5

A bunsetsu is one of the linguistic units in Japanese.
A bunsetsu consists of one content word possibly followed by one or more function words.

Table 10: Total Evaluation Results (precision/coverage)(%)
test
74.6/93.6
73.4/10075.9/10086.0/61.5
59.9/38.5

㪈㪇㪇
㪐㪇
㪏㪇
㪎㪇
㪍㪇
㪌㪇
㪋㪇
㪊㪇
㪉㪇
㪈㪇
㪇
㪈㪇
㪉㪇㪃㪇㪇㪇
㪊㪇㪃㪇㪇㪇㪌 㪃㪇㪇㪈㪇 㪇㪃㪇㪇㪇
㪈㪌㪇㪃㪇㪇 㪇㪉㪌㪇㪃㪇㪇㪇
㪇㪌㪇 㪃㪇㪇㪇㪎 㪇㪃㪇 㪇㪈㪃㪇 㪌㪇㪃 㪇㪇㪇㪈㪃㪌㪇㪇㪃 㪇㪇㪇㪇㪇㪉㪃㪌 㪇㪃 㪇㪇㪌㪃㪇㪇㪇㪃 㪇㪇㪇㪎 㪇㪇 㪇㪇㪈㪇 㪃㪌㪇㪇㪃㪇㪇㪇㪃㪇㪇 㪃㪇
㪇㪃㪇㪇㪇㪇㪇㪧㫉㪼㪺㫀㫊㫀㫆㫅㩷㩿㩼㪀

methoddev
K.A.R. (r ≤ 1)
75.8/93.2
word weights
77.3/100+ answer selection
Integration
78.6/100
K.A.R. (r ≤ 0.25)
86.9/60.4
word weights (r > 0.25)
65.9/39.6+ answer selection
K.A.R.: keyword association ratio㪧㫉㫀㫑㪼㩷㫄㫆㫅㪼㫐㩷㪸㫄㫆㫌㫅㫋㩷㩿㪰㪼㫅㪀

Figure 1: Precision classiﬁed by prize money
amounti.e., keyword association ratio presented in Section 3.2.2, and word weights of Section 3.1 +answer selection of Section 4. Integration of
keyword association ratio and word weight outperforms those baselines. In total, about 79%(for the development set) and 76% (for the testset) of the questions are solved by the proposed
answer validation method based on keyword association.
Comparing the performance of the two data
sets, word weights + answer selection has 4%
lower precision in the test set. This result indicates that rules for word weights as well as answer selection rules overﬁt to the developmentset. On the other hand, the diﬀerence of the precisions of the keyword association ratio is muchless between the two data sets, indicating that
keyword association ratio has less overﬁt to thedevelopment set.
Finally, the result of the experiment where
the development set was solved by the integration method was classiﬁed by prize money

amount. The result is shown in Figure 1. The
more the prize money amount is, the lower the
precision seems to be, while their precisions are
all above 60%, and their diﬀerences are less than
20% in most cases. It can be concluded that oursystem can solve questions of all the levels almost equally.

7

Related Work

Kwok et al. (2001) proposed the ﬁrst automatedquestion-answering system which uses the web.
First, it collects documents that are related tothe question sentence using google and picks answer candidates up from them. Second, it selects an answer based on the frequency of candidates which appear near the keywords.
In the method proposed by Brill et al. (2002),
answer candidates are picked up from the summary pages returned by a search engine. Then,each answer candidate is validated by searchingfor relevant documents in the TREC QA document collection. Both methods do not consider
the number of hits returned by the search engine.
Magnini et al. (2002) proposed an answer validation method which uses the number of searchengine hits. They formulate search engine
queries using AltaVista’s OR and NEAR operators. Major diﬀerence between the method ofMagnini et al. (2002) and ours is in keyword selection. In the method of Magnini et al. (2002),
the initial keywords are content words extracted
from a question sentence. If the hits of keywords
is less than a threshold, the least important keyword is removed. This procedure is repeated until the hits of the keywords is over the threshold.
On the other hand, in our method, keywords
are selected so that the strength of the association between the keyword and an answer candidate is maximized. Intuitively, our method of
keyword selection is more natural than that ofMagnini et al. (2002), since it considers boththe question sentence and an answer candidate.
As for measures for scoring answer candidates,
Magnini et al. (2002) proposed three measures,out of which “Corrected Conditional Probability” performs best. In our implementation, theperformance of “Corrected Conditional Probability” is about 5% lower than our best result.

8

Conclusion and Future WorkIn this paper, we proposed an approach of answer validation based on the strengths of lexical association between the keywords extracted

from a question sentence and each answer candidate. The proposed answer validation process
is decomposed into two steps: the ﬁrst is to
extract appropriate keywords from a question
sentence using word features and the strengthof lexical association, while the second is to estimate the strength of the association between
the keywords and an answer candidate based on
the hits of search engines. In the result of experimental evaluation, we showed that a good proportion (79%) of the multiple-choice quiz “Whowants to be a millionaire” can be solved by the
proposed method.
Future works include the followings: ﬁrst, weare planning to examine whether the syntactic
structures of the question sentence is useful for
selecting appropriate keywords from the question sentence. Secondly, it is interesting to see
whether the keyword selection method proposedin this paper is also eﬀective for other applications such as answer candidate collection of thewhole question answering process.

References
E. Brill, J. Lin, M. Banko, S. Dumais, and A. Ng. 2002.
Data-intensive question answering. In Proc. TREC
2001.
J. Fukumoto, T. Kato, and F. Masui. 2004. Question
answering challenge for ﬁve ranked answers and list
answers -overview of ntcir4 qac2 subtask 1 and 2-. In
Proc. 4th NTCIR Workshop Meeting.
Sadao Kurohashi and Makoto Nagao, 1999. JapaneseMorphological Analysis System JUMAN version 3.62
Manual.
Sadao Kurohashi, 1998. Japanese Dependency/Case
Structure Analyzer KNP version 2.0b6 Manual.
C. C. T. Kwok, O. Etzioni, and D. S. Weld. 2001. Scaling question answering to the web. In Proc. the 10th
WWW Conf., pages 150–161.
B. Magnini, M. Negri, R. Prevete, and H. Tanev. 2002.
Is it the right answer? exploiting web redundancy foranswer validation. In Proc. 40th ACL, pages 425–432.
D. Moldovan, S. Harabagiu, R. Girju, P. Morarescu, andF. Lacatusu. 2003. Lcc tools for question answering.
In Proc. TREC 2002.
S. Sato and Y. Sasaki. 2003. Automatic collection ofrelated terms from the web. In Proc. 41st ACL, pages
121–124.
E. M. Voorhees. 2004. Overview of the trec 2003 question answering track. In Proc. TREC 2003.