４択クイズを連想問題として解く
外 池 昌 嗣佐 藤 理 史宇 津 呂 武 仁

京都大学大学院 情報学研究科
tonoike@pine.kuee.kyoto-u.ac.jp, {sato, utsuro}@i.kyoto-u.ac.jp
表 1 ヒット数
選択肢

1. は じ め に
近年、自然言語で与えられた質問に明確に答える、質問応答 (QA) と呼ばれるタスクが注目されている。例えば、「世界で一番高い山は何ですか？」という質問があれ

ヒット数

ジョージ・ルーカス
スティーブン・スピルバーグ
フランシス・フォード・コッポラ
黒澤明

349
120
86
72

ば、QA では「エベレスト」と答えることが求められる。
これまでの QA を分類すると大きく２つのタイプに分

しかしながら、これまでの QA ではどのような問題な

Q1: 「アメリカン・グラフィティ」の監督は誰？
a: ジョージ・ルーカス
b: スティーブン・スピルバーグ
c: フランシス・フォード・コッポラ
d: 黒澤明ら深い理解が必要で、どのような問題なら浅い理解でもあなたはこの問題の正解を知らず、ウェブのサーチエンジよい、といったことが考えられていない。問題の難易度ンを使ってその正解を探そうとしているとしよう。最もをある尺度で測定することもされていない。

簡単な方法は、キーワード「アメリカン・グラフィティ」

けることができる。１つは文の深い理解に基づく方法1)であり、もう１つはウェブなどの大量文書から得られる単語の頻度に基づく方法 2) である。

そこで、本研究では連想問題という問題のクラスを定をサーチエンジンに与えて、検索結果のページから４人義し、その難しさと効率的な解き方を示す。連想で解くの監督の一人を探すというものである。この戦略は、キーとは、文書中からその質問の答えだとわかるような記述ワード「アメリカン・グラフィティ」を含むウェブペーを探すのではなく、問題文中の重要語句に関係の深い語ジ上に正解が現れることを仮定している。

を探すことを意味する。

もう少し賢い方法は、選択肢の一つとキーワードの両

しかし、QA の枠組みでは問題が大きすぎるので、こ方を含むページ数を調べるというものである。
「アメリカの枠組みを大量文書から解候補を探すステップと、解候

ン・グラフィティ」と「ジョージ・ルーカス」の２つの語補の中から解を選ぶステップに分割し、後者のみを対象でアンド検索することで、このページ数はサーチエンジとする。この制限された枠組みには、解候補はあらかじンのヒット数から推測できる。この仮定に基づくと、最め与えられている４択クイズが当てはまる。

大のヒット数を持つ解候補を正解であると決定するのは☆ 3)

本研究では、「クイズ＄ミリオネア」を題材として、理にかなっている。

４択クイズを連想問題として解くことを試みる。情報源

上記の例であれば、この戦略は成功する。それぞれのとしては、膨大なデータがあり、関係の深い語が共起す解候補をキーワードと組み合わせたクエリーのヒット数る傾向があって、誰もが使いやすいウェブを用いる。そしを表 1 に示す。正解である「ジョージ・ルーカス」と組て問題文中のキーワードとサーチエンジン goo☆☆ の返すみ合わせたクエリーが、最大のヒット数を返している。

ヒット数だけを使って連想が実現できることを示す。こ上記の戦略は問題文から選んだキーワードのみを使うのの枠組みは、適切なキーワードを選ぶ問題と、ヒット数で、クイズは以下のような形式に変換することができる。

から解を決定する問題に分割できる。以下では、この小問題に対する分析と解決法について述べ、2 つの手法を実装する。そして、この方法で「クイズ＄ミリオネア」の問題の 8 割が解けることを示す。

2. 問題文中のキーワードによる解の連想
ここに「クイズ＄ミリオネア」の例がある。

