Python、機械学習

カーネル法、カーネルトリックとは何か?

非線形な関係性を線形な手法を用いて表現できるのがカーネル法です。

とはいえ、カーネル法と言われてもピンとこないと思います。本記事ではその意味を噛み砕いてみます。

サポートベクターマシン(SVM)を例に

例えば、サポートベクターマシーン(SVM)では、最適なパラメータを算出するためにラグランジュ未定乗数法と呼ばれる最適化手法が用いられます(詳細は割愛します)。

その計算式の中に、各プロットの内積が出現します。例えば、P(a1,b1), Q(a2,b2)という2つのプロットがあると、PQの内積PTQは a1a+ b1b2となります。(2,3)、(6,1)というプロットなら、内積は(2×6)+(3×1)=15になります。

2つのプロットの組み合わせにおいて計算した内積にもろもろの係数を掛ける、これを全プロットにおいて行います。例えば、全部で4プロットならプロットのペアは4C2=6通りあります。最後に、各ペアの内積x係数を足し合わせます。

この足し合わせたものを含む計算式を評価関数として、評価関数が最大になるように、サポートベクターマシーンの境界線の傾きや切片を決めます。

ここで言いたいのは、内積を計算して、最後に足し合わせる作業がありますよ、ということです。

直線の境界をを引いてうまく分離ができそうな場合は、普通に計算すればOKです。

線形分離は難しんだけど、ぐねぐねした曲線で境界であればうまく分類できそう・・・。そのような場合は「カーネル法」を使います。

まずは王道のやり方で非線形な境界線を引いてみます。

普通のやり方

線形分離できる空間にプロットを移す

a, bという2つの軸からなる2次元上にプロットがあります。このままではうまく線形分離できません。

そこで、これらのプロットを違う空間に移します。例えば、x, y, zという3つの軸からなる3次元空間に移します。違う空間にプロットを映すことを「写像」と言います。

写像のいう操作をφで表してみます。例えば、プロットPを別の空間に写像した後をP’とすると、P’=φ(P)と表せます。

プロット(a1, b1)が写像で(x1, y1, z1)に移る、その操作がφだということです。ベクトルで書くとP=[a1 b1]TP’=[x1 y1 z1]Tです。

もしプロットの移し方、つまり写像の中身がx=a, y=b, z=abだとしたら、

元の空間における座標(1, 2)は、写像したあとの空間では(1, 2, 2)という座標となります。

座標が(4, 3)というプロットなら、(4, 3, 12)に移ります。

逆に、三次元空間から元の二次元空間に戻すこともできます。

写像先の空間において(3, 6, 18)の座標をもつプロットは、元の空間に戻すと(3, 6)になります。簡単です。

このようにしてプロットを別の空間に移し、線形分離できるかどうかを判断します。できないなら元の空間に戻って、次は、さっきとは異なる写像を試してみる。これをひたすら繰り返します。

線形分離できる空間になるように、φをいろいろと振って試行錯誤するということです。

新しい空間上で線形分離する

晴れて線形分離可能なφが見つかったら、SVMの計算式を解くために内積を算出します。
写像先の空間でSVMの計算式を解くことになりますので、SVMの式に入る内積は、写像後のプロットP’Q’を使ったもの、つまりP’TQ’となります。P’TQ’は、φ(P)Tφ(Q)とも書けます。

このように、新しい空間にプロットを移してから真っ直ぐな線を引き、元の空間に戻す方法をカーネル法といいます

新しい空間で引いた直線は、元の空間に戻すとぐにゃっと曲がった曲線となります。線形モデルを新しい空間で適用することで、元の空間では非線形な手法を使わないと分類や回帰ができない場合であっても、線形チックに解くことができるようになります。

なお、新しい空間は往往にして元の空間よりも高次元になります。

サポートベクターマシン以外におけるカーネル法

新しい空間で真っ直ぐな線を引く方法はサポートベクターマシンに限らず、リッジ回帰でもよくて、リッジ回帰の場合はカーネルリッジ回帰と呼ばれます。また、新しい空間で主成分分析(PCA)をしてよりはっきり分類することを検討するカーネル主成分分析(カーネルPCA)もあります。

この「普通」のやり方では計算が大変

ただし、このやり方は実はかなり大変です。その理由について説明します。

