verum ipsum factum

sudillap's blog

サポートベクターマシンとは[ソフトマージンサポートベクターマシン]

スラック変数の導入

スラック変数を導入すると、訓練データの各データが支持超平面から分類超平面のほうにどの程度はみ出したかを測ることができます。別の表現をすれば、はみ出したデータを無視して支持超平面を構成した結果として発生する誤差の程度を測る変数です。

スラック変数を$\xi=(\xi_1, \ldots, \xi_l)^T$と表記すると、スラック変数は誤差の大きさを表しているので
$$
\xi_i\geqq 0, i=1,\ldots, l
$$
です。

下図のような状況を考えます。このデータの配置では正例データと負例データを分ける超平面はもはや存在しないことがわかります。ピンク色の点は誤差データと考え、それ以外のデータから支持超平面を構成しています。誤差データに対してはスラック変数$\xi_i$でその大きさを考慮しています。
支持超平面からはみ出したデータに対応したスラック変数のみ$\xi_i> 0$となり、それ以外は$\xi_i= 0$となることに注意してください。

f:id:sudillap:20130405012051p:plain

ハードマージンサポートベクターマシンで出てきた最適化問題にスラック変数を導入すると次のようになります。

スラック変数を導入した最適化問題(主問題)

訓練データ
$D = \{(x_1, y_1), \ldots, (x_l, y_l)\}, (x_i, y_i) \in \Re^n \times \{-1, 1\}$
と定数$C(>0)$が与えられたとき、制約条件のもとで次の目的関数を最小化します。

目的関数

$$
\frac{||w||^2}{2}+C\sum_{i=1}^{l}\xi_i
$$

制約条件

$$
\begin{align}
y_i(w^Tx_i+b) &\geqq 1-\xi_i, i=1,\ldots, l\\
\xi_i &\geqq 0, i=1,\ldots, l
\end{align}
$$

この最適化問題についていくつかコメントしておきます。

目的関数には誤差項($\sum_{i=1}^{l}\xi_i$)が新たに加わり、制約条件にはスラック変数の制約が加わっています。

ここで誤差項の意味を考えてみます。
もし目的関数に誤差項を加えない($C=0$)と、制約条件を満たしつつ、マージンをいくらでも大きくできてしまいます。たとえば、訓練データ全てを誤差データとみなしまうことによりマージンを最大化できます。このような好ましくない状況を避けるためにこの誤差項がペナルティーとして必要であることが分かります。

ちなみに、この最適化問題では誤差項は$\xi$の一次式ですが、$p$次式を用いて次のように目的関数を構成することも可能です。
$$
\frac{||w||^2}{2}+\frac{C}{p}\sum_{i=1}^{l}\xi_i^p
$$

  • 定数Cについて

$C(>0)$は誤差項($\sum_{i=1}^{l}\xi_i$)と$||w||^2/2$の大きさのバランスまたはトレードオフを調整するパラメータでユーザーが指定する必要があります*1

ここで、$C$の効果を考えてみます。

まず、$||w||^2/2$と$\sum_{i=1}^{l}\xi_i$の大小関係を見てみます。
$||w||^2$を小さく(すなわちマージンを大きく)すると支持超平面の反対側にはみ出すデータが多くなります。それに伴い誤差項は大きくなります。逆に$||w||^2$を大きく(すなわちマージンを小さく)すると支持超平面の反対側にはみ出すデータが少なくなるため誤差項は小さくなります。このように目的関数の一方の項を小さくしようとすればもう片方の項が大きくなるので、そのトレードオフをパラメータ$C$で調整します。

