Microsoft PowerPoint - Kernel_3_methods_tmp.pptx

Transcription

1 3. さまざまなカーネル法 正定値カーネルによるデータ解析 - カーネル法の基礎と展開 - 福水健次統計数理研究所 / 総合研究大学院大学 統計数理研究所公開講座 0 年 月 3,4 日

2 概要 Kernel PCA の応用 Kernel CCA カーネル正準相関分析 サポートベクターマシンの基礎 カーネル法の方法論 共通する方法 Representer 定理 その他の話題 カーネルの選択 低ランク近似

3 カーネル法のアイデア x x j Space o orgnal data x k, x eature map x x j H k, Feature space RKHS データの非線形特徴 高次モーメントを表現するため, 特徴写像によってデータを特徴空間 RKHS に写像し, 特徴空間で線形のデータ解析アルゴリズムを適用する. 特徴写像 : :, x k, x H k 高次元 無限次元 特徴空間で, 内積の簡単な計算が可能. x, y k x, y カーネルトリック 3

4 特徴写像 正定値カーネルによる高次モーメントの抽出 Example Polynomal kernel: ky, x = yx + d on R 特徴写像 d k u, u d u d a d d d d d u ad u au 基底 {, u, u,..., u d } を用いると, ベクトル成分表示は, a,..., a 高次統計量,,..., d を含む. d d d, ガウスカーネルなど, 他の非線形カーネルでも事情は同様. ただし, カーネル法では成分表示 / 基底展開せずに内積計算が可能. 4

5 概要 Kernel PCA の応用 Kernel CCA カーネル正準相関分析 サポートベクターマシンの基礎 カーネル法の方法論 共通する方法 Representer 定理 その他の話題 カーネルの選択 低ランク近似 5

6 カーネル PCA 復習 特徴写像 目的関数 : 特徴空間での PCA,,,, 目的関数特徴空間での PCA ] Var[, ], Var[ : max ただし 中心化された デタの線形和で解が求まる j j ただし c 中心化された データの線形和で解が求まる 固有値問題 : 中心化グラム行列の固有値分解 c 解 T u u K 第 p 主軸デタ の第主成分 T p p p p p p u c c, データ の第 p 主成分 T p p p u, 6

7 カーネル PCA の応用 Wne データ UCI Machne Learnng Repostory 3 次元 連続値,78データ,3 種類 産地 のワインの化学成分に関する属性データ つの主成分を取った 3 クラスの色は参考に付けたもの,Kernel PCA には用いていない PCA 線形 KPCAGauss, = 3 7

8 KPCAGauss, = KPCAGauss, = KPCAGauss, = 5 8

9 カーネル PCA の雑音除去への応用 カーネル PCA による雑音除去 高次元の空間のなかで d 個の主成分の軸 F, F,..., F d が張る d 次元部分空間へ データ x を射影した点を G x とおく G x に最も近い埋め込み点を探す pre-mageの問題 雑音除去された特徴ベクトル x G x xˆ arg mn x G x x カーネル kx, x を使って表せる

10 USPS 手書き数字データベース 6x6 画素 56 次元 79 データ 元の画像 データとしては使用していない ノイズつきの画像 ノイズ除去された画像 lnear PCA ノイズ除去された画像 kernel PCA, Gaussカーネル Matlab stprtool by V. Franc により作成 0

11 カーネル PCA の特徴 非線形な方向でのデータのばらつきが扱える. max Var[ ] 結果はカーネルの選び方に依存するので, 解釈には注意が必要 ガウスカーネルの分散パラメータなど どうやって選ぶか? 必ずしも明確でない, 目的に依存 前処理として使われることが多い後の処理の結果を改良するための非線形特徴抽出例えば カーネル PCA + 識別機 SVM によるクラス識別問題 最終的な識別の正答率を向上させるカーネルがよい Cross-Valdatonの適用可能

12 概要 Kernel PCA の応用 Kernel CCA カーネル正準相関分析 サポートベクターマシンの基礎 カーネル法の方法論 共通する方法 Representer 定理 その他の話題 カーネルの選択 低ランク近似

13 正準相関分析 正準相関分析 Canoncal Correlaton Analyss, CCA CCA 種類の多次元データの相関を探る m 次元データ,, n 次元データ,, を a, を b 方向に射影したときに相関を最大にする a,b を求める 正準相関 T T T T a b max Corr[ a, b ] max m ar m ar T T n b n a b R max m ar br n T T av b T av a bv b br ただし V T j j など a a T b T b 3

14 T T T max av b subj. to av abv b Lagrange 乗数法 T T T max a V b a V a bv b 一般化固有値問題 O V a V O a V O b O V b = = ] 最大固有値, 固有ベクトルを求めればよい 4

