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が使える

参考文献