Q1’: 「アメリカン・グラフィティ」
a: ジョージ・ルーカス
b: スティーブン・スピルバーグ
c: フランシス・フォード・コッポラ
d: 黒澤明この変換された形式は、キーワードと選択肢の結び付きや関係の程度を問うものである。言い換えれば、「次のうち与えられたキーワードと最も関係の深いものを選べ」と☆
☆☆

Celador 社がオリジナルを製作し、フジテレビが日本版を製作
http://www.goo.ne.jpいうことであり、これが連想問題である。

キーワード表 2 ヒット数の例
選択肢
選択肢のみカツオ

ノリ
コンブワカメサンゴ

アニメ

ノリコンブワカメサンゴ組み合わせ165000
12400
29100
52900
165000
12400
29100
52900

2240
882
6060
976
39400
643
2210
600

3. ヒット数の比を用いる手法
では、このキーワードをどのようにして機械的に選べばよいか。例として、次の問題を考える。

表3比の範囲比= 00 < 比 ≤ 0.01
0.01 < 比 ≤ 0.1
0.1 < 比 ≤ 0.25
0.25 < 比 ≤ 0.5
0.5 < 比 ≤ 0.75
0.75 < 比 ≤ 11<比
失敗
合計

ヒット数の比と正解率の関係
個数
正解数 (率)
不正解数 (率)

14425
163
158
14371
48
53
3808

132 (91.7%)
23 (92.0%)
143 (87.7%)
135 (85.4%)
92 (64.3%)
36 (50.7%)
20 (41.7%)
17 (32.1%)
0 (0%)
598 (74.0%)

12 (8.3%)
2 (8.0%)20 (12.3%)
23 (14.6%)
51 (35.7%)
35 (49.3%)
28 (58.3%)
36 (67.9%)
3 (100%)210 (26.0%)

題文を日本語形態素解析システム JUMAN 2.62 で形態素解析し、その結果を使って、名詞を取り出してキーワードとする。ここで、複合名詞は結合した状態で取り出す。

A23 アニメ「サザエさん」で、カツオくんの妹の名前は？

ただし、疑問詞や形式名詞はキーワードとしない。次にA. ノリ, B. コンブ, C. ワカメ, D. サンゴ[正解: ワカメ]
ここでは、その中からキーワードとして、以下のものを選んだ場合について考える。
• カツオ

例えば、4 個のキーワードが抽出された場合は 24 = 16 通• アニメ
ここで、選択肢自身のヒット数と、キーワードと組み合わせたときのヒット数を求めた結果を表 2 に示す。 ヒッ
ト数 1 位を選ぶことにすると、前者のキーワードは「ワカメ」を、後者は「ノリ」を支持している。どちらのキー取り出したキーワードのすべての組み合わせを生成する。
りの組み合せが生成される。そして、得られたキーワードの組み合わせすべてに対して、上記のヒット数の比を計算する。最後に比が最少であるキーワードの組み合せの場合の、ヒット数 1 位の選択肢を最終解とする。ただし、1 位のヒット数が 3 未満またはヒット数の差が 2 未満であれば、信用できないので使わない。

3.2 ヒット数の比と正解率の関係
前節で作成したシステムを使って、ヒット数の比と正解率の関係を調べる。まず、問題セットを作成する。本ワードがふさわしいのかを決定するために、キーワード研究では、４択クイズとして、トミー社から発売されてによってどれぐらい検索結果が絞り込まれたのかを調べいるカードゲーム版の「クイズ＄ミリオネア」の問題をる。すなわち、キーワードと組み合わせたときのヒット用いた。ゲーム版の問題は、1960 問あり、それらは、賞数が 1 位の選択肢と 2 位の選択肢に注目し、選択肢自身金額別に A(￥10,000)〜O(￥10,000,000) の 15 クラスかのヒット数の比と、キーワードと組み合わせたときのヒッらなる。ここでは、それぞれのクラスを 2 つに分割し、ト数の比という２つの比の値の比を調べる。これを式で半分 (980 問) を分析用の問題セットとして、残り半分を書いたものを以下に示す。ただし X1st はキーワードと組評価用の問題セットとして使用する。ここでは、分析用み合わせたときのヒット数 1 位の選択肢を、X2nd は 2 位セットから、否定、比較、数値を含む問題を除いた、808の選択肢を、Y はキーワードを表すものとする。

