再生核ヒルベルト空間を

1

再生核ヒルベルト空間を

用いた非線形データ解析法

情報・システム研究機構 統計数理研究所

（兼）総合研究大学院大学

福水 健次

2

Outline

„

イントロダクション

„

正定値カーネルと再生核ヒルベルト空間

„

正定値カーネルによるデータ解析 ～ カーネル法 ～

„

独立性、条件付独立性と再生核ヒルベルト空間

„

カーネル正準相関分析の統計的性質

„

おわりに -

3

イントロダクション

„

線形のデータ解析

古典的なデータ解析 データの行列表現

⇒ 線形の処理 （主成分分析，正準相関分析，線形回帰．．．）

⎟⎟

⎟⎟

⎟

⎠

⎞

⎜⎜

⎜⎜

⎜

⎝

⎛

=

N m N

m m

X X

X X

X X

X

"

#

#

"

"

1

2 2

1

1 1

1

m

次元

点のデータ ∈ R

4

„

線形データ解析の例

線形回帰分析

線形識別（２クラス）

問題

データを説明するのに最適な 超平面

を求めよ

X Y

問題

赤： クラス１に属するデータ 青： クラス２に属するデータ ２クラスを識別するのに最適な

超平面

を求めよ

5 …

線形回帰の解

„

最適性の基準設定

最小２乗誤差

このとき、２乗誤差

線形なデータ解析を支えるもの

„

内積（相関）の計算 ＋ 線形代数 ＋ α

„

線形で十分か？

∑

a

X a

1Y min 2

[

]

a −2 +

min

( ^{X X} ) ^{X Y}

a ˆ =

（簡単のため

省略）

Y X X

X X Y Y

Y

−

(

)

6

„

非線形データ解析の重要性

-6 -4 -2 0 2 4 6

-6 -4 -2 0 2 4 6

線形識別不能

0 5

10 15

20 0 5

10 15

20 -15

-10 -5 0 5 10 15

線形識別可能

) 2

, , ( ) , ,

( z

z

z

= x

x

x

x

7

„

カーネル法の概略

高次元空間への写像を構成する方法論

データを高次元のヒルベルト空間（一般には無限次元）へ写像し、

解析しやすいデータに変換する。

カーネル法：

… H

内のデータに変換した後で線形の手法を用いる

… H

として再生核ヒルベルト空間を用いる

x_i Φ(x_i) z_i

Ω

→ H Ω

Φ :

^変換写像

Ω

： もとのデータの空間

H

： 高次元ベクトル空間

8

正定値カーネルと再生核ヒルベルト空間

9

正定値カーネル

„

正定値カーネル

Ω

：集合．

k(x,y)

が

上の正定値カーネルであるとは，次の２つを満たすことをいう

１．（対称性）

２．（正定値性） 任意の自然数

と，任意の

の点

に対し，

が（半）正定値．すなわち，任意の実数

に対し，

対称行列 のことを，グラム行列と呼ぶ

0 ) ,

1 (

, ≥

∑

j

i cicjk xi xj

(

)

→ R Ω

× Ω : k

(

)

⎟⎟

⎟

⎠

⎞

⎜⎜

⎜

⎝

⎛

=

) , ( )

, (

) , ( )

, (

1

1 1

1

n n n

n

x x k x

x k

x x k x

x k

"

#

%

#

"

n

×

行列

10

„

正定値カーネルの例

多項式カーネル

ガウスカーネル

… Fourier

カーネル

複素数値）

d T y c x

y x

k( , ) = ( + )

Rm

=

Ω

_（

d

：自然数，

）

⎟⎠

⎜ ⎞

⎝

⎛− −

= 1₂ ²

exp )

,

