metric-learning

Metric Learning Overview
清水伸幸
図書館電子化部門
東京大学情報基盤センター
1
Metric Learning

マハラノビス距離を学習する

Aが単位行列の場合、ユークリッド距離と同じ
満たさなければならない、いくつかの点の間の距離が訓練デー
タとして与えられる

半正定値行列Aの値を推定する

2
マハラノビス距離

ユークリッド距離
距離１
マハラノビス距離
距離１
3
Dimension Reduction
& Metric Learning

Dimension Reduction / Linear Manifold
Learning はPを学習する.



Principal Component Analysis (PCA), Locality
Preserving Projections (LPP)など
したがって両者の目的は似ている
PまたはAを学習する際の制約が違う
4
Outline


ここではDimension Reduction は扱わない。
主に下記の手法を解説する。



Distance metric learning, with application to
clustering with side-information
Relevant Components Analysis (RCA)
Neighborhood Component Analysis (NCA)

拡張



Regularized NCA
Maximum-Margin Nearest Neighbor (LMNN)
Information Theoretic Metric Learning (ITML)
5
Distance metric learning with
side-information

Distance metric learning, with application to
clustering with side-information



Eric P. Xing, Andrew Y. Ng, Michael I. Jordan and
Stuart Russell
NIPS 2002
単純に近くなるべきものを近づけるよう最適化
6
Equivalent Problem

Objective



２乗がある場所に注意
両方とも２乗してしまうとAがいつもランク１になる
Equivalent Problem
7
Algorithm

Take a gradient step to optimize g(.)

Repeatedly project A to
8
つづき

最初のProjection



Quadratic Programmingで、線形の制約
次元数の２乗
で解ける
二つ目のProjection

Aを固有値分解して、

負の固有値を０にする
9
Outline

主に下記の手法を解説する。



Distance metric learning, with application to
clustering with side-information
Relevant Components Analysis (RCA)
Neighborhood Component Analysis (NCA)

拡張



Regularized NCA
Maximum-Margin Nearest Neighbor (LMNN)
Information Theoretic Metric Learning (ITML)
10
Relevant Components
Analysis (RCA)

Learning Distance Functions using
Equivalence Relations


A. Bar-Hillel, T. Hertz, N. Shental, and D.
Weinshall.
ICML 2003
 Relevant Component Analysis (RCA) is a method
that seeks to identify and down-scale global
unwanted variability within the data.
 Finds global linear transformation which assigns
large weights to “relevant dimensions" and low
weights to “irrelevant dimensions.”
11
Chunklet


We define a chunklet as a subset of points that
are known to belong to the same (although
unknown) class; chunklets are obtained from
equivalence relations by applying a transitive
closure.
Transitive Closure of S.
12
Algorithm
13
Figure
14
解釈 Maximum Likelihood
15
RCA minimizes inner class
distances

詳しくは論文を参照

Information theoretic な解釈などもある。
16
17
Outline

主に下記の手法を解説する。



Distance metric learning, with application to
clustering with side-information
Relevant Components Analysis (RCA)
Neighborhood Component Analysis (NCA)

拡張



Regularized NCA
Maximum-Margin Nearest Neighbor (LMNN)
Information Theoretic Metric Learning (ITML)
18
Neighborhood Component
Analysis

Neighborhood Component Analysis (NCA)



Jacob Goldberger, Sam Roweis, Geoff Hinton,
and Ruslan Salakhutdinov
NIPS 2004
Motivation

To optimize the expected leave-one-out
classification error of kNN classifier on the
training data
19
K-Nearest Neighbor

テストデータの点のクラスを、その点に近い教師
データのクラスの多数決で決める手法
20
Soft Neighbor Assignments

学習対象はA

Soft neighbor assignments of kNN

Probability that i-th point is correctly
classified
21
Objective of NCA

The expected number of points correctly
classified

The objective is to maximize the above
objective using a gradient based optimizer
such as conjugate gradients.
Not convex

22
Gradient

The objective

Let
Differentiate f(.)

Reorder

23
Other options

Maximize f(A)
= Minimize the L1 norm between the true class
distribution (having probability one on the true class)
and the stochastic class distribution induced by pij via
A.

L1の代わりに KL divergence を使ってもよい


Gradient of g(.)
Low Rank Distance Metric Learning もできる。
24
結果
25
Outline

主に下記の手法を解説する。



Distance metric learning, with application to
clustering with side-information
Relevant Components Analysis (RCA)
Neighborhood Component Analysis (NCA)

拡張



Regularized NCA
Maximum-Margin Nearest Neighbor (LMNN)
Information Theoretic Metric Learning (ITML)
26
Information Theoretic Metric
Learning (ITML)

Learning Low-rank Kernel Matrices.



Information Theoretic Metric Learning



Kulis, B., Sustik, M., & Dhillon, I. S.
ICML 2006
Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra
and Inderjit S. Dhillon
ICML 2007 Best Student Paper
Structured Metric Learning for High-Dimensional
Problems


J. Davis and I. S. Dhillon
KDD 2008
27
ITML

ほぼ同じアルゴリズムに別な解釈を与えて３本
論文を書いた感じ

一つ目はLow Rank Kernel Matrices



二つ目はMetric Learning


ここですでに学習方法の妥当性は説明済み
LogDet Divergenceだと学習が簡単
ガウス分布にマップしてやればLogDet Divergenceがで
てくるから同じ学習方法でよい
三つ目は次元数が大きい時、半正定値行列Aの一部
を学習した場合の解釈

やはり同じ学習方法でよい
28
問題定義

マトリックスＡについての事前知識がある場合


多変量ガウス分布


A がA0 に近くなるよう正則化
マハラノビス距離と多変量ガウス分布には、1 対 1の対
応が存在する
KLダイバージェンスを用いて問題定義ができる
29
Objective



と、 x j のペアが類似集合Sに含まれれば
、二つの距離は u 以下
非類似集合Dに含まれれば、距離は l 以上
以上の制約を満たしつつ、最もユークリッド距離
に近いマハラノビス距離を見つける
xi
30
このObjectiveは何なのか？

LogDet Divergence

ガウス分布のKL Divergenceは mean が両方と
も零ならLogDet Divergence と同じ
31

新しいObjective

A,A0の位置が逆になったことに注意


これをBregman Projection を繰り返して解く
一番最初の論文、XingのDistance metric learning with
side-informationに似ている。
32
Bregman Projections
Constraint 1
Constraint 2

このプロジェクションがBregman Divergence で一番
近い点
33
Cyclic Bregman Projections



Objective f(A) =
Constraint の一つ
を書きなおしてEquality Constraint にする。
tr( At 1 X i )  bi
次の更新式を合わせて、αについて解く
f ( At 1 )  f ( At )  X iT

この式はSherman-Morrison inverse formulaで解け
る

α について解ければそのまま更新式になる。
34

3.6, 3.7 は、Equality ConstraintをInequality に直したため。
35
ITML の拡張

high-dimensional identity plus low-rank (HDILR )
metric learning

Dimensionが大きいとパラメタが多すぎて扱えないため
36
新たな制約

A－１のをUを使ってProjectがしてから、元の世
界に戻しても、同じ行列になるようなAを学習し
たい。

しかし、解いていくと、元々の更新式はこの制約
を満たしている。
37
HDILR

普通にUで次元削減してAを学習してから
Identityに足せばOK.
38
Uの選び方
39
結果
40
終りに

次元削減も含めた距離学習のサーベイ

http://www.cse.msu.edu/~yangliu1/distlearn.htm
41

Download Report