機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100%趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

サポートベクターマシン(ハードマージン)(1)

サポートベクターマシンにはハードマージン/ソフトマージンという分類があります。訓練データが線形分離可能であるという前提をおいたものをハードマージン、そうでないものをソフトマージンと呼びます。まずはハードマージンを見ていきます。下図はサポートベクターマシンで分類問題を解いた結果例です。緑色で強調した点がサポートベクトルと呼ばれる点です。分類境界を作っているのはこのサポートベクトルのみであり、その他の点は境界に一切影響しないのが特徴です。

f:id:opabinia2:20200122224207p:plain

分類境界がy(\mathbf{x})=\mathbf{w}^{T}\phi(\mathbf{x})+bで与えられるとすれば、訓練データ点\mathbf{x}_nと境界までの距離d_nは、直線と点の距離より、


\displaystyle | d_n | = \frac{|y(\mathbf{x}_n)|}{\|\mathbf{w}\|} = \frac{|\mathbf{w}^{T}\phi(\mathbf{x}_n)+b|}{\|\mathbf{w}\|}\tag{1}

です。

問題の前提をハードマージン、つまり訓練データが線形分離可能としていますから、データのラベルをt_n \in \{-1,1\}とすれば常にt_n y(\mathbf{x}_n) \gt 0となります。また、t_nをかけても大きさは変わりませんから、


\displaystyle  d_n  = \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \tag{2}

のように絶対値を外すことができます。

最大マージン分類器で書いた通り、サポートベクターマシンは、分類境界と最も近い点との距離(マージン)を最大にするような分類境界を求めることが目標です。マージンが最大となる\mathbf{w},bは、


\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\newcommand{\min}{\mathop{\rm min}\limits}
\displaystyle \argmax_{\mathbf{w},b} \left(  \min_{n} \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|}  \right) \tag{3}

です。ややこしいですが、内側の\minは、分類境界と最も近いn番目のベクトルを指し、このようなベクトルが境界から最も遠くなる\mathbf{w},bを選ぶというのが式(3)の意味です。まあ要するにマージンを最大化するということです。

ここで、\mathbf{w} \rightarrow \kappa\mathbf{w}b \rightarrow \kappa bとすると、式(2)の右辺は


\begin{eqnarray*}
\displaystyle  \frac{t_n(\kappa \mathbf{w}^{T}\phi(\mathbf{x}_n)+\kappa b)}{\kappa \|\mathbf{w}\|} &=&\frac{t_n\kappa (\mathbf{w}^{T}\phi(\mathbf{x}_n)+ b)}{\kappa \|\mathbf{w}\|} \tag{4}\\
&=&  \frac{t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b)}{\|\mathbf{w}\|} \tag{5}\\
&=&d_n \tag{6}
\end{eqnarray*}

となり、結局距離d_nは変わりません。\kappaによって任意に\mathbf{w},bをスケーリングできるわけですから、境界に最も近い点に対して、


t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) = 1 \tag{7}

となるように\mathbf{w},bを選ぶことができます。これを式(3)に代入すれば、


\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\displaystyle \argmax_{\mathbf{w},b}  \frac{1}{\|\mathbf{w}\|}  \tag{8}

となります。式(8)を最大にする\mathbf{w},bは、\|\mathbf{w}\|^{2}を最小にする\mathbf{w},bと同じです。したがって求める\mathbf{w},b


\newcommand{\argmin}{\mathop{\rm arg~min}\limits}
\displaystyle \argmin_{\mathbf{w},b}  \frac{1}{2}\|\mathbf{w}\|^{2}  \tag{9}

と書けます。\frac{1}{2}をかけているのは、微分したときにきれいな形にするためのもので、あってもなくても求められる解は同じです。また、わざわざ2乗しているのは、後で書くように2次計画問題にもっていきたいからです*1。なおbは式(7)の制約がありますから、消えているわけではありません。

式(7)は、分類境界から最も近い点までの距離が1であるということですから、その他の点までの距離は1より大きいといえます。

以上より、


\displaystyle  \frac{1}{2}\|\mathbf{w}\|^{2}  \tag{10}

を、


t_n(\mathbf{w}^{T}\phi(\mathbf{x}_n)+b) \ge 1 \quad\quad  (n=1,\cdots,N) \tag{11}

という不等式制約条件下での2次関数の最小問題を解けば良いことになります。制約条件が線形で、目的関数が凸の2次形式であるこのような問題を2次計画と呼ぶようです。

続き:サポートベクターマシン(ハードマージン)(2)

*1:詳しく調べていないのですが、そうしないと解を求めるのが大変、、、なのだと思います。