問からなる問題セットを作成した。

hits(X2nd andY )hits(X1st andY )hits(X2nd )hits(X1st )この問題セットを使って得られた、ヒット数の比と正解率の関係を表 3 に示す。 ここで、比が 0.25 以下の問題を数えると 490 問あり、これは全体の 60.6%を占める。

この値が、1 より小であれば、キーワードと組み合わ

そして、この範囲での正解率は 88.4%であった。すなわせることによって、ヒット数の差が開いたことを意味す

ち、比が 0.25 以下であれば、この手法で選ばれる答えはる。それぞれのキーワードに対して、この値を求めると、かなり信用できるものである。一方で、この範囲にあて「カツオ」は 0.0652、「アニメ」は 0.254 であった。これはまらない問題は別の解法で解くことが考えられる。

は、「カツオ」の方がより絞り込みに貢献する語であることを意味していると考えられる。そこで、すべてのキーワードの組み合せに対してこの値を計算し、この値が最4. 言語知識とヒット数を用いる手法
4.1 キーワード抽出

少のキーワードを選ぶという方法が考えられる。そして、2 章で検討した方法で問題を機械的に解くには、問題文このキーワードと組み合わせたヒット数が最大の選択肢から適切なキーワードを抽出することが必要となる。そを選ぶ。この問題であれば、キーワードとして「カツオ」

こで、語の種類とヒット数により語の重要さを推測してが選ばれ、解として「ワカメ」を選択することになる。

重要度を付与し、その上位語を抽出する。語の種類で重要3.1 手法の実装なのは、人名や組織名などの固有名詞である。キーワー

上記の考え方で問題を解く手法を実装した。まず、問ドの個数に関しては、多すぎるとサーチエンジンでヒッ表 4 重み付けのルール
条件

n 番目の文節「日本」で始まる
ストップワード「」中の語句人名
組織名
サ変名詞＋サ変動詞
関係を表す語カタカナ (重要でないものを除く)「賞」で終わる「時代」で終わる
国名
数字
疑問詞より後ろヒット数が 10 より小ヒット数が 10000000 より大ヒット数が 1000000 より大 and １文字
西暦 and 文中に「初」がある
西暦 and 文中に「初」がない
キーワードの後ろに「は」が存在 and「者」または「家」で終わる
ヒット数が 100000 より大ヒット数が 10000 より小文字数が 1
文字数が 2
文字数が 3
文字数が 4
文字数が 5 以上て評価できる。しかし、アンド検索のヒット数は選択肢

重み1 + 0.01 * n0.8033
1.5
0.5
222
0.5
0.5
30.2
0.3
0.5
0.92
1.5
0.1
0.2
1.1
0.2
0.25
0.5
1.1
1.2

自身のヒット数の影響を受ける。選択肢のヒット数が大きければ、アンド検索のヒット数も大きくなる。そこで、正規化することが求められる。
佐藤と佐々木は、ヒット数から２つの語の関係の程度を評価するための２つの距離 4) を提案した。

a(X, Y) = hits(X and Y)/hits(X)a(Y, X) = hits(Y and X)/hits(Y)X をキーワード、Y を選択肢とすると、我々のアプリケーションでは hits(X) は定数なので、a(X, Y) は hits(X andY) に比例する。a(Y, X) は正規化された値である。
本稿では、１つ目の距離をフォワードアソシエーショ
ン、２つ目の距離をバックワードアソシエーションと呼ぶ。
fa(X, Y) = a(X, Y);ba(X, Y) = a(Y, X);
ba が正しい答えを返すこともあるが、概して、fa の方がba よりも信頼できる。
4.2.2 決定ルール
ここでは、fa が 1 位の選択肢か ba が 1 位の選択肢か、どちらを選ぶかを決定する。この時点までに、データとして以下のものが得られている。