15 カーネル正準相関分析 カーネル CCA 赤穂, 000, Melzer et al. 00 Data:,,...,,., : arbtrary varables takng values n and resp.. 特徴写像 : k H A l CCA d,, : k H,, : k H Apply CCA on,..., and,...,. g g,,, max Corr, max, g g Corr g,, max g,,g g,, g lag sky, x x y y g g 5

16 カーネルPCA 同様, g としてよい. max T K K T T K K カーネルトリック R K, K R 実は ll-posed. K R {0} K K : 中心化 グラム行列 R であれば *, 常に正準相関 =. K 正則化 max, g,,, g H, g g H 一般化固有値問題として解ける O K K K I O K K O O K I * RT: 行列 T の像空間 6

17 カーネル CCA の実験例 ガウスカーネル x y gy x gy x x y 7

18 Kernel CCA の性質 複数の固有ベクトルも考えられる 第, 第 3,... 固有ベクトル も考えられる. もとのデータが 次元でも! 結果はカーネルや正則化係数 に依存する. 正準相関の値によって相関の大小を解釈するのは難しい 正則化のために正規化されない カーネル / 正則化係数の選択 : Cross-valdaton が用いられる場合もある. 他に提案されている方法もある Hardoon et al 004. See later.. が十分ゆっくり 0 に近づく場合, 一致性があることが知られている. Fukumzu et al

19 Kernel CCA の画像検索への応用 Idea: d 個の固有ベクトル,..., d と g,..., g d を と の依存性が最も強く表れている特徴空間とみなす. : mage, : text extracted rom the same webpage. : sky, Phoenx, harbor,... 方法 x kernel CCA によりd 個の固有ベクトル,..., d と g,..., g d を求める. g, y d d 各画像 に対して特徴ベクトル, x, g R を計算 y. p p x y d d テキスト new に対して特徴ベクトル g p, new R d, x を計算 gd, y p arg max * T なる を返す. * lag sky, k 9

20 例 テキストからの画像検索例 : heght: 6- weght: 35 lbs poston: orward born: september 8, 968, splt, croata college: none Hardoon et al. eural Computaton t 004. テキスト bag-o-words kernel 単語の頻度分布 を用いる. 正則化係数 の決め方 : arg max R : KCCAの固有値分布, R : と をランダム化したときの KCCA の固有値分布 0

21 概要 Kernel PCA の応用 Kernel CCA カーネル正準相関分析 サポートベクターマシンの基礎 カーネル法の方法論 共通する方法 Representer 定理 その他の話題 カーネルの選択 低ランク近似

22 クラス識別問題 データ,,,, 線形識別 m R {, } クラスのクラスラベル 線形識別関数 x x 0 y = クラス と判定 w x = a T w x+ b w x 0 y = - クラス と判定 w = a,b 問題 : 未知の x に対しても正しく答えられるように w x を構成せよ y = w x w x < 0 w x 0

23 マージン最大化 線形のサポートベクターマシン 仮定 : データは線形分離可能 学習データを分類する線形識別関数は無数にある. マージンを最大化する方向を選ぶ a マージン ベクトル a の方向で測った, データの クラス間の距離. 0 識別関数は, つの境界の真中 - -4 サポートベクター マージン 3

24 マージンの計算 a,b を正の定数倍しても識別境界は不変なので, スケールを一つ決める T mn a b = のとき T max a b = - のとき 8 マージン = a

25 サポートベクターマシン : ハードマージン マージン最大化基準による識別関数 max a, b T a b, subject to T a a b, サポートベクターマシン ハードマージン mn a a, b subject to T a b 次最適化 Quadratc Program, QP 線形制約のもとでの 次関数の最小化. 凸最適化 : 局所最適解の問題がない. 有効なソフトウエアの利用が可能 5

26 サポートベクターマシン : ソフトマージン ソフトマージン 線形識別可能の仮定は強すぎるので, 少し弱めるハードな制約条件ソフトな制約条件 T a b T a b 0 サポートベクターマシン ソフトマージン mn a, b, a a T C subject to 0 b 上の問題もQP. C はユーザが決める必要がある.Cross-valdaton がよく使われる. 6

27 SVM と正則化 ソフトマージン SVM は以下の正則化問題と同値 C = / mn a, b T a b a 損失関数 正則化項 ただし z + = maxz, 0 - z + 損失関数 : ヒンジ損失 x, y y x [Exercse] ソフトマージン SVM と上の正則化の同値性を確認せよ. 7

28 カーネル化された SVM SVM のカーネル化 kernelzaton Data:,,,, : 任意の集合 に値を持つ. {+, -} 正定値カーネル k による特徴ベクトル,,,, RKHS H における線形識別関数 h, x b sgn h x b x sgn h H 非線形関数 8

