2019-06-23

サポートベクターマシンのお話

サポートベクターマシン（SVM）は，深層学習によらない機械学習の手法の一つとして広く知られており，あるデータに関する事前知識が全く無いような場合に有効な手法と言われています．

ここでは，個人的な備忘録として，SVMの考え方を少しずつ厳選して扱います．

お膳立て

今，図のような分布の「●と😀の二値分類」をしたいときに，パーセプトロン系のネットワークでモデルを構築した場合，その識別面（境界線）は次の図の点線になるかもしれない．

いろんな境界線の比較

パーセプトロンのようなネットワークでは，経験損失（empirical loss）の最小化によって学習が行われる．なので，境界線がスレスレであっても，訓練データに対して損失を最小化するように学習して引かれた正しい線である場合がある．しかしながら，境界線がスレスレだと，テストデータで分類した時に，「●と😀」が間違えて分類されてしまう可能性があり，あまり嬉しくない．

SVMは，この問題に対処することで汎化性能をあげようとしているモデルである．SVMの学習は，汎化損失（generalization loss）の最小化により行われる．着想としては，テストデータは訓練データと同じ確率分布に従っているものと仮定して，境界面（separator；識別面）と観測データの距離がなるべく大きくなるような境界面を選ぶことで，汎化損失の最小化を目指すものである．

SVMの境界面の例と用語定義

用語の定義

  • サポートベクトル（support vector）
    境界面（separator；識別面）にもっとも近い点のことをサポートベクトルと呼ぶ．サポートと呼ばれる所以は，サポートベクトルが境界面を「支えている」ことから来ているらしい．

    通常，サポートベクトルの数は本来のサンプルサイズよりも小さくなるので，SVMはパラメトリックなモデルよりも更新の計算量が少なく済む．（サポートベクトル以外のデータが変化しても，境界は変化しないため．）また，重要なベクトルだけを見ればよいので，汎化性能も向上すると考えられる．

  • マージン（margin）
    図中で点線によって囲われた範囲をマージンと呼ぶ．マージンは境界面と境界面からもっとも近い点（観測データ）との距離の2倍となる．

    SVMにおいて，「境界面と観測データの距離がなるべく大きくなるように学習する」ということは，「マージンをなるべく大きくするように学習する」ということを意味している．

用語の数式的定義

以降，簡単にではあるが数式で説明を行うため，あまり書かれていない基本的な部分の計算手法について説明する．

識別面の数式的表記

識別面は，入力データが $\boldsymbol{x}$ と表されるとき，以下のように表される．

$$ \boldsymbol{w^Tx} + b = 0 $$

ここで，$\boldsymbol{w}$ は重みベクトルであり，$b$ はバイアスベクトルである．また，各サポートベクトルが作る直線（上図の点線に相当する）は，$\boldsymbol{w^Tx} + b = 1$ か $\boldsymbol{w^Tx} + b = -1$ で定義される．

マージンの数式的表記

さて，$\boldsymbol{w^Tx} + b = 1$ となるような，$\boldsymbol{x}$ のうちの一つを，$\boldsymbol{x}_1$ とする．また，$\boldsymbol{w^Tx} + b = -1$ となるような，$\boldsymbol{x}$ のうちの一つを，$\boldsymbol{x}_2$ とする．

このとき，境界面と，サポートベクトル $\boldsymbol{x}_1$ の距離 $r_1$は，垂線の公式の拡張版を用いて，次のように表される．

$$ r_1 = \frac{\boldsymbol{w^Tx}_1 + b }{||\boldsymbol{w}||} $$

ここではイメージを掴むのが目的なので，垂線の公式については触れません．

したがって，マージン: $m$は次のように表される．

$$ \begin{equation} \begin{split} m &= \frac{\boldsymbol{w^Tx}_1 + b }{||\boldsymbol{w}||} - \frac{\boldsymbol{w^Tx}_2 + b }{||\boldsymbol{w}||}\\ &= \frac{\boldsymbol{w^T}(\boldsymbol{x}_1 - \boldsymbol{x}_2)}{||\boldsymbol{w}||}\\ &= \frac{2}{||\boldsymbol{w}||} \end{split} \end{equation} $$