つぎに、$C$と$\sum_{i=1}^{l}\xi_i$の関係を見てみます。
最適化問題の目的は目的関数の値を小さくすることなので、1項目だけでなく2項目の$C\sum_{i=1}^{l}\xi_i$も小さくする必要があります。
もし$C$に大きな値を設定すると$C\sum_{i=1}^{l}\xi_i$は当然大きくなりますが、その程度を緩和するためには、$\sum_{i=1}^{l}\xi_i$を小さくする必要があります。$\xi_i \geqq 0$なので、これは$\xi_i$を全体的に小さくするすることになります。すなわち、$C$を大きくすると、誤差データをあまり許容できないためマージンの幅が狭くなります。
逆に$C$に小さい値を指定すると$\sum_{i=1}^{l}\xi_i$をある程度大きくしても$C\sum_{i=1}^{l}\xi_i$はそれほど大きくなりません。すなわち、マージン幅を広く取り誤差データを許容できる程度が大きくなります。

このようにユーザー設定パラメータである$C$の値に応じて分類超平面の位置が変わるため、最も高い分類性能が得られる$C$の値を探すことになります。

ところで、パラメータに文字$C$が用いられることが多いため、ソフトマージンサポートベクターマシンのことをC-SVC(C-support vector classification)と呼ぶこともあります*2

  • 決定関数について

スラック変数を導入しても決定関数はそのままで
$$
\hat{f}(x) = \text{sgn}(w^T x + b)
$$
です。この判別式に、分類超平面より負例(正例)側にある正例(負例)データを代入すると負例(正例)データと判別されるため、このデータは誤分類されます。しかし、もともとこのようなデータを誤差データとみなしていたので、誤分類されたとしても影響は小さいと考えられます。

最適化問題の解法

ハードマージンサポートベクターマシンの場合と同様に主問題の最適化問題を双対問題へ変換しましょう。

ソフトマージンサポートベクターマシンの場合のラグランジュ関数は次で定義されます。
$$
L(w, b, \xi, \alpha, \beta)=\frac{||w||^2}{2}+C\sum_{i=1}^{l}\xi_i-\sum_{i=1}^{l}\alpha_i(y_i(w^Tx_i+b)-1+\xi_i)-\sum_{i=1}^{l}\beta_i\xi_i
$$
ここで、$\alpha=(\alpha_1,\ldots, \alpha_k)^T, \beta=(\beta_1,\ldots, \beta_m)^T$はラグランジュ乗数です。

この場合のクーン・タッカーの定理の関係式はつぎのように表現されます。
$$
\begin{align}
\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial w}&=0,\\
\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial b}&=0,\\
\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial \xi}&=0,\\
\alpha_i(y_i(w^Tx_i+b) -1+\xi_i)&=0, i=1,\ldots,l,\\
\beta_i \xi_i&=0, i=1,\ldots,l,\\
\alpha_i&\geqq 0, i=1,\ldots,l,\\
\beta_i&\geqq 0, i=1,\ldots,l,\\
\xi_i&\geqq 0, i=1,\ldots,l,
\end{align}
$$
4番目と5番目の式がKKT相補性条件となります。

まずラグランジュ関数の偏微分を計算します。
$$
\begin{align}
\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial w}&=w-\sum_{i=1}^{l}\alpha_iy_ix_i\\
&=0\\
\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial b}&=-\sum_{i=1}^{l}\alpha_iy_i\\
&=0\\
\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial \xi_i}&=C-\alpha_i-\beta_i \\
&=0
\end{align}
$$
整理すると
$$
\begin{align}
w&=\sum_{i=1}^{l}\alpha_iy_ix_i,\\
\sum_{i=1}^{l}\alpha_iy_i&=0,\\
C&=\alpha_i+\beta_i, i=1,\ldots,l\\
\end{align}
$$

