1. No category

カーネル法入門
１．カーネル法へのイントロダクション
福水健次
統計数理研究所／総合研究大学院大学
大阪大学大阪大学大学院基礎工学研究科・集中講義
2014 September
1
カーネル法:
近年 (1990年代半ばごろから) 発展したデータ解析の方
法論．非線形な情報や高次モーメントの扱いが容易．
サポートベクターマシンの提案が発端となった．
2
線形なデータ解析，非線形な
データ解析
3
データ解析とは?
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
4
線形なデータ解析
– 数値の表
行列 表現
 X 1(1)  X m(1) 


 X 1( 2 )  X m( 2 )  m 次元
X 



 N 個のデータ
 X (N )  X (N ) 
m 
 1
– 線形代数を使ってデータ解析を行う．
• 相関,
• 主成分分析(Principal component analysis, PCA),
• 正準相関分析(Canonical correlation analysis, CCA),
• 線形回帰,
• 線形判別分析
• ロジスティック回帰
etc.
5
 例1: 主成分分析（Principal component analysis,
PCA)
PCA: 分散が最大となる低次元部分空間にデータを射影する．.
1st direction =
argmax||a||1Var[a T X ]
1
Var[a X ] 
N
T
 T  (i ) 1
a  X 

N

i 1 
N

N
j 1
X
( j)



2
 a T VXX a.
VXX
1

N
 (i ) 1
X 

N
i 1 
N
1
( j ) 
(i )
 j 1 X  X  N
N
( j) 
X
 j 1 
N
--- X の分散共分散行列
6
T
– 第p主成分方向
： VXX の第p最大固有値に対する単位固有ベクトル
PCA
行列
の固有値問題
7
 例2: 線形識別（判別）
– ２値識別
入力
クラスラベル
 X 1(1)  X m(1) 


( 2)
( 2)
 X1
 Xm 
X




 X (N )  X (N ) 
m 
 1
 Y (1) 
 ( 2) 
Y 
N


Y 
{
1
}




(
)
N
Y 


識別器
h ( x )  sgn( a T x  b )
を次にように構成する
h( X ( i ) )  Y ( i )
for all (or most) i.
– 例: Fisherの線形判別分析, 線形サポートベクターマシン, etc.
8
線形で十分か?
線形識別不能
線形識別可能
6
15
4
10
5
2
z3
x2
0
-5
0
transform
-10
-15
0
-2
20
5
-4
-6
-6
z1
-4
-2
0
2
4
15
10
10
15
5
6
20
x1
0
z2
( z1 , z 2 , z3 )  ( x12 , x22 , 2 x1 x2 )
Watch the movie! https://www.youtube.com/watch?v=3liCbRZPrZA
9
 Another example: correlation
 XY
Cov[ X , Y ]
E  X  E[ X ]Y  E[Y ]


2
2
Var[ X ]Var[Y ]
E  X  E[ X ] E Y  E[Y ]



3
2
 = 0.94
1
Y
0
-1
-2
-3
-3
-2
-1
0
1
2
3
X
10
Y
2.5
2.5
2
2
1.5
1.5
( X, Y )
1
= 0.17
0.5
0
-0.5
-1.5
( X2,Y )
1
= 0.96
0.5
0
-1
-0.5
0
0.5
1
-0.5
0
1.5
0.5
1
1.5
2
2.5
X
(X, Y)
transform
(X2, Y)
11
がん研 多目的コホート研究（JPHC Study)
肥満度（BMI）のがん全体の罹患に与える影響
12
非線形変換は有望
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.
カーネル法 = データの非線形情報，高次モーメントを抽出するために，デ
ータを高次元の特徴空間に写像する方法論．
13
カーネル法の要点
14
カーネル法の概略
– カーネル法の概念図

xi
xｊ
元のデータの空間

特徴写像
x
i
x
Hk
,
j
特徴空間
特徴空間で線形データ解析を施す!
e.g. SVM
– 特徴空間として望まれる性質：
• データのさまざまな非線形特徴を有していること
• 内積計算が容易にできること.
多くの線形データ解析の計算は内積に依拠している．
15
 計算の問題
– 高次情報の抽出
(X, Y, Z)  (X, Y, Z, X2, Y2, Z2, XY, YZ, ZX, …)
– 元の空間の次元が高いと 計算は実現できない!
e.g. 10000 次元のデータ,
２次までの特徴
10000C1
+ 10000C2 = 50,005,000
– 計算量爆発.
より効率的な方法が必要  カーネル法
16
特徴空間と正定値カーネル
– 特徴写像: 元の空間から特徴空間への写像
Φ: Ω →
,
↦Φ
– 特別な特徴空間（再生核ヒルベルト空間）を用いると，特徴ベクトルの
内積計算が関数値 (正定値カーネル)
, の評価に置き換えられる
 ( X i ),  ( X j )  k ( X i , X j )
kernel trick
– 内積計算さえできれば，特徴ベクトル (X).の陽な形は知らなくてもよ
い．
17
正定値カーネル
定義.
: 集合
カーネル : Ω
Ω→
が正定値であるとは
k ( x, y )  k ( y , x )
1) (対称性)
2) (正値性) 任意の点
 k ( x1 , x1 ) 




 k(x , x ) 
n
1

(Gram行列)
i.e.,
,…,

n
∈ Ω ∀
k ( x1 , xn ) 

 
k ( xn , xn ) 
c c j k ( xi , x j )  0
i , j 1 i
for any
に対し，
が半正定値
ci  R
18
– 例: Rm上
• Euclid内積
Gaussian
k ( x, y )  x T y
• Gaussian RBF カーネル