(x y y x

k σ

Rm

=

Ω

（

）

Rm

=

Ω k(x, y) = e ^{−1ωT(x−y)} (

ω

）

11

再生核ヒルベルト空間

集合

上の関数を要素に持つヒルベルト空間

が

再生核ヒルベルト空間（reproducing kernel Hilbert space, RKHS

） であるとは，

任意の

∈

に対して

^∈

^{があって，任意の}

∈

に対し

が成り立つことをいう．

… φ_x

のことを再生核という．

) (

, f x

f φ_x =

12

正定値カーネルと再生核ヒルベルト空間

„

定理

k(x,y) :

集合

上の正定値カーネル

Ω

上の関数からなるヒルベルト空間

が一意に存在して，

次の３つを満たす

(2)

有限和 の形の関数全体は

の中で稠密

（再生性）

注)

・

・・・

を固定した

変数関数

x k

k(⋅, )∈H ^{( x}

^∈

^{は任意に固定}

∑

= ⁿ_i c_ik x_i f ₁ ( , )

) , ( , )

(x f k x

f = ⋅

∀

∈

∈

13

„

正定値カーネルと RKHS

正定値カーネル ⇒

正定値カーネル

により定まる

は再生核を持つ

定理の

）

… RKHS

⇒ 正定値カーネル： 再生核

は正定値カーネルを定める

) , ( x

x = k ⋅ φ

正定値カーネル 再生核ヒルベルト空間

, f x

f _x =

⇒ φ

) ( )

,

(y x y

k =φ_x

⇒

∑

∑

∑

∑

n

i i x

n j

i i j x x

n j

i_{, 1}cicjk(xi,xj) _{, 1}c c φ _i ,φ _{j 1}cφ _i , ₁c φ _j ,

0

2

1 ≥

=

∑

i ciφx_i y

x

x y

x y

k( , ) =φ ( ) = φ ,φ ₍

_{対称性もわかる）}

(

正定値性

と定義

14

正定値カーネルによるデータ解析

15

„

カーネルによるデータ変換

データの非線形変換

データの空間 再生核ヒルベルト空間

＝ 特徴空間（feature space）

内積計算：

特徴空間における線形アルゴリズム

Æ

データの空間での非線形アルゴリズム

x_i Φ H_k

Ω x_ｊ

,

xi

φ

xj

φ x

k x

x 6 Φ ( ) = ( ⋅ , ) = φ

（

）

カーネル

カーネル

，プライン平滑化

) , ( )

, ( ), , ( )

( ),

(x Φ y = k ⋅ x k ⋅ y = k x y

Φ

・・・

16

カーネル法の例 – カーネル CCA –

„

正準相関分析（ canonical correlation analysis, CCA ）

２つの確率ベクトル

に対して、相関が最大となる方向を見つける

データ

に対して

b C b a C

a

b C a

YY T XX

T

T XY T

b a

n

m ˆ ˆ

max ˆ

R R

∈∈

(

)

T XY T

b T a

T

T T

b a

n m n

m

R R R

R

∈

∈

∈

∈ = max

] Var[

] Var[

] ,

max Cov[ _1/2

( )( )

∑

∑

∑

= _{N i}^{N i} _N ^N_j ^{j i} _N ^N_j ^{j T}

XY X X Y Y

Cˆ ¹ ₁ ¹ ₁ ¹ ₁

ただし

] ]) [ ])(

[

[( ^T

YX E Y E Y X E X

C = − −

17

„

カーネル CCA

Ω_X , Ω_Y

上の正定値カーネル

X

, …, X

φ

, …, φ

Y

, …, Y

φ

, …, φ

^{∈ H}

∈ H

( , ),

X

i

k

X

φ = ⋅ ( , )

Y

i

k

Y

φ = ⋅ ,

) ,

( )

,

~ (

1

1

∑

^⋅

−

⋅

=

X

i

k X k X

φ ⁼

^⋅

⁻

∑

^⋅

Y

i

k ( , Y )

k ( , Y ) φ ~

∑

∑

∑

=

=

=

∈∈ _{N i}^N _i^X + _{N N i}^N _i^Y + _N

N i

Y i X

N i

H g

H f

Y Y X X

Y X

Y

X f f g g

g f

1

2 2 1

1

2 2 1

1 1

, ~ , ~

, ~ , ~

max

H H H H

H H

ε φ

ε φ

φ φ

変換

とおいて関数データに対する

を書き下すと

18

„

グラム行列による表現

{ }

Span _i^{X N}

f

φ

∈ = ^{g ∈Span}

{ } ^φ

1

,

N X

i i i

f = ∑

a φ ^{g =} ∑

^b

^φ

2

, 1 1

1 1

1 , 1

( , ) ( , )

( , ) ( , )

N

X ij i j N a i a

N N

a j a b

a a b

N N

K k X X k X X

k X X K X X

=

= =

= −

− +

∑

∑ ∑

で十分

により表すと

(

) (

)

max

T

X Y

T T

a X N X Y N Y

b

a K K b

a K N ε K a b K N ε K b

∈

∈^R

+ +

R

ただし

Æ

固有値問題として解ける

19

-1 -0.5 0 0.5 1

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35

f(x)

-1 -0.5 0 0.5 1

-0.35 -0.3 -0.25 -0.2 -0.15 -0.1 -0.05 0

g(y)

-1 -0.5 0 0.5 1

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35

-0.35 -0.3 -0.25 -0.2 -0.15 -0.1 -0.05 0

y

x

y x

f(x) g(y)

Gaussian kernel is used.

) /

~ ||

||

exp( − z − z

σ

20

データ解析と関数空間

„

関数空間内での線形データ解析

線形データ解析のために必要な性質

„

内積（相関）の計算

ヒルベルト空間

„

「関数の値」が決まる

処理結果の利用

定理： 集合

上の関数を要素に持つヒルベルト空間

に対し、

任意の

∈

に対して

が連続汎関数であるとき、

は再生核ヒルベルト空間である

… RKHS

は、データ解析を行うのに自然な関数空間

空間

) (x f f

,

H → R 6

21

„

RKHS を使う利点

数理的な観点から

„ k

が

級ならば

に属する関数は

級

„ E_P[k(X,X)] <

∞ ならば

⊆

かつ包含写像は連続

情報処理的観点から

„

関数空間での内積計算が容易

„

従来の線形手法の非線形拡張が容易： 相関行列

グラム行列

„

非ベクトルデータの処理

もとのデータ空間はベクトル空間でなくてもよい

Æ

グラフデータ、ツリーデータ、ヒストグラムなどの処理

∑

∑

= _ia_ik X_i g _jb_jk X _j

f ( , ), ( , ) f , g ⁼

∑

22

独立性、条件付独立性と

再生核ヒルベルト空間

23

独立性と RKHS

„

特性関数による独立性の特徴づけ（確率論の復習）

確率ベクトル

と

が独立

[ ] [ ] [

]

X X

Y X

XY

T T

T

T e E e E e

e

E ^{−1ω −1η} = ^{−1ω −1η}

⇔ for all ω and η.

は様々な関数による非線形相関を調べるテスト関数

y

x ^T

T

e

e

,

[

]

Cov ^{1 1} =

⇔ e ^−ωTX e ^{−ηTY for all ω and η.}

24

„

RKHS による独立性の特徴づけ

H_X, H_Y

： 可測空間

上の

（有界で可測な正定値カーネル）

X

：

上に値を持つ確率変数

：

上に値を持つ確率変数

と

が独立

という特徴づけは可能か？

確率決定的

H

： 可測空間

上の有界で可測な正定値カーネルによる

上の確率測度全体

H

が確率決定的であるとは

が単射であることをいう。

[

]

[

] [

]

E_XY = _{X Y}

⇔ for all f ∈H _X , g∈H_Y

)]) (

[ (

*

,

X f E f

P 6 6

→ H

Π

25

定理１

直積 （

^で定まる

が確率決定的であるとき、

X

^と

^が独立

定理２（

）

(R^m, B_m)

^{に対して、ガウス}

^カーネル

は確率決定的である。

独立成分分析への応用

独立な

個の確率変数の線形変換像から、もとの確率変数を復元

[

]

[

] [

]

E_XY = _{X Y}

⇔

for all f ∈H _X , g∈H_Y

2

( , ) exp z 2z k z z

σ

⎛ − ⎞

= ⎜⎜⎝− ⎟⎟⎠

X ⊗ Y

H H

26

相互共分散作用素

„

相互共分散作用素の定義

X , Y:

可測空間

^{に値をとる確率変数}

H_X ^, H_Y ^: Ω_X , Ω_Y

^上の

（有界で可測な正定値カーネル）

有界作用素 を次式により定義することができる。

系３

Y X

YX H → H

Σ :

)]

( [ )]

( [ )]

( ) ( [

, f E f X g Y E f X E g Y

g _{YX XY X Y}

Y

−

=

Σ _H

for all f ^∈H _X ^, g ^∈H_Y

(

)

H_X ^, H_Y ^:

^{ガウスカーネルによる}

YX = O Σ

X

と

が独立

c.f. a^TC_YXb = Cov[a^T X ,b^TY]

27

条件付共分散作用素

„

共分散作用素の分解

相互共分散作用素 は以下のように分解できる

ただし

は有界作用素、

≦

かつ

„

条件付共分散作用素

Y X

YX H ^→ H

Σ :

1/ 2 1/ 2 YX YY

V

Σ = Σ Σ

( _YX ) ( _YY ), ( _YX ) ( _XX ) R V = R Σ N V = N Σ

2 / 1 2

/ 1

|X YY YY YX XY YY

YY

≡ Σ − Σ V V Σ

Σ ( ^{= Σ}

^{− Σ}

^Σ

^Σ

)

28

条件付独立性と RKHS

„

条件付共分散作用素と２乗誤差

定理４

c.f.

線形回帰の２乗誤差

„

条件付分散による表現

定理５

任意の

∈

^に対して

は

で稠密

YY XX

YY YY

T b YX

a

C C

C C

b X

a Y

m

E

1 2

,

| ) (

|

min

∈

∈

− + = −

R R

) ( ]

| ) (

[g Y X L² P_X

E = ⋅ ∈

⊕ R H X

[

]

, _| g E g Y X

g _{YY X X}

Y

=

Σ H

2

| inf ( ( ) [ ( )]) ( ( ) [ ( )])

, g E g Y E g Y f X E f X

g _XY

X f YY

Y X

−

−

−

= Σ H ∈H

29

„

条件付独立性の特徴付け

確率変数

に対し、

の特徴づけを考える。

定理６（

）

U, V, Y:

可測空間

に値をとる確率変数

H_U^, H_V^, H_Y ^{: Ω}_U ^{, Ω}_V ^{, Ω}_Y

^上の

（有界で可測なカーネルによる）

X = (U,V),

（直積）

H_X^, H_U

^{は定理５の}

を満たすとする。このとき、

さらに

が確率決定的であるならば

V U

X H H

H = ⊗

U V

Y ⊥ |

^{あるいは同値な条件}

X YY U

YY|

≥ Σ

Σ （≧は自己共役作用素の半順序）

U X

X

Y

YY U

YY_|

= Σ

⇔ ⊥ |

Σ

U X Y ⊥ |

30

条件付共分散作用素による次元削減

„

回帰問題における次元削減

回帰問題： 確率変数

が

にどう依存するかを調べる を推定する

回帰問題における次元削減

：

次元確率ベクトル

を満たす

×

（

）行列

を求める。回帰の低次元表現。

„

RKHS を用いた解法

)

| (Y X p

( | ) ( |

)

p Y X = p Y B X ( ⇔ Y ⊥ X | B

X )

[

]

B

Tr

min Σ ^{カーネル次元削減法}

（

）

31

カーネル CCA の統計的性質

32

統計的推測

„

統計的推測の原理

データの背後には、それを発生させる確率分布がある

有限個のデータを用いて、その確率分布あるいはそれから決まる量を 推測する

„

カーネル法の統計的推測としての見方

データの変換ではなく、確率変数の変換

に値をとる確率変数

から決まる量（関数）を、有限個のデータから推測する

„

統計的推測法の妥当性

一致性： 有限データからの推定量が、確率分布から決まる真の量に 収束するか？

) ,

( X

k ⋅ )

,

( X

k ⋅

33

カーネル CCA の作用素による表現

„

期待値によるカーネル CCA

„

最適解

ξ_∗, ζ_∗ :

の最大特異値に対する単位固有ベクトル

,

max ,

f g

g Σ f

f , Σ

f = 1, g , Σ

g = 1

1/ 2

* *

1/ 2

* *

XX YY

f g

ξ ζ

−

−

⎧ = Σ

⎪ ⎨

⎪⎩ = Σ

2 / 1 2

/

1 −

−

Σ Σ

Σ

=

V

34

„

有限サンプルに対するカーネル CCA

経験相互共分散作用素

カーネル

解

：

( ) 1 1 1

1 1 1

, ˆ

(

) ( )

(

)

( )

g Σ f = ∑

f X g Y − ∑

f X ∑

g Y

( ) ,

max , ˆ_YX^N

f g

g Σ f ^{subj. to}

^{f ,} ( ^{Σ ˆ}

^{+ ε}

^{I f} ) ^{= 1,}

( ^ˆ

)

,

1,

g Σ + ε I g = ˆ

, ˆ

ξ ζ ^{V ˆ}

^{: = Σ} ( ^ˆ

^{+ ε}

^I )

^{Σ ˆ}

( ^{Σ ˆ}

^{+ ε}

^I )

( ) 1/ 2

( ) 1/ 2

ˆ ( ˆ ) ˆ

ˆ ˆ

( )

ˆ

N

N XX N N

N

N YY N N

f I

g I

ε ξ

ε ζ

−

−

⎧ = Σ +

⎪ ⎨

= Σ +

⎪⎩

の最大特異値に対する単位固有ベクトル

35

„

解の一致性（収束性）

あるいは

は成り立つか？

どのような関数空間のノルムのもとで収束するか？

収束するための正則化係数

^{の条件は？}

*

*

, ˆ

ˆ f g g

f

→

→

*

*

, ˆ

ˆ ξ ζ ζ

ξ

→

→

36

カーネル CCA の一致性

Theorem 1

If V

is compact, and the regularization coefficient satisfies

then,

in probability as .

0,

( )

N

N

N

ε → ε → ∞ → ∞

ˆ ,

1,

N X

ξ ξ →

H

ˆ ,

1

N Y

ζ ζ →

H

N → ∞

Note: convergence of RKHS is very strong.

If the kernels are bounded, it is stronger than

the uniform norm.

37

Theorem 2

Suppose V

is compact, and the regularization coefficient satisfies

If ξ

and ζ

are included in R (Σ

) and R (Σ

), respectively, then

in probability as .

0,

( ).

N

N

N

ε → ε → ∞ → ∞

N → ∞

( ) ^{( )}

2( )

ˆ [ ˆ ( )] [ ( )] 0

X

N X N X

L P

f − E f X − f − E f X →

( ) ( )

2( )

[ ( )] [ ( )] 0

ˆ ˆ

N Y N Y L PY

g − E g Y − g − E g Y →

38

„

証明の核になる命題

命題

… Hilbert-Schmidt

ノルム

大数の法則

中心極限定理

上の命題は収束のオーダーに関する強い結果

) (

),

ˆ^{( )} −Σ = ( ^1/2 → ∞

Σ O_p N⁻ N

YX HS N

YX

2 1

2

|| ||

||

|| A

= ∑

A ϕ

（ { ϕ

}

：

）

∑

∑

∑

)]

( [ )]

( [ )]

( ) (

[ f X g Y E f X E g X

E −

→

f g

f

g,Σˆ_YX^(N) → ,Σ_YX

(

)

, Σ^{( )} − Σ f = O N^−1/2

g _YX^N _{YX p}

39

おわりに

„

再生核ヒルベルト空間を用いたデータ解析

… RKHS

： 関数の値が意味を持つヒルベルト空間

内積計算が容易

属する関数の連続性や微分可能性

ベクトルでないデータに対しても相関（内積）計算を可能にする

„

独立性、条件付独立性の特徴づけ

相互共分散作用素を用いた線形手法の非線形化

„

カーネル法の統計的性質

漸近的な性質、一致性

カーネル

の一致性のための正則化係数の十分条件

40

„

参考文献

… K. Fukumizu, F.R. Bach, and M.I. Jordan (2004)

Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces. Journal of Machine Learning Research.

5:73-99.

福水健次（

）「再生核ヒルベルト空間を用いた回帰問題における 次元削減法」 日本数学会２００３年秋季大会予稿集

… K. Fukumizu, F.R. Bach, and Arthur Gretton (2005) Consistency of kernel canonical correlation analysis.

ISM Research Memo 942.

… K. Fukumizu, F.R. Bach, and M.I. Jordan (2005)

Consistency of kernel dimensionality reduction. In preparation.

URL: http://www.ism.ac.jp/~fukumizu/