カーネル法

Transcription

1 講義 1: カーネル法 産業技術総合研究所津田宏治 1

2 産業技術総合研究所 ( 産総研 ) 産業技術分野におけるさまざまな研究開発を総合的に行う経済産業省所管の研究組織である ライフサイエンス 情報 通信 環境 エネルギー ナノテク 材料 製造 地質 海洋 標準 計測 の 6 分野を主軸に 日本の産業のほぼ全分野を網羅している 陣容は 研究職を中心とする常勤職員約 2500 名 事務系職員約 700 名に加え 企業 大学 外部研究機関等から約 5200 人の外来研究者を受け入れている (Wikipedia) 2

3 生命情報工学研究センター 東京 お台場 生命情報工学研究センターでは ゲノム情報 生体高分子の構造と機能 細胞内ネットワークを工学的な観点から総合的に解析し 個別技術の統合による実用的 応用志向の研究開発により産業技術に貢献することを目標とします 生物学データを処理する技術を開発中 3

4 津田宏治 : 経歴 1998 京大で博士号取得 旧電子技術総合研究所入所 2000 ドイツ GMD FIRST で在外研究 2001 産総研 CBRC に配属 , ドイツ マックスプランク研究所で研究 2010 ERATO 湊プロジェクトチームリーダ 2011 北海道大学客員教授 4

5 5

6 講義の構成 パターン認識カーネル法の紹介最適化理論の復習サポートベクターマシン化学構造の分類 : グラフカーネル 6

7 パターン認識 対象を識別するルールを訓練データより 自動的に取得する 二クラス分類 : 識別関数 f(x) 訓練データテストデータ :X Negative Positive 7

8 ベクトル表現 各対象を 同次元のベクトルで表現する 識別関数は 特徴空間上に定義される Feature Space 8

9 線形 vs 非線形 Feature Space 線形識別 計算が簡単 多くのデータに適用 非線形識別 精度が高い 9

10 非線形識別を線形識別器を用いて 行う 元の空間 ( 入力空間 ) を 非線形に写像 し 写像先 ( 特徴空間 ) で線形識別 どのように写像を定めるかは難しい問題 10

11 カーネル法 どのように写像を定めるかは難しい問題 写像を類似度関数 ( カーネル関数 ) に基づいて決める 例 : ガウシアンカーネル 11

12 カーネルと射影の関係 カーネル関数が 正定値 なら が成り立つような写像が存在 12

13 カーネルトリック 特徴空間における重要な量が 写像を計算することなく求められる 例 : ユークリッド距離 13

14 カーネル法のポイント 写像を陽に求めなくても 写像先の内積にアクセスできる 線形識別法のうち 計算がサンプル間の内積にしか依存しないものは カーネル化 できる 例 : サポートベクターマシン カーネル主成分分析 カーネル正準相関分析 カーネル Fishe r 判別分析 14

