小町守(†), 工藤拓(‡), 新保仁(†), 松本裕治(†) A Graph-Theoretic Approach to Reducing Semantic Drift in a Family of Bootstrapping Algorithms 小町守(†), 工藤拓(‡), 新保仁(†), 松本裕治(†) (†) 奈良先端科学技術大学院大学 (‡) グーグル株式会社 第7回SVM勉強会定例研究会　2008年8月31日 2017/3/5

背景 人手コストがかかる →できるだけコスト減らしたい 人手の介在を最小限に しながら学習を行える リソースがない言語でも 扱うことができる 自然言語処理における機械学習の成功 教師あり手法 タグ付きコーパスが必要 整備された辞書が必要 人手コストがかかる →できるだけコスト減らしたい 教師なし手法 ブートストラップ 人手の介在を最小限に しながら学習を行える リソースがない言語でも 扱うことができる 2 3/5/2017 3/5/2017

ブートストラップ パターン抽出とインスタンス獲得を交互に繰り返して少 量のシードインスタンスを反復的に増やす インスタンス コーパス co-training とはどういう関係にあるか MacBook Air アップルMacBook Air注文 アップル#注文 iPod touch アップルiPod touch注文 #:インスタンス が入るスロット MacBook Pro アップルMacBook Pro注文 3/5/2017

意味ドリフト=いったんジェネリックパターンを獲得してしまうとそれ以降シードインスタンスと関連性の低いインスタンスを獲得してしまう ブートストラップの問題点 意味ドリフトの問題 理論的裏付けに乏しい パラメータ数が多く調整が難しい タスク・ドメイン依存 熱海 湯布院 〜の写真 広末涼子 イチロー …… 共起パターン ジェネリックパターン =多数のインスタンスと共起するパターン 意味ドリフト=いったんジェネリックパターンを獲得してしまうとそれ以降シードインスタンスと関連性の低いインスタンスを獲得してしまう シード 3/5/2017

目的 ブートストラップのグラフ理論による解析 意味ドリフトと HITS (Kleinberg, 1999) のトピックドリフト との関連性 Espresso (Pantel and Pennachiotti, 2006) のリンク解析的定式化 Espresso の収束解析 意味ドリフトと HITS (Kleinberg, 1999) のトピックドリフト との関連性 ブートストラップにおけるヒューリスティックの意義 グラフに基づくカーネルを用いた意味ドリフトの解決 ジェネリックパターンの影響を抑えつつ関連性の高いインスタ ンスを獲得する手法 5 2017/3/5 3/5/2017

信頼性の高いインスタンスは信頼性の高いパターンに、パターンはインスタンスに支持されている Espresso アルゴリズム Espresso (Pantel and Pennacchiotti, 2006) 少量のシードインスタンスから始める 以下を反復 パターン抽出 パターンのランキングと選択 インスタンス獲得 信頼性の高いインスタンスは信頼性の高いパターンに、パターンはインスタンスに支持されている p:パターン, i:インスタンス P:パターン集合, I:インスタンス集合 pmi:自己相互情報量, max pmi:全P,I中のpmiの最大値 6 2017/3/5 3/5/2017

行列の(p,i)要素はパターンpとインスタンスiの共起 ブートストラップの定式化 シードインスタンスのスコアベクトル パターン-インスタンス共起行列P 以下を反復 I と p が収束したら終了 行列の(p,i)要素はパターンpとインスタンスiの共起 インスタンスの類似度行列をM=PTP として、このステップを再帰的に行うと in=Mni0 インスタンスとパターン のベクトルを出力 3/5/2017

簡略化版 Espresso (simplified Espresso) シードインスタンスのスコアベクトル パターン-インスタンス共起行列 以下を反復 iとpが収束したら終了 行列の(p,i)要素はパターンpとインスタンスiの正規化された自己相互情報量 パターン抽出はブートストラップにおいて必須ではない（小町ら, 2008） ブートストラップの反復の際スコア上位のパターン・インスタンスを獲得するというヒューリスティック 3/5/2017

