狠狠撸

Informa(on-?‐Theore(c
?Metric
?Learning
?
Jason
?V.
?Davis,
?Brian
?Kulis,
?
?
Prateek
?Jain,
?Suvrit
?Sra,
?Inderjit
?S.
?Dhillon
?
(ICML
?2007
?best
?paper)
suzukake weekend
?reading
?group
?#2
?
2013/04/20
?
?
?紹介者
?:
?matsuda
1
13/04/20
?17:42版

Metric
?Learningとは何か
[1
?
?0
?

?0
?
?1]
[2
?
?0
?

?0
?
?1]
①同クラスの事例間は近いほうが良い
?
②異クラスの事例間は遠いほうが良い
①
②
ユークリッド距離
分類しやすい(???)
距離空間を歪める
マハラノビス距離
2

別の例(Large
?Margin
?Nearest
?Neighbor)
hYp://www.cse.wustl.edu/~kilian/code/page21/page21.html?より
3

問題設定
?? マハラノビス距離を学習する
?
–? 特徴量同士の距離を表す行列を学習する
?
–? カーネルでない事に注意（ただ，相互に関係はある(実は等価???)）
?
?? カーネル
?:
?「データ間」の距離
?
?? マハラノビス
?:
?「特徴量間」の距離
?
?? 何のために？
?
–? 機械学習の前処理として組み込む
?
?? 典型的な例
?:
?k-?‐NN
?
–? semi-?‐supervised
?clustering
?
–? 特徴選択の一般化とも言えそう
?
?? 重み付け +
?特徴量空間での回転
4
Prasanta
?Chandra
?Mahalanobis
?
1893 1972

本論文のContribu(on
?? Metric
?Learning
?を
?LogDet
?Divergence
?の最適化
問題として定式化
?
–? Bregman
?Projec(onという手法に基づく効率的なアル
ゴリズムを導出
?
–? 高速 (
?O(d2)
?d:次元数
?)，おおむね高精度
?
?? カーネル学習との接続
?
–? 実際には等価な問題であることを示す
?
?? 拡張
?(時間の都合上，ちょっと触れるだけ)
?
–? カーネル化
?
–? オンライン化
?
?? Regret
?Boundも示している
5

マハラノビス距離とは
x
?
?:
?データ点を表すベクトル
?
A
?:
?マハラノビス距離行列（正定値行列）
?
Aが単位行列であれば，ユークリッド距離と一致
?
1
?0
?
0
?1
2
?0
?
0
?1
2
?1
?
1
?1
6

制約の表現
S
?
?:
?近いと分かっているデータ点ペアの集合
?
D
?:
?遠いと分かっているデータ点ペアの集合
これらの条件を満たすようなマハラノビス距離行列
?A
?を学習する
7

ユークリッド距離による正則化
?? Metric
?Learningにおける過去の研究において
?
–?ユークリッド距離は多くの場合，そこそこ上手くい
く，ということが知られている
?
–?ユークリッド距離からあまりかけ離れたくはない
?
?? そのため，単位行列(ユークリッド距離)で正則
化をかけたい
?
?? どうやって？
?
A-?‐1
?を共分散行列として持つ正規分布間の
?
KLダイバージェンスを考える
この論文の
?
メインアイディア
8

ユークリッド距離による正則化
p(x;
?A)
?:
?A-?‐1を共分散行列として持つ正規分布(平均は考えない)
単位行列
すると，解くべき最適化問題は以下のようになる
9

LogDet
?divergenceの導入
さきほどの最適化問題は以下のように書ける
制約を満たす解が無い場合もある
?

?＝＞?スラック変数
?ξ
?を導入
?
?:
?式
?(4.5)
?
n
?:
?行列のサイズ
平均が等しい多変量正規分布間のKLダイバージェンス :
?LogDet
?Divergence
xTAx
?=
?tr(AxxT)
?で書き換えてるだけ
10

Bregman
?Projec(onに基づく学習
?? [Kulis+,
?ICML’06]によりカーネル学習で用いられた手
法
?
?? Algorithm
?1はスラック変数を考慮しているため複雑
に見えるが,以下を繰り返しているだけ
?
1.? 制約を一個ピックアップする
?
2.? 制約を満たすように距離行列を修正する
?
計算量：
?

?それぞれの射影に
?O(d2),
?c個の制約を一巡するのにはO(cd2)
?

?関連研究で必要とされていた半正定値計画,
?固有値分解等をとかなくて良い
?

?収束保証はなされていないが，実験的には高速(後述)
11
制約の「方向」
更新幅

Bregman
?Projec(on(イメージ)
制約1
?
d(xi,xj)
?=
?u
制約2
?
d(xi,xj)
?=
?l
β
?：制約を満たす最小の更新幅(閉じた形で求まる)
射影を繰り返すことで，すべての制約を満たすAに収束する※
12
この図は清水さんのスライド hYp://www.r.dl.itc.u-?‐tokyo.ac.jp/study_ml/pukiwiki/index.php?schedule%2F2008-?‐07-?‐24
?にインスパイアされています
制約1を満たす
空間
制約2を満たす
空間
※制約が三つ以上ある場合は，すべての制約を満たす点は一般には存在しない(スラック変数の出番)
ココでmin
?Dld(At,At+1)を担保

カーネル学習との関連
X=
?
x1
x2
x3
x4
d次元
距離行列A
ー
行
列
K
と書けば，見る方向が違うだけで問題は等価
Metric
?Learning
Kernel
?Learning
(Theorem
?1：初等的に証明できる)
両者は等価な計算であるゆえ：
?
高次元少事例(or低次元多事例)
?
の場合は O(min{n,d}2)
?で計算可能
?
[Jain+
?JMLR
?2012]
?
事
例
?
13

拡張（カーネル化/オンライン化）
?? カーネル化 (Φ(?)
?:
?(高次元への)写像関数)
?
?? オンライン化
?
–? Algorithm
?2?（ Regret
?Boundも示されている
?)
?
–? 詳細は割愛
?
線形カーネル
?(K
?=
?I)
学習された(距離行列のもとでの)カーネル
新たなデータ点に対するカーネルは以下の式で計算できる
?(σ:
?A
?–
?I
?の要素)
14
とおけば，Algorithm1がそのまま使える

実験結果（k-?‐NN)
UCI
?Dataset
Cralify
?Dataset
(baseline)
(baseline)
ソフトウェアの自動サポートのための
?
データセット
?
Informa(on
?Gainで20次元に次元削減
分類アルゴリズム：4-?‐NN
?
制約：
?
?

?20
?c2
?ペア
?(
?c
?:
?クラス数
?)
?

?をランダムに選択×5
?trial
15

実験(速度,
?クラスタリング)
HMRF-?‐Kmeans
?:
?[Basu+
?KDD’04]
?

?Must-?‐link,
?Cannnot-?‐link制約を隠れ状態として持つクラスタリング
16

まとめ /
?感想 /
?私見
?? Metric
?Learningを，LogDetダイバージェンスの最適化として定式化
?
–? カーネル学習と等価であることを示した，拡張：カーネル化，オンライン化
?
?? 盛りだくさんの内容！
?
–? カーネル学習と距離学習という，漠然と関係ありそうなものを明確に接続していて爽快
?
–? 要素技術はカーネル学習[Kulis+
?ICML’06]で使われているものの踏襲のようだ
?
?? 私見(間違っている可能性高し！)
?
–? 線形分離できない問題ができるようになるの？?
?
?? →?単なる線形変換なのでならない．適切にスケーリングされてない状況でerror
?rate下げる効果はあるかも
?
–? 前処理せずSVMにかけるのとどっちがいいの？?
?
?? →?多くのケースでだいたい同じくらいらしい(k-?‐NNが異様に効くような状況除く)
?[要出典]
?
–? マハラノビス距離行列A
?の非対角要素(回転)にはどんな意味があるの？?
?
?? →?どうなんでしょう????カーネル行列Kの非対角要素には明らかに意味があるので，考えればわかるかも
?
–? そもそも今さらkNNって????
?
?? →?意外と強いっすよ．メモリに載れば+近傍探索が速ければ
?
–? どういう時に使う？?
?
?? →?教師データが部分的にしか無い，学習されたMetricそのものを他の用途に使いたい状況など
?
–? そもそもそもそも，線形変換が意味を持つ状況が思いつかない???
?
?? →?分類器が非線形な場合(k-?‐NNなど)は意味があるはず．?分類器が線形な場合は???誰か教えてください．
?17

Further
?Reading
?? “Metric
?and
?Kernel
?Learning
?Using
?a
?Linear
?Transforma(on”
?[Jain+,
?
?
JMLR’12]
?
–? 本研究を含んだジャーナル，あんまり読んでない
?
?? “Distance
?Metric
?Learning:
?A
?Comprehensive
?Survey”
?[Yang,
?2006]
?
–? サーベイ論文．ちょっと古いけど，基本的な考え方は分かりそう
?
?? “Learning
?Low-?‐Rank
?Kernel
?Matrices”[Kulis+,
?ICML’06]
?
–? 同チームによるカーネル学習の論文，基本的なアイディアは同じ
?
–? IBM井出さんによる分かりやすい解説スライドあり
?
?? 日本語で読めるもの
?
–? 清水さんのスライド
?
–? イントロ的なところは首都大小町先生による解説もあり
?
–? “計量学習を用いた画像検索エンジンとアニメ顔類似検索v3について”
?
?? かっこいい！
?
?? 自然言語処理への応用例
?
–? 類義語獲得
?[Shimizu+,
?Coling’08]
?
–? Sen(ment
?Analysis
?における Domain
?Adapta(on
?[Dhillton+,
?Coling’12]
?
–? 語義曖昧性解消
?[Sasaki
?and
?Shinnou,
?SEMAPRO’12][佐々木,新納,
?NLP’11]
18

狠狠撸

Information-Theoretic Metric Learning

More Related Content

What's hot (20)

Viewers also liked (13)

Similar to Information-Theoretic Metric Learning (20)

More from Koji Matsuda (19)

Information-Theoretic Metric Learning