DEIM2021 F31-4

因果関係に基づく類似出来事の検索
澄川靖信†† 東京都立大学 〒 192–0364 東京都八王子市南大沢 1-1
E-mail: †ysumikawa@acm.org
あらまし

過去の出来事の因果関係を現代に類推させながら活用することが重要視されている。これまでの出来事どうしの類似度を測定する手法は、一つの文章で出来事が記述されている事を前提としており、因果関係を明示的に用いた出来事どうしの類似度を測定するものは少ない。本研究では、因果関係の類似度を考慮した出来事どうしの類似度を測定するアルゴリズムを提案する。本手法は、比較する出来事の因果関係間の類似度を重みとする二部グラフ上の最大重みマッチング問題を解く。本手法の有効性を評価するために先行研究と比較したところ、本手法の方が良い精度で類似度を測定できることを確認した。
キーワード 出来事検索、因果関係、二部グラフ、最大重みマッチング与える。この制約によって、サブ出来事どうしを因果関係の原

1 はじめに歴史をよく知り、その知識を現代社会で活用する能力の重要性が近年注目されている [1] [2]。実際、歴史を学習する授業は多くの国で小学校から開講されていることや、単に歴史を暗記するだけでなく現代社会で知識を活用できる能力を育成することを重視するカリキュラムや学習支援研究が行われていることから、歴史に重要性は広く認識されている。

因と結果に対応付けながらその関係性の類似を評価できる。

2 準

備

2. 1 定義2. 1. 1 出来事、サブ出来事、因果関係
本稿では出来事を、複数のサブ出来事を統括するものと定義する。例えば、第二次世界大戦を用いてこの定義を考慮すると、「歴史は繰り返すのではなく、リズムが繰り返される」とい出来事は第二次世界大戦、サブ出来事として真珠湾攻撃やポツう言葉があるように、過去や現代で生じている出来事は、互いダム宣言がある。本稿では因果関係を、2 つ以上のサブ出来事に類似する点だけでなく異なる点も含まれていることが多い。の集まりとする。なお、この集まりの中ではそれらが生じた時

すなわち、過去の知見を現代で活用するためには、単に出来事系列で全順序が定義できるものとする。の記述文で用いられている単語の類似度だけでなく、因果関係

2. 1. 2 二部グラフのような関係性の類似度を考慮して現代に類推させることがで二部グラフ G は二つの節集合 A と B の組み (A, B) である。

きると望ましいと考えられている [3]。
出来事を検索する研究はこれまでに行われてきているものの、それらの多くはその記述文で使われている単語 [11] やそのカテゴリ [8] がどの程度似ているのかを分析しているので、因果関係は考慮していない。歴史教育の研究において因果関係の類似二部グラフの辺集合 E は、A と B の節同士の類似度を重み辺e = (ai , bi ) の集合である。
本手法を適用するとき、すべてのサブ出来事に対して節を定義する。

2. 1. 3 順序付き二部グラフ

度を求めさせる学習方法も研究されているが、その学習テーマ

順序付き二部グラフ G は、二つの節集合 A と B のおいて全は研究者が選んだ特定のもののみが対象になるので、あらゆる順序を定義したものと定義する。すなわち、ai , a j ∈ A の添え字出来事を対象にすることは難しい。

i, j に全順序を定義したものである。

本研究では、長期的な因果関係に基づいた出来事の類似度を測定するためのアルゴリズムを提案する。本研究では出来事の2. 2 最大重みマッチング

因果関係を複数のサブ出来事の組みによって表現し、そのサブ与えられたグラフ G に対して、マッチングとは、端点を共有

出来事どうしの類似度の総和によって出来事どうしの類似度をしない辺の集合 M ⊂ E である。最大重みマッチングは M とし求める。て選択された辺の重みの総和が、最も高いもの M ′ ∈ M を求め本手法を適用するために類似度を求める二つの出来事に対しる問題である。て二部グラフを構築し、サブ出来事の類似度の総和が最大となる組み合わせを求めるために最大重みマッチングを本手法は解く。本研究で構築する二部グラフは出来事を表し、因果関係の類似度を求めることを目的としているので、最大重みマッチン
グの解となる辺には「互いに交点が存在しない」という制約を

3 関連研究3. 1 出来事検索
出来事同士の類似性を評価する手法は、新聞記事で報道されたものを対象とする研究 [4], [6], [9]、Twitter 上にポストされた2b1a1b110b2a2bjb3

ʀʀʀ

a1a21a3ʀʀʀ

ai4b|B|-1b4ʀʀʀ

図 1 二部グラフの例.

