カーネル法といくつかの応用

はじめに

この記事はQiitaのアドベントカレンダーに掲載する予定のものです.
カーネル法はいろいろな分野に応用されており,本記事ではそれを紹介していきます.

カーネル法の基礎

簡単な概要としてはカーネル法とは例えば\mathcal{R}^2のデータだとしたら,その再生核ヒルベルト空間への写像を考えて,そのデータに対してデータ分析を行います.

カーネル関数とは

(半)正定値性を満たす関数(k:\mathcal{X} \times \mathcal{X} \to \mathbb{R})のことカーネル関数といいます.
集合\mathcal{X}の二つの要素x,x^{'}に対し,カーネル関数k(x,x^{'})x,x^{'}それぞれの特徴ベクトルの内積

k(x,x^{'})=\phi(x)^{T}\phi(x^{'}) = \sum_{m=1}^d \phi_m(x)\phi_m(x^{'})

として定義される.

正定値性

\mathcal{X}を集合とするとき,正定値性とは以下の2条件を満たすカーネル k:\mathcal{X} \times \mathcal{X} \to \mathbb{R}を(\mathcal{X}上の)正定値カーネル(positive definite kernel)といいます.
・対称性:任意のx,y\in \mathcal{X}に対しk(x,y)=k(y,x)
・正値性:任意のn \in \mathbb{N},x_1, \dots , x_n \in \mathcal{X}, c_1, \cdots ,c_n \in \mathbb{R} に対し,
\sum_{i,j=1}^n c_i c_j k(x_i, x_j) \geq 0

正定値カーネルの定義で用いられる正値性は,数学的には対称行列の半正定値性と呼ばれます.これはカーネル法の分野の習慣のために正定値カーネルと呼ばれる訳です.

グラム行列

行列Aに対してA^TAという行列をグラム行列といいます.
また,カーネル法で扱うデータ分析におけるグラム行列とは以下のようなものをいいます.

    \[K=\left(\begin{array}{cccc}k(x_1,x_1) & k(x_2,x_1) & \cdots & k(x_n,x_1) \\k(x_1,x_2) & k(x_2,x_2) & \cdots & k(x_n,x_2) \\\vdots & \vdots & \ddots & \vdots \\k(x_1,x_n) & k(x_2,x_n) & \cdots & k(x_n,x_n)\end{array}\right)\]

カーネルを設計するということはこのグラム行列を計算することと等しいです.(詳しくは参考文献を読んでください.)

再生核ヒルベルト空間

ヒルベルト空間Hとは

再生核ヒルベルト空間に行く前にまずヒルベルト空間の定義です.
ヒルベルト空間\mathcal{H}(または単に\mathcal{H}とも書く)は以下の内積の公理を満たすベクトル空間\in\mathbb{R}であるとする.
関数\langle\cdot,\cdot \rangle_\mathcal{H}:\mathcal{H} \times \mathcal{H} \to \mathbb{R}はヒルベルト空間\mathcal{H}の内積とする.

(ちなみに\langle \rangleはブラケット記法といいよく量子力学などで使われる記法です.ブラベクトル(左の括弧)とケットベクトル(右括弧)の内積を表してます.)

また,次の条件を満たします.
1.線形性:\langle \alpha_1 f_1 + \alpha_2 f_2,g\rangle_\mathcal{H} = \alpha_1 \langle f_2,g\rangle_\mathcal{H} + a_2\langle f_2,g\rangle_\mathcal{H}
2.対称性:\langle f,g \rangle_\mathcal{H} = \langle g,f\rangle_\mathcal{H}
3.正値性:\langle f,f \rangle_\mathcal{H} \geq 0 かつ \langle f,f \rangle_\mathcal{H} = 0 \quad f=0のときになりたつ.

またノルムを以下のように定義することが出来る.
||f||<em>\mathcal{H} := \sqrt{ \langle f,f \rangle </em>\mathcal{H} }によってfのノルムの定義が出来ました.
このように内積をとることが出来る空間の事をヒルベルト空間といいます.(ここでは,完備性については議論しないこととします.)

やっと再生核ヒルベルト空間です.カーネル法で一番重要な空間です.
上で定義したカーネル関数の定義を思い出してください.上にスクロールするのも面倒だと思うのでもう一度張ります.

    \[k(x,x^{'})=\langle \phi(x)^{T}\phi(x^{'}) \rangle _\mathcal{H}\]


これがカーネル関数でした.このとき再生核ヒルベルト空間では次の性質を持ちます.

1.任意のxに関して,k(\cdot,x)\in \mathcal{K}
2.任意の関数f\in\mathcal{K}に対して,f(x)= \langle f, k(\cdot,x) \rangle _\mathcal{K}
特に2を再生性といいます.
\mathcal{K}はパラメータベクトルと特徴ベクトルの内積で定義される関数の全体の集合です.

定理の中の再生性は,\mathcal{K}の中の任意の関数fとカーネル関数の内積がその関数の値になるという特徴的な性質があります.これが再生核ヒルベルト空間と呼ばれるゆえんであり,特にヒルベルト空間\mathcal{K}を再生核ヒルベルト空間(RKHS:Reproducing Kernel Hilbert Space)といいます.また,カーネル関数kのことをその再生核といいます.

動画による理解

カーネルサポートベクトルマシンの動画で再生核ヒルベルト空間へデータを射影(多項式カーネルを用いて)してデータを分離する超平面を求めている動画になります

正定値カーネルの例

m次元ユークリッド空間\mathbb{R}^m上の正定値カーネルの例を示します.

・指数型

    \[k_E(x,y)=exp(\beta x^{T}y) \quad (\beta > 0)\]

・ガウスRBF(radial basis function)カーネル

    \[k_G(x,y)=exp(-\frac{1}{2\sigma^2}||x-y||^2) \quad (\sigma>0)\]

・ラプラスカーネル

    \[k_L(x,y)=exp(-\alpha \sum_{i=1}^n |x_i-y_i|) \quad (\alpha > 0)\]

・多項式カーネル

    \[k_P(x,y) = (x^{T}y+c)^d \quad (c \geq0,d\in \mathbb{N})\]




ラドマッハ複雑性

統計の問題で確率的上界を求めたい場面があります.
そのようなときに用いられることがあるのが,ラドマッハ複雑性です.

集合A \subseteq \mathbb { R } ^ { m }が与えられた時,集合Aのラドマッハ複雑性は次のように定義されます.

    \[\operatorname { Rad } ( A ) : = \frac { 1 } { m } \mathbb { E } _ { \sigma } \left[ \sup _ { a \in A } \sum _ { i = 1 } ^ { m } \sigma _ { i } a _ { i } \right]\]



\sigma _ { 1 } , \sigma _ { 2 } , \dots , \sigma _ { m }はラドマッハ分布から抽出されたか独立したランダム変数です.


誤差解析

更新します.すいません.

カーネル法を使っている論文

Learning deep kernels for exponential family densities

Li Wenliang, Dougal Sutherland, Heiko Strathmann, Arthur Gretton

 https://arxiv.org/abs/1811.08357

更新します、すいません。

さいごに

コメントを残す

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください