"機械学習","信号解析","ディープラーニング"の勉強

HELLO CYBERNETICS

深層学習、機械学習、強化学習、信号処理、制御工学などをテーマに扱っていきます

カーネル法

 

 

ディープラーニングが現れる以前の機械学習で一斉を風靡した学習機械と言えばSupport Vector Machine(SVM)ですね。このSVMが大活躍した背景には、線形回帰・分離の手法を非線形へ拡張するカーネル法の存在がありました。

今回はそのカーネル法について解説します。

機械学習における非線形な問題の基本的な考え方は、線形では扱えなさそうなデータに対して変換を施して、その変換先で線形な処理ができるようにすることです。 

ではそのような上手い変換はいかにして獲得されるのでしょう。その変換先での空間の次元はいくつにすべきでしょう。様々な問題が浮上しますが、カーネル法では陽に変換の具体的な形を扱うことなく、内積演算(すなわちスカラー値)だけによって問題を解決します。

ニューラルネットでは上手い変換を学習によって獲得するため、高い表現能力を得る一方、学習の時点で多大なる時間を要するのが問題でした。

 

 

 非線形回帰・分離の基本的な考え方

まずは線形分離の例を見てみましょう。

クラス1のデータが赤、クラス2のデータが青のときに分離直線を以下のように引けます。

 

f:id:s0sem0y:20160522212549p:plain

 

はたして分離直線の位置(切片)や傾きはこれでいいのかという問題があります。パーセプトロン学習は、ともかく分離できる直線を適当に見つけ出し、SVMの場合は分離にきわどいデータ点からなるべく離れるように直線が引かれます。これらは個々の手法で詳しく学んでください。

 

今回着目すべきは、データ点が直線では分離できないような場合に、どのように問題を解決するかということです。こういう場合は、下図左のように2次元のデータ点x_n(この図ではデータ点が15個なのでn=1,...,15)が得られた場合に、これを適当な非線形変換φ(x_n)によってデータ点を変換してしまい、具合の良い変換であれば右図のように、クラス毎に固まった場所にデータ点が写ってくれます。よって変換先の新しい平面では線形分離ができそうです。

回帰の問題も基本的には同じで、データ点が直線上に配置されていないなというときに、データ点を変換してしまい、変換後の空間で直線を引きます。

 

f:id:s0sem0y:20160522213416p:plainf:id:s0sem0y:20160522213556p:plain

 

これらの手続きをすると、変換後の空間での直線は、元の空間に戻ってきたら曲線になっているので、結果だけ見れば、もとのデータ点にたいして曲線により回帰・分類を行ったことになります。

 

カーネル法

カーネル関数

カーネル法にとって最も重要なのはカーネル関数と呼ばれる内積演算に相当する関数です。

カーネル関数k()は2つのデータ点x,x'に対して以下で定義されます。

 

k(x,x')=φ(x)^Tφ(x')

 

です。ここでφ()はデータ点を変換する都合の良い関数です。今は、そのような関数φが見つかっているものとして考えてください。カーネル法ではこのカーネル関数が後々に重要な役割を担います。

 

回帰問題の例

基本的な線形回帰の問題を例に見て行きましょう。

普通の重回帰の問題であれば、データxに対して、重みベクトルwを使い、y=w^Txによって回帰をしたいという問題です。いまは、データを適当な変換φによって変換して、その値を使って回帰をしようとしているので、y=w^Tφ(x)によって回帰することを考えます。

 

例として、いろいろな部屋のx=(温度,体積)_nに対してt_n=圧力_nのデータが複数あるとき、これらの関係を知りたい場合に回帰を使います。つまりy=w^Tφ(x)というのは各x_nに対して、回帰線上の点y_nがなるべくt_nに近づくように決められるべきです。

つまり、

 

J(w)=\frac{1}{2} \sum_{n=1}{N} \left( w^Tφ(x_n)-t_n \right)^2

 

を最小化するようにwを決定します。オーバーフィッティングを避けるために正則化という手法が使えますから、今回は正則化項\frac{λ}{2}w^Twを用いて

 


J(w)=\frac{1}{2} \sum_{n=1}{N} \left( w^Tφ(x_n)-t_n \right)^2+\frac{λ}{2}w^Tw

 

を最小化します。正則化についての効用は以下の記事を参照してください。

s0sem0y.hatenablog.com

 

問題を同値な別の表現へ:双対問題

 

J(w)=\frac{1}{2} \sum_{n=1}^{N} \left( w^Tφ(x_n)-t_n \right)^2+\frac{λ}{2}w^Tw

 

wについて最小化すべくwについてJ(w)を微分し、J'(w)=0となるwを探します。まずJ'(w)=0は以下となります。

 

\sum_{n=1}^{N} \left( w^Tφ(x_n)-t_n \right)φ(x_n)+λw=0

 

通常はこれをwについて解いて、解を求めたいということですが、これを以下のように式変形していきます。

 

w=-\frac{1}{λ} \sum_{n=1}^{N} \left( w^Tφ(x_n)-t_n \right)φ(x_n)

 

ここで、a_n=-\frac{1}{λ} \left( w^Tφ(x_n)-t_n \right)として、そのベクトルをa=(a_1,...,a_N)^Tと置き、

 

w= \sum_{n=1}^{N}a_nφ(x_n)=Φ^Ta

 