ものを対象とした研究 [5]、などがこれまでに数多く行われてきa|A|

た。これらの先行研究は、本研究で構築する二部グラフ G を用いて表現すると、G の 2 つの節集合 A と B の大きさをそれぞれb|B|

図 2 制約付き最大重みマッチングの例.

1 とし、1 つしか無い辺の重みを求めるための手法である。一方、本研究の提案手法は辺の重みを計算するためのではなく、その値を用いて因果関係を考慮した出来事全体の類似度を測定する。すなわち、上記の先行研究と本研究は目的が異なり、本手法で用いる二部グラフの辺の重みを計算するために先行研究の手法を用いることができる。

3. 2 因果関係抽出
出来事の因果関係を抽出する研究は、将来起こりうる出来事を予測するために過去の出来事の記述の中から因果関係を抽出する手法 [7]、現代社会における技術発展の影響を分析するための因果–効果関係を抽出する手法 [10] が提案されている。
これらの研究は本研究と同様に出来事の因果関係に注目しているが、本手法は出来事間の因果関係は既に与えられていることを仮定し、その因果関係を用いて出来事同士の類似度を測定

一方の辺よりも高い値なので一般的な最大重みマッチングでは解として選ばれる。しかし、辺（a2 , b2 ）、（a3 , b3 ）と交点を持つので本研究では解とせず、もう一方の辺（a1 , b1 ）を解とする。

4. 1. 1 二部グラフの構築
本研究で定義する二部グラフ G = (A, B) は因果関係を表す
出来事なので、節集合 A, B それぞれの内部の節は、その添え字番号に対して順序を定義している。また、因果関係は複数の出来事の集合 S ubG で表現しているので、因果関係の類似度はS ubG のサブ出来事どうしの順序と内容の類似度に帰着させることができる。
因果関係を表すサブ出来事を節とし、節となる出来事どうしの類似度を辺の重みとする順序付き二部グラフを定義する。

4. 1. 2 制約付き最大重みマッチング
本手法の順序付き二部グラフはサブ出来事を節とし、因果関する。

係はサブ出来事を列挙することによって表現するので、因果関

4 提案手法係に基づいた類似度はサブ出来事どうしの類似度を、一対一で求めながら、その順序を守ることと言い換えることができる。

本節で本研究で解決する最大重みマッチング問題について説

本稿では、因果関係に基づいた出来事どうしの類似度を、第明するために提案手法の理論を最初に述べる。次に、提案手法

4. 1. 1 節で定義した二部グラフ上で、交点を持たない辺の組みの動的計画法による実現方法を述べる。

合わせの中で、それらの重みが最大となるものと定義する。

4. 1 理論

本研究では従来の最大重みマッチング問題に対して、解となる辺には「互いに交点が存在しない」という制約を与える。図1 にこの制約によって得られる解の違いを示す。
例：図 1 を用いて一般的な最大重みマッチング問題と本研究の解の違いを示す。なお、本研究ではグラフは平面空間上で定義

e = (ai , b j ) と e′ = (ak , bl ) を解をなす辺 (e , e′ ) とする。このとき、解をなす辺集合が互いに交点を持たないを以下のように定義する。

•

もし k < i ならば l < j である。

•もし l < j ならば k < i である。

4. 2 実装することを仮定する。黒線はどちらの問題でも共通して解とな本手法は動的計画法によって実現する。本節では、まず、図る辺、青線は一般的な最大重みマッチング問題のみで解となる

2 と図 3 を用いて本研究で提案した二部グラフ上での制約付き辺、赤線は本研究のみで解となる辺を示す。節 a1 には 2 つの辺最大重みマッチング問題の動的計画法による解法の例を示す。

が接続している。節 b4 にも接続している辺の重みの方が、もうその後、本手法を一般化するために定義やアルゴリズムを示す。

123ʞjʞ|B|

170669957567694

221873108269332726

13967989

222:// Table calculation30

3:

for i = 1 to ColumnSize(W)4:for j = 1 to RowSize(W)Algorithm 1 動的計画法による実装
Input: A weighted matrix W, tables DP and range max
Output: A set of edge SubE

ʞi588585455

3814466778

ʞ|A|

図 3 動的計画法による解法.

1: Function OGMM(W, DP, range max)

5:

prev max ← Val(range maxi−1, j−1 )6:DPi, j ← prev max + Wi, j

7:

range maxi, j ← tuple val max(range maxi−1, j , range maxi, j−1 )8:

if DPi, j > val(range maxi, j )

9:
10:

b1
a1
a2
a3

b2

200

1000

b3001