29 マージン最大化 mn h h, b, H C subject to h, b 0 正則化問題として表わすと mn h, b 最適な h は次の形 h x h, b h w w k x, データ { } の張る H の部分空間を H 0, 直交補空間を H とするとき, h = h 0 + h の分解で, 正則化表現第 項は h 0 のみに依存. 第 項は h = h 0 + h により h = 0のときが最適. H Gram 行列表現 T h H w Kw, h Kw. K k,., [Exercse] Check them. j j 9

30 サポートベクターマシン カーネル化 mn w, b, w T Kw C subject to Kw 0 b この最適化も QP. 標準的ソルバーが使える. 実際には, 双対問題を考えることが多い. 日目で述べる 係数 C とカーネル あるいはカーネル内のパラメータ の選択は, cross-valdaton によることが多い. 30

31 補足 : 正則化 例 リッジ回帰 : mn SVM: mn b, H HH b H H が多様な関数をとりえると, 第 項目 損失 だけでは解が一意でない. 正則化項 第 項目 の付加 正則化項は滑らかさに関係するものが多い 平滑化 3

32 SVM の Java applet SVM デモ 3

33 SVM の文字認識への応用 MIST: Handwrtten dgt recognton 8 x 8 bnary pxels tranng data 0000 test data Some results k 0PCA RBF Leet-4 Leet-5 SVM RS-SVM +Quad +Lnear poly4 poly5 Test Err % LeCun et al

34 概要 Kernel PCA の応用 Kernel CCA カーネル正準相関分析 サポートベクターマシンの基礎 カーネル法の方法論 共通する方法 Representer 定理 その他の話題 カーネルの選択 低ランク近似 34

35 カーネル法導出に共通する構造 正定値カーネルの定める特徴写像によるデータの変換,,,, 高次モーメント / 非線形性を抽出 特徴ベクトルに RKHS 上で 線形の アルゴリズムを適用. 目的関数の最適解は特徴ベクトルの線形和 x a で与えられることが多い. 目的関数は,Gram 行列で表現される. その最適化は各アルゴリズムによって異なる. KPCA,KCCA KCCA 固有値問題 ; SVMQP いったんGram 行列が得られれば, 後はデータサイズ に依る計算量 - 元の空間の次元などに依存しない. 高次元データに有利. 35

36 正則化の問題 復習 Representer Theorem リッジ回帰 mn H H SVM mn b, b 一般化された問題 k: 正定値カーネル, H : k により定まる再生核ヒルベルト空間ルト空間 x,, x, y,, y : データ 固定 h x,, h d x : 固定された関数 SVM の定数 b など H * mn L H d b R { },{ }, d x y x b h x H 36