以上の考え方でキーワードを抽出するアルゴリズムを• キーワードのみのヒット数• 選択肢のみのヒット数• 選択肢＋キーワードのヒット数
これら自身とこれらから計算できる ba の値、fa の比、ba以下に示す。日本語構文解析には KNP 2.0 を使用する。の比を利用してどちらを選ぶかを決定する。検索結果をトを得られなくなることを考慮して１個か２個とした。

(1)
(2)

問題文を KNP で構文解析する分析し、次のようなルールを作成した。このルールは上

文節列を先頭から順に調べるから順に、最初にマッチしたものが適用される。

(a)
(b)
(c)

文節から自立語のみを切り出す(1)

名詞であれば候補語として抽出する
構文情報または形態素情報で、「人名」、「地名」、「組織名」、「カタカナ」、「数字」などの特徴があれば、フラグを立てる「」中の語句を抽出する

fa と ba の支持する選択肢が同じであれば、それを採用する

(2)
(3)
(4)
(5)

fa が僅差 (比が 0.8 以上) なら、ba を信用する
fa が大差 (比が 0.2 以下) なら、fa を信用する
ba が僅差 (比が 0.8 以上) なら、fa を信用する
キーワードのヒット数が大きければ (1300 以上)、ba を信用する

(3)
(4)

すべての選択肢に含まれている語を削除する

(5)
(6)

それぞれの候補語のヒット数を調べ、ヒット数が(7)(8)

15 未満のものを削除する
候補語に重要度を付与する
重要度の低い語から順に、個数が 2 個以下でアンfa がそれほど離れていない (比が 0.6 以上) なら、ba を信用する( 7 ) それ以外は fa を信用する
ここで、前述の 808 問の問題セットで調べると、fa とba が一致する問題は 494 問であり、このうち 452 問が正ド検索のヒット数が 15 以上になるまで削除する解であった。半数以上の問題の fa と ba が一致し、このKNP で判別できない人名を同定する

手順 (7) では、品詞やヒット数や係り受けなどの素性を利用して、抽出された語句は重みを付ける。重み付けのルールを表 4 に示す。候補語の初期スコアは 1 とし、ルールにマッチしたらその重みを乗算する。このルール(6)

うち 9 割以上は正解であった。fa と ba が一致することは重要な判断基準となることが確かめられた。

5. 実

験

4.2 解 の 決 定
4.2.1 フォワードとバックワードのアソシエーション

5.1 組み合わせ手法
これまでに説明した、ヒット数の比を用いる手法と語彙知識とヒット数を用いる手法の２つを組み合わせた、新たな手法を設計する。ここではまず、問題をヒット数の語と語の関係の強さは、アンド検索のヒット数によっ比を用いる手法で解く。このとき、最少の比が 0.25 以下では、「」中の語句や人名、組織名など具体的な事物を表す語を重視している。

表 7 組み合せ手法の内訳

表 5 実験の結果
クローズテスト

オープンテスト

手法

正解率

正解率

ヒット数の比
言語知識とヒット数
組み合わせ

74.0%
79.2%
80.3%

72.9%
74.3%
77.0%

表 6 解決定ルールの比較
クローズテスト
オープンテスト手法

fa が 1 位
ba が 1 位
決定ルール

正解率
72.3%
69.4%
79.2%

正解率
69.0%
67.1%
74.3%

クローズテスト
内訳

オープンテスト

占める割合

正解率

占める割合

60.6%
39.4%
100%

88.4%
67.9%
80.3%

62.9%
37.1%
100%

ヒット数の比
言語知識とヒット数合計正解率
86.7%
60.6%
77.0%わかる。このことから、比が 0.25 以下という閾値が高い正解率を保証することが確かめられた。オープンテストの結果が単独の手法よりかなりよくなったのは、多くの問題がヒット数の比を用いる手法で解かれたことによる。

6. お わ り にであればこの手法の解を採用する。一方、比が 0.25 より

