ブートストラップ法 Espresso における意味ドリ

ブートストラップ法 Espresso における
意味ドリフトのグラフ理論的分析
小町守
奈良先端科学技術大学院大学情報科学研究科自然言語処理学講座
ゼミナールII発表練習 2008年9月24日
2015/9/28
背景
自然言語処理における機械学習の成功


教師あり手法


タグ付きコーパスが必要
整備された辞書が必要
人手コストがかかる
→できるだけコスト減らしたい
ブートスト
ラップ
2
人手の介在を最小限に
しながら学習を行える
9/28/2015
ブートストラップ
パターン抽出とインスタンス獲得を交互に繰り返して少
量のシードインスタンスを反復的に増やす

インスタンス
（抽出対象）
iPhone
コーパス
アップルにiPhoneを注文する
パターン
（インスタンス抽出の
ためのテンプレート）
アップルに#を注文する
iPod touch
アップルにiPod touchを注文する
MacBook Air
アップルにMacBook Airを注文する
3
#:インスタンス
が入るスロット
9/28/2015
博士論文のトピック
Web 検索クエリログからの意味知識獲得のためのブー
トストラップ手法
ブートストラップ法 Espresso における意味ドリフトのグラ
フ理論的分析
グラフカーネルを用いた意味的類似度の定義と意味知
識獲得



4
9/28/2015
ブートストラップの問題点
意味ドリフト

シード
共起パターン
広末涼子
湯布院
熱海
ジェネリックパターン
=多数のインスタンスと共起するパターン
〜の写真
イチロー
……
意味ドリフト=いったんジェ
ネリックパターンを獲得して
しまうとそれ以降シードイン
スタンスと関連性の低いイ
ンスタンスを獲得してしまう
パラメータ数が多く調整が難しい




5
反復の初期段階で止めるほうが一般的によい精度
後述する Espressoではパラメータ数は8個
タスク・ドメイン依存
9/28/2015
本研究の主要な貢献
1.
ブートストラップのグラフ理論による解析
•
•
2.
意味ドリフトと HITS (Kleinberg, 1999) のトピックドリフト
との関連性
•
3.
ブートストラップにおけるヒューリスティックの意義
グラフに基づくカーネルを用いた意味ドリフトの解決
•
6
Espresso (Pantel and Pennachiotti, 2006) のリンク解析的定式化
Espresso の収束解析
ジェネリックパターンの影響を抑えつつ関連性の高いインスタ
ンスを獲得する手法
9/28/2015
2015/9/28
ブートストラップの定式化
シードインスタンスのスコアベクトル i 0  0,...,1,...,0
パターン-インスタンス共起行列P 行列の(p,i)要素はパターンp


0

1

P
1

0
1
0
1
1
0
0
0
1
0

0
1

1
以下を反復
p  Mi


i  MT p
I と p が収束したら終了


7
とインスタンスiの共起

インスタンスの類似度行列をM=PTP
として、このステップを再帰的に行うと
in=Mni0
インスタンスとパターン
のベクトルを出力
9/28/2015
簡略化版 Espresso (Simplified Espresso)
 シードインスタンスのスコアベクトル i 0  0,1,0,0
パターン-インスタンス共起行列行列の(p,i)要素はパターンpと

0.001

0.6

A
0.001

0.001
0.6
0.001
0.2
0.3
0.001
0.001
0.001
0.3
0.001

0.001
0.2  

0.001
以下を反復
p  Mi


i  MT p
iとpが収束したら終了


8
インスタンスiの正規化された
自己相互情報量
1 pmi(i,p)
M  A A
I P maxpmi
T
パターン抽出はブートストラップにおいて
必須ではない（小町ら, 2008）

ブートストラップの反復の際スコア上位
のパターン・インスタンスを獲得するとい
うヒューリスティック
9/28/2015
意味ドリフトと HITS のトピックドリフトの関連性
Simplified Espresso では、各反復ごとにinを正規化しなが
らn→∞とすると、シードインスタンスベクトルi0によらず
in→Mの主固有ベクトル



Pを隣接行列とするHITSが返す権威度ベクトルと一致
どのシードインスタンスに対してもランキングは一定
ブートストラップの反復を繰り返していくと意味ドリフトは不可避?
HITSではトピックドリフトと言われている現象


ブートストラップはHITSとは異なり反復の際スコア上位のパタ
ーン・インスタンスのみ使うというヒューリスティック
ヒューリスティック入りの Espresso（Filtered Espresso）
は意味ドリフト抑制に成功する?
9
9/28/2015
意味ドリフトとトピックドリフトの評価実験


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.
10
訓練事例には人手でつけた
語義がついている
評価事例の語義を当てる
9/28/2015
ブートストラップによる語義曖昧性解消

シードインスタンス=語義を当てる対象の用例

システムの出力=スコアの高い順3インスタンスのうち多
数を占める語義（k=3 の k-nearest neighbour）


語義が同数の場合はスコアの一番高い語義
Espresso の足切りヒューリスティック（Filtered Espresso）
 初期パターン数p=20 （反復ごとにp=p+1）
 初期インスタンス数m=100 （反復ごとにm=m+100）