ただし，$\boldsymbol{w^Tx}_1 + b = 1$ と $\boldsymbol{w^Tx}_2 + b = -1$ から，$\boldsymbol{w^T}(\boldsymbol{x}_1 - \boldsymbol{x}_2) = 2$ となることを用いた．

SVMの学習方法

SVMの学習方法は2種類あり，直感的な解き方としては，マージンを最大化する問題を解くことであり，そこから派生した解法も存在する．そのため，以下で紹介する2手法は双対問題と言われる．双対問題とは，ある最適化問題の制約条件を用いて，より最適化しやすい問題に置き換えて解くような問題のことをいい，どちらかの解が両方の解になる性質を持つ．

マージン最大化（主問題）

マージン最大化の定式化

さて，マージンは，$\frac{2}{||\bm{w}||}$ で定義されることを先ほど示した．マージンを最大化することは，重みベクトルのノルムを最小化することに他ならない．したがって，式でマージン最大化を表すと，$\argmax_{\bm{w}} \frac{2}{||\bm{w}||}$ となる．これでは，最適化をする際に計算の都合上扱いにくいので，大半の説明では以下が等価であるとみなしている．

$$ \argmin_{\bm{w}} \frac{1}{2} ||w||^2 $$

マージン最大化の制約条件

最適化のための制約条件について考える．入力データ $\{ \bm{x}_1, \bm{x}_2, \bm{x}_3, \dots, \bm{x}_n \}$ があったときに，それに対応する（正解）ラベルデータが，$\{ y_1, y_2, y_3, \dots, y_n \}$ であるとする．ただし，$y_i$ は，$1$か$-1$をとる．このとき，以下の制約条件が成り立つ．

$$ y_i (\bm{w}^T\bm{x}_i + b) \ge 1 \qquad{\rm for} \; i=1,\dots, n $$

したがって，マージン最大化は上記の制約条件をもとに，条件を満たす重みベクトルを探す問題に帰着される．

ラグランジュの未定乗数法による方法（補問題）

一方で，別の解き方も存在して，ラグランジュの未定乗数法を使う解き方がある．ラグランジュアンを活用することで，上記のマージン最大化問題は次のように書き換えられる．

$$ \mathcal{L}(\bm{w}, b, \alpha) = \frac{1}{2}||\bm{w}||^2 + \sum_{i=1}^{n} \alpha_i (1 - y_i(\bm{w}^T\bm{x_i} + b)) $$

このとき，最適化条件を考慮すると，以下が得られる．

$$ \begin{equation} \begin{split} \frac{\partial}{\partial \bm{w}} \mathcal{L} &= \bm{w} - \sum_{i=1}^{n} \alpha_i y_i \bm{x}_i = 0\\ \frac{\partial}{\partial b} \mathcal{L} &= - \sum_{i=1}^{n} \alpha_i y_i = 0 \end{split} \end{equation} $$

上記の最適化条件を，元のラグランジュアン $\mathcal{L}$ に代入して計算すると，以下が得られる．

$$ \mathcal{L}(\bm{w}, b, \alpha) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\bm{x}_i^T \bm{x}_j) \tag{1} $$

また，双対問題時のKKT条件を考慮することにより，追加の制約条件: $\alpha_i \ge 0$ を得られる．以上から，マージン最大化の問題は，ラグランジュ関数を活用することで，$\alpha$ を最大化する問題に落としこむことができる．式で表すと下記のようになる．

$$ \argmax_\alpha \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\bm{x}_i^T \bm{x}_j) $$

これは，二次計画問題であるため，ソルバーを使えば最適解を得ることができる．最適なベクトル $\alpha$ を見つけることができれば，最適化条件である，$\bm{w} = \sum_{i=1}^{n} \alpha_i y_i \bm{x}_i$ を用いて，重みベクトル $\bm{w}$ も芋づる式に求めることができる．また，バイアス $b$ についても，上述のマージン最大化の制約条件から算出することができる．これによって，識別関数を求めることができるので，ラグランジュの未定乗数法による方法で，SVMの学習ができることがわかった．