kG ( x, y )  exp  x  y
2
2

(  0)
• Laplace カーネル
Laplacian

k L ( x, y )  exp   i 1 | xi  yi |
m
• 多項式カーネル
k P ( x, y )  ( c  x T y ) d

(  0)
(c  0, d  N)
19
命題1.1
を内積 ⋅,⋅ を持つベクトル空間とし， Φ: Ω →
とする. : Ω Ω → を
,
により定義すると，
Φ
,
,Φ
,
を写像(特徴写像)
(kernel trick)
は正定値である.
– カーネルトリックを成り立たせる関数は，正定値カーネルである.
*Proof)

c c j k ( X i , X j )  i 1  j 1 ci c j  ( X i ),  ( X j )
n
n
n
i , j 1 i


n
c  ( X i ), j 1 c j  ( X j ) 
i 1 i
n

n
2
c ( X i )  0
i 1 i
20
– 正定値性は十分でもある.
定理1.2 (Moore-Aronszajn)
Ω上の正定値カーネル に対し，Ω上の関数からなるHilbert空間*
(再生核ヒルベルト空間, RKHS) が存在して，次が成り立つ．
1) ⋅, ∈
∀ ∈Ω .
⋅,
∈ Ω は で稠密
2) span
3) (再生性)
, ⋅,
for any ∈ , ∈ Ω.
*Hilbert空間: 内積を持つベクトル空間で，内積により決まるノルムが完備であ
るもの．
21
正定値カーネルによる特徴写像
– 正定値カーネル を用意
– 特徴空間 = RKHS
– 特徴写像:
Φ: Ω →
,…,
,
↦ ⋅,


feature map
xi
xｊ
Space of original data
↦
,…,
x
i
x
Hk
,
j
Feature space
⋅,
⋅,
– カーネルトリック（再生性）:
 ( X i ),  ( X j )  k ( X i , X j ),
– 正定値カーネルを与えれば十分.
• 特徴写像，特徴ベクトルを陽に知る必要はない.
• カーネル法の計算は，グラム行列
,
による計算となる.
22
カーネル法の例：カーネルPCA
23
PCAからカーネルPCAへ
– PCA: 線形な次元削減.
– カーネルPCA: 非線形な次元削減 (Schölkopf et al. 1998).
– 特徴空間でPCAを行う
max ||a||1 :
max || f ||1 :
Var[a T X ] 
1
N
1
Var[ f ,  ( X ) ] 
N
 T  (i ) 1
a  X 

N

i 1 
N
( j ) 
X
 j 1 


1
(i )
 f , ( X ) 

N
i 1 
N
2
N

( j)
 j 1 ( X ) 

N
24
2
次の形の
を考えれば十分

N
f   ci  ( X ( i ) )  N1  j 1  ( X ( j ) )
i 1
N

 f
(直交する方向は分散に効いてこない!) [Representer定理]
(カーネルトリックを使うと)
max Var
1
,Φ
T ~
||
f
||

1

c
KXc 1
subject to
 
~
KX
ij
1
N
 k ( X , X )  b 1 k ( X (i ) , X (b ) )
N
1
1
N
N
(a)
( j)
 a 1 k ( X , X )  2 a ,b 1 k ( X ( a ) , X (b ) )
N
N
(i )
( j)
(中心化Gram行列)
25
– 証明
•
∑
Var
,Φ
Φ
∑
∑
∑
∑
∑
∑
∑
Φ
,Φ
Φ
]
,Φ
≡
.
,∑
Φ
∑
•
∑
≡Φ
,Φ
Φ
∑
•
[Φ
とすると，
Φ
.
Φ
∑
,
∑
Φ
∑
,Φ
,
∑
,
Φ
∑
,
,
26
 カーネルPCAのアルゴリズム:
• 中心化Gram行列
の計算
N
~
の固有分解 K
•

 u uT

i 1
X
i i i
eigenvalues
1  2    N  0
u1 , u2 ,  , u N
unit eigenvectors
∑
• 第p主成分方向
Φ
• X(i)の第p主成分
Φ
∑
Φ
,
Φ
: 中心化特徴ベクトル
,Φ
∑
27
カーネルPCAの例
 Wine データ (UCI repository)
3種類のイタリアワインに関する，13 次元の化学測定値
178 データ.
クラスの情報はカーネルPCAには用いていない
4
Linear PCA
0.6
3
0.4
Kernel PCA (Gaussian kernel)
( = 3)
2
0.2
1
0
0
-0.2
-1
-0.4
-2
-0.6
-3
-4
-5
0
5
-0.8
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
28
カーネル法の構成要素
– 特徴空間上で線形データ解析を適用する. (Kernelization)
– 多くの場合，目的関数をカーネルによって書き直すことができる
 ( X i ),  ( X j )  k ( X i , X j )
f , ( X i )
– 解は以下の形で考えれば十分である（有限パラメータの問題に還元）
N
f   ci  ( X ( i ) ),
i 1
(Representer定理),
 すべての量がGram行列によって表現される(サイズ = データ数).
– 元の空間が高次元でも計算量の問題が生じない．Gram行列を計算し
た後は，データ数のみに依存した計算量．
以上はカーネル法一般に共通の要素である.
29
参考文献
 福水 「カーネル法入門」 １章 朝倉書店 2010.
 B. Schölkopf and A. Smola. Learning with kernels. MIT Press, 2002.
 赤穂 「カーネル多変量解析 ―非線形データ解析の新しい展開」 岩波書店
（2008）
30