基本的に、高次元の空間ほど、線形分離が実現しやすくなります。したがって、写像先の空間は高次元になりがちです。

P(a1, b1)というプロットが高次元空間に写像されると、プロットの座標は(x1, y1, z1, l1, m1, n1, …)のように増えます。

軸が増え、1軸目はこう、2軸目はこう、3軸目はこう…と決めるべき軸が多いため、写像の仕方のパターンが鬼のように増えます。これではφを探索するのが大変になります。

内積の計算も大変です。先ほどの3次元の例だとx, y, zの3軸のみでした。したがって、内積の計算は x1x+ xy1y+ z1z2だけで済みます。これが高次元になると…、たくさんかけ算して足し合わせないといけません。これもなかなか大変です。

カーネルトリックの登場

そこで登場するのがカーネルトリックです。

そもそも、カーネルって何者なのでしょうか?

カーネルとは、写像先における内積のことです。例えば、カーネルをKとすると、K= P’TQ’ = φ(P)Tφ(Q) です。カーネル関数と呼ぶこともあります。

PQはもとの空間上のプロット(座標)です。P=[a1 b1]TQ=[a2 b2]Tですね。先ほどの例ですと、φを通して写像するとP’ = φ(P) = [x1 y1 z1] = [a1 b1 a1b1]、Q’ = φ(Q) = [x2 y2 z2] = [a2 b2 a2b2]となります。そして、P’Q’の内積は a1a2 + b1b2 + a1b1a2bとなります。

カーネルKは a1a2 + b1b2 + a1b1a2bとなるわけですね。つまり、Kは a1, a2, b1, b2で決まる関数ってことです。これが、SVMの計算式の中に出てきます。

ここで気づきたいのが、Kが元の空間における2プロットの座標で決まる関数だということです。写像の仕方、つまりφの中身が変わっても、Kがa1, a2, b1, b2からなる関数になることに変わりはありません。

ここで、面倒くさがり屋ののび太くんが、「例えば、とりあえずK = paqa2+ rb+ sb+ t みたいな形にしてしまって、係数p, q, r, s, tを適当に振ってやれば、線形分離できるようにならないかなあ」と言いました。

SVMの評価関数が最大になるように係数p, q, r, s, tを決めてしまえばそれでおしまいということです。これがカーネル法です。

Kの関数の形をまじめに決めるなら、φを設定し、内積を求めないといけませんが、これじゃあ面倒くさい。ならば、Kは適当な関数の型にしてしまって、φを求めたり内積を一個一個求める手続きをすっとばそう。いい意味でズルなやり方です。

このように、写像先での内積を適当なシンプルな関数に置き換えて計算をラクにする方法がカーネルトリックです

線形分離できる写像の答えは一つしかない、という訳ではありません。線形分離可能にする写像は幾通りもあるはずです。そのどれか1つが見つかればよい。Kを適当な関数にしてしまうやり方でも、そのどれか1つと結果的にBINGO!するよってイメージです。

しつこいですが、、、φを振って線形分離可能なφを決めて、さらに内積をとるなんてめんどくさい、Kを適当な関数の形にして、それをSVMの計算式に放り込んでしまおう、それでその関数のパラメータの最適値を求めよう、そうすると結果的にSVMの精度が良くなる。試しにKからφを逆算して、φが作る高次元空間を可視化したら、ああ確かに線形分離できているわー、みたいなノリです。

カーネルトリックでよく使われる関数の型

Kに用いる関数の型はいくつかあって、SVMでよく使われるのはRBFカーネル(ガウシアンカーネル)という関数です。RBFカーネルにしてしまって、パラメータ(σの1個のみ)を最適な値にしたらおしまいです。。

RBFカーネルの他に、多項式カーネル、フーリエカーネルというものもあります。上の例で取り上げた、K = paqa2+ rb+ sb+ t というものは1次の多項式カーネルです。

アルゴリズム(SVM, ガウス過程…)やデータによってどの型が最もよく線形分離できるかが変わってくると思いますので、精度を求めるなら関数の型を色々振ってみることです。

Kに使われる関数の型はだいたい決まっているのですが、本来は何でもよいはずです。経験上、というか、さまざまなケースでうまくいくのがRBFカーネルという型である、いう理解です。