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

決定リストの機械学習による wikification
袁 楊

綱川 隆司

梶 博行

静岡大学大学院情報学研究科
gs13050@s.inf.shizuoka.ac.jp , {tuna, kaji}@inf.shizuoka.ac.jp
1. はじめにWeb 上の百科事典 Wikipedia は記事間にリンクがはられ、関連記事を容易にたどることができる。一般のテキス
トから Wikipedia 記事にリンクを張る“wikification”が実現されれば、新聞、論文、その他さまざまなテキストを読む際に Wikipedia を容易に参照することができるようになる。
新たに作成した Wikipedia 記事に wikification を適用することももちろん可能であり、記事作成者のリンク付与作業の負担を軽減することが期待される。
Wikification は、一般に、アンカーテキストとよばれるリンク元の語句を選定するステップと選定されたアンカーテキストのリンク先記事を決定するステップからなる[1]。字面だけでは複数の概念／エンティティを表し得るアンカーテキストも多く、リンク先記事の曖昧性解消がwikification における最大の技術課題となっている。リンク
先記事の曖昧性解消は Word Sense Disambiguation（語義曖昧性解消）の一ケースと考えられ、WSD のさまざまな手法の適用が試みられている。
本 稿 で は 、 決 定 リ ス ト [2] を 用 い た WSD 手 法 のwikification への適用について述べる。Yarowsky によって提案された決定リストを用いた WSD では、多義語の周辺に出現する語を手がかりとする語義決定ルールをルールの確信度順に並べた決定リストをコーパスから学習する[3]。これに対し、本稿で提案する wikification では、同一テキスト中の他のアンカーテキストを手がかりとするリンク先記事決定ルールをルールの確信度順に並べた決定リストを Wikipedia のリンクデータから学習する。
決定リストを用いた WSD は、テキスト中に複数の手がかりが含まれる場合でも、最も有力な単一の手がかりに基づいて語義を決定することが特徴で、決定プロセスの透明性が高く理解しやすい方法となっている。この特徴は、他のアンカーテキストを手がかりとしてリンク先記事を決定する場合にも適していると思われる。よって、決定リス
トによる wikification を提案し、実験結果を報告する。

2. 関連研究
Wikification におけるリンク先記事の曖昧性解消に対する代表的なアプローチは教師ありの機械学習で、ナイーブベイズ、決定木、サポートベクターマシンなどさまざまな手法が適用されている[4][5][6]。Wikipedia のリンクデータ、すなわちアンカーテキストとリンク先記事のタグの組がトレーニングデータとして利用される。素性としては、通常の WSD と同様にアンカーテキスト周辺の語とその品詞などが用いられている。
アンカーテキストを含むテキストとリンク先記事候補の間の文脈の重なり度合を利用する方法も典型的な方法である[7]。これは、語義説明文を用いた WSD において語義説明文を Wikipedia 記事に置き換えた手法と考えることができる。性質の異なるこの手法と機械学習手法を組み合わせてリンク先記事を決定する方法も提案されている[1]。
以上は、アンカーテキストごとにリンク先記事を決定するいわば局所的な方法であるが、同一テキスト中の各アンカーテキストのリンク先記事の間の関連も考慮する大域的な方法も提案されている [5][7][8][9]。記事間の関連としては、記事間のリンクを直接利用するほか、文脈の重なり度合、参照している記事の共通性（グーグル距離）、記事の属するカテゴリ間の距離などが用いられる。