15 15 正定値カーネル 正定値カーネル W: 集合. k(x,y) が W 上の正定値カーネルであるとは, 次の 2 つを満たすことをいう 1. ( 対称性 ) k(x,y) = k(y,x) 2.( 正定値性 ) 任意の自然数 n と, 任意の W の点 x 1,, x n に対し, が ( 半 ) 正定値. すなわち, 任意の実数 c 1,, c n に対し, 対称行列のことを, グラム行列と呼ぶ 0 ), ( 1, n j i j i j i x x k c c n j i x i x j k 1, ), ( k :WW R n j i x i x j k 1, ), ( ), ( ), ( ), ( ), ( n n n n x x k x x k x x k x x k n n 行列

16 正定値カーネルの例 多項式カーネル k ( x, y) ) ガウスカーネル (RBF カーネル ) Fourier カーネル ( 複素数値 ) T d ( x y c ( d: 自然数, c 0 ) 1 k( x, y) exp y x 2 2 > 0 k( x, y) e 1 T ( xy) m R 16

17 17 例 : 多項式カーネル 二次元空間上の正定値カーネル k(x,y) = (x T y ) 2 = (x 1 y 1 + x 2 y 2 ) 2 対応する写像 :2 次元から 3 次元へ ) ( x x x x x

18 様々な構造データへの応用 カーネル法では 類似度さえ定義できればどのような対象にでも適用できる 例 : 生物学的ネットワーク上のタンパク質の分類 18

19 IBM Research Tokyo Research Laboratory 様々なカーネル 2005 IBM Corporation 生物学的配列のカーネル Spectrum kernel (Leslie et al., 2002) Marginalized kernel (Tsuda et al., 2002) Profile kernel (Kuang et al., 2004) Local alignment kernel (Saigo et al., 2004) 木構造に関するカーネル Kernel for phylogenetic profiles (Vert, 2002) Kernel for natural language (Suzuki et al., 2003) Kernel for RNA sequences (Kin et al., 2002) Kernel Methods in Computational Biology, MIT Press, 2004

20 IBM Research Tokyo Research Laboratory 様々なカーネル 2005 IBM Corporation ネットワーク上のノード間のカーネル Diffusion kernel (Leslie et al., 2002) Locally constrained diffusion kernel (Tsuda and Noble, 2004) グラフカーネル Marginalized Graph Kernels (Kashima et al., 2003) MGK without tottering (Mahe et al., 2004) Acyclic Pattern Kernels (Horvath et al., 2004)

21 21 最適化理論の復習

22 条件なし最適化 ある関数 f が与えられたとき それが最小値を取る点を見つけ出す 微分をとって 0 になる点を見つければいい 22

23 条件あり最適化 条件を満たすもので f を最小にする点 ラグランジュ未定係数法 : 係数 λ を導入して次の関数を考える 23

24 ラグランジュ未定乗数法 ラグランジュ関数を x に対して最小化し λ に対して最大化すると 制約付き問題の最適解が得られる ( 鞍点 ) 24

25 双対問題 ラグランジュ関数が x に関して解ける場合 鞍点発見問題は次のような最適化問題 ( 双対問題 ) になる 25

26 Duality Gap 主問題は最小化 双対問題は最大化 最適解において 主問題と 双対問題の目的関数の値は一致する Duality Gap 主問題 双対問題 26 最適化の進行

27 サポートベクターマシン チュートリアル 27

28 サポートベクターマシン (SVM) ベクトル空間上での線形識別器 : 重みパラメータ : バイアス カーネルトリックを行うことによって 非線形に拡張 28

29 線形識別器の学習 訓練サンプルの誤分類数を減らすようにパラメータを決める 29

30 SVM の学習の考え方 訓練サンプルを完全に識別する超平面は無数にある この中で 未知のテストサンプルの識別に優れているのは? 二つのクラスの 真ん中 を通るもの 正則化理論 VC 理論による正当化 30

31 学習方法 ( マージン最大化 ) 超平面と訓練サンプルとの最小距離を評価関数として, これを最大にするように超平面を決定する評価関数の値を大きくすれば, 二つのクラスへの距離が自動的にバランスされ, ほぼ真ん中に超平面が位置する 31

32 サポートベクター 超平面との最小距離に対応するサンプルは, 一つではない. これらのサンプルは, 超平面の周辺に位置し, 超平面を サポート = サポートベクター 32

33 学習法の定式化 (1) 学習サンプルクラスラベル学習の目的は パラメータ クラス A なら 1, クラス B なら -1 を決定すること 学習サンプルを完全に識別する超平面があると仮定正規化 : パラメータを定数倍しても超平面は不変 このようにすると最小距離は 33

34 学習法の定式化 (2) 訓練サンプルとの最小距離を最大化するには 次の最適化問題を解けば良い目的関数 制約条件 最小化 制約条件により, 訓練サンプルはすべて正しく分類される. 最適解は, 正規化条件を満たす. 34

35 学習法の定式化 (3) 制約つきの問題をラグランジュの乗数法で解く 最適解においては これから 次のような関係が導かれる 35

36 学習法の定式化 (4) これらの関係を代入して 双対問題を得る目的関数 制約条件 最大化 ポイント :X の内積のみで記述される 36

37 カーネル関数との組み合わせ 写像先の空間での識別関数 ここで より 37

38 学習問題のカーネル化 内積をカーネルに入れ替えて 以下の問題を得る 目的関数 最大化 制約条件 38

39 39

40 ソフトマージン これまでは 訓練サンプルが超平面で完全に識別できることを仮定 そうでない場合には 制約条件を満たす超平面が存在しないので 解なし 制約条件を緩める = ソフトマージン 40

41 ソフトマージン スラック変数を導入し 制約条件を以下のように変更する 最適化においては 次の目的関数を最小化 C は どこまで制約条件を緩めるかを指定するパラメータであり 設定は実験的に行われる 41

42 ソフトマージンの双対問題 目的関数 制約条件 42

43 サポートベクターマシンの理論 なぜ 超平面を 真ん中 に置けば 誤識別率が最小になることが期待できるのか? PAC 学習の枠組みに沿って説明 43

44 期待リスクと経験リスク 損失関数 期待リスク ( テストサンプルに対する誤識別率 ) 経験リスク ( 訓練サンプルに対する誤識別率 ) 学習の目的は 期待リスクを最小化する f を求めることだが 我々は経験リスクしかしらないので これを最小化するしかない = 経験リスク最小化 44

45 リスクの差 経験的リスク最小化での学習結果は 母関数集合に影響される 期待リスクを最小にするような方は? の選び 一つの手掛かりとなるのは リスクの差の上限 45

46 一般化バウンド に対応する損失関数の集合のVC 次元をとすると 次の不等式は 以上の確率で成立する ここで 46

47 一般化バウンドの意味 が大きな集合の場合 損失関数の集合の VC 次元は増加し リスク差の上限は 大きくなる リスクの差の上限を小さく抑えるには を小さな集合にすればいい 47

48 構造的リスク最小化 構造 : 入れ子になった関数集合の族 どれを選んで 経験リスク最小化を行えば 最も期待リスクを小さくできるのか? 48

49 関数集合の大きさによる トレードオフ 期待リスク = 経験リスク + リスクの差 関数集合大 : 経験リスク小 リスクの差大 関数集合小 : 経験リスク大 リスクの差小 49

50 SVM と構造的リスク最小化 SVM で用いられている構造 SVMでは 訓練サンプルを完全識別する関数の中で 最もの小さいものを選んでいる 経験リスクを 0 にするものの中で 最も小さい関数集合を選んでいる これにより リスクの差を小さくし 結果的に 期待リスクを小さくできる 50

51 構造的リスク最小化の理論の特 徴 サンプルの従っている分布に何の仮定も置かない (Distribution Free) リスクの差の上限に関わるわずかな手がかりから手法を構築 51

52 次元数の呪いについて パラメータの次元数が大きくなると 尐数の訓練サンプルから 精度よくパラメータ推定することが難しくなる現象 カーネルトリックによって パラメータ数は大幅に増加するので 次元数の呪いに陥る可能性がある PAC 学習の立場からは このような心配はない リスクの差は パラメータ数ではなく パラメータベクトルのノルムによって左右される 52

53 SVM のまとめ SVM はマージン最大化に基づく線形識別器 カーネル関数と組み合わせることによって非線形な識別も可能 サンプル間の類似度にしか依存しない 非ベクトルデータの分類も可能 53

54 PCA とカーネル PCA 主成分分析 (PCA, 復習 ) m 次元データ X 1,, X N 主成分分析 分散が最大になる方向 ( 部分空間 ) にデータを射影 単位ベクトル a 方向の分散 : V 1 N N i 1 ~ X i ~ X T i Var[ a T 分散共分散行列 N T ~ 2 X ] 1 1 ( a X ) N i ~ i a T 1 N X i X i N j 1 Va X j ( 中心化 ) V の固有ベクトル u 1, u 2,, u m ( ノルム 1) 固有値 ( l 1 l 2 l m ) 第 p 主成分の軸 = u p データ X j の第 p 主成分 = T u p X j

55 カーネル PCA(Schölkopf et al 98) データ X 1,, X N カーネル k を設定 特徴ベクトル f 1,, f N 特徴空間での単位ベクトル h 方向の分散 = ただし 1 N ~ 2 i 1 h, fi N ~ 1 N f f f ( 中心化 ) i i N j 1 j h N i 1 i i 主成分は ~ f 分散 1 N としてよい ( 直交する方向は分散に寄与しない ) max T K ~ ~ f, f 1 T ~ K N ~ ~ f ~ f N N 2 2 a1 j1 j j a ただし Kij i, j ~ 2 制約条件 ~ T K 1 h ~ ~ T ~ iifi, iifi K H k 55

56 カーネルPCAのアルゴリズム分散最大の方向 = K ~ ~ K ~ の固有値分解 ~ 第 p 主成分を与える : K N a 1 の最大固有値の固有ベクトル方向 N 1 N 1 N Kij K( X i, X j ) 1 N a1 K( X i, X a) N a1 K( X a, X j ) N a, b1 K( X a, X ) 2 b Q KQ N N ij 1 T ただし QN I N N 1N1N, 1 N = (1,,1) T l u a ( p) a u a T u ~ T K 1 ( p) 1 p ゆえ u l p p データ X j の第 p 主成分 = N ( p) i ~ ~ 1 i fi, j f l p u p j 56

57 カーネル PCA の実験例 Wine データ (UCI Machine Learning Repository) 13 次元,178データ,3 種類のワインの属性データ 2つの主成分を取った (3クラスの色は参考に付けたもの) PCA( 線形 ) KPCA(RBF, = 3) 57

58 KPCA(RBF, = 2) KPCA(RBF, = 4) KPCA(RBF, = 5) 58

59 カーネル PCA の特徴 非線形な方向でのデータのばらつきが扱える. 結果はカーネルの選び方に依存するので, 解釈には注意が必要 ガウスカーネルの分散パラメータなど どうやって選ぶか? 必ずしも明確でない 前処理として使える 後の処理の結果を改良するための非線形特徴抽出 59

60 カーネル CCA 正準相関分析 (CCA, 復習 ) CCA 2 種類の多次元データの相関を探る m 次元データ X 1,, X N n 次元データ Y 1,, Y N X を a 方向,Y を b 方向に射影したときに相関が大きくなる (a,b) を求める 1 T ~ T ~ T N i a X i b Yi a VXYb 正準相関 max max m m ar T ~ 2 T ~ 2 ar T T 1 1 n a X b Y n a VXX a b VYY br N i b i N i ただし V i XY br 1 N i ~ ~ X Y i T i など X a a T X b T Y b Y 60

61 カーネル CCA(Akaho 2001, Bach and Jordan 2002) データ X 1,, X N 特徴ベクトル f X 1,, f X N Y 1,, Y N カーネル k X, k Y を設定 f f X j Y j f Y 1,, f Y N k (, X ) H Y X k (, Y ) H j j k Y k X カーネルCCA: 特徴空間での相関を最大化する射影方向 f, g を求める 1 ~ X ~ Y N i f, fi g, f H i H kx ky max f H X 2 Y 2 k 1 ~ 1 ~ X f, f g, f gh ky N i i H kx N i i H ky カーネルPCA 同様 f N ~ X 1 f, T ~ ~ K X KY maxn T ~ 2 T ~ R K K 2 N R X Y g N Y 1 ~ f としてよい. 61

62 まとめ カーネルによる非線形化 線形データ解析アルゴリズムを特徴空間で行うことによって非線形アルゴリズムが得られる カーネル化 (kernelization) 内積 を使って表される線形手法なら拡張が可能 射影, 相関, 分散共分散,etc 例 : サポートベクターマシン, スプライン平滑化, カーネル PCA, カーネル CCA, など 非線形アルゴリズムの特徴 線形ではとらえられない性質が調べられる. とらえることのできる非線形性はカーネルの選び方に影響を受ける 62