これらの式をラグランジュ関数に代入すれば主問題に対する双対問題の目的関数が得られます。
$$
\begin{align}
L(w, b, \xi, \alpha, \beta)&=\frac{w^Tw}{2}+C\sum_{i=1}^{l}\xi_i-\sum_{i=1}^{l}\alpha_i(y_i(w^Tx_i+b)-1+\xi_i)-\sum_{i=1}^{l}\beta_i\xi_i\\
&=\frac{(\sum_{i=1}^{l}\alpha_iy_ix_i)^T(\sum_{i=1}^{l}\alpha_iy_ix_i)}{2}+\sum_{i=1}^{l}(\alpha_i+\beta_i)\xi_i\\
&-\sum_{i=1}^{l}\alpha_i\{y_i((\sum_{i=1}^{l}\alpha_iy_ix_i)^Tx_i+b)-1+\xi_i\}-\sum_{i=1}^{l}\beta_i\xi_i\\
&=\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\sum_{i=1}^{l}\alpha_i\xi_i+\sum_{i=1}^{l}\beta_i\xi_i\\
&-\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j-b(\sum_{i=1}^{l}\alpha_iy_i)+\sum_{i=1}^{l}\alpha_i-\sum_{i=1}^{l}\alpha_i\xi_i-\sum_{i=1}^{l}\beta_i\xi_i\\
&=\sum_{i=1}^{l}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j (\because \sum_{i=1}^{l}\alpha_iy_i=0)
\end{align}
$$


また$C=\alpha_i+\beta_i$を変形すると
$$
\beta_i=C-\alpha_i, i=1,\ldots,l
$$
となり、ラグランジュ乗数$\beta_i \geqq 0$であることから、最終的に$C \geqq \alpha_i \geqq 0, i=1,\ldots,l$が得られます。

以上をまとめると$\alpha$に関する次の最適化問題(双対問題)が得られます。

最適化問題(双対問題)

目的関数

$$
\sum_{i=1}^{k}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j
$$
を次の制約条件のもとで$\alpha$に関して最小化

制約条件

$$
C \geqq \alpha_i\geqq 0, i=1,\ldots,l\\
\sum_{i=1}^{l}\alpha_iy_i=0
$$

この最適化問題を解いて$\alpha$を求めれば、$w$を計算できます。

最適化問題(主問題)でスラック変数$\xi$を導入したにもかかわらず、この双対問題にはスラック変数が現れないことに注意しましょう。そのため、目的関数の式はハードマージンサポートベクターマシンのときと同じになっています。
ただしハードマージンサポートベクターマシンとの相違点は、制約条件$C \geqq \alpha_i\geqq 0, i=1,\ldots,l$にパラメータ$C$が現れていることです(ソフトマージンでは$\alpha_i\geqq 0, i=1,\ldots,l$でした)。


この制約条件の式$C \geqq \alpha_i\geqq 0$から$\alpha_i$の取りうる値に関して次の3つの場合が考えられます。

  • $\alpha_i=0$のとき

$C=\alpha_i+\beta_i$なので$C=\beta_i$となり、$C>0$であることに注意すると$\beta_i>0$となります。このときKKT相補条件の式$\beta_i \xi_i=0$から$\xi_i=0$となります。すなわち双対問題の解$\alpha_i=0$となるデータでは$\xi_i=0$なので、訓練データ$x_i$は支持超平面の正例側または負例側にある(支持超平面からはみ出していない)ことが分かります。したがってこのデータは正しく分類されます。

  • $0<\alpha_i < C$のとき

$\beta_i=C-\alpha_i$なので$\beta_i>0$となります。このとき、KKT相補条件の式$\alpha_i(y_i(w^Tx_i+b) -1+\xi_i)=0$、$\beta_i \xi_i=0$から、それぞれ$y_i(w^Tx_i+b) -1+\xi_i=0$、$\xi_i=0$となるので、両式から$y_i(w^Tx_i+b) -1=0$が成り立つことが分かります。これは訓練データ$x_i$が支持超平面にちょうど乗っているので、$x_i$はサポートベクターとなります。当然ながらこのデータは正しく分類されます。

  • $\alpha_i = C$のとき

$C=\alpha_i+\beta_i$なので$\beta=0$となります。このとき、KKT相補条件の式$\alpha_i(y_i(w^Tx_i+b) -1+\xi_i)=0$、$\beta_i \xi_i=0$から、それぞれ$y_i(w^Tx_i+b) -1+\xi_i=0$、$\xi_i \geqq 0$が得られます。すなわち、訓練データ$x_i$は支持超平面の反対側にはみ出していることになります。このようにはみ出しているデータもサポートベクターと呼ばれます。