意味ドリフトと HITS のトピックドリフトの関連性 各反復ごとにinを正規化しながらn→∞とすると、シードイ ンスタンスベクトルi0によらずin→Mの主固有ベクトル Pを隣接行列とするHITSが返す権威度ベクトルと一致 シードインスタンスによらずランキングは一定 HITSによるグラフ解析ではトピックドリフトと言われてい る現象 ブートストラップはグラフ解析とは異なり反復の際スコア上位 のパターン・インスタンスのみ使うというヒューリスティック ブートストラップの反復を繰り返していくと意味ドリフトは不可避? 足切りヒューリスティックは意味ドリフト抑制効果がある? 3/5/2017

意味ドリフトとトピックドリフトの評価実験 Senseval-3 English Lexical Sample タスクのデータ Bank の語義を当てる 訓練事例262個・評価事例132個 評価事例中の再頻出語義は「土手」の意味の86個(F=0.674) … the financial benefits of the bank(銀行) 's employee package ( cheap mortgages and pensions, etc ) , bring this up to … 訓練事例には人手でつけた 語義がついている In that same year I was posted to South Shields on the south bank(土手) of the River Tyne and quickly became aware that I had an enormous burden … Possibly aligned to water a sort of bank(???) by a rushing river. 評価事例の語義を当てる 3/5/2017

ブートストラップによる語義曖昧性解消 シードインスタンス=語義を当てる対象の用例 システムの出力=スコアの高い順3インスタンスのうち多 数を占める語義（k=3 の k-nearest neighbour） 語義が同数の場合はスコアの一番高い語義 語義曖昧性解消に用いた素性 グローバル素性: パラグラフの bag-of-words 出現すれば1,出現しなければ0 ローカル素性: インスタンスの前後n単語(n=3)から作成した単語列 パターン （例） interest が対象のとき “sale of * interest in * *” Espresso の足切りヒューリスティック（filtered Espresso） 初期パターン数p=200 （反復ごとにp=p+1） 初期インスタンス数m=100 （反復ごとにm=m+100） 最初にテスト事例を入れてパターンインスタンス共起行列を作っているが、 最初にテスト事例がない状態でどうなるか知りたい(高村さん) 3/5/2017

Espresso のヒューリスティックの比較結果 反復を繰り返しても意味ドリフトは起きない →足切りは意味ドリフトを抑えるために必要な処理 徐々にジェネリックインスタンスに高いスコアが割り振られ、意味ドリフトが起きている インスタンスの順番はHITSの重要度ランキングと一致 →意味ドリフトとHITSのトピックドリフトは同じ原因 3/5/2017

Filtered Espresso の学習曲線 最頻出語義の割合が増加 →意味ドリフトが起きている 足切りヒューリスティックを入れても意味ドリフトは不可避 3/5/2017

解決するための2つの手法 グラフ解析を用いた意味ドリフトの解決 ノイマンカーネル 正則化ラプラシアンカーネル Espresso 意味ドリフトが避けられない HITS 重要度の高いインスタンスを獲得してしまう 足切りヒューリスティックの効果は限定的 設定しなければならないパラメータが多い 最適化が大変 解決するための2つの手法 ノイマンカーネル 正則化ラプラシアンカーネル 3/5/2017

ノイマンカーネル (Kandola et al., 2002) Kβの(i,j)要素=インスタンスi,j間の類似度 シードインスタンスに対する相対的重要度が計算できる 共引用関連度と HITS 重要度との混合を表現(伊藤ら, 2004) 3/5/2017

ノイマンカーネルはなにをするか? A=PTPが表す共引用グラフ上での各ノード間の全ての経 路数の重み付き和 湯布院 熱海 広末涼子 イチロー N次のパターン共起を考慮に入れている (PTP)nの各行 Nが小さいとき→各ノード間の関連度 Nが大きいとき→HITS 重要度 湯布院 熱海 広末涼子 イチロー 〜の写真 〜の旅館 〜のホームページ …… 3/5/2017

ノイマンカーネルのパラメータ ノイマンカーネル: n=1〜∞までの(PTP)nの重み付き和 拡散係数βが小さいとき→関連度 拡散係数βが大きいとき→HITSの重要度 βを小さめに設定すれば意味ドリフトを抑制・高次のパタ ーン共起も考慮できるはず あとで実験により検証 湯布院 熱海 広末涼子 イチロー 〜の写真 〜の旅館 〜のホームページ …… 3/5/2017

