1. はじめに
本記事はJDLA E資格の認定プログラム「ラビットチャレンジ」における機械学習のレポート記事である。
本記事では機械学習における「サポートベクターマシン（SVM）」について要点をまとめている。
【ラビットチャレンジ】要点のまとめ - 機械学習 その１
【ラビットチャレンジ】要点のまとめ - 機械学習 その２
【ラビットチャレンジ】要点のまとめ - 機械学習 その３
【ラビットチャレンジ】要点のまとめ - 機械学習 その４
【ラビットチャレンジ】要点のまとめ - 機械学習 その５
【ラビットチャレンジ】要点のまとめ - 機械学習 その６
2. サポートベクターマシン（SVM）
2.1. サポートベクターマシン（SVM）
- 2クラス分類のための機械学習手法であり、線形モデルの正負で2値分類する
- 最も近いデータ点との距離（マージン）が最大となる線形判別関数を求める。
目的関数：$ \smash{ min_{w, b}\dfrac{1}{2}||w||^{2} } $
制約条件：$ \smash{ t_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i} + b) \geq 1} $ $ (i=1,2, \cdots , n) $
$ \qquad \smash{ \boldsymbol{w} } $：パラメータ
$ \qquad \smash{ b } $：バイアス
$ \qquad \smash{ t_{i} } $：分類。$-1$か$1$
$ \qquad \smash{ \boldsymbol{x}_{i} } $：説明変数
$ \qquad \smash{ i } $：説明変数のインデックス。$1～k$までをとる
2.2. ラグランジュの未定乗数法
- サポートベクターマシンにおいて、目的関数の制約付き最適化問題を解くにはラグランジュの未定乗数法を用いる。
-
制約$ g_{i}(\boldsymbol{x}) \geq 0(i = 1,2, \cdots , n) $の下で、$ f(\boldsymbol{x}) $が最小になる$ \boldsymbol{x} $は、変数$ \lambda_{i} \geq 0(i = 1,2, \cdots , n) $を用いて新たに定義したラグランジュ関数$ \smash{ L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) - \sum_{i=1}^{n}\lambda_{i}g(\boldsymbol{x}) } $において$ \smash{ \dfrac{\partial L}{\partial x_{j}} = 0(j = 1,2, \cdots , m) } $を満たす
- $ \lambda_{i} \geq 0(i = 1,2, \cdots , n) $：ラグランジュ乗数
- $ \smash{ L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) - \sum_{i=1}^{n}\lambda_{i}g(\boldsymbol{x}) } $：ラグランジュ関数
このとき、SVMの主問題の目的変数と制約条件より、
$ \qquad \smash{ f(\boldsymbol{x}) = \dfrac{1}{2}||w||^{2} } \qquad \smash{ g_{i}(\boldsymbol{x}) = t_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i} + b) - 1} $
と捉えると、
$ \qquad \smash{ L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) - \sum_{i=1}^{n}\lambda_{i}g(\boldsymbol{x}) = \dfrac{1}{2}||w||^{2} - \sum_{i=1}^{n}\lambda_{i}(t_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i} + b) - 1}) $
とできる。
ただし、ここで変数となっているのは$\boldsymbol{x}$ではなく$\boldsymbol{w}, b$のため、正確には
$ \qquad \smash{ L(\boldsymbol{w}, b, \boldsymbol{\lambda}) = \dfrac{1}{2}||w||^{2} - \sum_{i=1}^{n}\lambda_{i}(t_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i} + b) - 1}) $
と記述するのがふさわしいと思われる。
最小となる$\boldsymbol{w}, b$は以下を満たす。
$ \qquad \dfrac{\partial L}{\partial \boldsymbol{w}} = \boldsymbol{w} - \sum_{i=1}^{n}a_{i}t_{i}\boldsymbol{x}_{i} = 0 \qquad \dfrac{\partial L}{\partial b} = - \sum_{i=1}^{n}a_{i}t_{i} = 0 $
つまり、
$ \qquad \boldsymbol{w} = \sum_{i=1}^{n}a_{i}t_{i}\boldsymbol{x}_{i} \qquad \sum_{i=1}^{n}a_{i}t_{i} = 0 $
2.3. サポートベクター
サポートベクターは線形判別関数の最も近くにあるデータを指す。
分離超平面を構成する学習データは、サポートベクターだけで残りのデータは不要。
2.4. ソフトマージンSVM
サンプルを線形分離できないとき、誤差を許容し、誤差に対してペナルティを与えることで対応できるようにしたSVM。
目的関数：$ \dfrac{1}{2}||w||^{2} $
制約条件：$ C\sum_{i=1}^{n}\xi_{i} $
このとき $ \xi_{i} = 1 - \boldsymbol{w}^{T}\boldsymbol{x}_{i} + b > 0 $
パラメータ$C$の大小で決定境界が変化する。
2.5. 非線形分離
線形分離できないとき、特徴空間に写像してその空間で線形に分離する。
→元の空間上では非線形な分離となる。
2.6. カーネルトリック
非線形分離において、複雑な問題になるとより高次元に写像する必要が出てくるが、そのまま計算しては計算量が膨大になってしまう。しかしSVMの場合は実際は写像を求める必要があるわけではなく、ベクトルの内積（カーネル関数）のみわかれば計算ができる。このときカーネル関数を用いて高次元ベクトルの内積を表現する方法をカーネルトリックという。
特徴空間が高次元でも計算コストを抑えることができるという特徴がある。
3. ハンズオン
3.1. サポートベクターマシン
3.1.1. 課題
サポートベクターマシンの動作を確認する。
- 訓練データが線形分離可能な場合
- 訓練データが線形分離不可能な場合
- 訓練データに重なりがある場合（ソフトマージンSVM）
3.1.2. 演習結果
3.1.2.1. 準備
必要なモジュールのインポート。
3.1.2.2. 訓練データが線形分離可能な場合
線形分離が可能なように2つの分類のデータを標準正規分布に沿った乱数で作成する。
最急降下法の使用。
バイアスの取得およびSVMの決定関数による予測。
データおよびマージン、決定境界をプロットすると、ちゃんと決定境界で分かれていることがわかる。
3.1.2.3. 訓練データが線形分離不可能な場合
線形分離が不可能なように2つの分類のデータを作成する。
RBFカーネルの関数の使用。
バイアスの取得およびSVMの決定関数による予測。
データおよびマージン、決定境界をプロットすると、非線形においても決定境界で分かれていることがわかる。
3.1.2.4. 訓練データに重なりがある場合（ソフトマージンSVM）
2つの分類のデータを重なりがある状態になるように、標準正規分布に沿った乱数で作成する。
最急降下法の使用（ただし外れ値に対応するため各イテレータの最後に値aを0からCの間に収めている。）
バイアスの取得およびSVMの決定関数による予測。
データおよびマージン、決定境界をプロットすると、ソフトマージンSVMでは重なりがあっても決定境界で分けられていることがわかる。