参考：ベクトルの微分
参考：KKT条件

2手法の比較

ラグランジュの未定乗数法を用いる手法の方が種々の利点がある．

  • $\mathcal{L}$ は凸関数であるため，唯一の大域最適解を見つけやすい．
  • サポートベクトル以外の$\alpha_i$ は0となるため，計算が少なく済む．

線形分離不可能なときは？

入力データが線形分離できない場合，非線形変換を施して高次元空間に写像してしまえば，分類可能となるときがある．例として，ある特徴空間 $F(\bm{x})$ が，次のように定義されるとする．

$$ F([x_1, x_2]) = (x_1^2, x_2^2, \sqrt{2} x_1 x_2) $$

このとき，$F(\bm{x})$ でのラグランジュアン: 式(1)は次のように書き換えられる．

$$ \mathcal{L}(\bm{w}, b, \alpha) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j F(\bm{x}_i) F(\bm{x}_j) \tag{2} $$

式(2)の値を求めるには，高次元空間 $F(\bm{x})$ での内積 $F(\bm{x}_i) \cdot F(\bm{x}_j)$の値を計算する必要がある．今回の例の場合，高次元空間における内積を計算してみると，以下のようになる．

$$ \begin{equation} \begin{split} F(\bm{x}_i) \cdot F(\bm{x}_j) &= \begin{bmatrix} x_{i_1}^2\\ x_{i_2}^2\\ \sqrt{2} x_{i_1}x_{i_2} \end{bmatrix} \cdot \begin{bmatrix} x_{j_1}^2\\ x_{j_2}^2\\ \sqrt{2} x_{j_1}x_{j_2} \end{bmatrix}\\ &= x_{i_1}^2 x_{j_1}^2 + x_{i_2}^2 x_{j_2}^2 + 2x_{i_1}x_{i_2}x_{j_1}x_{j_2} \end{split} \end{equation} $$

高次元空間に変換してから内積を計算する手間がお分かりになったと思う．

そんなところに朗報で，実は上記の内積は変換前における，$(\bm{x_i}\cdot\bm{x_j})^2$ の演算結果に一致する．この$(\bm{x_i}\cdot\bm{x_j})^2$ を，カーネル関数（kernel function）と呼ぶ．カーネル関数さえわかれば，元の空間でのベクトル演算だけで済むので，逐一各入力ベクトルの値を高次元空間に写像する処理は必要なく，少ない手間で線形分離できないデータに対応することができる．このことをカーネルトリックともいう．

種々のカーネル関数

カーネル関数はいくつか種類があり，多項式カーネルとガウスカーネルが有名である．

多項式カーネル

多項式カーネルは次のように定義される．

$$ K(\bm{x}_i, \bm{x}_j) = (\bm{x}_i^T \bm{x}_j + 1)^d $$

ガウスカーネル

ガウスカーネル（RBFカーネルと表記されていることが多い）は次のように定義される．

$$ K(\bm{x}_i, \bm{x}_j) = \exp(-\beta||\bm{x}_i - \bm{x}_j||^2) $$

ただし，$\beta$は正の定数．なお，実際にSVMでデータ分類をする際には，ガウスカーネルを使う場合が多いようである．

参考：SVMのカーネルについて

ソフトマージンとハードマージン

理想的な環境であればデータにノイズが入ることはない．しかし，現実にはそうはいかない．今まで説明してきたSVMの考え方を元に，ノイズの入ったデータを分類させると，ノイズにサポートベクトルが左右されてしまうため，分類がうまくいかなくなってしまう．そこで，ソフトマージンという考え方が一般に知られている．反対に，これまで説明してきたSVMのマージンの決め方は，ハードマージンと呼ばれる．

SVMを実用する

今回は量が多くなってしまったので理論だけに留めておきますが，Pythonのライブラリである，scikit-learnにはSVMが実装されています．これを使えばひとまずは実データで分類ができるでしょう．

参照：scikit-learnにおけるSVMのドキュメント