【統計学修士の備忘録】#6 サポートベクターマシン

2024年6月6日 08:19

こんにちは、ぽむぽむです。今日は名前がかっこいい Support Vector Machine（SVM）について学習したことを記録します。日本語では何と呼ばれているのでしょうか…。調べても出てこなかったので気になります。

SVMの基本的な考え方は、データを境界線の様なもので区切ることです。二次元のデータだったら、こんな風に区切れたら嬉しいですよね。

ところがどっこい、現実世界ではそうは問屋が卸さない。データが入り乱れていて、簡単に２つに分けられないことがほとんどです。そこで、①境界を曖昧にして、②軸を変えることで、この問題を解決していきます。

まずはデータが綺麗に区切られることを想定した Maximal Margin Classifier から始めて、その次に境界を曖昧にした Support Vector Classifier、そして最後に Support Vector Machine という風に発展させていきます。

Maximal Margin Classifier

まずは語句の説明から。p次元空間において、p-1次元の平坦な部分アフィン空間のことを Hyperplane （超平面）と呼びます。例えば、二次元空間だったら p-1=1 で、超平面はただの線になりますし、三次元だったら p-1 = 2なので、ただの面です。これを概念上、四次元、五次元、それよりもっと高次元の空間にも当てはめていくものになります。高次元になると概念上でしか存在しないものがたくさん出てくるので嫌ポムです。

この超平面を数式で表すと、

$$
\beta_{0} + \beta_{1} X_{1} + \cdots + \beta_{p} X_{p} = 0
$$

となるので、この右側が $${>0}$$ になるか$${<0}$$ になるかで、Xが超平面のどちら側にいるのか分かるというイメージです。

例えばこの図では、この黒い線が超平面です。また、矢印で書かれている各点と超平面の距離のうち最短のものをマージンと呼びます。2つのクラスをくっきり分けるためには、2クラス間の距離が最大化する必要があるので、以下の最適化問題を解くことでベストな超平面を得ることができます。

$$
maximize_{\beta_{0},…,\beta_{p}} M \\
\text{subject to } \sum_{j=1}^{p}\beta_{j}^{2} =1, y_{i}(\beta_{0} + \beta_{1} X_{1} + \cdots + \beta_{p} X_{p}) \geq M \text{ for all } i=1,…,n
$$

ここで$${y_{i}}$$は各点のクラスを表しており、超平面のどちら側にいるかによって -1 あるいは 1 となるものです。

それでは、このような場合はどうでしょうか。

一本の境界線で区切ることは不可能ですので、MMCはこの様な場合に用いるのには適していません。

Support Vector Classifier

なぜSVCが必要となってくるかは、この図を見れば分かると思います。

(2,1) あたりに青が1点加わっただけで境界線が大きく変わってしまっています。このように1点の変化にセンシティブな境界線を用いていては予測の精度が落ちてしまいますので、よりロバストな分類器が必要となります。

そこで、この問題を解決するのが SVC です。SVC は一部の点がマージンの内側にのってしまうことや、超平面の逆側にのってしまうことを許します。

例えば、左の図では1と8がマージンの内側にのっており、右の図では、11と12が超平面の逆側にのっています。これを許すことで超平面から離れている点たちの分類が、ちょっとやそっとのことで変わることはほとんどなくなるという仕組みです（分類がロバストになります）。

ではこの様な分類器を数式で表すと以下の様になります。

$$
maximize_{\beta_{0},…,\beta_{p}, \epsilon_{1}, …, \epsilon_{n}} \\
\text{subject to } \sum_{j=1}^{p}\beta_{j}^{2} =1, \\
y_{i}(\beta_{0} + \beta_{1}X_{i1} + \cdots + \beta_{p}X_{ip}) \geq M(1-\epsilon_{i}), \\
\epsilon_{i} \geq 0, \sum_{i=1}^{n} \epsilon_{i} \leq C
$$

3行目まではMMCとほとんど同じですが、マージンが$${M}$$から$${M(1-\epsilon_{i})}$$に変わっています。この$${\epsilon_{1},…,\epsilon_{n}}$$はスラック変数と呼ばれ、各点がどこまでマージンより内側、あるいは超平面より逆側に行くのを許すのか調整することで、超平面に緩みを持たせます。$${\epsilon_{i}=0}$$だったら点$${i}$$はちゃんとマージンより外側にいますし、$${\epsilon_{i}>0}$$だったらマージンより内側、$${\epsilon_{i}>1}$$だったら超平面の逆側にいます。

