Learning Low-Rank Kernel Matrices” by Brian Kulis,

Tokyo Research Laboratory
“Learning Low-Rank Kernel Matrices”
by Brian Kulis, Mátyás Sustik, and Inderjit Dhillon*
IBM東京基礎研究所
井手剛
*Proceedings of the 23rd international conference on Machine learning, pp.505-512
| 2006/07/29 | ICML読む会
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
目次






問題設定
カーネル同士の距離をどう測るか
距離制約をどう取り込むか
正定値制約をどう満たすか
ランク制約をどう満たすか
まとめ
Page 2
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
問題設定
Page 3
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
やりたいこと: 距離制約を満たすように低ランクのカーネル行列を学習する。これ
はPCA座標を修正するのとほぼ同じ。
のように思えば、
カーネルを「学習」（＝修正）するこ
とは、座標を修正することに対応
r次元空間に次元削減
もとのデータ
「この二つの距
離は××以下」
r次元表現＋距離制約
制約を満たすように座標を修正
（つまりカーネル行列を修正）
Page 4
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
実用的なご利益の例（§6）: もしデータの一部のクラスタラベルが知られているな
ら、その情報を使ってクラスタリング結果を改善できる。
 Digitsデータの紹介




UCIの手書き文字データ
本来、3つのラベルがある：「３」「８」「９」
各画像は16次元ベクトル
3つあわせてn=317文字ある
 カーネルk平均法でクラスタリングして、クラスタリング
の良さを、相互情報量で測る



つかったカーネルは線形カーネル
• だから結局k-means
カーネル行列のサイズはn×nであるが、そのランクは
r=16。
このr=16をそのまま制約として採用。
（
ク
ラ
ス
タ
リ
ン
グ
の
良
さ
）
規
格
化
相
互
情
報
量
 距離制約（ズル情報）の入れ方


Page 5
任意のデータ点の対を選ぶ
• 16次元のベクトルはわかっているので、厳密に距離 d
を計算できる。
ラベルを見て距離制約をつける
• 両者が同一の数字を表す：距離＜ 0.75d
• 両者が異なる数字を表す：距離＞ 1.25d
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
制約が増えると顕著に結
果が良くなる。
制約なしだとイマイチな結果
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
問題設定：制約条件を満たしながら、元のカーネルと最も「近い」ものを求める。ラ
ンク制約・半正定値制約は非線形制約なのでこれは難しい最適化問題。
 なるべく元のカーネル行列を乱さないようにし
たい。

つまり、配置のバランスを崩さないようにしたい。
• ちなみに、座標が知れているとは限らない。
カーネルだけが既知かもしれない。
 距離制約をうまいこと式に乗せたい

一般には線形制約を扱いたい
 ランクを一定に保ちつつ、カーネル行列を修正
したい。

「ランクを一定」なんて式で表せるのだろうか？
 当然、半正定値性を保ちつつカーネル行列を
修正したい。
Page 6
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
カーネル同士の距離をどう測るか
Page 7
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
カーネル行列同士の距離尺度としてBregman divergenceを採用。
 Bregman divergence ：通常、ベクトル
に対して定義される擬距離

凸領域上の凸関数Φ によっていろいろな
バリエーション
 Bregman divは行列に拡張できる

「添え字をつぶす」操作でスカラーをつくる
• ベクトルなら内積をとる
• 行列ならTraceをとる
 Φの例： vN と Burgをここでは採用
Frobenius
von Neumann
Burg
Page 8
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
距離制約をどう取り込むか
Page 9
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
距離制約は、Tr(AK) < b のような形で表せる（Kはカーネル行列、bは定数）。
行列Aは、ランク1行列となる。
 カーネル行列Kから距離行列を作れる
（距離）＝
 行列Aは、次のようにとればよい

もしデータ点 i と j の距離に制約を加えたい場合
他の要素はすべて0。
すると Tr(AK) < bは、距離をb以下にするという制約を表すことに。
Aをいろいろえらべば、一般の線形制約を表現可能。
（例）類似度（内積）に対する制約
Page 10
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
Bregman projectionという手法でBregman divを最小化。
 基本となる事実： Bregman
divergenceの勾配は変数分離型

したがって、逐次更新風の最適化算法を
容易に構成できる
 とりあえず、ランク制約と正定値制約を
忘れて、距離制約のみを考え、距離制
約をラグランジュ変数で取り込むことに
する。

c個の距離制約があると仮定
 c個の制約から1個取り、それに対し、勾
配法的に最適なカーネル行列Xを計算

tr(AX) のX につ
いての微分はAT
次のステップでは他の制約へ
Page 11
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
正定値制約をどう満たすか
Page 12
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
Bregman projectionによる更新式の表式：都合のいいことに、カーネル行列の
更新式において、半正定値性は自動的に満たされる
 αは負、zzT は正定 → X0 が正定ならXt も正定
 exp(行列) はいつも正定
Page 13
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
ランク制約をどう満たすか
Page 14
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
これまた都合のよいことに、von Neumann & Burg divergences については、
Xt+1のランクがXt より大きいと、両者の距離が無限大になってしまう。
 証明のロジック

Page 15
これが非ゼロなのに、これが0なら発散してしまう
• D(Xt+1, Xt)において、Xt+1のランクがXtより大きいと、発散
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
まとめ
Page 16
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
まとめ
 線形制約下での低ランクカーネル行列学習問題を定式化した。
 正定値制約と低ランク制約は非線形制約なので取り込むのが一般に難しいが、Burg
divergence または von Neumann divergenceを使うと、これらを同時かつ自動的に満
たすことができる。


なお、von Neumann divによる行列の学習問題の定式化は、Tsuda-Noble (2004) や TsudaRätsch-Marmuth (2005)とか最初。しかし本論文は、Tsudaさんの不等式制約の取り込み方が不
完全だと批判している。
（具体的なアルゴリズムの説明は省略した。）
 カーネル学習問題を、semi-supervisedな感じのクラスタリング＆分類問題に適用して、
わずかなズル情報を使うことで、結果を顕著に改善できることがわかった。
Page 17
| 2006/07/29 | ICML読む会 Leaning Low Rank Kernel Matrices (井手剛)
© Copyright IBM Corporation 2006

Download Report