と表現します。ここで、Φφ(x_n)Tn行目に持つ行列です。

ともかくw=Φ^Taは元々のJ(w)を最小化するために、微分して0と置いたときに出てきた式です。このwJ(w)代入すると

 

J(w)=J(a(w))=\frac{1}{2}a^TΦΦ^TΦΦ^Ta-a^TΦΦ^Tt+\frac{1}{2}t^Tt+\frac{λ}{2}a^TΦΦ^Ta

 

となります。ただしt=(t_1,...,t_N)です。

やけにΦ^TΦがたくさん出てくるので、この行列をK=Φ^TΦと置きます(N✕N行列になっている)。

このときKij列の成分はカーネル関数k(x_i,x_j)となっています。このKを使ってJ(a)を表現し直すと

 

J(a)=\frac{1}{2}a^TKKa-a^TKt+\frac{1}{2}t^Tt+\frac{λ}{2}a^TKa

 

と書くことができます。

 

この考えのメリット

w= \sum_{n=1}^{N}a_nφ(x_n)=Φ^Ta

a_n=-\frac{1}{λ} \left( w^Tφ(x_n)-t_n \right)

 

これらから、wを消去してしまえば

 

a=(K+λI_N)^{-1}t

 

となる。これを線形回帰のモデルに代入し直すと

 

y(x)=w^Tφ(x)=a^TΦφ(x)=k(x)^T(K+λI_N)^{-1}t

 

と得られる。新しいデータxに対する予測値は上記の式にデータを代入すればいいことになります。これのメリットは、もはや回帰式はカーネル関数によってのみ完全に表現されていることです。具体的な非線形基底関数φ(x)を取り扱う必要はなく、k(x,x')=φ(x)^Tφ(x')という値についてのみ考えれば良くなっています。これは非線形基底関数がどれだけ次元が高かろうが、(事実上無限次元だろうが)取り扱えるということです。一旦データを違う空間に写像することで、その写像先で線形回帰をしようという発想だったのが、カーネル法では、写像先を具体的に考えられない無限次元などでも写像を直接取り扱わずにその効用を得られるのです。

 

識別の問題、SVMへの応用

s0sem0y.hatenablog.com

前回の記事で、SVMへの基礎を説明しました。

サポートベクターマシンはマージン最大化という観点で、データを識別する上手い境界線(識別面)を決める手法です。

 

SVMの解法

t_n(w^Tφ(x_n)+w_0)\geq 1

 

のもとで

 

arg \min_{w,w_0} \frac{1}{2}|w|^2

 

 

を解き、識別面y=w^Tφ(x)+w_0

を決定することができます。上記の数式の導出は前回記事で行っています。

まずは双対問題を導くことです。非負のラグランジュ定数a=(a_1,...,a_N)^Tを導入してラグランジュ関数を

 

L(w,w_0,a)=\frac{1}{2}|w|^2-\sum_{n=1}^{N}a_n \left(t_n(w^Tφ(x_n)+w_0)-1 \right)

 

とします。ww_0それぞれについて微分して0と置いた式が、条件式になりそれぞれ以下のように得られます。

 

w=\sum_{n=1}^{N}a_nt_nφ(x_n)

 

0=\sum_{n=1}^{N}a_nt_n

 

これをラグランジュ関数に戻すことで、以下の式の最大化問題になります。

 

L(a)=\sum_{n=1}^{N}a_n-\frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk(x_n,x_m)

 

制約条件は以下です。 

 

a_n \geq 0

 

\sum_{n=1}^{N}a_nt_n=0

 

これが双対表現で、最大化問題はまたしてもカーネル関数によって表現されました。これはラグランジュ定数aに対する最大化問題になっており、この二次計画問題を解いてaを決めれば良いのです。

 

w=\sum_{n=1}^{N}a_nt_nφ(x_n)

 

を使えば、元々の識別平面の式は

 

y=w^Tφ(x)+w_0=\sum_{n=1}^{N}a_nt_nφ(x_n)^Tφ(x)+w_0=\sum_{n=1}^{N}a_nt_nk(x,x')+w_0

 

となります。結局双対問題でaを決定したあとは、新しいデータxについて上記の式y(x)の符号を調べれば識別ができるというわけです。(x_nは訓練データですから、実際には具体的に識別面がxの関数で決まっています)

 

まとめ

回帰でも識別でも、一次関数では通用しないときに、データをφ(x)で非線形写像して、その写像先で線形問題にしてしまうことを考えます。しかし、様々な非線形写像を試す際にはやけに高次元な、強いては無限次元への写像を考えると便利なことも多いです。

そのような場合に実際にその写像を計算することなく、しかしその効果だけを上手にいただく方法がカーネル法です。その肝はカーネル関数k(x,x')=φ(x)φ(x')というスカラー関数を考えることです。スカラー関数を考えてしまえば、事実上無限次元だろうが、計算するときには何も関係ありません。

 

そして、そうであるならば、わざわざ非線形写像φ(x)から考えずともカーネル関数k(x,x')を適当に作ってしまうところからスタートしてもいいはずです。これは非線形写像を作るよりもずっと簡単です。

 

 

具体的な理解を深めるためにはサポートベクターマシンの判定方法を手計算をして追ってみましょう。

s0sem0y.hatenablog.com