言語処理学会 第21回年次大会 発表論文集 (2015年3月)

アレキサンダー大王の遠征は再現できるか？
〜人物移動モデルによる歴史文章解釈〜
村上優樹
鶴岡 慶雅
東京大学 電子情報工学科{murakami, tsuruoka}@logos.t.u-tokyo.ac.jp
はじめに1

自然言語の意味理解は近年研究が盛んに行われているが、用いられている手法の多くは自然言語の表層の情報をもとに確率統計処理するものである。しかし、自然言語の深い理解を得るためには世界知識やモデルがないと難しい [5]。例えば以下のような、与えられたテキストから質問に答える場面を考える。
テキスト「21 日の朝、太郎はフランスにいた。」

図 1: 提案手法概要図

質問「21 日に太郎は東京で昼ご飯を食べたか？」

われた SHRDLU[4] のデモはその代表である。これは答えは当然「誤」であるが、これを正しく判定するた積み木という限定された世界において自然言語を理解めにはフランスと東京の地理的位置関係や、飛行機のするモデルである。最近の研究では、Windows のマ移動時間、時差などの情報を用いた深い理解が必要でニュアルの文章と実際の操作の結果を組み合わせて、あり、従来の自然言語処理では処理するのは難しい。

文章をアクションとして理解させるもの [1] や、テキ本研究では例で示したような問題に対して、空間・ストから 3D モデルの位置関係などを理解させたり、時間など現実世界の定量的要素を含むモデルの例とし3D モデルを生成したりする研究 [2] などが発表されてて、人物がグラフ上を移動するモデルを考え、それにいる。これらの研究ではいずれもある限定された環境よって適切な言語処理が行えるかどうか検証する。具のなかで現実世界の情報をモデル化し用いることで、体例として「アレキサンダー大王の遠征」を取り上げ、自然言語を理解しようという試みがなされている。

当時の地図をグラフとして作成し、アレキサンダー大3

人物移動モデル

3.1

モデル概要

王が時間とともにグラフ上を移動するようなモデルを考える。ここに自然言語文から生成した制約条件を加え、それを満たすような軌跡をモンテカルロ木探索で空間・時間などの定量的な情報を含む自然言語を理求めることでアレキサンダー大王の移動を推測させ、解させるために、現実世界の限定された一部の情報をその結果をもとにして質問応答や照応解析を行う手法

扱うためのモデルを考える。提案する手法とモデルのを提案する。実験では実際に４択問題を用いて正解率概要を図 1 に示す。本研究では、ある人物がいくつかを求め、モデルを利用することで定量的な情報を含むの場所を移動するだけの単純な人物移動モデルを想定

問題を解けることを示した。また、照応解析についてする。このモデルは、時間が進むにつれて人物が基本も問題を用意し、モデルを用いて適切に処理できるこ的なルールにしたがってさまざまな場所を移動するよとを示した。

うに設定する (図 1-(a))。ただそれだけでは状態は無2

関連研究

2.1

現実のモデルを利用した自然言語理解作為に変化するだけなので、入力として与えられた自然言語文から、「誰がいつどこにいた」という情報を抽出し、それらを満たすべき制約条件とする (図 1-(b))。

現実の情報を利用したモデルの基本的な概念は昔かその制約条件を満たすように探索を行うことで、与えら研究されており 1971 年に T.Winograd によって行られた自然言語文の情報と整合性の取れた移動をモデ― 361 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

図 3: モンテカルロ木探索にモンテカルロ木探索を用いてそれらの制約をできる

図 2: モデル化された地図だけ満たすようなエピソードを複数求め、それらを利用してアレキサンダー大王の遠征に関する質問応答や表 1: 取れる行動 ( 隣接場所の数を n とする )行動
確率
移動しない隣接場所 (一つ前の場所以外) に移動
隣接場所 (一つ前の場所) に移動照応解析のタスクを試す。また、制約条件を生成するにあたって自然言語からの抽出を間違えた場合、それ22n+1
22n+1
12n+1をモデルを利用して検出できるかどうかも検証する。

3.4

モンテカルロ木探索

モンテカルロ木探索は囲碁などのゲーム AI 研究でルで表現できる (図 1-(c))。こうして得られた移動のよく用いられている探索手法である [3]。これは、候履歴をエピソードと定義する。エピソードを用いるこ補手（合法手）の中でその時点で最も有望そうなものとで、質問として与えられた「誰がいつどこに存在しを選択し、最後までランダムに試してみてその手を選たか」という内容の実現可能性を評価することができんだ場合の結果を評価することを繰り返す、最良優先る (図 1-(d))。

探索手法である。シミュレーションを最後まで試行す

3.2

ることをプレイアウトと呼ぶ。具体的なアルゴリズム

モデルの具体例・設定実験で扱う具体例として、「アレキサンダー大王のは次の通りである（図 3）。

遠征」を取り上げる。図 2 のように当時の地図をグラ