また、$${\epsilon_{i}}$$の合計である$${C}$$は全体としてどれだけ緩みを許すのか調整します。実はこの$${C}$$もまた、バイアスと分散のトレードオフに大きく関わっています。$${C}$$が大きいほど、マージンの内側に多くの点が乗ることを許すので、マージンが広がります。そうすると、確かに間違った観測点を多く含むのでバイアスは大きくなりますが、逆に、超平面は動かなくなるので分散は小さくなります。

ちなみに先ほどの最適化問題を解くと、マージンの内側にあるデータたちだけが超平面を決めることがわかります。彼らのことをサポートベクターと呼ぶのですが、SVCの名前はここから来ているのですね。

このSVCもMMCに比べると大分柔軟なモデルになりましたが、やはり線形の境界ということで、以下の様な場合には上手く区切ることができません。

そこで必要になってくるのが、非線形の境界です。

Support Vector Machines

境界を非線形にするためにはどうすれば良いでしょうか。1番シンプルなアイディアは特徴空間の次元を上げることです。具体的には、先ほどの最適化問題に $${X_{1}^{2},…,X_{p}^{2}}$$を加えて

$$
maximize_{\beta_{0},…,\beta_{p}, \epsilon_{1}, …, \epsilon_{n}} \\
\text{subject to } \sum_{j=1}^{p}\beta_{j}^{2} =1, \\
y_{i}(\beta_{0} + \sum_{j=1}^{p} \beta_{j1}X_{ij} + \sum_{j=1}^{p} \beta_{j2}X_{ij}^{2}) \geq M(1-\epsilon_{i}), \\
\epsilon_{i} \geq 0, \sum_{i=1}^{n} \epsilon_{i} \leq C
$$

にすることなどが考えられます。

これを実装すると確かに境界が非線形になります。

しかし、先ほどの様な多項式が加わると途端に計算コストが高くなります。そこで、特徴空間を拡張して非線形の境界を作るという目的を変えないまま、計算コストを低くするために用いられるのがカーネル法です。

カーネル法

まずベクトルの内積から始めます。ご存知の通りベクトル$${x_{i}}$$と$${x_{i'}}$$の内積は

$$
(x_{i}, x_{i'}) = \sum_{j=1}^{p}x_{ij}x_{i'j}
$$

ですので、線形のSVCの分類器は

$$
f(x) = \beta_{0} + \sum_{i=1}^{n} \alpha_{i}(x,x_{i})
$$

と表すことができます。先ほどあった様に、サポートベクターのみが係数を決めるので、ここではサポートベクターに対応する$${\alpha_{i}}$$のみが非負になる、ということになります。ということで先の式を以下の様に変形します。

$$
f(x) = \beta_{0} + \sum_{i \in S} \alpha_{i}(x,x_{i})
$$

（ここでのSはサポートベクターのインデックスの集合です。）

あとはこの内積をカーネルに置き換えるだけで完成です。カーネルは以下の定義を満たしていれば、どんな関数でもOKです。

＜カーネルの定義＞
$${\phi(x)^{T}\phi(x') = K(x,x')}$$を満たす$${K:X \times X \rightarrow \mathbb{R}}$$
（$${\phi = X \rightarrow F}$$は入力空間を高次元特徴空間に非線形写像する関数。）

※ただし、$${K}$$は正値かつ対称（PDS）でないと$${\phi}$$の存在が保証されないので、これだけは制約になります。

まあつまり、理由はよく分かりませんが、カーネルを使えば$${\phi(x)^{T}\phi(x')}$$をわざわざちゃんと計算しなくとも、$${x,x'}$$をもっと簡単な関数Kにインプットして計算すれば同じ結果になるよ、ということでしょうか。

例えば多項カーネルというものがあるのですが、

$$
K(x_{i}, x_{i}') = (c+(x_{i}, x_{i'}))^{d}= (c+\sum_{j=1}^{p} x_{ij}x_{i'j})^{d}
$$

さえ計算すれば、d次元多項式に必要な内積（$${_{p+d}C_{d}}$$個の基底関数）が全て揃うようです。本当かと疑いたくなってしまいますが、まあでもいちいち新しい変数$${\phi(x)}$$を計算せずとも、元々知ってる$${x}$$だけを使って計算できるのでしたらそれに越したことはないですね。

分類器に話を戻すと、その様な具合で選んだカーネルを先ほどの分類器に入れると Support Vector Machine (SVM) の完成です。

$$
f(x) = \beta_{0} + \sum_{i \in S} \alpha_{i}K(x,x_{i})
$$

いつかより深くこのトピックを理解できるようになったら、またカーネルについて書きたいと思います。

この記事が気に入ったらサポートをしてみませんか？