注意

当記事は「はじめてのパターン認識」輪読会で担当した8章について備忘録です。
間違いや誤記があった場合は教えてくれると幸いです。

流れ

はじめてのパターン認識8章の以下三節について整理していく。
・ハードマージンSVM
・ソフトマージンSVM
・非線形特徴写像
→今回はソフトマージンSVM
→前回はハードマージンSVM(https://qiita.com/samsa/items/aa0686dba5ee0e9881eb)

線形分離不可能な分類問題への拡張

ハードマージンSVMは線形分離可能な場合に限って言えば、素晴らしい手法です。しかし、線形分離可能な場合というのは非常に整備された問題です。
世の中には線形分離不可能な場合に分類したいという問題の方が多いでしょう。また、どうやってその問題が線形分離可能か判定することも課題として生じます。
そこで次に線形分離不可能な場合に対しても、SVMが使えるよう、細工をします。

具体的には、ハードマージンSVMの誤分類無しの条件を緩和します。

ソフトマージンSVM　定義

定義は凡そハードマージンSVMと変わりませんが、誤分類無しの条件にスラック変数というものを導入します。
スラック変数はデータがマージンや線形識別境界に対してどの位置にあるかを示す変数です。

スラック変数を導入することで誤分類無しの条件は次のように書き換えられます。

しかし、そもそもサポートベクトル(SV)は線形識別境界に最も近いデータ点だったが今回はどう決めるのか？
→スラック変数を導入することで、データ点の位置をSVの位置まで移動させると考えればよい

ソフトマージンSVM　最適化問題（主問題）

スラック変数を導入し、ソフトマージンSVMの最適化問題（主問題）は次のように書き換えらる。
また、そのままラグランジュ関数まで示す.

前回と同様にラグランジュ関数は展開しておく。

ソフトマージンSVM　最適化条件（KKT条件）

最適化条件（KKT条件）は以下の通り。

KKT条件(1)～(3)は偏微分を行い、書き直すと

これらをラグランジュ関数に適用すると、

KKT条件(2)の適用によりバイアスbのかかる項は消える。
KKT条件(3)の適用により$C=\alpha+\mu$となり、後ろ2項はまとめられる→Cのかかる項が±存在するので消える。
途中でKKT条件(1)（$\boldsymbol{w}=\boldsymbol{w_{0}}$）を適用するため、等号ではなく右矢印で表現。

ソフトマージンSVM　双対問題

双対問題を整理する過程はハードマージンSVMと変わらない。

まとめ

SVMは線形分離不可能な問題に対して拡張可能である。しかし、ハイパーパラメータCをどのように設定するかという問題が新たに出現した。
これは交差検証法やグリッドサーチを行うなどして決める必要がある。極端に大きくしてしまった場合は誤分類を許さないことになり、ハードマージンSVMと
同等になる。