機械学習5:サポートベクターマシーン

要点まとめ

n次元ベクトル\boldsymbol{x}の分類を行うために、パラメータ\boldsymbol{w}を用いてf(\boldsymbol{x}) = \boldsymbol{w}^{T} \boldsymbol{x} + bの符号で分類する。 分類境界から最も近いベクトルをサポートベクトルといい、分類境界とサポートベクトルとの距離をマージンという。

分類誤りを許さない分類をハードマージンといい、スラック変数 \boldsymbol{\xi}を用いて誤りを許容する分類をソフトマージンと言う。

誤りを小さくしつつ、マージンを最大化する\boldsymbol{w}を求める最適化問題(主問題)は、ラグランジュ関数を導入することで、より変数の少ない双対問題に置き換えられる。

非線形分類を行う場合は写像する関数\boldsymbol{\phi}(\boldsymbol{x})を用いて高次元空間に写像した双対問題を解くことになるが \phi(\boldsymbol{x}_i)^{T} \phi(\boldsymbol{x}_j) の計算コストが膨大で現実的は計算困難。ここでカーネル関数K(\boldsymbol{x}_i, \boldsymbol{x}_j) = \phi(\boldsymbol{x}_i)^{T} \phi(\boldsymbol{x}_j)に置き換えることで計算コストを大幅に下げることが可能になる。

実装演習

f:id:yui-gen-ron:20211119125809p:plain

2クラス分類の分類境界

決定関数

特徴ベクトル \boldsymbol{x} と同じ次元のパラメータ\boldsymbol{w} を用いて決定境界を決める決定関数f(x)を下記のように表す。

 \displaystyle{
  \displaystyle 
  f(x) = \boldsymbol{w}^T\boldsymbol{x}+b
}

決定関数を用いて下記のような2クラス分類を考える。

 \displaystyle{
  \displaystyle 
  y = sgn f(x) = 
    \begin{cases}
      +1 & (f(x) > 0) \\
      -1 & (f(x) < 0)
    \end{cases}
}

\boldsymbol{x}が2次元の場合、決定関数は下記のようになる。

 \displaystyle{
  \displaystyle 
  f(\boldsymbol{x}) = 
  \begin{pmatrix}
    w_1 & w_2
  \end{pmatrix}
  \begin{pmatrix}
    x_1 \\
    x_2 \\
  \end{pmatrix}
  + b = w_1 x_1 + w_2 x_2 + b

}

線形サポートベクトル分類 (ハードマージン)

線形分離可能な場合、分類境界から最も距離が近い訓練データをサポートベクトルと言い、サポートベクトルと分類境界との距離をマージンと呼ぶ。

マージンが最大となる分類境界f(\boldsymbol{x})を求める。

サポートベクトル\boldsymbol{x}と分類境界f(\boldsymbol{x})との距離は、\boldsymbol{w}のL2ノルム || \boldsymbol{w} ||^2 = \sqrt{w_1^{2} + w_2^{2} + \cdots + w_n^{2}}を用いて、次のように表せる。

 \displaystyle{
  \displaystyle 
  %\begin{align}
    \frac{|f(x_i)|}{||\boldsymbol{w}||} = \frac{|\boldsymbol{w}^T \boldsymbol{x}_i + b|}{||\boldsymbol{w}||} 
    = \frac{y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b)}{||\boldsymbol{w}||}
  %\end{align}
}

分類境界から最も近くにあるサポートベクトル\boldsymbol{x}_iとの距離は、下記のように表せる。

 \displaystyle{
  \displaystyle 
  \min_{i} \frac{y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b)}{||\boldsymbol{w}||} \equiv \frac{M(\boldsymbol{w},b)}{||\boldsymbol{w}||}
}

マージンを最大化するには、下記の問題を解けば良い。

 \displaystyle{
  \displaystyle 
  \max_{\boldsymbol{w}, b} \frac{M(\boldsymbol{w},b)}{||\boldsymbol{w}||}
}

更に式を変形すると、ハードマージンの場合は下記を解けば良いことになる。

 \displaystyle{
  \min_{\boldsymbol{w}, b} \frac{1}{2} || \boldsymbol{w}||^2} , ただし、すべてのiに対して y_i (\boldsymbol{w}^T \boldsymbol{x}_i + b) \geq 1

線形サポートベクトル分類 (ソフトマージン)

完全には分類不可能な、多少の誤りを許す分類を、ハードマージンに対してソフトマージンと言う。ソフトマージンはでは誤りを許容する非負の変数スラック変数 \boldsymbol{\xi} = (\xi_1, \xi_2, \cdots , \xi_n) と正則化係数Cとを用いることで、下記のように表せる。

 \displaystyle{
  \displaystyle 
  \min_{\boldsymbol{w}, b, \boldsymbol{\xi}} \bigl(\frac{1}{2} ||\boldsymbol{w}||^2 + C \sum_{i=1}^{n} \xi_i \bigr) \quad ただし、すべてのiに対して \quad y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \geq 1 - \xi_i , \quad \xi_i \geq 0
}

SVMにおける双対表現

これまでの最適化問題を、主問題 と呼び、主問題と等価な双対問題を解くことが一般的。双対問題を解くメリットは下記。

  • 変数を少なくできる
  • 分類境界の非線形化を考える上で、双対問題の方が有利。

