カーネル法による非線形データ解析法

Size: px

Start display at page:

Download "カーネル法による非線形データ解析法"

あきひさうなだ
5 years ago
Views:

1 カーネル法による非線形データ解析入門福水健次情報システム研究機構統計数理研究所 March 3, ROIS Cross-talk

2 あらまし. イントロ : 線形から非線形へ 2. カーネル法 : 高次元の内積計算 3. カーネル法の具体例 : カーネル PCA とカーネル CCA 4. グラフに対するデータ解析 5. まとめ 2

3 Introduction 線形から非線形へ. イントロ : 線形から非線形へ 2. カーネル法 : 高次元の内積計算 3. カーネル法の具体例 : カーネルPCAとカーネルCCA 4. グラフに対するデータ解析 5. まとめ 3

4 はじめにデータ解析実験 / 観測などで得られたデータから有用な情報を抽出するための方法情報の集約低次元表現圧縮表現関係の抽出相関依存性可視化による分析 2,3 次元表現予測発見 4

5 線形なデータ解析線形データ解析データが m 次元数値ベクトルとして表現されている X = (.52, -0.98, 5.0, -0.24, -3.3 ) X 2 = ( 2.3,.58, -2.76, 4.37, 3.09 ) X 3 = (-0.0, -2.28, 4.7, -2.5, )... データに線形な処理を施してデータ解析を行う例 : 主成分分析回帰分析相関分析 etc. 5

6 例 : 主成分分析 (PCA, principal component analysis) 主成分分析ばらつきの大きい方向にデータを射影して眺める復習 a T は a の転置 a T b = a b + + a m b m は内積を表す max a ( X X ) max a V a N ( T i j ) 2 T N j = a = N i= a = N ( i N j)( i N j) T XX = N j= N j= N i= V X X X X m 次元データ低次元の主成分による表現 a: 分散共分散行列 V XX の最大固有値に対応する固有ベクトル d 個まで取れば d 次元表現を得る XX なる a を求める 6

7 例 2: 正準相関分析 (CCA, canonical correlation analysis) 正準相関分析 2 つ多次元変数間の相関を見る手法 ρ = m 次元 X,, X m X N,, X N m = a n 次元 a T X i b T Y i b Y,, Y n... Y N,, Y N n a T X と b T Y の相関が最大になるようにベクトル a, b を決める max m T i T j T i T j i( a X ja X )( by jby ) ( a X a X ) ( b Y b Y ) N N N a R 2 2 T i T j T i T j n b R N i N j N i N j max m a R b R n T T av XX XY b T av a bv b YY 一般化固有値問題として解ける 7

8 線形から非線形へ線形手法の限界非線形なデータの構造は捕らえにくい複雑なデータに対して線形な構造だけを見ていては不十分なこともあるデータが数値ベクトルである必要がある非数値的データには別途考慮が必要カーネル法 : 非線形データ解析手法カーネル法非線形データ解析の一般的枠組みデータの非線形な関係を考慮できる既存の線形手法を容易に非線形化できる非数値的データにも適用可能 8

9 非線形データ解析の重要性正準相関分析の例 X = (X, X 2 ), Y = (Y, Y 2 ) X と Y が強い非線形な依存関係を持つ.5 3 非線形な関係は発見できない 0.5 CCA 2 Y 0 b T Y X a T X 9

10 非線形データ解析の重要性非線形変換 +CCA 2 次式による変換 (X, X 2 ) (X, X 2, X 2, X X 2, X 22 ) = F X (Y, Y 2 ) (Y, Y 2, Y 2, Y Y 2, Y 22 ) = F Y それぞれ 5 次元データに変換変換後のデータに対して CCA 非線形相関が考慮できる b T F Y 相関係数 = a T F X 0

11 非線形化の困難高次相関多次元データでは計算量が爆発もとの変数 : m 次元 d 次式の空間高次元 X,, X m X N,, X N m Φ (X ) d,, (X m) d, (X ) d- X 2, (X ) d- X 3, (X N ) d,, (X N m) d, (X N ) d- X N 2, (X N ) d- X N 3, ( m+ d )! d!( m )! 次元例 ) m = 28, d = 次元莫大な計算量

12 カーネル法高次元の内積計算. イントロ : 線形から非線形へ 2. カーネル法 : 高次元の内積計算 3. カーネル法の具体例 : カーネルPCAとカーネルCCA 4. グラフに対するデータ解析 5. まとめ 2