1. UCB 値が最大の候補手を選択フ化して、アレキサンダー大王を移動させることを考2. 候補手に対応するノードが存在しないとき (UCB= ∞) は枝を拡張してノードを作るえる。左上の「Pella」をアレキサンダー大王の初期位置とする。モデルのシミュレーションの単位時間は、1年間を 6 分割して 2ヶ月を 1 ステップとし、実際に遠征

3. そのノードからシミュレーションが終了するまでプレイアウトし、その結果を報酬値とするが起きた BC.334 から BC.323 の 12 年間、計 72 ステップ分のシミュレーションを行う。シミュレーションは

4. 木をさかのぼりながら報酬値をもとに UCB 値を更新する

1 ステップ時間が進むごとに、モデル内の人物は「移動しない」・「隣接場所に移動」のいずれかの行動をとるようにする。どの行動を選択するのかは表 1 の確率

ここで用いられている候補手・報酬値は、モデルではに基づいて無作為に選ぶようにする。表中の「一つ前それぞれ、1 ステップ後の状態・エピソードが満たしの場所」というのは、現在の場所に移動してくる前にた制約条件の割合に相当する。また、「ノード」は図いた場所という意味で、すぐ前の場所に戻ることは遠2 のグラフではなく図 3 に示される探索木のノードを征という行動では生じにくいと考えられることから確指す。UCB 値は以下の式 1 で表される。

率を半分にした。なお入力や質問応答に使用する自然√

言語文はアレキサンダー大王に関係するものとする。

3.3

U CB = X̄j + 2Cp

モデルの制約条件

Wikipedia のアレキサンダー大王に関係する文章か
ら「アレキサンダー大王がいつ、どこにいた」という情報がそろっているものから制約条件を生成する。次2 ln nnj(1)X̄j が平均報酬値、n が総プレイアウト回数、nj がノード j のプレイアウト回数、Cp は定数を示す。この式から、あるノードを試行すると nj が増加し、UCB値が下がることがわかる。そのためモンテカルロ木探― 362 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

索は「まだあまり試してないが高い平均報酬値を得ら
表 2: 質問応答の問題例と結果れるノードを優先的に探索する」手法となる。
選択肢時間場所

結果

4

モデルを用いた質問応答実験

1BC.331

Hekatompylos04.1

探索

2BC.324Aornos

0.063(正解)

BC.329Eschate0.74

4BC.328

Tarsus0.02

制約条件を満たすようなエピソードの探索は、モンテカルロ木探索で行う。1 式の Cp には 0.2 を使用し

原文: In 329 BC , Alexander the Great founded

た。平均報酬値 X̄j は、プレイアウトを最後まで行って得られたエピソードがどれだけ制約条件を満たせた

Alexandria Eschate (かの割合とする。プレイアウト回数の上限は 1,000,000

to the southewest of the Jaxartes river valley, siteof the modern Khokand in Tajikistan.

回とし、これを超えたら 1 回分のシミュレーションをFarthest Alexandria)終了する。このシミュレーションを 50 回繰り返し、50個のエピソードを取得する。

4.2

生成された問題例と正解選択肢のもとになった

Wikipedia 原文を表 2 に示す。

制約条件の生成

なお、入力に使用する Wikipedia の文章からは、正実験で使用する制約条件は「アレキサンダーが、解選択肢に出現する地名をあらかじめ削除しておく。

いつ、どこに存在したか」という情報をもつ。英語

これは、質問文に該当する情報を削除することで、直Wikipedia のうち「Alexander the Great」を含む項目は 1,969 個あり、そのうち「BC」という文字列を含む文は 482 文あった。この 482 文を入力とする。制約接書かれていないことも探索から判定できるかどうか条件の生成は簡単なルールベースで行う。それぞれの肢の条件を満たすものの割合を求める。その割合が最文について、文中に月や BC の表記があればそれをも大の選択肢を回答として出力する。4 択問題を 100 問とに時間情報とする。なお、月の情報が得られなかっを確認するためである。
実験で得られた 50 個のエピソードのうち、各選択用意して、これの正解率を求めた。

た場合は BC の情報から年は決まるので、モデルの 1
結果・考察年間に相当する 6 ステップ分の時間として幅を持たせ4.4

た制約条件とする。この 6 ステップ分のどこかで条件を満たせば制約条件を満たしたとする。場所について100 問の正解率は 0.55 であった。これは無作為に選択した場合の 0.25 を遥かに上回っている。問題例のは、モデル中に設定された地名に該当するものを見つ

結果は表 2 の右端に示す。表 2 の結果の値は、各選択けたらそれを採用する。この簡単なルールベースで生肢の条件を満たしたエピソードの割合を示している。

成した制約条件の精度を確認するために、人手で 482

選択肢 3 の割合が最も大きいので、この問題は正しく文について「いつ、アレキサンダーが、どこに存在し正解選択肢を判定できている。

たか」という情報を抽出し制約条件を生成した。このルールベースで生成された制約条件には誤った抽出2 つを比較することで、ルールベースで生成された制約条件のうち７割が正しいことが確認できた。

による間違った条件が３割程度含まれており、さらに4.3

正解選択肢に関する直接的な情報は与えていないにも関わらず５割を超える正解率となっている。このこと