本研究では、４択クイズを連想問題とみなし、ヒット数大であれば語彙知識とヒット数を用いる方法で解き直し、を使って解く方法を 2 種類検討した。これらの手法を組その結果を採用する。

み合わせることにより、クローズテストで 80.3%、オー5.2 クローズテストとオープンテスト
これまでに、説明した手法でどれぐらいの問題が解けるのかを確かめるために、実験を行った。これまでに、使ってきた問題によるテストはクローズテストである。一方、オープンテスト用に、評価用セットから否定、比較、数プンテストで 77.0% の正解率を得ることができた。した値を含む問題を除いた、840 問からなる問題セットを作解を探す部分に貢献できるであろう。

成した。これらの問題セットを使って、3 種類の手法で実験を行った結果を表 5 に示す。

がって、言語知識とヒット数を組み合わせることによって、連想を実現できると言える。
本研究の手法は、一般の QA において、キーワードを抽出する部分と、何らかの方法で得られた解候補から正関連研究として、Magnini らはウェブのヒット数を利用して与えられた解候補が正しいかを検証する方法を提

ヒット数の比を用いる手法では、クローズテストとオー案 5) している。システムの構成は我々の語彙とヒット数プンテストで結果に大きな違いはなかった。この手法でを用いる方法と似ているが、本研究で成功した、ヒットは、問題に合わせてパラメータを調整することはしてい数を他の解候補と比較しながらキーワードを選択する要ないので、自然な結果と言える。オープンテストの結果

素は含まれていない。

が多少低いのは、キーワード取り出す際の、複合語を分割するルールの影響が考えられる。
一方、語彙知識とヒット数を用いる手法では、オープンテストで正解率が約 5%低下している。この手法では、キーワード抽出部及び解の決定部で様々なパラメータを調整しているので、その影響が考えられる。解の決定部が有効に機能しているかを調べるために、fa が 1 位の選択肢を答えにした場合と、ba が 1 位の選択肢を答えにした場合と比較した。その結果を表 6 に示す。 この結果、解決定ルールを使うと、単純にヒット数 1 位の選択肢を選ぶ手法よりも遥かによい結果が得られることがわかった。したがって、解決定ルールは有効であると言える。ここで、クローズテストとオープンテストの違いに注目する。すべての手法で、オープンテストの正解率が低下しているが、解決定ルールの低下が著しい。これは、キーワード抽出と解決定ルールの両方がクローズテストセット用に強く調整されてしまっている事を意味する。
組み合せ手法においては、残り 2 つの手法を単独で使うよりもよい結果となった。オープンテストではその差が顕著に現れている。この現象を説明するために、どちらの手法が使われたのかの内訳の統計を表 7 に示す。 これを見ると、ヒット数の比を用いる手法で解いた問題はどちらのテストセットでも高い精度で解けていることが今後の課題としては、これらの手法で有益であるとわかった素性を利用して、機械学習でパラメータを調整することを考えている。そして、今回考慮していなかった文型情報についても検討する予定である。

参考 文

献

1) Moldvan, D., Harabagiu, S., Girju, R., Morarescu,
P. and Lacatusu, F.: LCC Tools for Question
Answering, Proceedings of the Eleventh Text REtrieval Conference (TREC 2002) (2003).
2) Kwok, C. C. T., Etzioni, O. and Weld, D. S.: Scaling Question Answering to the Web, Proceedingsof the 10th International World Wide Web Conference, pp. 150–161 (2001).
3) クイズ＄ミリオネア (編): 完全攻略！クイズ＄ミリオネア, フジテレビ出版 (2002).
4) Sato, S. and Sasaki, Y.: Automatic Collection ofRelated Terms from the Web, Proceedings of ACL
2003 , pp. 121–124 (2003).
5) Magnini, B., Negri, M., Prevete, R. and Tanev,
H.: Is It the Right Answer? Exploiting Web Redundancy for Answer Validation, Proceedings ofthe 40th Annual Meeting of ACL, pp. 425–432(2002).