サポートベクトルマシンで非線形問題を解くときにカーネルトリックというものが使われますが、ざっくり本質を理解するのに骨が折れました。間違っているかもしれませんが、私なりに理解したことを整理しておこうと思います。
分かっている特徴量で散布図を描いた場合に、明らかに線形分離可能な場合
ふつうのサポートベクトルマシンの話です。
サポートベクトルマシンでは、マージンを最大化するための直線を明らかにするために、重み$w$とバイアス$b$を求めたいわけですが、それを真っ向から解くのは難しいです。
そこで、双対問題と言われる、別の問に置き換えます。置き換えに利用されるのが、ラグランジュの未定乗数法です。いかにも難しそうですね。ここでは詳細には立ち入りませんので、ご安心ください。
どんな問題に置き換えるかというと、色々と小難しい変換を経て、最終的には以下で構成される関数を得ます。
- $α$というパラメータ （ラグランジェ乗数と呼ばれます）
- $x^{(i)\mathrm{T}}x^{(j)}$ （分かっている特徴量の内積）
この関数を最大化する$α$を求める、という問題に置きかわります。
後者の$x^{(i)}$ と $x^{(j)}$ は、それぞれ別々の特徴量です。アヤメ(iris）の話でいうと、「がく片の長さ」と「花弁の長さ」みたいなものですね。
後者については実際のデータがあるわけですから、未知なのは前者の$α$だけです。後者に実際のデータを代入すると、$α$についての方程式になりますので、簡単に$α$の値が分かります。その$α$をもとに、重み$w$とバイアス$b$を導出し、マージンを最大化する直線が明らかとなります。
分かっている特徴量で散布図を描いた場合に、明らかに線形分離できない場合
この場合、分かっている特徴量から、新たな特徴をつくって、その新たな特徴量をつかって表現する座標空間上で、線形分離を試みます。
この場合も、色々と小難しい変換を経て、最終的には以下で構成される関数を得ます。
- $α$というパラメータ （ラグランジェ乗数と呼ばれます）
- $\phi(x^{(i)})^{\mathrm{T}}\phi(x^{(j)})$
さきほどの $x^{(i)\mathrm{T}}x^{(j)}$ が、$\phi(x^{(i)})^{\mathrm{T}}\phi(x^{(j)})$ に置き換わっただけです。
$\phi()$は、分かっている特徴量から新たな特徴量を算出する関数です。本当は、この関数がものすごく大事なはずです。なぜなら、新たな特徴量がどんなものかによって、新たな座標空間上で線形に分離できるかどうか決まってくるわけですから。
理論上はそうなんですが、以下の問題が生じます。
- ふつうは、この$\phi()$という関数を見つけるのが大変だと思われます。
- $\phi()$が分かったとしても、さきほどの内積 $\phi(x^{(i)})^{\mathrm{T}}\phi(x^{(j)})$ を計算しようとすると、ものすごい計算コストになります。
この二つの問題を解決するのが、いわゆる「カーネル関数」です。
カーネル関数は $\phi(x^{(i)})^{\mathrm{T}}\phi(x^{(j)})$ を置き換えるもので、いくつか種類があります。
$\phi()$ がどんなものであったとしても、$\phi(x^{(i)})^{\mathrm{T}}\phi(x^{(j)})$ の計算結果は、カーネル関数での計算結果と同じになります。言い換えると、$\phi()$ の内容については考えなくてもよいわけです。すごいですね。これが「トリック」と呼ばれる１つ目の理由です。
そして、カーネル関数は計算コストが低いです。これが「トリック」と呼ばれる２つ目の理由です。たとえば代表的なガウスカーネル（RBFカーネル）は、以下のとおりです。
exp(-\frac {||x^{(i)} - x^{(j)}||^2} {2\sigma^2})
二つの特徴量$x^{(i)}$ と $x^{(j)}$ と、ハイパーパラメータ$2\sigma^2$ （我々が自由に決めてよいパラメータ）から、$\phi(x^{(i)})^{\mathrm{T}}\phi(x^{(j)})$ の計算結果が、簡単に得られてしまいます。
あとは、線形分離できる場合と同様に、$α$を求め、それをもとに重み$w$とバイアス$b$を求めます。重み$w$とバイアス$b$によって定義される面こそが、新たな座標空間上で、マージンを最大化する面となります。
なお、カーネル関数には種類があり、どれを選ぶかによって結果が変わってきます。実際、scikit-learnなどのライブラリでは、サポートベクトルマシンを簡単に利用できますが、そのAPIでカーネル関数を指定できるようになっています。
参考
https://kenyu-life.com/2019/04/22/svm_kernel/
https://www.slideshare.net/moa108/8-28571831