Spectral Learning を用いた 語義曖昧性解消

Spectral Clustering による
語義曖昧性解消のための
教師あり類似度学習
松本研研究会 2009-01-28
小町守
やりたいこと
• ラベル付きデータが少ない状況での語義曖
昧性解消(半教師あり語義曖昧性解消)
– ラベルつきデータもラベルなしデータも両方活用
スペクトラルクラスタリング
• ラベルなしデータを用いたパターン(素性)・イ
ンスタンスの適切な重み付け
– ラベル見るのもアリ
教師あり距離(類似度)学習
2
本日の内容
• kNN による語義曖昧性解消
• 教師あり類似度(距離)学習
• 半教師ありクラスタリング
– Spectral Clustering
• 制約付きスペクトラル学習による語義曖昧性
解消実験
3
背景:kNNによる語義曖昧性解消
シード
シード = 語義を当てたいインスタンス
距離 = インスタンス同士の類似度(正則化ラプラシ
アンカーネル)
学習 = k-nearest neighbor (k=3)
→△分離平面がきれいにならない
→△SVM に負けている
4
類似度尺度(距離)とは
• 2インスタンス間の(非)類似度を返す
クラスタリング、知識獲得、構文解析、意味解析
などに応用可能
ユークリッド距離、コサイン類似度、etc.
イオンで はし を買ってきた
どっちが「近い」?
ホームの はし は危険です
この はし わたるべからず
5
類似度(マハラノビス距離)学習
r r
r r 2
r r
r r
• 距離 D( x i , x j )  L( x i  x j )  ( x i  x j )M( x i  x j )
→類似度行列のパラメータ M = W’W (W はインス
タンス-パターン行列)を学習
→M を対角行列にするとパターンの「重み」を学習

• Pointwise-mutual information や tf.idf は教師
なしで重みをつけられるが、類似度学習では
ラベル付きデータから重みを推定
• 素性選択や次元削減に相当
6
教師あり類似度学習
• 距離をグラフ全体で最適化するように学習
– Relevant Component Analysis (Bar-Hillel ICML-2003)
• 局所的な距離を学習
– Neighborhood Component Analysis (Goldberger et al. NIPS2005)
– Large magin nearest neighbor (Weinberger et al. NIPS-2006)
• カーネルを学習
– Kernel alignment (Cristianini et al. NIPS-2002)
– Idealized kernel (Kwok and Tsang ICML-2003)
7
最大マージンNN(LMNN)
8
LMNN のコスト関数
r r 2
r r 2
r r 2

(L)  ij Lx i  x j   c  ji 1 y il 1 Lx i  x j   Lx i  x l  


ij
ijl
• ただしηijはxiとxjが近傍にあるかどうか判定す
る関数(学習時には変わらない)
– ユークリッド距離に基づいて k 個のインスタンス
を近傍とする
– [z]+はmax(z, 0)で、hinge loss に相当
• SVM に似た定式化
9
コスト関数の効率的な最適化
• Semi-definite programming として表現できる
r r  r r
Maximizeij x i  x j  Mx i  x j  c ij 1 y il  ijl subject to
ij
ij
r r
r r
r r
r r
(1) x i  x l  Mx i  x l   x i  x j  Mx i  x j  1  ijl
(2)  ijl  0 (slack variable)
(3) Mf 0
• 3番目の制約は行列Mが半正定値(固有値が
全て正)という条件(対角行列なら対角要素
が全て正)
10
本日の内容
• kNN による語義曖昧性解消
• 教師あり類似度(距離)学習
• 半教師ありクラスタリング
– Spectral Clustering
• 制約付きスペクトラル学習による語義曖昧性
解消実験
11
半教師ありクラスタリング
• ラベルを2項間の制約として入れる(Wagstaff
and Cardie 2000)
– Must-link 2つのインスタンスが同じラベル
– Cannot-link 2つのインスタンスは違うラベル
12
K-means +半教師ありクラスタリング
• 制約ベース: インスタンスが制約を満たすようク
ラスタリング
– COP-kmeans (Wagstaff et al. ICML-2001)
• 距離ベース: 制約を考慮してインスタンス間の距
離を再計算
– CCL (Klein et al. 2002)
– Must-link を持つインスタンス同士の距離を0、
cannot-linkを∞とし、Must-link に関係する距離を修
正→最後はcomplete-linkでクラスタリング
→△使えるクラスタリングに条件があるという問題
13
スペクトラルクラスタリング
• クラスタ間の類似度が最小(クラスタ内の類
似度が最大)になるようなグラフカット
14
固有ベクトルとラプラシアンの関係
• グラフラプラシアン L = D – A (Dは対角行列、
ただし
) の2番目に小さい固有ベクトル
D  A
がそうしたグラフカットの近似になっている
• 2番目に小さい固有ベクトルを用いてデータを