3. 基本アイデア(1) “One sense per collocation”仮説
決定リストによる WSD は“One sense per collocation”仮説[10]に基づいている。Wikification では、リンク先記事がアンカーテキストの sense に対応するが、テキスト中の他のアンカーテキストを collocation と考えるとやはりこの仮説が有効と思われる。例えば、アンカーテキスト“Jaguar”のリンク先記事候補として“Jaguar”（動物のジャガーについての記事）、“Jaguar Cars”（スポーツカー“ジャガー”についての記事）、その他がある。“Jaguar”をリンク先とするアンカーテキスト“Jaguar”を含む Wikipedia 記事は“lion”,“tiger”など、“Jaguar”に対して動物のジャガーを連想させるアンカーテキストを含んでいる。したがって、Wikipediaのリンクデータから、「IF “lion” co-occurs with “Jaguar”
THEN link “Jaguar” to “Jaguar”.」というようなリンク先決定ルールを学習することができる。
決定リストは決定ルールを確信度の降順に並べたものである。ルールの確信度としては、条件部の共起アンカーテキストとアクション部のリンクとの関連度を用いることが考えられる。すなわち、Wikipedia に含まれる大量のリンクデータから対数尤度比などの関連度を計算すればよい。
(2) “One sense per collocation”の反例への対策
上に述べた方法によれば、「IF “BMW” co-occurs with“Jaguar” THEN link “Jaguar” to “Jaguar Cars”.」というルールも上位に順位付けられるであろう。しかし、このルールは誤ったリンク先をもたらす可能性がある。実は、“Jaguar”の リ ン ク 先 記 事 候 補 に は 前 記 の ２ つ の ほ か に “JaguarRacing”（F1 参加チーム“ジャガー”についての記事）が含まれる。そして、共起アンカーテキスト“BMW”をもつアンカーテキスト“Jaguar”のリンク先が“Jaguar Racing”であることも多い。要するに“One sense per collocation”仮説が成立しないのである。
このような場合を考慮すると、ルールの確信度として、競合するリンクとの相対的な関連度の大きさを用いるほうがよいかもしれない。そこで、(i)関連度によるルールの順位付け、(ii)相対的な関連度によるルールの順位付け、(iii)関連度と相対的な関連度の組合せによるルールの順位付けの 3 案の比較実験を行うこととする。
“One sense per collocation”仮説が成立しない共起アンカーテキストによるリンク先記事の決定誤りを防止する方― 688 ―Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

図 1 提案方法
法としては、複数の共起アンカーテキストに基づいて決定することも考えられる。そのような考え方を決定リストに組み込む方法として次の 2 案があるだろう。
(a) ルールの仕様を拡張し、条件部に共起アンカーテキストの連言（AND）を記述できるようにする。
(b) リスト中のヒットする（条件が成立する）上位 k 個のルールの多数決によってリンク先を決定する。決定
リストの精神からはずれないように、k は比較的小さな値とする。
(a)案は、共起アンカーテキストの組合せが爆発的に増え、データスパースネスの問題が深刻になる。そこで、(b)案を採用し、k のいくつかの値について実験的に比較することとする。

𝑙(𝑎, 𝐷𝑗 )4.1. 決定リストの学習
アンカーテキスト𝑎のリンク先記事を決定するための決定リストを以下のステップで学習する。
(1) 共起アンカーテキストの選択
アンカーテキスト𝑎のリンク先決定の手がかりとする共起アンカーテキストとして、𝑎との共起頻度が閾値を超えるアンカーテキストを選択する。それらを𝑎𝑖（𝑖 = 1, 2, …）とする。
(2) 共起アンカーテキストとリンクの関連度の計算
アンカーテキスト𝑎のリンク先記事候補が𝐷𝑗（𝑗 = 1, 2, …）であるとする。共起アンカーテキスト𝑎𝑖 と𝑎からの各リン

ク𝑙(𝑎, 𝐷𝑗 )の関連度Ass (𝑎𝑖 , 𝑙(𝑎, 𝐷𝑗 ))を計算する。関連度として相互情報量、t スコア、対数尤度比のいずれかを用いる。それぞれ以下のように定義される。ただし、定義式中の𝑚, 𝑛1 , 𝑛2 , 𝑁はアンカーテキストとリンクの共起デー
タの分割表に示すとおりである。

すべて

𝑎𝑖

𝒎𝑛2 − 𝑚𝒏𝟐

¬𝑎𝑖𝑛1 − 𝑚𝒏𝟏