$0 \leqq \xi_i \leqq 1$のときは、$x_i$は支持超平面から反対側にはみ出していますが分類超平面は超えていない(下図の点$x_A$)ため正しく分類されます。しかし$\xi_i \geqq 1$になると、$x_i$は支持超平面だけではく分類超平面も超えてはみ出している(図の点$x_B$、$x_C$)ためこのデータは誤分類されることになります。

f:id:sudillap:20130405012051p:plain

$w$の計算量削減

ハードマージンサポートベクターマシンの場合と同様に、$\alpha_i=0$となるデータはサポートベクターではないことを利用すれば、$w$の計算量を削減できます。すなわち、サポートベクターの集合を$\mathcal{V}$で表現すると、$w$は次で計算できます。
$$
\begin{align}
w&=\sum_{i=1}^{l}\alpha_iy_ix_i\\
&=\sum_{x_i \in \mathcal{V}}\alpha_iy_ix_i
\end{align}
$$

$b$の計算方法

ソフトマージンサポートベクターマシンでも分類超平面の式の$b$の計算方法はハードマージンと同じ方法で求めます。
すなわち、正例、負例のサポートベクター($0<\alpha_i < C$のとき)をそれぞれ$x_{+}, x_{-}$とし、支持超平面の式に代入すると
$$
\begin{align}
w^Tx_{+}+b&=1,\\
w^Tx_{-}+b&=-1
\end{align}
$$
なので、両式を足し合わせ、$b$に関して解くと
$$
\begin{align}
b&=-\frac{1}{2}w^T(x_{+}+x_{-})\\
&=-\frac{1}{2}\sum_{\mathcal{V}}\alpha_iy_ix_i^T(x_{+}+x_{-})\\
&=-\frac{1}{2}\sum_{\mathcal{V}}(\alpha_iy_ix_i^Tx_{+}+\alpha_iy_ix_i^Tx_{-})
\end{align}
$$
が得られます。

決定関数

サポートベクターのみを使って決定関数$\hat{f}(x)$を表すと
$$
\begin{align}
\hat{f}(x) &= \text{sgn}(w^T x + b)\\
&=\text{sgn}(\sum_{\mathcal{V}}\alpha_iy_ix_i^Tx + b)
\end{align}
$$


これで分類超平面の式が求まりましたので、以上をまとめます。

ソフトマージンサポートベクターマシン

訓練データ
$D = \{(x_1, y_1), \ldots, (x_l, y_l)\}, (x_i, y_i) \in \Re^n \times \{-1, 1\}$
が与えられたとき、次の最適化問題を解き、$\alpha$を求めます。

目的関数

$$
\sum_{i=1}^{l}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{l}\alpha_i\alpha_jy_iy_jx_i^Tx_j
$$
を制約条件のもとで$\alpha$に関して最小化

制約条件

$$
C \geqq \alpha_i \geqq 0, i=1,\ldots,l,\\
\sum_{i=1}^{l}\alpha_iy_i=0
$$

このとき、決定関数は
$$
\hat{f}(x) = \text{sgn}(\sum_{\mathcal{V}}\alpha_iy_ix_i^Tx + b)
$$
ここで、$b$は
$$
\begin{align}
b&=-\frac{1}{2}\sum_{\mathcal{V}}(\alpha_iy_ix_i^Tx_{+}+\alpha_iy_ix_i^Tx_{-})
\end{align}
$$
$\mathcal{V}$はサポートベクターの集合です。

ところで、上のソフトマージンサポートベクターマシンのアルゴリズムを見ると、訓練データ$x_i$は全て内積$x_i^Tx_j$の形でしか現れていないことに気付きます。このことを利用すると次に述べるカーネル法による非線形サポートベクターマシンが導かれます。

*1:LIBSVMsvm-train)では「-c」オプションを用いてこのパラメータを指定できます。

*2:たとえばLIBSVMsvm-train)のヘルプではサポートベクターマシンの種類を指定する「-s」オプションの説明に「0 -- C-SVC」と書かれています。したがってソフトマージンサポートベクターマシンでデータの分類を学習するのであれば「-s 0」を指定します