13 非線形変換としてのカーネル法カーネル法の原理もとの変数高次元ベクトル空間 ( 無限次元でよい ) X X N Φ 非線形写像 ( うまい性質を持つ ) Φ(X ) Φ(X N ) 変換後のデータに線形の手法を用いる非線形相関などが考慮できる Ω X i Φ(X i ) 高次元空間 3

14 カーネル法における内積計算内積計算線形手法の計算. 内積計算が本質 ( 相関行列分散共分散行列 ) 内積 Φ(X i ) Φ(X j ) が計算できれば OK カーネル法 : 変換 Φ を与える代わりに内積が Φ(x ) Φ(x 2 ) = K(x, x 2 ) と計算できるようなカーネル関数 K(x, x 2 ) を与える高次元ベクトル空間と非線形変換は自然と定まる Φ(x ) カーネル K(x, x 2 ) : データ x と x 2 の類似度を定めるようなもの Φ(x 2 ) 4

15 例 : カーネル主成分分析高次元空間内での PCA N max ( ) ( ) N F N F = i= N = ( { i j Fi Φ X }) 2 j Φ X 高次元空間内のベクトル F は { s X } = α Φ( ) Φ( ) i= N s X の形で探せば十分 ( 直交性 ) N max ( ) ( ) ( ) ( ) N N α N ( N { s } { i j }) 2 = α Φ X sφ X i Φ X jφ X Φ(X i ) Φ(X j ) = K(X i, X j ) を使って展開すると 5

16 例 : カーネル主成分分析カーネルPCAのアルゴリズム max α α N ただし T 2 K α ベクトル F のノルムはなので制約 α T K α = N N N (, ) (, ) (, ) (, ) N N N t= s= s, t= K = K X X K X X K X X + K X X ij i j i t s j 2 s t K : データ数のサイズの行列 ( データの次元には無関係 ) () α (),..., α (d) K : の大きいd 個の固有値に対応するノルムの固有ベクトルを求める (2) データ点 X i の第 p 主成分 ( N ( p ) { }) { } ( X s i j = α ) s ( X ) i ( X ) j ( X ) = Φ Φ Φ Φ N F ( p) N ( p) = Kα の第 i 成分 6

17 正定値カーネルどのような K(x,y) がカーネルとして使えるか? 対称性 K(x, y) = K(y, x) と次の正定値性を満たせば OK 任意の点 x,..., x n と実数 α,..., α n に対して i, j= αα K( x, x ) 0 正定値カーネルの例 n i j i j ( 半 ) 正定値線形カーネルガウスカーネル多項式カーネル K(x, y) = x T y ( 普通のユークリッド内積 ) ( 2 2 ) K( x, y) = exp x y σ (σ > 0) K(x, y) = (c + x T y) d (c 0, d N ) 7

18 カーネル法の具体例カーネル PCA とカーネル CCA. イントロ : 線形から非線形へ 2. カーネル法 : 高次元の内積計算 3. カーネル法の具体例 : カーネルPCAとカーネルCCA 4. グラフに対するデータ解析 5. まとめ 8

19 カーネル主成分分析 ( カーネル PCA) カーネルPCAのアルゴリズム. カーネルの選択 2. 中心化グラム行列の計算 K K K X X K X X N ij = ( i, j ) a ( i, a ) N = N N N a= K Xa X j 2 N a, b= K Xa Xb (, ) + (, ) 3. の固有値分解 λ 0 U U T K = 0 λ Ν U: 直交行列 λ λ N 0 4. 第 i データの第 p 主成分 = λ U p ip 9

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

21 KPCA(Gauss,σ = 2) KPCA(Gauss,σ = 4) KPCA(Gauss,σ = 5) 2

22 カーネル PCA の特徴非線形な方向でのデータのばらつきが扱える. 結果はカーネルの選び方に依存するので, 解釈には注意が必要 ( カーネルの種類カーネル内のパラメータ ) どうやって選ぶか? 必ずしも明確でない目的に依存前処理として使われることが多い後の処理の結果を改良するための非線形特徴抽出例えばカーネル PCA + 識別機 (Fisher 判別分析サポートベクターマシン ) によるクラス識別問題最終的な識別の正答率を向上させるカーネルパラメータがよい 22

