Spectral Clustering による 語義曖昧性解消のための 教師あり類似度学習 松本研研究会 2009-01-28 小町守

やりたいこと ラベル付きデータが少ない状況での語義曖昧性解消（半教師あり語義曖昧性解消） ラベルつきデータもラベルなしデータも両方活用 ラベルなしデータを用いたパターン（素性）・インスタンスの適切な重み付け ラベル見るのもアリ スペクトラルクラスタリング 教師あり距離（類似度）学習

本日の内容 kNN による語義曖昧性解消 教師あり類似度（距離）学習 半教師ありクラスタリング Spectral Clustering 制約付きスペクトラル学習による語義曖昧性解消実験

背景:kNNによる語義曖昧性解消 シード = 語義を当てたいインスタンス 距離 = インスタンス同士の類似度（正則化ラプラシアンカーネル） 学習 = k-nearest neighbor (k=3) →△分離平面がきれいにならない →△SVM に負けている シード

類似度尺度（距離）とは 2インスタンス間の（非）類似度を返す クラスタリング、知識獲得、構文解析、意味解析などに応用可能 ユークリッド距離、コサイン類似度、etc. イオンで　はし　を買ってきた ホームの　はし　は危険です どっちが「近い」？ この　はし　わたるべからず

類似度（マハラノビス距離）学習 距離 →類似度行列のパラメータ M = W’W （W はインスタンス-パターン行列）を学習 →M を対角行列にするとパターンの「重み」を学習 Pointwise-mutual information や tf.idf は教師なしで重みをつけられるが、類似度学習ではラベル付きデータから重みを推定 素性選択や次元削減に相当

教師あり類似度学習 距離をグラフ全体で最適化するように学習 局所的な距離を学習 カーネルを学習 Relevant Component Analysis (Bar-Hillel ICML-2003) 局所的な距離を学習 Neighborhood Component Analysis (Goldberger et al. NIPS-2005) Large magin nearest neighbor (Weinberger et al. NIPS-2006) カーネルを学習 Kernel alignment (Cristianini et al. NIPS-2002) Idealized kernel (Kwok and Tsang ICML-2003)

最大マージンNN（LMNN）

LMNN のコスト関数 ただしηijはxiとxjが近傍にあるかどうか判定する関数（学習時には変わらない） SVM に似た定式化 ユークリッド距離に基づいて k 個のインスタンスを近傍とする [z]+はmax(z, 0)で、hinge loss に相当 SVM に似た定式化

コスト関数の効率的な最適化 Semi-definite programming として表現できる

本日の内容 kNN による語義曖昧性解消 教師あり類似度（距離）学習 半教師ありクラスタリング Spectral Clustering 制約付きスペクトラル学習による語義曖昧性解消実験

半教師ありクラスタリング ラベルを2項間の制約として入れる（Wagstaff and Cardie 2000） Must-link 2つのインスタンスが同じラベル Cannot-link 2つのインスタンスは違うラベル

K-means +半教師ありクラスタリング 制約ベース: インスタンスが制約を満たすようクラスタリング COP-kmeans (Wagstaff et al. ICML-2001) 距離ベース: 制約を考慮してインスタンス間の距離を再計算 CCL (Klein et al. 2002) Must-link を持つインスタンス同士の距離を0、cannot-linkを∞とし、Must-link に関係する距離を修正→最後はcomplete-linkでクラスタリング →△使えるクラスタリングに条件があるという問題

スペクトラルクラスタリング クラスタ間の類似度が最小（クラスタ内の類似度が最大）になるようなグラフカット

固有ベクトルとラプラシアンの関係 グラフラプラシアン L = D – A (Dは対角行列、ただし 　　　　) の2番目に小さい固有ベクトルがそうしたグラフカットの近似になっている 2番目に小さい固有ベクトルを用いてデータを2つに分割できる（Shi and Malik CVPR-1997） K個の固有ベクトルを使って複数クラスタに分割できる（Ng et al. NIPS-2002; Meila and Shi AISTAT-2001） →○Kクラスの分類問題に利用できる

スペクトラル学習のアルゴリズム 類似度行列 A を作る 対角行列 D を作る A を正規化する（=N） Cos 類似度、ユークリッド距離、etc… 対角行列 D を作る A を正規化する（=N） D-1A, D-1/2AD-1/2, (A + dmaxI – D) / dmax （dmax = A の行和の最大値） N のk個の最大固有ベクトルを計算し、列に順番に並べて行列 X を作る X の各行を正規化する →ここから先がクラスタリングと分類で違う

スペクトラルクラスタリング 各インスタンスをXの各行にマップし k 個のクラスタに分割（K-means などを使う） 分類の場合は上記に変えて以下の2ステップ 各インスタンスをXの各行にマップ 各行を訓練事例として教師あり学習 インスタンスのラベルはマップされた X の行に相当するラベル

制約つきスペクトラルクラスタリング1 類似度行列に制約を入れる（Kamvar et al. IJCAI-2003） →○多クラスでも扱える Must-link のあるところは Aij = Aji = 1 Cannot-link のあるところは Aij = Aji = 0 残りは普通にスペクトラルクラスタリング →○多クラスでも扱える →△（数学的に）きれいではない →△?（制限）類似度尺度は0-1の範囲のみ

制約つきスペクトラルクラスタリング2 Subspace trick（De Bie et al. SSPR-2004） →○（数学的に）きれい 制約を書いた行列を用いることによって固有ベクトルの探索空間を変化させる（DMLA 12月17日） →○（数学的に）きれい →△（2クラスの場合はよいが）多クラスの場合Cannot-link の書き方が自明ではない 2 7 5 4 1 6 3

スペクトラル学習によるWSD Must-link、Cannot-link はラベル付きデータから生成できる 複数ラベルを考慮したモデルがよい Kamvar et al. の方法を試した →2クラスに限定すれば subspace trick も使えるが……

制約つきスペクトラル学習 類似度行列 A を作る 対角行列 D を作る 制約を満たすよう A を修正する A を正規化する（=N） Must-link のあるところは Aij = Aji = 1 Cannot-link のあるところは Aij = Aji = 0 A を正規化する（=N） N のk個の最大固有ベクトルを計算し、列に順番に並べて行列 X を作る →以下同様

（予想） スペクトラル学習はラベル付きデータが少ないときに有効 →SVM や kNN と比べてラベル付きデータが少ないところで勝ちたい いくつか分岐点がある 類似度尺度、クラスタリング（どのクラスタリング手法） or 分類（どの分類器）、正規化方法、制約の入れ方 →どれがよい?

実験設定 データ: 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 （線形カーネル）

SVM, kNN(k=5) との比較 精度 データ量（利用できる訓練データに対する割合）

考察 ×最頻出語義ベースライン以下 結果を分析したところ、（全てではないが）ほとんど最頻出語義を選択してしまっている →類似度に正則化ラプラシアンカーネルを使うべき? Kの数は大きすぎると過学習するが、小さすぎると全く判別できない

まとめ 制約付きスペクトラル学習を用いて語義曖昧性解消ができる。 ただし、類似度行列、正規化方法、分類器、制約の入れ方など、設定するべきパラメータが多い。 特に類似度行列の選び方が意味ドリフトを防ぐために重要（みたい）。

TODO LMNN による類似度行列の学習 （2クラス問題に限定して）subspace trick を使ってみる （多クラス問題で Must-link のみに限定して）subspace trick を使ってみる

コメント・アドバイスありましたら どうぞよろしくお願いします。