37 Representer Theorem 正則化項の関数 は,[0, 上の単調増加関数とする. H span{ k, x,, k, x } {k, x } の張る 次元部分空間 * の解 は H の中にある. すなわち の形で探してよい. x k x, x d { x},{ y}, x b h x H d mn L H b R d T mn L { x},{ y}, K b h x K j j j d R b R K = kx,x j : グラム行列 H 無限次元 上の最適化が 次元の最適化に還元できる 37

38 Representer theorem の証明 Representer theorem の証明, },{ } { mn H d x h b x y x L H H H 直交分解 } { } { H y 0,, x k,,,,,, x x k x k x k x L の値はだけで決まる H H H の値はが有利 =0 の値はが有利 =0 H に最適解がある 証明終 38

39 概要 Kernel PCA の応用 Kernel CCA カーネル正準相関分析 サポートベクターマシンの基礎 カーネル法の方法論 共通する方法 Representer 定理 その他の話題 カーネルの選択 低ランク近似 39

40 カーネルの選択 How to choose / desgn a kernel? 問題の構造に適したカーネルを用いるべし 構造化データ : 日目 教師付き学習 e.g. SVM cross-valdaton. 教師無し学習 e.g. g kernel PCA, kernel CCA 理論的に裏付けのある方法はほとんど無いのが現状. Suggeston: 関連する教師付学習を作ってCVを使う. Gaussan kernel に対する heurstcs med{ j} カーネル学習 Multple kernel learnng MKL: M a j k x, y c k x, y M c, 0 a a a a ca の形でカーネルも最適化する. 計算がハード 40

41 補足 : 教師有り学習と教師無し学習 教師有り学習 Supervsed learnng Data or nput and output are prepared. s regarded as supervsor or teacher o the learnng. e.g. classcaton, regresson, predcton. 教師無し学習 Unsupervsed learnng There s no teachng data. e.g. PCA, CCA, clusterng. 半教師有り学習 Semsupervsed learnng, の訓練データと のテストデータが事前に与えられている. 4

42 グラム行列の低ランク近似 カーネル法 : Gram 行列を求めてしまえば, データ数 に依る計算量 -- もとの空間の次元などに依らない. 高次元データに有利. 逆に, データ数 が大きいと,Gram 行列 K に関する演算は困難. 逆行列, 固有値分解は O 3 の演算量必要 低ランク近似 : T K RR R: x r 行列 r << K R R T 4

43 計算量の大きな削減が可能. 例 kernel rdge regresson, x I RR x I K T T T k k x I RR x I K k k, x R I R R R x T r T T T k k 演算量 Or + r 3. 低ランク近似の つの方法 : 低ランク近似の つの方法 : Incomplete Cholesky decomposton: sample complextyor, space complexty Or. yström approxmaton: random samplng + egendecomposton. G 行列は多くの微小な固有値を持ことが多く低ランク近似の方 Gram 行列は, 多くの微小な固有値を持つことが多く, 低ランク近似の方法が有効. 43

44 その他のカーネル法 カーネル Fsher 判別分析 kernel FDA Mka et al. 999 カーネルロジスティック回帰 Roth 00, Zhu&Haste 005 カーネル Partal Least Squarekernel PLSRospal&Trejo 00 カーネル K-means クラスタリング Dhllon et al 004 SVM の仲間 Support vector regresson SVR, Vapnk 995 -SVM Schölkop et al 000 one-class SVM Schölkop et al 00 44

45 セクション 3 のまとめ さまざまな線形解析手法のカーネル化が可能 効率的な内積計算 Kernel PCA, SVM, kernel CCA, etc. 最適解は多くの場合, 特徴ベクトルの線形和 x a で与えられる representer theorem. 問題は, データサイズ のGram 行列によって表現される. 高次元で, 中程度までのデータサイズに適している. データサイズが大きい場合には, 低ランク近似が有効. 正定値カーネルさえ定義されれば, 任意のデータ型に適用可能. structured non-vectoral data, such as graphs, strngs, etc 45

46 参考文献 赤穂. 000 カーネル正準相関分析. 第 3 回情報論的学習理論ワークショップ予稿集 IBIS000. Bach, F.R. and M.I. Jordan. 00 Kernel ndependent d component analyss. Journal o Machne Learnng Research, 3: 48. Dhllon, I. S.,. Guan, and B. Kuls. 004 Kernel k-means, spectral clusterng and normalzed cuts. Proc. 0th ACM SIGKDD Intern. Con. Knowledge Dscovery and Data Mnng KDD, Fukumzu, K., F.R. Bach, and A. Gretton. 007 Statstcal consstency o kernel canoncal correlaton analyss. Journal o Machne Learnng Research, 8: Hardoon, D.R., S. Szedmak, and J. Shawe-Taylor. 004 Canoncal correlaton analyss: An overvew wth applcaton to learnng methods. eural Computaton, 6: LeCun,., L. Bottou,. Bengo, and P. Haner. 00 Gradent-based learnng appled to document recognton. In Smon Haykn and Bart Kosko, eds, Intellgent Sgnal Processng, IEEE Press. 46

47 Melzer, T., M. Reter, and H. Bscho. 00 onlnear eature extracton usng generalzed canoncal correlaton analyss. Proc. Intern. Con..Artcal eural etworks ICA, Mka, S., G. Rätsch, J. Weston, B. Schölkop, and K.-R. Müller. 999 Fsher dscrmnant analyss wth kernels. In.-H. Hu, J. Larsen, E. Wlson, and S. Douglas, edts, eural etworks or Sgnal Processng, volume I, IEEE. Murphy P.M. and D.W. Aha. 994 UCI repostory o machne learnng databases. Tech report, UC Irvne, Dept Inormaton and Computer Scence. html Rospal, R. and L.J. Trejo. 00 Kernel partal least squares regresson n reproducng kernel Hlbert space. Journal o Machne Learnng Research, : Roth, V. Probablstc dscrmnatve kernel classers or mult-class problems. In Pattern Recognton: Proc. 3rd DAGM Symposum, Sprnger, 00. Schölkop, B., A. Smola, and K-R. Müller. 998 onlnear component analyss as a kernel egenvalue problem. eural Computaton, 0:

48 Schölkop, B., A. Smola, R.C. Wllamson, and P.L. Bartlett. 000 ew support vector algorthms. eural Computaton, 5: Schölkop, B., J.C. Platt, J. Shawe-Taylor, R.C. Wllamson, and AJS A.J.Smola. 00 Estmatng the support o a hgh-dmensonal dstrbuton. eural Computaton, 37: Vapnk, V.. The ature o Statstcal Learnng Theory. Sprnger