質問応答から直接言及されていない文章に関して正しく判定す

1 章の例で示したような、質問文の内容がテキストることが可能だと考えられる。従来の自然言語処理でに直接書かれていない問題について、提案手法によっは扱うのが困難なこのような問題でも、現実の時間・て解けるかどうか検証する。使用する問題は 4 択問題

空間の情報をもつモデルを利用することで処理することし、この中から時間と場所の組み合わせが正しいもとができる可能性を示した。のを選択させる。問題の生成は以下の通り行う。

• Wikipedia から人手で生成した制約条件の中から一つ選択し、正解選択肢とする• その他の間違った選択肢は、モデルの範囲内から時間と地名をランダムに、その組み合わせが正しくないように選択し生成する

5

モデルを用いた照応解析実験

5.1

照応解析

質問応答以外の別のタスクとして照応解析の例を示す。Wikipedia の文章で時間情報はあるが地名がモデルに存在せず、制約条件として使用できなかったもの― 363 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

• 制約条件: 334BC, Alexandria, Alexander

表 3: 照応解析の問題例• 原 文: The port of Alexandria, founded byAlexander the Great in 334 BC, was a hub for
Mediterranean trade for centuries.

時間

BC.325代名詞

the area

正解

Bela

他候補（不正解）

Arachosia, Carmania, Babylon• 制約条件: 323BC, Memphis, Alexander• 原文: Arrhidaeus, one of Alexander the Great’sgenerals, was entrusted with the conduct of Alexander’s funeral to Egypt in 323 BC.

表 4: 照応解析の結果例
選択肢
出現頻度

Bela(正解)

50

Arachosia0が建設したのは紀元前 332 年だったため、そもそもテCarmania

0

キストの情報が間違っている。2 つ目は、アレキサン

Babylon0

ダー大王の葬儀の内容であり、アレキサンダー大王の1 つ目は、アレキサンドリアをアレキサンダー大王死後の話になるため、テキストから情報抽出し、生成を利用して、表 3 に示したような問題を作る。モデル

された制約条件が間違っていたことがわかる。このよに存在しない地名として「the area」などの代名詞のうに明らかなテキストの間違いや、その解釈の間違い表現も含む。候補は、該当する文章とその前の数文にがある程度含まれていても、シミュレーションを行う存在する地名とする。

ことで絶対に満たせない制約として検出、除去できる問題の代名詞が指している地名として正しいものを候補から判別する実験を行う。これらの候補の地名に関する制約条件を削除した上で探索を行い、得られた可能性があることを示した。

7

おわりにエピソードを参照して、時間条件をみたしている地名

本研究では入力で与えられた自然言語を制約条件との出現頻度を調べる。この出現頻度の最も高かったもして、モンテカルロ木探索を用いたシミュレーションのを代名詞の指しているものとして回答し、その正しにより、アレキサンダー大王の移動モデルを構築し、さを検証する。なお探索手法や制約条件の生成は 4 章

それに関する内容のタスクを処理できるかどうかを検と同様とする。

証した。その結果、入力で直接言及されていない情報5.2に関しても正しく判別できることを示した。

結果・考察

今後の課題としては、モデルの拡張があげられる。

結果は表 4 に示す。表 4 の値は、時間の条件を満

現時点では人物が決められたグラフ上を移動することたしている選択肢の地名が 50 個のエピソード中に出だけで、扱える問題が限定されている。今後は複数の現した回数を示している。この値が大きいほど、「代人物同士の相互作用や、人物が行える行動を増やすこ名詞」として指定されている場所が、その地名を指しとにより、できるだけ現実世界の扱える処理を増やすている可能性が大きいとする。この表の例では正しくことでモデルの表現力を向上させる必要がある。

「Bela」を判定できている。また、不正解の候補はモデルを利用することで「the area」が指し示すものとしてはありえないということが判断できている。このように現実の情報をもつモデルを利用し、文の意味を考慮することで、候補のうち正解であり得ないものを判定することができる可能性を示した。

6

制約条件の誤り検出
最後に、モンテカルロ木探索を行う際にほとんど条件が満たせなかった制約条件について調べてみる。各シミュレーション時に満たせなかった制約条件を出力し、その出現頻度が高かった上位 2 つを以下に示す。

参考文献[1] S. R. K. Branavan, Harr Chen, Luke S. Zettlemoyer,and Regina Barzilay. Reinforcement learning for
mapping instructions to actions. In ACL, 2009.
[2] Angel X Chang, Manolis Savva, and Christopher D
Manning. Learning spatial knowledge for text to 3D
scene generation. In EMNLP, 2014.
[3] Rémi Coulom. Eﬃcient selectivity and backup operators in monte-carlo tree search. In Computers andgames, pp. 72–83. Springer, 2007.
[4] Terry Winograd. Procedures as a representation fordata in a computer program for understanding natural languages. PhD thesis, Massachusetts Institute ofTechnology, Project Mac, 1971.
[5] Alexander Yates. Extracting world knowledge fromthe web. In IEEE, 2009.

― 364 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.