線形SVM(サポートベクトルマシン)
はじめに
SVM(サポートベクトルマシン)は教師あり学習を用いたパターン認識手法で、
その特徴として、高い汎化性能を持っていることが挙げられます。(理由は後述※1)
SVMは決定境界と教師データとのマージンを定義し、そのマージンを最大化するように学習を行います。
理論
単純な線形の２クラス分類器を考えると、その識別関数$ f(\boldsymbol{x}) $は$ \eqref{eq:rec_fnc} $のようになります。
$$ \begin{eqnarray} f(\boldsymbol{x}) = \boldsymbol{w}^T\boldsymbol{x} + b \label{eq:rec_fnc} \end{eqnarray} $$
ここで、$ f(\boldsymbol{x}) $はclass1のときに1, class2のときに-1を出力するものとします。
また、すべての訓練標本 $ \{(\boldsymbol{x}_i , y_i)\}^n_{i=1} $ を識別可能であるとき、 $ \eqref{eq:cond1} $が成り立ちます。
$$ \begin{eqnarray} f(\boldsymbol{x}_i)y_i = (\boldsymbol{w}^T\boldsymbol{x}_i + b) y_i \ge 1 (i=1, 2, \dots, N) \label{eq:cond1} \end{eqnarray} $$
SVMでは、マージンを最大化すると前述しました。 このマージンは、訓練標本と決定境界の距離と定義されています。
あえてわかりにくく表現すると、「決定境界に最も近い訓練標本とのマージンを最大化する」ことで学習($ \boldsymbol{w} $の計算)を行います。 式で言うと$ \eqref{eq:margin} $
$$ \begin{eqnarray} \max_{\boldsymbol{w}, b} \min \frac{|\boldsymbol{w}^T\boldsymbol{x}_i + b|}{\|\boldsymbol{w}\|} \label{eq:margin} \end{eqnarray} $$
うん。ちょっと複雑ですね。なので今からこれをもう少しシンプルにしてあげましょう。 まず、$ \eqref{eq:cond1} $より、
$$ \begin{align} \begin{split} \min \frac{|\boldsymbol{w}^T\boldsymbol{x}_i + b|}{\|\boldsymbol{w}\|} &= \min \frac{(\boldsymbol{w}^T\boldsymbol{x}_i + b)y_i}{\|\boldsymbol{w}\|} \\ &= \frac{1}{\|\boldsymbol{w}\|} \end{split} \label{eq:cond2} \end{align} $$
さらに、$ \frac{1}{\|\boldsymbol{w}\|} $を最大化するということは、 $ \frac{1}{2}{\|\boldsymbol{w}\|}^2 $を最小化することと等価であると取れるため、 $ \eqref{eq:margin} $は$ \eqref{eq:cond3} $となります。
$$ \begin{eqnarray} \min_{\boldsymbol{w}, b} \frac{1}{2}{\|\boldsymbol{w}\|}^2 \text{ subject to } (\boldsymbol{w}^T\boldsymbol{x}_i + b) y_i \ge 1 (i=1, 2, \dots, N) \label{eq:cond3} \end{eqnarray} $$
これは、不等式制約付き最適化問題として扱うことができ、 ( KKT条件 - 機械学習の「朱鷺の杜Wiki」 )
ラグランジュ関数$ \eqref{eq:lag} $を得ます。
$$ \begin{eqnarray} L(\boldsymbol{w}, b, \boldsymbol{a}) = \frac{1}{2}{\|\boldsymbol{w}\|}^2 + \sum^{N}_{i=1}{a_i(-(\boldsymbol{w}^T\boldsymbol{x}_i + b)y_i + 1)} \label{eq:lag} \end{eqnarray} $$
この時、KKT条件より$ \frac{\partial{L}}{\partial{\boldsymbol{w}}}=0 $, $ \frac{\partial{L}}{\partial{b}}=0 $, $ a_i \ge 0 (i=1,2,\dots,N) $を満たしながらLを最小化します。 これより、
$$ \begin{align} \begin{split} \frac{\partial{L}}{\partial{\boldsymbol{w}}} &= \boldsymbol{w} - \sum^{N}_{i=1}{a_i y_i \boldsymbol{x}_i} = 0 \\ \boldsymbol{w} &= \sum^{N}_{i=1}{a_i y_i \boldsymbol{x}_i} \end{split} \label{eq:lag_cond1} \end{align} $$ $$ \begin{eqnarray} \frac{\partial{L}}{\partial{b}} = \sum^{N}_{i=1}{a_i y_i} = 0 \label{eq:lag_cond2} \end{eqnarray} $$
$ \eqref{eq:lag} $, $ \eqref{eq:lag_cond1} $, $ \eqref{eq:lag_cond2} $より、 $$ \begin{align} \begin{split} L(\boldsymbol{w}, b, \boldsymbol{a}) &= \frac{1}{2}\sum^{N}_{i=1}{\sum^{N}_{j=1}{a_i a_j y_i y_j \boldsymbol{x}^T_i \boldsymbol{x}_j}} - \sum^{N}_{i=1}{a_i y_i \boldsymbol{w}^T \boldsymbol{x}_i} - b\sum^{N}_{i=1}{a_i y_i} + \sum^{N}_{i=1}{a_i} \\ &= \sum^{N}_{i=1}{a_i} + \frac{1}{2}\sum^{N}_{i=1}{\sum^{N}_{j=1}{a_i a_j y_i y_j \boldsymbol{x}^T_i \boldsymbol{x}_j}} - \sum^{N}_{i=1}{a_i y_i \sum ^{N}_{j=1}{a_j y_j \boldsymbol{x}^T_j \boldsymbol{x}_i}} \\ &= \sum^{N}_{i=1}{a_i} - \frac{1}{2}\sum^{N}_{i=1}{\sum^{N}_{j=1}{a_i a_j y_i y_j \boldsymbol{x}^T_i \boldsymbol{x}_j}} \\ &= \sum^{N}_{i=1}{a_i} - \frac{1}{2}\sum^{N}_{i=1}{\sum^{N}_{j=1}{a_i a_j y_i y_j k(\boldsymbol{x}_i, \boldsymbol{x}_j)}} \\ &(\text{ただし、}a_i \ge 0 (i=1,2,\dots,N)) \end{split} \label{eq:relative} \end{align} $$ (ここで、$ \boldsymbol{x}^T_i \boldsymbol{x}_j = \boldsymbol{x}^T_j \boldsymbol{x}_i $, $ k(\boldsymbol{x}_i, \boldsymbol{x}_j) = \boldsymbol{x}^T_i \boldsymbol{x}_j $を利用しています。※$ k(\boldsymbol{x}_i, \boldsymbol{x}_j)$:カーネル関数)
$ \eqref{eq:relative} $は$ \eqref{eq:lag} $の相対問題と呼ばれ、
$ \eqref{eq:relative} $を最大化するを計算することでも解を得ることができます。
なぜなら、
$$
\begin{align}
\begin{split}
f(\boldsymbol{x}) &= \boldsymbol{w}^T\boldsymbol{x} + b \\
&= \sum^{N}_{i=1}{a_i y_i \boldsymbol{x}^T_i}\boldsymbol{x} + b \text{ }(\eqref{eq:lag_cond1} \text{ より})\\
&= \sum^{N}_{i=1}{a_i y_i k(\boldsymbol{x}, \boldsymbol{x}_i)} + b
\end{split}
\end{align}
$$
また、bについては、マージン上に存在する訓練データに関して、$ (\boldsymbol{w}^T\boldsymbol{x}_i + b)y_i - 1 = 0 $であり、
かつ、マージン上にないデータは決定境界の計算に影響しないことから$ a_i $が0となります。
これらより、
$$
\begin{align}
\begin{split}
&\text{まずは特定のiについて} \
b &= \frac{1}{y_i} - \boldsymbol{w}^T\boldsymbol{x}_i \\
&= y_i - \sum_{j:a_j \gt 0}{a_j y_j \boldsymbol{x}^T_j}\boldsymbol{x}_i \\
&= y_i - \sum_{j:a_j \gt 0}{a_j y_j k(\boldsymbol{x}_i, \boldsymbol{x}_j)} \\
&a_i \gt 0\text{となるすべてのiについて} \\
b &= \frac{1}{N_s} \sum_{i:a_i \gt 0}{(y_i - \sum_{j:a_j \gt 0}{a_j y_j k(\boldsymbol{x}_i, \boldsymbol{x}_j)})} \\
&(※N_s\text{は}a_i \gt 0\text{となるiの数})
\end{split}
\end{align}
$$
というように必要な値を計算することができるからです。
bの計算で出てきた、「$ a_i \gt 0 $となるようなi」を持つ$ \boldsymbol{x}_i $は
サポートベクトルと呼ばれます。それ以外のiに関しては
となることから、
SVMの決定境界を決める計算には利用されません。
このことから、多少の外れ値を持ったとしても、決定境界には影響せず、結果高い汎化性能を得ることができます(※１フラグ回収)
そしてその先へ
$ \eqref{eq:relative} $は二次計画法問題であり、 これ以降については良い記事を見つけたので、こちらに説明をお任せしたいと思いますw
おわりに
なんだかんだ大学生時代に勉強した時より理解できた気がします(๑•̀ㅂ•́)و✧