b4
400(a) W

000

11:

00222

602

12121202

121313(b) DP

図 4 動的計画法による図 2 の解.

end for12:

end for13:// Answer determination

14:

i, j ← ColumnSize(W), RowSize(W)15:SubE ← ∅16:

while i , −1 and j , −1

17:0range maxi, j ← (DPi, j , (i, j))
end if

18:

SubE.append(ei, j )i, j ← Index(range maxi−1, j−1 )19:

end while

20:

return SubE

W は二部グラフ G = (A, B) の各辺の重みを要素とする行列とする。すなわち、引数で与えられた辺の重みを返す関数 weightを用いて、W の各要素を、任意の eai ∈ A, eb j ∈ B に対して、

Wi, j = weight(e(ai , b j )) と定義する。
例：図 2 と図 3 は解の対象となるか解析を終えた辺を緑、現在本手法を動的計画法として定義するために表 DP を定義する。

解析している辺を赤、赤を解として選択した場合にこれから解

この表に上記の例で示したように値を帰納的に記録することで析対象とする辺を青で示す。

制約付き最大重みマッチング問題を解く。

本手法は二部グラフ G = (A, B) の節集合 A, B に対して添字の第 4. 1. 2 節の定義より「もし e(ai , b j ) を解とするとき、直前ま昇順で解析する。このとき、もし現在解析している辺を解としでに解として選ばれていた辺に接続される節の添え字は i, j のて選択したなら、それまでに解として選択した辺集合に加えてそれぞれよりも小さい」となるので、もし e(ai , b j ) が解をなす重みの総和を表にメモする。すなわち、図 3 の矢印が表すようならば、ai や b j に接続される他の辺を選択するよりも e(ai , b j )に、緑の領域から選択済みの辺の重みを赤色のセルへ流していを選択し、その重みを (0,0) から (i-1,j-1) の範囲までに求めた解き、最終的にその値が最も高い辺を解とする。このとき、「辺が集合の辺の重みの総和に足した結果は大きくなる。

交点を持たない」という制約を満たすために、選択した辺の添

この特徴を利用して、辺 e(ai , b j ) を解とした場合の計算結果

字よりも大きい値の添字は解として選択できないように対象かを表 DP に記録するためには、DPi−1, j−1 に Wi, j を足した結果が、ら除外する。

DPi, j−1 や DPi−1, j よりも値が大きくなるはずである。さもなけ

本手法は辺の重みを記録する表 W と、選択済みの辺の重みの総和を記録する表 DP を用いる。
例：図 1 に対して本手法で作成する 2 つの表を図 4 に示す。図4(a) に示すように、辺が未定義の場合には表に 0 を記録する。

れば、e(ai , b j ) を解としない場合の方が値が大きくなっている。
この考えを用いると、DPi, j の計算式は以下のようになる。

DPi, j = max(DPi−1, j−1 + Wi, j , DPi−1, j , DPi, j−1 ) + Wi, j(1)表 DP は選択済みの辺集合の重みの総和を記録するので、各セAlgorithm1 に本手法のアルゴリズムを示す。本手法を適用す

ルには、表 DP の左、左上、上の 3 つの値の中から最大のものる前に、表 DP を 1 行目と 1 列目のすべての成分を 0 で初期化と、現在のセルに対応する W の値を足した値を記録する。これしておくことを仮定する。また、表 DP を埋めながら解となるを全てのセルに値を記録するまで反復する。この結果、表 DP辺を記録するために表 range max を用いる。range max は、解の右下に本手法で選択した辺集合の重みの総和が記録できるのとなる辺の重み value と接続されている節の添え字 index の組で、その構成要素となる辺を逆方向に走査することで実際の辺を成分とする。2 行目から 12 行目が表 DP の各成分に式 1 の集合を求める。

計算結果を記録している。3 行目の ColumnSize は引数の表の行数を返す関数、4 行目の RowSize は引数の表の列数を返す関数、

表 1 評価用データセットの統計情報.

度が最も精度が低いので因果関係を考慮する際にはサブ出来事

地震

222の順序を考慮するのが出来事同士の類似度を評価する際には重地震と津波

57

要であることがわかる。

地震と地崩れ3

ウィルスの発生とワクチン開発

5

ウィルスの発生と治療

6

計

293

6 おわりに
本稿では因果関係に着目した出来事同士の類似度を測定するための手法を提案した。本手法は因果関係を表すサブ出来事を

表 2 p@1.
コサイン類似度

DTW提案手法

0.567

0.753

0.858