𝑁 − 𝑛1 − 𝑛2 + 𝑚
𝑁 − 𝑛1𝑁 − 𝑛2𝑵

すべて

 相互情報量MI：
MI (𝑎𝑖 , 𝑙(𝑎, 𝐷𝑗 )) = log 2
 t スコアT：
T (𝑎𝑖 , 𝑙(𝑎, 𝐷𝑗 )) =𝑚 ⁄𝑁(𝑛1 ⁄𝑁)(𝑛2 ⁄𝑁)𝑚 − 𝑛1 𝑛2 ⁄𝑁√𝑚 対数尤度比LLR：

4. 提案方法3 章で述べた考え方にしたがって、次の２つのステップからなる方法を提案する。
I. Wikipedia のリンクデータをトレーニングデータとしてアンカーテキストごとに決定リストを学習する。
II. リンクをもたない入力テキストに対し、アンカーテキストを選定し、I で学習した決定リストを用いてリンク先記事を決定する。
図 1 に概要を示し、各ステップの詳細を 4.1 節と 4.2 節で述べる。

¬𝑙(𝑎, 𝐷𝑗 )LLR (𝑎𝑖 , 𝑙(𝑎, 𝐷𝑗 )) = −2(log 𝐿(𝑚, 𝑛1 , 𝑟)
+ log 𝐿(𝑛2 − 𝑚, 𝑁 − 𝑛1 , 𝑟)
− log 𝐿(𝑚, 𝑛1 , 𝑟1 )− log 𝐿(𝑛2 − 𝑚, 𝑁 − 𝑛1 , 𝑟2 ))L(𝑘, 𝑛, 𝑟) = 𝑟 𝑘 (1 − 𝑟)𝑛−𝑘𝑟1 = 𝑚⁄𝑛1 , 𝑟2 = (𝑛2 − 𝑚)⁄(𝑁 − 𝑛1 ), r = 𝑛2 ⁄𝑁上の定義からもわかるように、関連度Ass (𝑎𝑖 , 𝑙(𝑎, 𝐷𝑗 ))の計算においてアンカーテキスト𝑎と共起アンカーテキスト
𝑎𝑖 の記事中での距離は考慮しない。アンカーテキストの連想関係と出現位置はあまり関係がないと考えるからである。
(3) リンク先決定ルールの生成
共起アンカーテキスト𝑎𝑖 の各々について、𝑎𝑖 との関連度が最大のリンク先を選択するルール
̂ (𝑎, 𝑎𝑖 )．
𝑟𝑖 : IF 𝑎𝑖 co-occurs with 𝑎 THEN link 𝑎 to 𝐷̂を生成する。ここに 𝐷 (𝑎, 𝑎𝑖 ) = argmax Ass (𝑎𝑖 , 𝑙(𝑎, 𝐷𝑗 ))で𝐷𝑗ある。
(4) 決定ルールの順序付け(3)で生成したリンク先決定ルールを順序付け、最後にデフォールトルールを追加する。デフォールトルールはアンカーテキスト𝑎の最頻リンク先記事に無条件にリンクするルールである。順序付けの方法として、以下の 3 案を比較評価する。
(i) 関連度による順位付け関連度をルールの確信度と考える。すなわち、CF1 (𝑟𝑖 ) =― 689 ―Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

表 1 Wikipedia 全体とテストセット T200 のアンカーテキスト*)(a) 出現頻度 f の分布
fWikipedia 全体
テストセットf<100690800 (87%)
0 (0%)

100≤f<500
80320 (10%)
168 (84%)

500≤f<1000
12107 (2%)
24 (12%)f≥100010694 (1%)
8 (4%)

合計
793921200*) Wikipedia 全体についても曖昧性のないアンカーテキス
トを除外している。

(b) リンク先記事候補数 n の分布
nWikipedia 全体
テストセット2449192(57%)
22 (11%)3141733(18%)
26(13%)