2つに分割できる(Shi and Malik CVPR-1997)
• K個の固有ベクトルを使って複数クラスタに分
割できる(Ng et al. NIPS-2002; Meila and Shi
AISTAT-2001)
→○Kクラスの分類問題に利用できる
n
ii
ij
j1
15
スペクトラル学習のアルゴリズム
1. 類似度行列 A を作る
Cos 類似度、ユークリッド距離、etc…
n
2. 対角行列 D を作る D   A
3. A を正規化する(=N)
ii
ij
j1
D-1A, D-1/2AD-1/2, (A + dmaxI – D) / dmax (dmax = A の行和の最大値)

4. N のk個の最大固有ベクトルを計算し、列に順
番に並べて行列 X を作る
5. X の各行を正規化する
→ここから先がクラスタリングと分類で違う
16
スペクトラルクラスタリング
6. 各インスタンスをXの各行にマップし k 個のク
ラスタに分割(K-means などを使う)
分類の場合は上記に変えて以下の2ステップ
 各インスタンスをXの各行にマップ
 各行を訓練事例として教師あり学習
7. インスタンスのラベルはマップされた X の行
に相当するラベル
17
制約つきスペクトラルクラスタリング1
• 類似度行列に制約を入れる(Kamvar et al.
IJCAI-2003)
– Must-link のあるところは Aij = Aji = 1
– Cannot-link のあるところは Aij = Aji = 0
– 残りは普通にスペクトラルクラスタリング
→○多クラスでも扱える
→△(数学的に)きれいではない
→△?(制限)類似度尺度は0-1の範囲のみ
18
制約つきスペクトラルクラスタリング2
• Subspace trick(De Bie et al. SSPR-2004)
– 制約を書いた行列を用いることによって固有ベク
トルの探索空間を変化させる(DMLA 12月17日)
→○(数学的に)きれい
→△(2クラスの場合はよいが)多クラスの場合
Cannot-link の書き方が自明ではない
1

1
1
v  
0
0

0
0
0
0
1
1
0
0 

0 
0 
u  Yu
0 
0 

In 5 
2
7
1
5
4
6
3
19
スペクトラル学習によるWSD
• Must-link、Cannot-link はラベル付きデータか
ら生成できる
– 同じ語義なら Must-link、違う語義なら Cannot-link、
語義が分からないときは制約なし
• 複数ラベルを考慮したモデルがよい
– Kamvar et al. の方法を試した
→2クラスに限定すれば subspace trick も使える
が……
20
制約つきスペクトラル学習
1. 類似度行列 A を作る
2. 対角行列 D を作る
3. 制約を満たすよう A を修正する
1. Must-link のあるところは Aij = Aji = 1
2. Cannot-link のあるところは Aij = Aji = 0
4. A を正規化する(=N)
5. N のk個の最大固有ベクトルを計算し、列に順
番に並べて行列 X を作る
→以下同様
21
(予想)
• スペクトラル学習はラベル付きデータが少な
いときに有効
→SVM や kNN と比べてラベル付きデータが少
ないところで勝ちたい
• いくつか分岐点がある
– 類似度尺度、クラスタリング(どのクラスタリング
手法) or 分類(どの分類器)、正規化方法、制約
の入れ方
→どれがよい?
22
実験設定
• データ: Senseval-3 English Lexical Sample
– 57単語、1語につき100-200文章の訓練データ
– 語義の数は平均して6.47個
– 10%, 25%, 50%, 75%, 100% で実験
• 手法(スペクトラル学習)
– 類似度行列 A = PPT (ただしPは各行で正規化)
– A の正規化 なし
– K = 50 (てきとう)
– 分類器 libsvm-2.84.0 (線形カーネル)
23
SVM, kNN(k=5) との比較
75
70
65
60
SVM
精度
スペクトラル学習
kNN(名詞のみ)
55
最頻出語義
50
45
40
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
データ量(利用できる訓練データに対する割合)
100%
24
考察
• ×最頻出語義ベースライン以下
• 結果を分析したところ、(全てではないが)ほ
とんど最頻出語義を選択してしまっている
→類似度に正則化ラプラシアンカーネルを使う
べき?
• Kの数は大きすぎると過学習するが、小さす
ぎると全く判別できない
25
まとめ
• 制約付きスペクトラル学習を用いて語義曖昧
性解消ができる。
• ただし、類似度行列、正規化方法、分類器、
制約の入れ方など、設定するべきパラメータ
が多い。
• 特に類似度行列の選び方が意味ドリフトを防
ぐために重要(みたい)。
26
TODO
• LMNN による類似度行列の学習
• (2クラス問題に限定して)subspace trick を
使ってみる
• (多クラス問題で Must-link のみに限定して)
subspace trick を使ってみる
27
コメント・アドバイスありましたら
• どうぞよろしくお願いします。
28