Microsoft PowerPoint - OsakaU_1intro.pptx

福水健次

統計数理研究所／総合研究大学院大学 大阪大学大阪大学大学院基礎工学研究科・集中講義 2014 September

カーネル法入門

１．カーネル法へのイントロダクション

カーネル法:

近年 (1990年代半ばごろから) 発展したデータ解析の方

法論．非線形な情報や高次モーメントの扱いが容易．

サポートベクターマシンの提案が発端となった．

線形なデータ解析，非線形な

データ解析

データ解析とは?

Analysis of data is a process of inspecting, cleaning, transforming,

and modeling data with the goal of highlighting useful information, suggesting conclusions, and supporting decision making.

線形なデータ解析

– 数値の表 行列 表現

– 線形代数を使ってデータ解析を行う．

• 相関,

• 主成分分析(Principal component analysis, PCA),

• 正準相関分析(Canonical correlation analysis, CCA), etc. • 線形回帰, • 線形判別分析 • ロジスティック回帰































) ( ) ( 1 ) 2 ( ) 2 ( 1 ) 1 ( ) 1 ( 1 N m N m m

X

X

X

X

X

X











X

m 次元 N 個のデータ

 例1: 主成分分析（Principal component analysis,

PCA)

PCA: 分散が最大となる低次元部分空間にデータを射影する．. 1st direction =

_argmax

_Var

_[

_]

1 || ||

a

X

T a 





 

























_



N i N j j i T T

X

N

X

a

N

X

a

1 2 1 ) ( ) (

1

1

]

[

Var

.

a

V

a

T _XX









         _       _  N i T N j j i N j j i X N X X N X N ₁ 1 ) ( ) ( 1 ) ( ) ( 1 1 1 XX

V

– 第p主成分方向

PCA 行列 の固有値問題

 例2: 線形識別（判別）

– ２値識別 識別器 を次にように構成する – 例: Fisherの線形判別分析, 線形サポートベクターマシン, etc.                ) ( ) ( 1 ) 2 ( ) 2 ( 1 ) 1 ( ) 1 ( 1 N m N m m X X X X X X      X 入力 N N Y Y Y Y { 1} ) ( ) 2 ( ) 1 (                   クラスラベル

)

sgn(

)

(

x

a

x

b

h



T



) ( ) (

)

(

X

i

Y

i

線形で十分か?

-6 -4 -2 0 2 4 6 -6 -4 -2 0 2 4 6 x₁ x₂ 線形識別不能 0 5 10 15 20 0 5 10 15 20 -15 -10 -5 0 5 10 15 z₁ z₃ z₂ transform

)

2

,

,

(

)

,

,

(

z

₁

z

₂

z

₃



x

₁2

x

₂2

x

₁

x

₂ 線形識別可能

 Another example: correlation

]

[

]

[

]

,

[

Y

Var

X

Var

Y

X

Cov

XY





















2









2



]

[

]

[

]

[

]

[

Y

E

Y

E

X

E

X

E

Y

E

Y

X

E

X

E











-3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3 X Y



= 0.94

0 0.5 1 1.5 2 2.5 -0.5 0 0.5 1 1.5 2 2.5 -1.5 -1 -0.5 0 0.5 1 1.5 -0.5 0 0.5 1 1.5 2 2.5 X Y



( X, Y ) = 0.17



( X2,Y ) = 0.96 transform (X, Y) _(X2_{, Y)}

がん研 多目的コホート研究（JPHC Study) 肥満度（BMI）のがん全体の罹患に与える影響

非線形変換は有望

Analysis of data is a process of inspecting, cleaning, transforming,

and modeling data with the goal of highlighting useful information, suggesting conclusions, and supporting decision making.

Wikipedia.

カーネル法 = データの非線形情報，高次モーメントを抽出するために，デ

カーネル法の概略

– カーネル法の概念図 – 特徴空間として望まれる性質： • データのさまざまな非線形特徴を有していること • 内積計算が容易にできること. 多くの線形データ解析の計算は内積に依拠している． 特徴空間 x_i  H_k  _x ｊ , i x  j x  元のデータの空間 特徴写像 特徴空間で線形データ解析を施す! e.g. SVM

 計算の問題

– 高次情報の抽出 (X, Y, Z)  (X, Y, Z, X2_{, Y}2_{, Z}2_{, XY, YZ, ZX, …)} – 元の空間の次元が高いと 計算は実現できない! e.g. 10000 次元のデータ, ２次までの特徴 10000C1 + 10000C2 = 50,005,000 – 計算量爆発. より効率的な方法が必要  カーネル法

特徴空間と正定値カーネル

– 特徴写像: 元の空間から特徴空間への写像 – 特別な特徴空間（再生核ヒルベルト空間）を用いると，特徴ベクトルの 内積計算が関数値 (正定値カーネル) , の評価に置き換えられる – 内積計算さえできれば，特徴ベクトル (X).の陽な形は知らなくてもよ い．

)

,

(

)

(

),

(

X

_i



X

_j



k

X

_i

X

_j



kernel trick

Φ: Ω → , ↦ Φ

正定値カーネル

定義. : 集合 カーネル : Ω Ω → が正定値であるとは 1) (対称性) 2) (正値性) 任意の点 , … , ∈ Ω ∀ に対し，

0

)

,

(

1 ,





 n j i

c

i

c

j

k

x

i

x

j





















)

,

(

)

,

(

)

,

(

)

,

(

1 1 1 1 n n n n

x

x

k

x

x

k

x

x

k

x

x

k











)

,

(

)

,

