SVM

• 線形分類器の一種
• カーネルトリックを使って高精度（注:SVM以外にも使える）
• ハードマージンSVMはソフトマージンSVMの特殊形
• 現実にはソフトマージンSVMを使う

ハードマージンSVM

• 線形分離可能: 分離超平面を引いてすべてのデータが分類できる
• 方針: 分離超平面を2クラスの事例の出来る限り”真ん中”に引く
  • サポートベクトル(SV) ${{\bold x}}^\*$: 平面から一番近い各クラスのデータ点
  • マージン: SVから分離超平面までの距離
• 導出
  • 分離超平面を表す式: $f({{\bold x}}) = y ( {{\bold w}}^T {{\bold x}} + b) = 0$
    • 分離超平面上の全ての点${{\bold x}}$がこの式を満たす
  • マージン: $\frac{ | {{\bold w}}^T {{\bold x}}^\* +b | }{ \| {{\bold w }} \| }$
    • ${{\bold w}}, b$の全要素を定数倍するといくらでもマージンを大きくできる
    • $| {{\bold w}}^T {{\bold x}}^\* +b | = 1$としても一般性は失われない
  • マージンは (ア) $\frac{1}{\|{{\bold w}}\|}$と書き直せる
  • また，どのデータサンプルも分離超平面との距離はマージン以上なので，全てのデータサンプル${{\bold d}}$について以下の式が成り立つ
    • (イ) $\frac{ | {{\bold w}}^T {{\bold d}} +b | }{ \| {{\bold w }} \| } \geq \frac{1}{\|{{\bold w}}\|} \Leftrightarrow | {{\bold w}}^T {{\bold d}} +b | \geq 1$
  • したがって，(イ)の制約下で「(ア)を最大化」(目的関数)するのがハードマージンSVM
    • 目的関数の最大化問題は，目的関数を置き換えることで最小化問題ともみなせる
    • $\max \frac{1}{\|{{\bold w}}\|} \Leftrightarrow \min \| {{\bold w}} \|^2$

ソフトマージンSVM

• ハードマージンSVMでは，分離不可能なデータに対して，制約(ア)を満たす解が存在しないので，分離超平面を計算できない
• 制約の代わりに，分類に失敗した場合ペナルティ$\xi$を与えて，ペナルティを目的関数に組み込む
  • 目的関数は $L({{\bold w}}) = \min_{{{\bold w}}} \left( \sum_t \xi^{(t)} \right) + C \| {{\bold w}} \|^2$
  • $C$は正の定数
  • $\xi^{(t)}$には以下の2つの制約条件を満たす必要がある
    • $y^{(t)} {{\bold w}}^T {{\bold x}}^{(t)} \geq 1- \xi^{(t)}$
    • $\xi^{(t)} \geq 0$
  • 2つの制約条件は以下と同値
    • $\xi^{(t)} = \max \left( 1- y^{(t)} {{\bold w}}^T {{\bold x}}^{(t)}, 0 \right)$
  • よって目的関数は $L({{\bold w}}) = \min_{{{\bold w}}} \left( \sum_t \max ( 1- y^{(t)} {{\bold w}}^T {{\bold x}}^{(t)}, 0 ) \right) + C \| {{\bold w}} \|^2$
    • 第1項が損失項で，ヒンジ損失とよばれる
    • 第2項が正則化項で，これはL2正則化

学習

オンライン学習

• オンライン機械学習本のp.37を参照
• 目的関数を劣微分して劣勾配を求める
• その劣勾配を使って例えばSGDが使える

参考文献

• 徳永さんのblog
  • SVMのマージン最大化についてしつこく考えてみる
  • パーセプトロンはマージン最大化の夢を見るか？
  • SVMの正則化項がマージン最大化のために必要な
• 確率的勾配降下法によるSVMの実装