463919(8%)
34 (17%)535501(4%)
34 (17%)621607(3%)
26 (13%)714893(2%)
21 (10%)810443(1%)
29 (15%)

97919
(1%)
8 (4%)≥1048710(6%)
0 (0%)

合計
793921200(c) 最頻リンク先記事の確率 p の分布
pWikipedia 全体
テストセット0<p<0.4
82007 (10%)
19 (9%)

0.4≤p<0.5
46962 (6%)
31 (15%)0.5≤p<0.6
0.6≤p<0.7
181319 (23%) 126958 (16%)
53 (27%)45 (23%)̂ (𝑎, 𝑎𝑖 )))の降順に並べる。
Ass (𝑎𝑖 , 𝑙 (𝑎, 𝐷(ii) 相対的な関連度による順位付け
他のリンク先候補の関連度と比べた相対的な関連度の大きさをルールの確信度と考える。すなわち、CF2 (𝑟𝑖 ) =̂ (𝑎, 𝑎𝑖 )))⁄∑𝑗 Ass (𝑎𝑖 , 𝑙(𝑎, 𝐷𝑗 ))の降順に並べる。
Ass (𝑎𝑖 , 𝑙 (𝑎, 𝐷(iii) 関連度と相対的な関連度の組合せによる順位付け(i)による順位と (ii)による順位の平均をルールの順位と考えて順位付ける。CF1 (𝑟𝑖 )とCF2 (𝑟𝑖 )はとり得る値の範囲が異なり、直接結合することが困難であるので、それぞれによる順位を求めたうえで組み合わせる。

4.2. リンク先記事の決定
入力テキスト中のアンカーテキストの選定は、本研究の主たる目的ではないので、以下のような簡単な方法を用いる。Wikipedia において 1 回でもアンカーテキストとして選定されている語句をすべてアンカーテキストとして選定する。それらのアンカーテキストの各々について、それ以外のアンカーテキストを共起アンカーテキストと考え、以下の手順によってリンク先記事を決定する。ここに、𝑘はリンク先決定に用いるルール数（の下限）を定めるパラメータである。
(1) ヒットするルールの集合R 𝐻 を空にする.
(2) 決定リストの上から順にヒットするルール、すなわち条件部に書かれた共起アンカーテキストが入力テキ
ストに含まれるルールを求めてR 𝐻 に加える。同順位の複数のルールがヒットする時はそれらをすべて加える。これを|R 𝐻 | ≥ 𝑘になるまで繰り返す。
(3) R 𝐻 に含まれるルールの多数決によりリンク先記事を決定する。票数が最大のリンク先記事が１つ得られたら終了であるが、票数が最大のリンク先候補記事が２つ以上の場合は(4)へ。
(4) ヒットするルールを求めてR 𝐻 に加える処理を再開し、|R 𝐻 |が 1 でも増加したら、(3)へ。デフォールトルールに到達したら、デフォールトルールによってリンク先記事を決定し、終了。

5. 評価実験
英語版の Wikipedia 記事をトレーニングデータ及びテストデータとして評価実験を行った。使用したのは 2014 年
02 月 03 日の Wikipedia で、記事の総数は 10,771,274 であ

0.7≤p<0.889818 (11%)
26 (13%)0.8≤p<1266857 (34%)
26 (13%)

合計
793921200った。アンカーテキストタイプの総数は 10,508,316 で、うち曖昧性のあるもの（複数のリンク先記事候補をもつもの）が 793,921（7.6%）、曖昧性のないものが 9,714,395（92.4%）であった。

5.1. 代替案・パラメータの比較
提案方法は、関連度の定義とルールの順位付け方法に複数の案があり、また共起アンカーテキストの共起頻度に対する閾値とリンク先決定に用いるルール数の下限𝑘の２つのパラメータをもつ。最適な組合せを決定するため、200のアンカーテキストタイプを対象として、5 分割交差検定による比較実験を行った。
(1) アンカーテキストのテストセット T200
曖昧性のあるアンカーテキスト 200 個からなるテストセット T200 を構成した。その際、決定リストの学習のためにある程度の量のトレーニングデータが必要であるので、頻度 100 以上のアンカーテキストに限定した。また、リンク先記事候補数が 10 未満のものに限定した。リンク
先記事候補が多すぎると、リンク先候補記事あたりのトレーニングデータの量が少なすぎる可能性が高いからである。
表 1 に、Wikipedia 全体と T200 それぞれの出現頻度 f、リンク先記事候補数 n、最頻リンク先記事の確率 p の分布を示す。Wikipedia 全体と比較して、T200 はリンク先記事候補数 n が大きいアンカーテキスト、最頻リンク先記事の確率 p が低いアンカーテキストの比率が高い。そのようにした理由は、代替案の間の優劣やパラメータの値による差違をはっきりさせるためである。
(2) 実験結果と検討
代替案・パラメータの各組合せによるリンク先決定の正解率を表 2 にまとめた。ベースライン（最頻リンク先記事をリンク先とする方法の正解率）は 0.61 であり、どの代替案・パラメータの組合せもこれを上回っている。実験の結果、関連度は対数尤度比が、ルールの順位付けは相対的な関連度によるのが一番よいことが明らかになった。
共起頻度の閾値は 2 がよく、関連度あるいは相対的な関連度で順位付けるので、共起頻度の低い共起アンカーテキストを除外する必要がなかったといえる。また、リンク
先決定に用いるルール数の下限は、k=1 との差が小さいものの k=3 が最適であるとの結論を得た。k=10 では明らかに正解率が低下しており、１、２の有力な共起アンカーテ― 690 ―

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

表 2 代替案・パラメータの比較実験の結果
関連度 共起頻度 ルールの順位付けの リンク先決定の正解率
Ass閾値
方法
k＝1 k=3 k=5 k=10(i) 関連度
0.65 0.73 0.73 0.67
2(ii) 相対的な関連度
0.73 0.78 0.77 0.70(i)(ii)の組合せ
0.71 0.77 0.76 0.69(i) 関連度
0.69 0.73 0.70 0.65
5MI(ii) 相対的な関連度
0.73 0.75 0.73 0.67(i)(ii)の組合せ
0.73 0.75 0.72 0.66
(i) 関連度
0.69 0.70 0.69 0.66
10(ii) 相対的な関連度
0.70 0.71 0.69 0.67(i)(ii)の組合せ
0.7 0.71 0.69 0.67(i) 関連度
0.74 0.77 0.76 0.71
2(ii) 相対的な関連度
0.75 0.79 0.79 0.73
(i)(ii)の組合せ
0.77 0.79 0.78 0.72
(i) 関連度
0.73 0.74 0.73 0.69
5T(ii) 相対的な関連度
0.75 0.77 0.75 0.70(i)(ii)の組合せ0.75 0.76 0.74 0.70(i) 関連度
0.70 0.71 0.70 0.6810(ii) 相対的な関連度
0.72 0.72 0.71 0.69(i)(ii)の組合せ
0.72 0.72 0.71 0.69(i) 関連度
0.75 0.77 0.77 0.71
2(ii) 相対的な関連度
0.79 0.80 0.79 0.73(i)(ii)の組合せ
0.77 0.79 0.78 0.72(i) 関連度
0.74 0.75 0.73 0.69
5LLR(ii) 相対的な関連度
0.76 0.77 0.75 0.70(i)(ii)の組合せ
0.75 0.76 0.74 0.69(i) 関連度
0.71 0.71 0.70 0.6810(ii) 相対的な関連度
0.72 0.72 0.71 0.69(i)(ii)の組合せ
0.72 0.72 0.71 0.68

表 3 大量のアンカーテキストを対象とした評価実験の結果
関連度 共起頻度閾値AssLLR

2

ルールの順位付けの リンク先決定の正解率
方法
k=3(i) 関連度

0.9045(ii) 相対的な関連度

0.9036(i)(ii)の組合せ

0.9044

キストに基づいてリンク先記事を決定するのがよいと言える。

5.2. 大量のアンカーテキストを対象とした評価(1) アンカーテキストのテストセット T10000
曖昧性のあるアンカーテキスト 10000 個からなるテス
トセット T10000 を構成した。頻度 100 以上という条件のもとで、ランダムに選択したので、このテストセットに対する評価結果を Wikipedia の全アンカーテキストに対する評価結果と考えてよいであろう。
(2) 実験結果と検討
5.1 節の結果に従い、関連度は対数尤度比、共起頻度の閾値=2、リンク先決定に用いるルール数の下限 k=3 とした。ただし、ルールの順位付けについては、(ii)相対的な関連度と(iii)関連度と相対的な関連度の組合せとの正解率の差はそれほど大きくなかったので、(i)関連度を含む３つの案を実行した。表 3 に結果をまとめた。T10000 に対するベースラインの正解率は 0.85 であり、ルールの順位付け方法がどれであっても提案方法は有効であるといえる。

ルールの順位付け方法による正解率の差はほとんどなかったが、 T200 の場合とは逆の順になった。T200 とT10000 の違いから、次のように推察される。T200 は曖昧性が高いアンカーテキストの比率を恣意的に高めており、“One sense per collocation”が成立しないアンカーテキストも多かったので、それに強い(ii)の正解率が相対的に高かった。これはあくまでも推察であり、結果を詳細に分析する必要がある。

6. おわりに
Wikification におけるリンク先記事の曖昧性解消のため、共起アンカーテキストによるリンク先決定ルールを確信度順に並べた決定リストを学習する方法を提案した。英語
Wikipedia 記事を用いた交差検定による評価実験では正解率 90％を達成した。最頻リンク先を選択する方法によるベースラインは 85%であり、提案方法の有効性が確認された。出現頻度が小さいアンカーテキストに対する決定リス
トの学習が今後の課題である。

参考文献[1] R. Mihalcea and A. Csomai. 2007. Wikify! Linking documents toencyclopedic knowledge. In Proceedings of the16th ACM
Conference on Information and Knowledge Management,
pp.233-242.
[2] R. L. Rivest. 1987. Learning decision lists. Machine Learning,
Vol.2, pp.229-246.
[3] D. Yarowsky. 1995. Unsupervised word sense disambiguation
rivaling supervised methods. In Proceedings of the 33rd Annual
Meeting of the Association for Computational Linguistics,
pp.189-196.
[4] R. Bunescu and M. Paseca. 2006. Using encyclopedic knowledge
for named entity disambiguation. In Proceedings of the 11thConference of the European Chapter of the Association forComputational Linguistics, pp.9-16.
[5] D. Milne and I. H. Witten. 2008. Learning to link with Wikipedia.
In Proceedings of the 17th ACM Conference on Information andKnowledge Management, pp.509-518.
[6] R. Mihalcea. 2007. Using Wikipedia for automatic word sense
disambiguation. In Proceedings of the Annual Conference of theNorth American Chapter of the Association for ComputationalLinguistics, pp.196-203.
[7] L. Ratinov, D. Roth, D. Downey, and M. Anderson. 2011. Local andglobal algorithms for disambiguation to Wikipedia. In Proceedings ofthe 49th Annual Meeting of the Association for Computational
Linguistics, pp.1375–1384.
[8] D. Turdakov and P. Velikhov. 2008. Semantic relatedness metric forWikipedia concepts based on link analysis and its application to word
sense disambiguation. In Proceedings of the Spring Young
Researcher's Colloquium on Database and Information Systems,
pp.35-40.
[9] S. Cucerzan. 2007. Large-scale named entity disambiguation basedon Wikipedia data. In Proceedings of the Empirical Methods in
Natural Language Processing and Computational Natural Language
Learning, pp.708-716.
[10] D. Yarowsky. 1993. One sense per collocation. In Proceedings ofthe Workshop on the Human Language Technology, pp.266-271.

― 691 ―

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