23 カーネル PCA の雑音除去への応用 ( カーネル )PCA による雑音除去高次元の空間のなかで d 個の主成分の軸 F, F 2,..., F d が張る d 次元部分空間へデータ Φ(x) を射影した点を G x とおく Φ の像の中で G x に最も近いものを ˆx とする Φ(x) G x xˆ = arg min Φ( x ) G x x 2 カーネル K(x, x 2 ) を使って表せる

24 USPS 手書き数字データベース 6x6 画素 (256 次元 ) 729 データカーネル PCA の雑音除去への応用元の画像 ( データとしては使用していない ) ノイズつきの画像ノイズ除去された画像 (linear PCA) ノイズ除去された画像 (kernel PCA) Matlab stprtool (V. Franc 作 ) により作成 24

25 カーネル CCA 高次元空間内の CCA 線形の CCA max a R b R m n T Cov[ a X, b Y] ( T T Var[ a X]Var[ b Y] ) /2 T カーネル CCA: 非線形変換後のデータの CCA Cov[ F iφ ( X), GiΦ ( Y)] X Y max FG, Var[ X ( )]Var[ Y ( )] ( FiΦ X GiΦ Y ) /2 Φ X と Φ Y ( あるいは K X と K Y ) は異なってよい 25

26 X に対する高次元空間 X H X Φ X Φ X ( X i ) x i x j Φ X ( X ) j linear CCA Y y i y j Φ Y ( Y ) i H Y Φ Y Φ Y ( Y ) j Y に対する高次元空間 26

27 カーネルCCAの定式化 N i{ j } カーネル CCA ( F ΦX( Xi) ΦX( X j) )( Gi{ ΦY( Yi) jφy( Yj) }) N N N i= FG, N /2 /2 2 N 2 N ( Fi{ ΦX( Xi) N jφx( X j) }) N ( Gi{ ΦY( Yi) N jφy( Yj) }) i= i= max N ( N N i= i X( i) j X( j) N = ) ( N G = i= bi ΦY( Yi) j Y( Yj) N = Φ ) F = a Φ X Φ X Kernel CCA max N a R b R N T T a K K b X ( 2 ) T ( 2 ) X + ε N X Y + ε N Y a K N K a b K N K b Y の形で十分 ε N : 正則化係数最適な a と b は一般化固有値問題の解として解ける 27

28 カーネル CCA の適用例 X = (X, X 2 ), Y = (Y, Y 2 ) カーネル CCA Y X X 2, Y 2 は独立なノイズガウスカーネル 2 exp( z z / 9) GiΦ( Y i ) FiΦ( X i ) 相関係数 = (c.f. 2 次式での CCA, 相関係数 = 0.963) 28

29 カーネル法の特徴非線形写像 Φ(x) を決めるのではなく内積を表すカーネル K(x,y) を決める相関行列 ( 分散共分散行列 ) のかわりにグラム行列が活躍する K(X i, X j ) グラム行列のサイズ = データのサイズカーネル K(x,y) はデータ x, y の類似度を定めている 29

30 グラフに対するデータ解析. イントロ : 線形から非線形へ 2. カーネル法 : 高次元の内積計算 3. カーネル法の具体例 : カーネルPCAとカーネルCCA 4. グラフに対するデータ解析 5. まとめ 30

31 非ベクトルデータに対するカーネルカーネルは任意の集合上に定義可能正定値カーネル K(x, y) : x, y はベクトルでなくともよい非ベクトルデータ上のカーネルの定義非ベクトルデータに対するデータ解析が可能主成分分析正準相関分析判別分析 etc 複雑な構造を持つデータ ( グラフネットワークツリー etc.) のデータ解析に有用カーネルをどう定義するか?( 類似度をどう決めるか?) 個別の工夫が必要モデリングの問題 3

32 グラフの類似度をはかるカーネルグラフ間の類似度を定める方法グラフカーネル (Kashima et al. 2002) Φ : グラフ G Φ( G) H ベクトル空間化合物の毒性予測 Cl s s d に応用 C C Cl s s H Cl ラベル付グラフと思う α a b γ β a c β b α α a b γ α a β b α 生成可能なパス ( ラベル列 ) の類似度を K(G, G 2 ) に用いる G G 2 32

33 グラフの類似度をはかるカーネル自然言語処理への応用 Φ : ツリー T Φ ( T ) H ベクトル空間サブツリーの一致により類似度を定義構文解析 (Collins & Duffy 2002) Jeff ate the apple. S NP VP N V NP D the サブツリーの例 NP N D N apple the apple NP D NP NP N Jeff ate D N D N D N the apple the apple 33

