ＩＣＭＬ２００６勉強会 ２００６年７月２９日 局所フィッシャー判別分析 東京工業大学　計算工学専攻 杉山　将

次元削減 次元の呪い：高次元データは扱いにくい 次元数を削減したい 本発表では以下の設定を考える 線形次元削減： 教師付き次元削減：

クラス内多峰性 あるクラスのデータが多峰性である クラス１（青） クラス２（赤） 医療データ： ホルモンアンバランス（多い・少ない）ｖｓ．正常 数字認識： 偶数（０，２，４，６，８）ｖｓ．奇数（１，３，５，７，９） 多クラス分類： 一クラスｖｓ．残りのクラス (one vs. rest)

本研究の目的 多峰性のデータをうまく埋め込みたい！ クラス間分離性を最大化 クラス内多峰性を保存 クラス間分離性：ＯＫ クラス内多峰性：ＮＧ クラス間分離性：ＮＧ クラス内多峰性：ＯＫ クラス間分離性：ＯＫ クラス内多峰性：ＯＫ

フィッシャー判別分析 (FDA) クラス内散布行列： クラス間散布行列： ＦＤＡ規準： クラス内散布を小さく クラス間散布の度合いを大きく Fisher (1936)

FDAの解釈 ：クラス　　の標本数 Pair-wise表現： 同じクラスの標本は近くに埋め込む 違うクラスの標本は遠くに埋め込む ：全標本数

ＦＤＡの例 FDA はクラス内多峰性を考慮していない 注意： のため，ＦＤＡはＣ－１個 の特徴しか取り出せない 単純 ラベル混合クラスタ 近く 近く 近く 遠く 遠く 遠く FDA はクラス内多峰性を考慮していない 注意：　　　　　　　　　　　のため，ＦＤＡはＣ－１個 　の特徴しか取り出せない ：クラス数

局所性保存射影(LPP) 局所性行列： 類似度行列： 例） LPP規準： 元の空間で近くにある標本は近くに埋め込む 拘束条件は を避けるため He & Niyogi (NIPS2003) 局所性行列： 類似度行列： 例） LPP規準： 元の空間で近くにある標本は近くに埋め込む 拘束条件は　　　　　　を避けるため

ＬＰＰの例 単純 ラベル混合クラスタ 多峰性 近く 近く 近く LPPはクラス間分離性を考慮していない （教師無し）

本研究のアプローチ ＦＤＡとＬＰＰを組み合わせる！ 同じクラスの近くの標本は近くに埋め込む 同じクラスでも遠くの標本は近づけない 異なるクラスの標本は遠くに埋め込む 遠く 近く 条件無し

局所フィッシャー判別分析（ＬＦＤＡ） 局所クラス内散布行列： 局所クラス間散布行列：

埋め込み行列の求め方 ＬＦＤＡ規準はＦＤＡ規準と同じ形式なので，一般化固有値問題を解くだけで埋め込み行列を求めることができる！

ＬＦＤＡは３種類全てのデータに対してうまくいく！ ＬＦＤＡの例 単純 ラベル混合クラスタ 多峰性 ＬＦＤＡは３種類全てのデータに対してうまくいく！ 注意：通常は　　　　　　　　　　が成り立つため， 　　　　ＬＦＤＡではＣ個以上の特徴が取り出せる

Goldberger, Roweis, Hinton & Salakhutdinov (NIPS2004) 近傍成分分析（ＮＣＡ） Goldberger, Roweis, Hinton & Salakhutdinov (NIPS2004) 確率的最近傍分類機のクロスバリデーションエラーを最小化する 求まる埋め込みは分離性が高い ＮＣＡは非凸最適化問題を含む 局所最適解が存在 解の解析形は知られていない 遅い繰り返しアルゴリズム ＬＦＤＡは最適解が解析的に求まる

Globerson & Roweis (NIPS2005) 最大縮退座標系学習（ＭＣＭＬ） Globerson & Roweis (NIPS2005) 考え方はＦＤＡと同様 同じクラスの標本は近くに（一点に） 異なるクラスの標本は遠くに ＭＣＭＬは非凸最適化問題を含む しかし凸近似が存在する 近似解しか求まらない 近似解の解析形は知られていない 遅い繰り返しアルゴリズム

実験 ＵＣＩデータの可視化： 元のデータから３つのクラスを取り出す その内２つのクラスをくっつける クラス１（青） クラス２（赤） Letter recognition (D=16) Segment (D=18) Thyroid disease (D=5) Iris (D=4) 元のデータから３つのクラスを取り出す その内２つのクラスをくっつける クラス１（青） クラス２（赤）

実験結果のまとめ クラス間分離性ＯＫ，クラス内多峰性ＯＫ クラス間分離性ＯＫ，クラス内多峰性ＮＧ クラス間分離性ＮＧ，クラス内多峰性ＯＫ Lett Segm Thyr Iris コメント FDA 非多峰性 LPP 非分離性 LFDA NCA 遅い，局所解 MCML 遅い，非多峰性 クラス間分離性ＯＫ，クラス内多峰性ＯＫ クラス間分離性ＯＫ，クラス内多峰性ＮＧ クラス間分離性ＮＧ，クラス内多峰性ＯＫ

Letter Recognition FDA LPP LFDA NCA MCML 青 vs. 赤

Segment FDA LPP LFDA NCA MCML 青 vs. 赤

Thyroid Disease FDA LPP LFDA NCA MCML 青 vs. 赤

Iris FDA LPP LFDA NCA MCML 青 vs. 赤

Globerson & Roweis (NIPS2005) カーネル化 ＬＦＤＡはカーネルを使うことにより非線形に拡張できる FDA: Kernel FDA LPP: Laplacian eigenmap MCML: Kernel MCML NCA: できない？ Mika et al. (NNSP1999) Belkin & Niyogi (NIPS2001) Globerson & Roweis (NIPS2005)

Zelnik-Manor & Perona (NIPS2004) 結論 ＬＦＤＡはＦＤＡとＬＰＰの良い所を組み合わせる ＬＦＤＡは多峰性データの埋め込みに向いている 埋め込み行列が解析的に求まるため計算が速い ＬＦＤＡは類似度行列を定める必要がある 本発表では，局所スケーリング法を用いて類似度行列を定めた． 局所スケーリング法はチューニングパラメータを含まないので使いやすいが，有効性の理論的な裏づけはない． Zelnik-Manor & Perona (NIPS2004)