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

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

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

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

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

線形なデータ解析 線形データ解析 データが 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, -0.83 )... データに線形な処理を施してデータ解析を行う例 : 主成分分析 回帰分析 相関分析 etc. 5

例 : 主成分分析 (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

例 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

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

非線形データ解析の重要性 非線形変換 +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 非線形相関が考慮できる 2.5 2.5 b T F Y 0.5 0 相関係数 = 0.963-0.5 - -.5-2 -2 -.5 - -0.5 0 0.5.5 a T F X 0

非線形化の困難 高次相関 多次元データでは計算量が爆発 もとの変数 : 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 = 3 3.6 0 5 次元 莫大な計算量

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

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

カーネル法における内積計算 内積計算 線形手法の計算. 内積計算が本質 ( 相関行列 分散共分散行列 ) 内積 Φ(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

例 : カーネル主成分分析 高次元空間内での 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

例 : カーネル主成分分析 カーネル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

正定値カーネル どのような 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

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

カーネル主成分分析 ( カーネル 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

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

0.5 0.6 0.4 0.3 0.2 0.4 0.2 0. 0 0-0. -0.2-0.2-0.3-0.4-0.5-0.5-0.4-0.3-0.2-0. 0 0. 0.2 0.3 0.4 KPCA(Gauss,σ = 2) 0.6-0.4-0.6-0.8-0.8-0.6-0.4-0.2 0 0.2 0.4 0.6 KPCA(Gauss,σ = 4) 0.4 0.2 0-0.2-0.4-0.6-0.8-0.8-0.6-0.4-0.2 0 0.2 0.4 0.6 KPCA(Gauss,σ = 5) 2

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

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

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

カーネル 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

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

カーネル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

カーネル CCA の適用例 X = (X, X 2 ), Y = (Y, Y 2 ).5-0.2 0.5 カーネル CCA -0.25-0.3-0.35 Y 0-0.5 - -.5 -.5 - -0.5 0 0.5.5 X X 2, Y 2 は独立なノイズ ガウスカーネル 2 exp( z z / 9) GiΦ( Y i ) -0.4-0.45-0.5-0.55-0.6 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 FiΦ( X i ) 相関係数 = 0.976 (c.f. 2 次式での CCA, 相関係数 = 0.963) 28

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

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

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

グラフの類似度をはかるカーネル グラフ間の類似度を定める方法 グラフカーネル (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

グラフの類似度をはかるカーネル 自然言語処理への応用 Φ : ツリー 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

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

カーネル 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

カーネル 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

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

References ホームページ 2004 年度統数研公開講座資料 カーネル法 -- 正定値カーネルを用いたデータ解析 -- ( 福水 ) http://www.ism.ac.jp/~fukumizu/ism_lecture_2004/ カーネル法の関するポータルサイト http://www.kernel-machines.org/ ソフトウエア The Spider (Matlab ツールボックス ) http://www.kyb.tuebingen.mpg.de/bs/people/spider/index.html Statistical Pattern Recognition Toolbox (Matlab ツールボックス ) http://cmp.felk.cvut.cz/~xfrancv/stprtool/ Gist (C 言語, Support Vector Machine) http://microarray.cpmc.columbia.edu/gist/ 38

References 書籍赤穂昭太郎. カーネルマシン 学習システムの理論と実現 3 章. 森北出版 (2005) Schölkopf, B. and A. Smola. Learning with Kernels. MIT Press. 2002. 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 i370. 39

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