ノイマンカーネルの問題点の解決 グラフラプラシアンを用いて解決できる ノイマンカーネルの問題点 湯布院 熱海 広末涼子 イチロー 〜の写真 βが小さいとき:高次のパターン共起を十分考慮できない βが大きいとき:ジェネリックパターンに強い重みがつく グラフラプラシアンを用いて解決できる 旅行パターンと共起するインスタンスは関連度高くしたい ジェネリックパターンと共起するインスタンスは関連度低くしたい 湯布院 熱海 広末涼子 イチロー 〜の写真 〜の旅館 〜のホームページ …… 3/5/2017

正則化ラプラシアンカーネル グラフ内の全経路の重み付き和 負のラプラシアン -L はグラフ G の自己ループの重みを 変更したものに相当 高次のパターン共起も考慮に入れることができる 負のラプラシアン -L はグラフ G の自己ループの重みを 変更したものに相当 グラフGのラプラシアンL A:隣接行列 β:拡散係数 次数対角行列Dのi番目の対角要素 正則化ラプラシアン行列Rβ ノイマンカーネル行列 においてAの代わりに-Lを使用、右辺第一項のAを削除 3/5/2017

グラフ解析を用いた意味ドリフト解決評価実験 提案手法が意味ドリフトの抑制に成功しているかどうか グラフベースの語義曖昧性解消手法との比較 Agirre et al. (2006) との比較 HyperLex (Veronis, 2004) と PageRank (Brin and Page, 1998) を用いた実験 ノイマンカーネル・正則化ラプラシアンカーネルにおける 拡散係数の影響の比較 本当にβが大きいときは大域的重要度に、小さいときは関連度 に偏った結果となっているか? 20 3/5/2017 3/5/2017

Espresso は意味ドリフトが避けられない Bank に対する予測ラベル（再現率） Espresso は意味ドリフトが避けられない アルゴリズム MFS それ以外 Simplified Espresso 100.0 0.0 Filtered Espresso 30.2 Filtered Espresso (opt.) 94.4 67.4 ノイマンカーネル (β=10-5) 92.1 65.1 正則化ラプラシアン (β=10-2) 62.8 ノイマンカーネルや正則化ラプラシアンは 意味ドリフトを回避している 3/5/2017

グラフベースの語義曖昧性解消（名詞のみ） Espresso はパラメータのチューニングが必要 アルゴリズム 精度 再現率 F値 Most frequent sense 54.5 HyperLex 64.6 PageRank 64.5 Simplified Espresso 44.1 Filtered Espresso 46.9 Filtered Espresso (opt.) 66.5 ノイマンカーネル (β=10-5) 67.2 正則化ラプラシアン (β=10-2) 67.1 HyperLexやPageRankより数ポイント上 3/5/2017

WordNet等外部リソースを用いない教師なしの手法 教師なし語義曖昧性解消手法 他の手法と比較して高い適合率 アルゴリズム 適合率 再現率 F値 Espresso(足切りなし) 42.8 Espresso(足切りあり) 63.6 ノイマンカーネル 64.9 正則化ラプラシアン 65.4 ベースライン(MFS) 55.2 Cymfony 57.9 Prob0 54.7 clr04 45.0 Duluth-SenseRelate 40.3 38.5 39.4  教師あり手法と比較するとどれくらいか(高村さん) WordNet等外部リソースを用いない教師なしの手法 23 3/5/2017 3/5/2017

拡散係数βに対する感受性 ノイマンカーネル 正則化ラプラシアンカーネル パラメータによってかなり性能に違い パラメータによらずほとんど性能に違いは見られない 3/5/2017

Espresso (Pantel and Pennachiotti, 2006) 関連研究 Agirre et al. (2006) HyperLex (Veronis, 2004) と PageRank (Brin and Page, 1998) を用いた手法 単語をノード、単語間の共起の相対頻度を エッジとしたグラフを作成しクラスタリング パラメータ数が多く最適化が難しい Espresso (Pantel and Pennachiotti, 2006) グラフ解析との関連性については言及なし 3/5/2017

まとめ グラフ理論によるブートストラップの解析を提案した HITS におけるトピックドリフトとブートストラップにおける 意味ドリフトの類似性を指摘した ブートストラップにおける意味ドリフトを防ぐために ノイマンカーネル 正則化ラプラシアンカーネル が使えることを語義曖昧性解消タスクで示した 今後の予定 固有表現抽出タスクでも提案手法が適用できるか検証 語義曖昧性解消タスクのドメイン適応 3/5/2017