11
9/28/2015
Espresso のヒューリスティックの比較結果
反復を繰り返しても意味ドリフトは起
きない
→ヒューリスティックは意味ドリフトを
抑えるために必要な処理
入力によらず
最頻出語義を
出力する
徐々にジェネリックインスタンスに
高いスコアが割り振られ、意味ド
リフトが起きている
12
インスタンスの順番はHITSの重要度ランキングと一致
9/28/2015
→意味ドリフトとHITSのトピックドリフトは同じ原因
Filtered Espresso の学習曲線
最頻出語義の割合が増加
→意味ドリフトが起きている
ヒューリスティックを入れても
意味ドリフトが起きている
13
9/28/2015
グラフカーネルを用いた意味ドリフトの解決

Espresso

意味ドリフトが避けられない



HITS 重要度の高いインスタンスを獲得してしまう
ヒューリスティックの効果は限定的
設定しなければならないパラメータが多い

最適化が大変
関連度の高いインスタンスの獲得のための手法
① ノイマンカーネル（重要度と関連度の混合）
② 正則化ラプラシアンカーネル（重要度によらない関連度）
14
9/28/2015
正則化ラプラシアンによる関連度の定義
旅行パターンと共起するイン
スタンスは関連度高くしたい
〜の旅館
湯布院
熱海
パターン
ジェネリックパターンと共起するイ
ンスタンスは関連度低くしたい
〜の写真
広末涼子
〜のホームページ
イチロー
インスタンス
15
9/28/2015
……
正則化ラプラシアンカーネル


グラフ内の全経路の重み付き和
負のラプラシアン -L はグラフ G の自己ループの重みを
変更したものに相当
グラフGのラプラシアンL
次数対角行列Dのi番目の対角要素
L  D A
D(i,i)   A(i, j)
j
A:隣接行列
β:拡散係数

正則化ラプラシアン行列Rβ

16

R   n (L)n  (I  L)1
n 0
9/28/2015
グラフカーネルによる意味ドリフト解決の評価
1.
提案手法が意味ドリフトの抑制に成功しているかどうか
2.
グラフベースの語義曖昧性解消手法との比較
•
Agirre et al. (2006) との比較
•
HyperLex (Veronis, 2004) と PageRank (Brin and Page, 1998) を用いた実験
17
9/28/2015
Bank に対する予測ラベル（F値）
Espresso は意味ドリフトが避けられない
アルゴリズム
最頻出語義それ以外
Simplified Espresso
100.0
0.0
Filtered Espresso
100.0
30.2
Filtered Espresso （最適パラメータ）
94.4
67.4
正則化ラプラシアン（β=10-2）
92.1
62.8
正則化ラプラシアンは
意味ドリフトを回避している
18
9/28/2015
グラフベースの語義曖昧性解消（名詞のみ）
Espresso はパラメータのチューニングが必要
アルゴリズム
F値
再頻出語義（ベースライン）
54.5
HyperLex
64.6
PageRank
64.6
Simplified Espresso
44.1
Filtered Espresso
46.9
Filtered Espresso (最適パラメータ) 66.5
正則化ラプラシアン（β=10-2）
67.1
HyperLexやPageRankより数ポイント上
19
9/28/2015
まとめ



グラフ理論によるブートストラップ法 Espresso の解析を
提案した
HITS におけるトピックドリフトとブートストラップにおける
意味ドリフトの類似性を指摘した
正則化ラプラシアンカーネルがブートストラップにおける
意味ドリフトを抑制することを語義曖昧性解消タスクで示
した
今後の予定
 固有表現抽出タスクでも提案手法が適用できるか検証
 語義曖昧性解消タスクのドメイン適応
20
9/28/2015
21
9/28/2015
Espresso アルゴリズム

Espresso (Pantel and Pennacchiotti, 2006)


少量のシードインスタンスから始める
以下を反復
信頼性の高いインスタンスは信頼性の



パターン抽出
パターンのランキングと選択
インスタンス獲得
pmi(i, p)

maxpmi  r (i)
r (p)  iI
I
x, p, y
pmi(i, p)  log
x,*, y *, p,*
22

高いパターンに、パターンはインスタン
スに支持されている
pmi(i, p)

maxpmi  r (p)
r (i)  p P
P
p:パターン, i:インスタンス
P:パターン集合, I:インスタンス集合
pmi:自己相互情報量, max pmi:全P,I中のpmiの最大値
9/28/2015
2015/9/28
拡散係数βに対する感受性
ノイマンカーネル
正則化ラプラシアンカーネル
パラメータによってかなり性能
に違い
パラメータによらずほとんど
性能に違いは見られない
23
9/28/2015
関連研究

Agirre et al. (2006)
HyperLex (Veronis, 2004) と PageRank (Brin
and Page, 1998) を用いた手法
 単語をノード、単語間の共起の相対頻度を
エッジとしたグラフを作成しクラスタリング
 パラメータ数が多く最適化が難しい


Espresso (Pantel and Pennachiotti, 2006)

24
グラフ解析との関連性については言及なし
9/28/2015

Download Report