双対問題を考える上では、新たな非負の変数\boldsymbol{\alpha} = (\alpha_1, \cdots, \alpha_n)^{T}, \quad \boldsymbol{\mu} = ( \mu_1, \cdots, \mu_n)^{T} を用いてラグランジュ関数を導入。

 \displaystyle{
  \displaystyle 
  L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \frac{1}{2}||\boldsymbol{w}|| + C \sum_{i=1}^{n} \xi_i - \sum_{i=1}^{n} \alpha_i \bigl( y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) - 1 + \xi_i\bigr) - \sum_{i=1}^{n} \mu_i \xi_i
}

ラグランジュ関数を用いて、主問題は下記のように表せる。

 \displaystyle{
  \displaystyle 
  \min_{\boldsymbol{w},b,\boldsymbol{\xi}} \max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu})
}

SVM分類の場合は下記のような強双対性が成り立ち、右辺のような双対問題に置き換えることができる。

 \displaystyle{
  \displaystyle 
  \min_{\boldsymbol{w},b,\boldsymbol{\xi}} \max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} \min_{\boldsymbol{w}, b, \boldsymbol{\xi}} L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu})
}

最初に双対問題の\boldsymbol{w}, b, \boldsymbol{\xi}の最小化を行うためにラグランジュ関数の偏微分を求める。

 
\newcommand{\partialdiff}[2] {\frac{\partial {#1}}{\partial{#2}}}
\displaystyle{
  \displaystyle 
  \left. \partialdiff{}{\boldsymbol{w}} L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) \right|_{\boldsymbol{w} = \boldsymbol{w}^*} = \boldsymbol{w}^* - \sum_{i=1}^n \alpha_i y_i \boldsymbol{x}_i = 0 \\
  \left. \partialdiff{}{\boldsymbol{b}} L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) \right|_{b = b^*} =  - \sum_{i=1}^n \alpha_i y_i = 0 \\
  \left. \partialdiff{}{\xi_i} L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) \right|_{\xi_i = \xi_i^*} =  - C - \alpha_i - \mu_i = 0 \quad (i=1,\cdots,n)\\
}

これの最適解(\boldsymbol{w}^*, b^*, \boldsymbol{\xi}^*)を用いて双対問題を書き直すと、結局下記のように\boldsymbol{\mu}が消えて\boldsymbol{\alpha}のみの関数となる。

 \displaystyle{
  \displaystyle 
  \max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} \min_{\boldsymbol{w}, b, \boldsymbol{\xi}} L(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} L(\boldsymbol{w}^*, b^*, \boldsymbol{\xi}^*, \boldsymbol{\alpha}, \boldsymbol{\mu}) \\
  = \max_{\boldsymbol{\alpha}} \biggl( -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \boldsymbol{x}^T \boldsymbol{x} + \sum_{i=1}^n \alpha_i \biggr) \\
  ただし、\sum_{i=1}^{n} \alpha_i y_i = 0, \quad 0 \geq \alpha_i \geq C \quad (i=1,\cdots,n)
}

カーネルを用いた非線形分離への拡張

線形分離が不適切な問題に対しては、

 \displaystyle{
  \displaystyle 
  \phi(\boldsymbol{x}) : (x_1, x_2) \rightarrow (x_1, x_2, x_1^2 +x_2^2)
}

のような高次元データへの拡張 ( 写像 )を用いる。

一般的になn次元をr次元へ写像する関数は、下記のように表せる。

 \displaystyle{
  \displaystyle 
  \boldsymbol{\phi}(\boldsymbol{x}) = 
  \begin{pmatrix}
    \phi_1(\boldsymbol{x}) \\
    \vdots \\
    \phi_r(\boldsymbol{x})
  \end{pmatrix}
}

これを用いて、ソフトマージンの双対問題は下記のように拡張できる。

 \displaystyle{
  \displaystyle 
  \max_{\boldsymbol{\alpha}} \biggl( -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \boldsymbol{x}^T \boldsymbol{x} + \sum_{i=1}^n \alpha_i \biggr)  = \max_{\boldsymbol{\alpha}} \biggl( -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \boldsymbol{\phi}(\boldsymbol{x}_i)^T \boldsymbol{\phi}(\boldsymbol{x}_i) + \sum_{i=1}^n \alpha_i \biggr) 
}

現実的に\boldsymbol{\phi}(\boldsymbol{x}_i)^{T} \boldsymbol{\phi}(\boldsymbol{x}_j)の計算が膨大で解くことが困難だが、カーネル関数

 \displaystyle{
  K(\boldsymbol{x}_i, \boldsymbol{x}_j) = \boldsymbol{\phi}(\boldsymbol{x}_i)^T \boldsymbol{\phi}(\boldsymbol{x}_j)
}

に置き換えることで、下記のような形になり、計算コストを削減できる。

 \displaystyle{
  \displaystyle 
  \max_{\boldsymbol{\alpha}} \biggl( -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \boldsymbol{\phi}(\boldsymbol{x}_i)^T \boldsymbol{\phi}(\boldsymbol{x}_i) + \sum_{i=1}^n \alpha_i \biggr) = \max_{\boldsymbol{\alpha}} \biggl( -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(\boldsymbol{x}_i, \boldsymbol{x}_j) + \sum_{i=1}^n \alpha_i \biggr) 
}

主なカーネル関数

 \displaystyle{
  K(\boldsymbol{x}_i, \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j + c)^d
}

 \displaystyle{
  K(\boldsymbol{x}_i, \boldsymbol{x}_j) = \exp (-\gamma ||\boldsymbol{x}_i - \boldsymbol{x}_j||^2)
}

 \displaystyle{
  K(\boldsymbol{x}_i, \boldsymbol{x}_j) = \tanh (b \boldsymbol{x}_i^T \boldsymbol{x}_j + c)
}