Tokyo Research Laboratory
“Regression on Manifolds using Kernel
Dimension Reduction”
by Jens Nilsson, Fei Sha, and Michael I. Jordan
IBM東京基礎研究所
井手剛
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
概要 ── 次元削減モノ。教師あり次元削減と、教師なし次元削減を組み合わせた
点に新規性を主張。
 次元削減には2流派ある



教師なし
• データXの分布(or 多様体)をうまく表すような座標を求める
• PCA、Isomap、Laplacian eigenmap、LLE、...
教師あり
• ラベル情報と矛盾しない写像を求める
• FDA、LFDA、その他
両者の組み合わせ
• SELF (semi-supervised LFDA)
- M. Sugiyama et al., Technical report TR07-0006,
http://www.cs.titech.ac.jp/~tr/reports/2007/TR07-0006.pdf
- ラベルが分かっているものについてはLFDA、そうでないものはPCA
• ほか
 この仕事は次の二つの次元削減手法の組み合わせ


Page 2
教師なし: Laplacian eigenmap
教師あり: 福水さんのカーネル次元削減
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
目次
 カーネル次元削減とは
 Laplacian eigenmapとは
 どう組み合わせるのか
 実験結果は?
Page 3
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
カーネル次元削減とは
Page 4
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
「十分な次元削減」(sufficient dimension reduction; SDR)。カーネル次元削
減はSDRの一種。回帰関係を表すために最も「かけがえのない」部分空間を探す。
 SDRは教師あり次元削減の一種

確率変数XとYが、何か強い結びつきを持つと仮定
• 回帰直線の周りにばらつくとか
 直交射影の行列Bを使って、Xを狭めてみる


Z = BTX
Zが動く範囲をSとする
 SDRの問いかけ: 「もしSを失ったら、どれだけYとXは無関係になってしまうだろうか?」

「Sを失った結果、YとXが無関係になってしまう」 = 「Sはかけがえのないもの」
 Zを与えた時にYとXが条件付き独立になってしまうように、Bを選べばよい
Page 5
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
条件付き独立性の成立を、条件付き共分散行列の等式に帰着させる
 「条件付き独立性を言うためには、XとYの同時分布がいるのでは?(問題を簡単にしてな
いのでは)?」という心配は要らない

確率モデルの仮定が要らぬ、というのがSDRおよびKDRのキモ。
 論文の定理1(の半分):

条件付き独立性は、条件付き共分散行列の等式と同値

つまり、 この等式を満たすようなB(射影行列)を求めればよい
• でもそれを直接やるのは難しい
Page 6
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
等式を満たすのをあきらめて、「できる限り最善な」Bを求める
 条件付き共分散行列についての性質:


「制約をゆるめるとばらつきの余地は大きい」
「制約が厳しいとばらつきの余地は小さい」
直感的には、
Zを与えた時
のYのばらつ
き
 結局、
をBについて「最小化」すればいい
 残る問題


Page 7
Z = BTX を使って
をBについてパラメトライズするなんてできるのか
行列もしくは演算子の大きさの尺度をどう測るのか
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
条件付き共分散行列を、条件なしのものを使って「展開」する
 条件付き共分散行列(演算子)は、条件なしのものを使って書ける

• Xとありますが、Zのことです
 ガウシアンを条件付けた時の共分散と同じ形をしているが、これは分布によらずに一般
に成り立つ

Page 8
証明は福水さんの論文たちに書いてある
• Fukumizu et al. JMLR 2004
• Fukumizu et al. 2006
• 数学的にハイレベルだが、証明をフォローすることはなんとか可能
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
条件なしの共分散行列をグラム行列で表す
 条件付き共分散行列(演算子)は、条件なしのものを使って書ける

 単純作業でグラム行列(中心化しておく)に書き換えることができる

Page 9
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
KDRの目的関数の完成
条件付き共分散行列の大きさはTraceで測ることにする
 単純作業でグラム行列(中心化しておく)に書き換えることができる

 さらに簡単化する

ノリ的には次のような式を使ったと思えばいい
 行列の大きさはトレースで測ることにする
 結局、条件付き独立性の条件は下記に帰着される
Page 10
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
Laplacian eigenmapとは
Page 11
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
原論文から(1/2): M. Belkin and P. Niyogi, "Laplacian eigenmaps and
spectral techniques for embedding and clustering", NIPS 2001
 元の座標x1、x2、...から、新しい座標y1、...を求めたい。その時の目的関数

つまり、「集団移住した後でも近所のつながりを大切にする」
 2乗誤差の目的関数はグラフ・ラプラシアンを使って書き直せる

要するにこれを最小化すればいい
Page 12
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
原論文から(2/2): 一般化固有値問題として解ける
 下記の最適化問題を解く


条件1: スケーリングの任意性を省く
条件2: ゼロ固有値の解を省く
 解は固有値最低のものからM個の固有ベクトル

ただし、ゼロ固有値(最小)は省く
Page 13
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
どう組み合わせるのか
Page 14
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
基本的に、Laplacian eigenmap で次元削減されたデータにKDRを行うだけ
 Laplacian eigenmapでもとの座標xiを、M次元の座標に変換


M本の固有ベクトルから作ったM次元データのデータ行列をUとする
ui が新座標
 そのデータUから、KDRにより第2弾の次元削減写像を求める。

d次元
Φui が新々座標

解くべきなのは下記

非線形、非凸。
射影勾配法で解く。
Page 15
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
実験結果は?
Page 16
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
実験結果1
地表面温度
 もともとは2次元の問題

温度Y vs 地表の位置X
 1段目での次元削減

M=100
 2段目の次元削減

d=1
 きれいな線形相関
 次元「削減」としてはつまらないが、
削減した座標により再現誤差を描い
てみると、異常気象が分かる、らしい
Page 17
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
実験結果2
スノーマンの画像を回転してみる
 本当の自由度は4


回転角と傾き角、ずらし量(タテヨコ)
画像は 110×80、1000枚
 回転角(Y) vs ピクセル強度(X)、のような回帰
関係を設定したらしい。
Page 18
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
感想
Page 19
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
Tokyo Research Laboratory
感想
 KDRは普通使われるような誤差基準とはちょっと毛色が変わっていて面白い

福水さんの論文についてはもうちょっと勉強の必要あり
 この論文の組み合わせ方には、あまり感銘を受けなかった。

ただ福水さん論文に寄りかかっているだけ、という感じがした。
 実験結果も、興味深いのか深くないのかよくわからなかった。
Page 20
| 2007/08/20 | ICML [email protected]
© Copyright IBM Corporation 2007
ダウンロード

発表資料