節、各サブ出来事同士の類似度を辺の重みとする二部グラフ上で、解となる辺は交差しないという制約を与えた最大重みマッチング問題を解く。本手法を実現し、先行研究と比較したところ、本手法の方が良い精度が得られることを確認した。

5 行目の Val は引数として与えられた値と添え字の組の中から値を返す関数、7 行目の tuple val max は引数として与えられた

今後の課題としては次の 2 つが考えられる。1 つ目は、因果関係を含む他の出来事に対して網羅的に評価を行う。2 つ目は、値と添え字の組の中から値が最大のものを返戻する関数、18 行

木構造で表現した因果関係を用いることによって問題の一般化

目の Index は引数として与えられた値と添え字の組の中から添を行う。

え字を返す関数である。このアルゴリズムでは、DP を埋めるのと同時に、解として選択した辺の添え字を range max に記録している。解となる辺の添え字は昇順に並ばれているので、13行目から 19 行目で示すような range max の添え字を逆順で辿ることによって本手法で求める辺集合を得られる。
計算量. DP 行列と range max を同時に計算できるので各DPi, j 、range maxi, j は定数時間で求めることができる。すなわち、時間計算量は O(|A||B|) となる。一方、空間計算量は O(|A||B|)
である。

5 実

験

5. 1 データ収集
本稿では、Wikipedia に記載されいている地震とウィルスに関する出来事を用いて提案手法を評価する。特に、表 1 の 6 種類の Wikipedia 記事を収集し、各サブ出来事が記述された章・節・段落のいずれかを手動で抽出して二部グラフの節を定義した。

5. 2 比 較 対 象
本稿では以下の手法を比較対象とする。

•TF-IDF+CosSim（コサイン類似度）：特徴ベクトルを作成する際に TF-IDF を用いる。この特徴ベクトルに対してコサイン類似度を用いて文章間の類似度を評価する。

•TF-IDF+動的時間伸縮法（DTW）：DTW は時系列データ同士の類似度を、２つの時系列の各点の距離を総当たりで求め、全て求めた上で２つの時系列が最短となるパスを見つけることによって類似度を測る。

5. 3 評 価 基 準
本稿では、上述した比較対象と本手法を、各手法を適用した結果の上位 1 件の結果が正解かどうかを表す p@1 によって評価する。

5. 4 結果

表 2 に各手法の p@1 の結果を示す。この結果から提案手法が一番良い結果が得られたことがわかる。また、コサイン類似

謝辞 本研究の一部は科研 (#19K20631) の助成を受けたものである.
文

献[1] Abelson, R.P., Levi, A.: Decision making and decision theory, handbook of social psychology. pp. 231–309 (1985)[2] Gilovich, T.: Seeing the past in the present: The eﬀect of associations
to familiar events on judgments and decisions. Journal of Personality
and Social Psychology 40(5), 797 (1981)[3] Ikejiri, R.: Designing and evaluating the card game which fosters theability to apply the historical causal relation to the modern problems.
Japan Society for Educational Technology 34(4), 375–386 (2011).
(in Japanese)[4] Lei, Z., Wu, L.d., Zhang, Y., Liu, Y.c.: A system for detecting andtracking internet news event. PCM 05, pp. 754–764. SpringerVerlag, Berlin, Heidelberg (2005)[5] Manaskasemsak, B., Chinthanet, B., Rungsawang, A.: Graphclustering-based emerging event detection from twitter data stream.
ICNCC’16, pp. 37–41. ACM, New York, NY, USA (2016)[6] Qi, Y., Zhou, L., Si, H., Wan, J., Jin, T.: An approach to news event
detection and tracking based on stream of online news. pp. 193–196(2017)[7] Radinsky, K., Davidovich, S.: Learning to predict from textual data.
J. Artif. Int. Res. 45(1), 641–684 (2012)[8] Sumikawa, Y., Jatowt, A.: System for category-driven retrieval ofhistorical events. JCDL ’18, pp. 413–414. ACM, New York, NY,USA (2018)[9] Tan, Z., Zhang, P., Tan, J., Guo, L.: A multi-layer event detection algorithm for detecting global and local hot events in social networks.
Procedia Computer Science 29, 2080–2089 (2014). 2014 International Conference on Computational Science[10] Zhang, Y., Jatowt, A., Tanaka, K.: Causal relationship detection inarchival collections of product reviews for understanding technology
evolution. ACM Trans. Inf. Syst. 35(1) (2016)[11] 池尻良平, 澄川靖信: 真正な社会參画を促す世界史の授業開発 –その日のニュースと関連した歴史を検索できるシステムを用いて–. 社会科研究 84, 37–48 (2016)