ブートストラップ法 Espresso における 意味ドリフトのグラフ理論的分析 小町守 奈良先端科学技術大学院大学情報科学研究科自然言語処理学講座 ゼミナールII発表練習　2008年9月24日 2017/3/11

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

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

博士論文のトピック Web 検索クエリログからの意味知識獲得のためのブー トストラップ手法 ブートストラップ法 Espresso における意味ドリフトのグラ フ理論的分析 グラフカーネルを用いた意味的類似度の定義と意味知 識獲得 3/11/2017

意味ドリフト=いったんジェネリックパターンを獲得してしまうとそれ以降シードインスタンスと関連性の低いインスタンスを獲得してしまう ブートストラップの問題点 意味ドリフト パラメータ数が多く調整が難しい 反復の初期段階で止めるほうが一般的によい精度 後述する Espressoではパラメータ数は8個 タスク・ドメイン依存 熱海 湯布院 〜の写真 広末涼子 イチロー …… 共起パターン ジェネリックパターン =多数のインスタンスと共起するパターン 意味ドリフト=いったんジェネリックパターンを獲得してしまうとそれ以降シードインスタンスと関連性の低いインスタンスを獲得してしまう シード 3/11/2017

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

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

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

意味ドリフトと HITS のトピックドリフトの関連性 Simplified Espresso では、各反復ごとにinを正規化しなが らn→∞とすると、シードインスタンスベクトルi0によらず in→Mの主固有ベクトル Pを隣接行列とするHITSが返す権威度ベクトルと一致 どのシードインスタンスに対してもランキングは一定 HITSではトピックドリフトと言われている現象 ブートストラップはHITSとは異なり反復の際スコア上位のパタ ーン・インスタンスのみ使うというヒューリスティック ブートストラップの反復を繰り返していくと意味ドリフトは不可避? ヒューリスティック入りの Espresso（Filtered Espresso） は意味ドリフト抑制に成功する? 3/11/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/11/2017

ブートストラップによる語義曖昧性解消 シードインスタンス=語義を当てる対象の用例 システムの出力=スコアの高い順3インスタンスのうち多 数を占める語義（k=3 の k-nearest neighbour） 語義が同数の場合はスコアの一番高い語義 Espresso の足切りヒューリスティック（Filtered Espresso） 初期パターン数p=20 （反復ごとにp=p+1） 初期インスタンス数m=100 （反復ごとにm=m+100） 最初にテスト事例を入れてパターンインスタンス共起行列を作っているが、 最初にテスト事例がない状態でどうなるか知りたい(高村さん) 3/11/2017

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

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

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

正則化ラプラシアンによる関連度の定義 湯布院 熱海 広末涼子 イチロー 〜の写真 〜の旅館 〜のホームページ …… 旅行パターンと共起するインスタンスは関連度高くしたい ジェネリックパターンと共起するインスタンスは関連度低くしたい パターン 湯布院 熱海 広末涼子 イチロー 〜の写真 〜の旅館 〜のホームページ …… インスタンス 3/11/2017

正則化ラプラシアンカーネル グラフ内の全経路の重み付き和 負のラプラシアン -L はグラフ G の自己ループの重みを 変更したものに相当 グラフGのラプラシアンL A:隣接行列 β:拡散係数 次数対角行列Dのi番目の対角要素 正則化ラプラシアン行列Rβ 3/11/2017

グラフカーネルによる意味ドリフト解決の評価 提案手法が意味ドリフトの抑制に成功しているかどうか グラフベースの語義曖昧性解消手法との比較 Agirre et al. (2006) との比較 HyperLex (Veronis, 2004) と PageRank (Brin and Page, 1998) を用いた実験 17 3/11/2017 3/11/2017

Espresso は意味ドリフトが避けられない Bank に対する予測ラベル（F値） Espresso は意味ドリフトが避けられない アルゴリズム 最頻出語義 それ以外 Simplified Espresso 100.0 0.0 Filtered Espresso 30.2 Filtered Espresso （最適パラメータ） 94.4 67.4 正則化ラプラシアン （β=10-2） 92.1 62.8 正則化ラプラシアンは 意味ドリフトを回避している 3/11/2017

グラフベースの語義曖昧性解消（名詞のみ） Espresso はパラメータのチューニングが必要 アルゴリズム F値 再頻出語義（ベースライン） 54.5 HyperLex 64.6 PageRank Simplified Espresso 44.1 Filtered Espresso 46.9 Filtered Espresso (最適パラメータ) 66.5 正則化ラプラシアン （β=10-2） 67.1 HyperLexやPageRankより数ポイント上 3/11/2017

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

3/11/2017

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

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

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