(

x

y

k

y

x

k



が半正定値

i.e., for any

c

_i



R

– 例: Rm上 • Euclid内積 • Gaussian RBF カーネル • Laplace カーネル • 多項式カーネル



2 2



exp

)

,

(

x

y

x

y



k

_G







d T P

x

y

c

x

y

k

(

,

)



(



)

(

c

 d

0

,



N

)

)

0

(









_

_







m i i i L

x

y

x

y

k

1

|

|

exp

)

,

(



)

0

(





y

x

y

x

k

(

,

)



T Gaussian Laplacian

命題1.1 を内積 _{⋅,⋅ を持つベクトル空間とし， Φ: Ω →} を写像(特徴写像) とする. : Ω Ω → を , Φ , Φ , により定義すると， , は正定値である. – カーネルトリックを成り立たせる関数は，正定値カーネルである. (kernel trick)

0

)

(

)

(

),

(

2 1 1 1















_



_



n_ i i i n j j j n i

c

i

X

i

c

X

c

X

 







 





n i n j i j i j n j i, 1

c

i

c

j

k

(

X

i

,

X

j

)

1 1

c

c

(

X

),

(

X

)

*Proof)

– 正定値性は十分でもある. 定理1.2 (Moore-Aronszajn) Ω上の正定値カーネル に対し，Ω上の関数からなるHilbert空間* (再生核ヒルベルト空間, RKHS) が存在して，次が成り立つ． 1) ⋅, ∈ ∀ ∈ Ω . 2) span ⋅, ∈ Ω は で稠密 3) (再生性) , ⋅, for any ∈ , ∈ Ω. *Hilbert空間: 内積を持つベクトル空間で，内積により決まるノルムが完備であ るもの．

正定値カーネルによる特徴写像

– 正定値カーネル を用意 – 特徴空間 = RKHS – 特徴写像:

Φ: Ω → ,

↦

⋅,

, … ,

↦ ⋅,

, … , ⋅,

– カーネルトリック（再生性）: – 正定値カーネルを与えれば十分. • 特徴写像，特徴ベクトルを陽に知る必要はない. • カーネル法の計算は，グラム行列 , による計算となる.

),

,

(

)

(

),

(

X

_i



X

_j



k

X

_i

X

_j



Feature space x_i  Hk  _x ｊ , i x  j x 

Space of original data

PCAからカーネルPCAへ

– PCA: 線形な次元削減.

– カーネルPCA: 非線形な次元削減 (Schölkopf et al. 1998).

– 特徴空間でPCAを行う

:

max

_||f||1

:

max

_||a||1





 

























_



N i N j j i T T

X

N

X

a

N

X

a

1 2 1 ) ( ) (

1

1

]

[

Var





 























N i N j j i

X

N

X

f

N

X

f

1 2 1 ) ( ) (

)

(

1

)

(

,

1

]

)

(

,

[

Var

次の形の を考えれば十分 (直交する方向は分散に効いてこない!) [Representer定理]









 









N i N j j N i i

X

X

c

f

1 1 ) ( 1 ) (

)

(

)

(

max

subject to

||

f

||



1



c

T

K

~

_X

c



1

(カーネルトリックを使うと)

 





_

N_ b b i j i ij X

k

X

X

N

X

X

k

K

1 ) ( ) ( ) ( ) (

)

,

(

1

)

,

(

~













N b a b a N a j a

X

X

k

N

X

X

k

N

, 1 ) ( ) ( 2 1 ) ( ) (

)

,

(

1

)

,

(

1

(中心化Gram行列) 

 f

Var

, Φ

1

– 証明 • ∑ Φ とすると， [ Φ ≡ Φ ∑ Φ ] Var , Φ ∑ , Φ ∑ ∑ Φ , Φ ∑ ∑ Φ , Φ ∑ ∑ . • ∑ Φ , ∑ Φ ∑ . • Φ ∑ Φ , Φ ∑ Φ , ∑ , ∑ , ∑ _, , ≡

 カーネルPCAのアルゴリズム:

• 中心化Gram行列 の計算 • の固有分解 • 第p主成分方向 ∑ Φ , • X(i)の第p主成分 , Φ ∑







N i T i i i X

u

u

K

1

~

_

0

2 1











N







eigenvalues unit eigenvectors N

u

u

u

₁

,

₂

,



,

Φ Φ ∑ Φ : 中心化特徴ベクトル

カーネルPCAの例

 Wine データ

(UCI repository)

3種類のイタリアワインに関する，13 次元の化学測定値 178 データ. クラスの情報はカーネルPCAには用いていない -2 -1 0 1 2 3 4 -0.4 -0.2 0 0.2 0.4 0.6

Linear PCA Kernel PCA (Gaussian kernel) (



= 3)

カーネル法の構成要素

– 特徴空間上で線形データ解析を適用する. (Kernelization) – 多くの場合，目的関数をカーネルによって書き直すことができる – 解は以下の形で考えれば十分である（有限パラメータの問題に還元） (Representer定理),  すべての量がGram行列によって表現される(サイズ = データ数). – 元の空間が高次元でも計算量の問題が生じない．Gram行列を計算し た後は，データ数のみに依存した計算量． 以上はカーネル法一般に共通の要素である.

)

,

(

)

(

),

(

X

_i



X

_j



k

X

_i

X

_j



)

(

,

X

_i

f



,

)

(

1 ) (









N i i i

X

c

f

参考文献

 福水 「カーネル法入門」 １章 朝倉書店 2010.

 B. Schölkopf and A. Smola. Learning with kernels. MIT Press, 2002.

 赤穂 「カーネル多変量解析 ―非線形データ解析の新しい展開」 岩波書店