34 グラム行列によるネットワークデータの処理カーネル手法グラム行列に対する操作もとのデータを知らなくてもグラム行列が与えられれば適用可能なものが多いグラム行列類似度行列正定値な類似度行列が与えられればカーネル法を適用可能な場合があるグラム行列によるネットワークの表現隣接ノードは似た振る舞い A = 隣接行列 e β(a-d) グラム行列 34

35 カーネル CCA によるネットワーク推定タンパク質ネットワークの推定 (Yamanishi et al. 2004) 複数の遺伝情報からグラム行列を構成し逆にネットワークを推定する yeast (Saccharomyces cerevisiae) Gene expression data K X, Two-hybrid systems K X,2 Protein localization data K X,3 K Y Protein network ( 既知の相互作用 ) Phylogenic profile K X,4 35

36 カーネル CCA によるネットワーク推定相互作用ネットワークに関連した特徴をカーネル CCA で抽出 K X = K X, + K X,2 + K X,3 + K X,4 K Y 4 種の遺伝情報の統合ネットワークデータ () ( d ) i カーネル CCA () ( d ) F i Φ( X ),, F i Φ( X ) 遺伝情報に含まれるネットワーク推定と関連が強い情報 i G iφ( Y),..., G iφ( Y) d p p K ij = p ΦX ( Xi ) if F iφx ( X j ) = ( ( ))( ( ) ) 閾値処理によるネットワーク推定 i ネットワーク推定に有効な類似度 i 36

37 まとめカーネルを用いた非線形データ解析カーネル法カーネルで定まる非線形変換 + 線形データ解析手法カーネル内積 ( 類似度 ) を定義する従来の線形手法の拡張が容易カーネル PCA カーネル CCA カーネル判別分析 etc. カーネルの選択は個別に考える必要があるデータの分析などへの応用の際は結果の合理性を考慮すべし ( 非線形手法は局所的な情報のみを強調することもある ) 複雑な構造を持つデータの処理も可能である非ベクトルデータに対しても内積定義線形手法の適用可能 37

38 References ホームページ 2004 年度統数研公開講座資料カーネル法 -- 正定値カーネルを用いたデータ解析 -- ( 福水 ) カーネル法の関するポータルサイトソフトウエア The Spider (Matlab ツールボックス ) Statistical Pattern Recognition Toolbox (Matlab ツールボックス ) Gist (C 言語, Support Vector Machine) 38

39 References 書籍赤穂昭太郎. カーネルマシン学習システムの理論と実現 3 章. 森北出版 (2005) Schölkopf, B. and A. Smola. Learning with Kernels. MIT Press Shawe-Taylor, J. and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press (2004) Schölkopf, B., K. Tsuda, and J.-P. Vert (eds.). Kernel Methods in Computational Biology. MIT Press (2004). 言及した論文 Kashima, H., K. Tsuda and A. Inokuchi. (2003) Marginalized Kernels Between Labeled Graphs. Proc. 20th Intern.Conf. Machine Learning (ICML2003). Collins, M. & N. Duffy. (2002) Convolution Kernels for Natural Language. Advances in Neural Information Processing Systems 4. Yamanishi, Y., J.-P. Vert and M. Kanehisa. (2004) Protein network inference from multiple genomic data: a supervised approach. Bioinformatics. Vol. 20 Suppl., pages i363 i

40 宣伝ですさらに詳しく知りたい方は統計数理研究所 2006 年度公開講座カーネル法の最前線 -- SVM, 非線形データ解析, 構造化データ年 7 月上旬 2 日間 (0 時間 ) 講師 : 福水健次 ( 統数研 ) 赤穂昭太郎 ( 産総研 ) 松井知子 ( 統数研 ) 詳細は 40

PowerPoint Presentation

PowerPoint Presentation . カーネル法への招待正定値カーネルによるデータ解析 - カーネル法の基礎と展開 - 福水健次統計数理研究所 / 総合研究大学院大学統計数理研究所公開講座 0 年月 34 日概要カーネル法の基本線形データ解析と非線形データ解析カーネル法の原理カーネル法のつの例カーネル主成分分析 : PCA の非線形拡張リッジ回帰とそのカーネル化概要カーネル法の基本線形データ解析と非線形データ解析

カーネル法による 非線形データ解析法

カーネル法による非線形データ解析法