One Class Support Vector Machine(One Class SVM)入門

こんにちはtetsuです。

今回は外れ値検知や異常検知で使われるOne Class Support Vector Machine（よくOCSVMやOne Class SVMと略されます。本稿ではOne Class SVMと略すことにします。）の概要と導出について述べていきたいと思います。ベクトルの演算ができれば、最後のラグランジュの未定乗数法の部分を除いて問題なく読める想定です。

One Class Support Vector Machineとは？

One Class SVMは大多数が正常であるようなデータの集合{\mbox{\boldmath $x$}}_1,\cdots,{\mbox{\boldmath $x$}}_Nをもとに学習をおこない、未知のデータが正常であるのか、異常であるのかを判定する手法です。一般には正常に作られた製品や正常な状態のデータは多く手に入れることができても、異常な製品や異常な状態のデータはあまり手に入りません。そのようなケースに対してOne Class SVMを適用することが可能です。

One Class Support Vector Machineの導出

早速One Class SVMの導出に入っていきますが、まずはハードマージン最大化というものを紹介し、その後にソフトマージン最大化の場合について述べます。

ハードマージン最大化

One Class SVMでは次のような関数を用いて未知のデータ{\mbox{\boldmath $x$}}が正常なのか、異常なのかを判定します。

    \begin{eqnarray*}y={\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}} - b. \end{eqnarray*}

ここで{\mbox{\boldmath $w$}}, b(>0)はそれぞれ学習によって得るパラメータです。
{\mbox{\boldmath $x$}}に対するyの値が0より大きいときに{\mbox{\boldmath $x$}}は正常と判定され、0より小さいときに{\mbox{\boldmath $x$}}は異常と判定されます。y=0となるような{\mbox{\boldmath $x$}}の集まりによって作られる境界線が正常か異常かの分かれ目になるため、この境界を識別平面といいます。

ここで問題となるのは{\mbox{\boldmath $w$}}, bをどう求めるかになります。
One Class SVMでは次のような目標に沿って{\mbox{\boldmath $w$}}, bを求めます。

目標1
原点と識別平面との距離が最大になるように{\mbox{\boldmath $w$}}, bを求める。
ただし、すべてのデータ{\mbox{\boldmath $x$}_i}が異常と判定されないようにする。つまり、

    \begin{eqnarray*}{\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}_i} - b \geq 0,\ i=0, 1,\cdots,N.\end{eqnarray*}

この目標1を達成している状態を2次元の図であらわすと次のようになります。緑の丸が学習に用いられたデータで、黄色の線が識別平面になります。すべてのデータが黄色の識別平面を境にして原点と反対側（あるいは識別平面上）に位置するように識別平面が決定されています。
ocsvm_target
2次元の場合には図にしてみることでそれらしい識別平面が引けますが、実際には{\mbox{\boldmath $x$}_i}がもっと大きい次元のベクトルになるので図にすることができません。次からは数式を使って目標1を達成する方法を考えます。

まず先に知っておくと便利な性質を示します。以下のようなものです。

性質：{\mbox{\boldmath $w$}}と識別平面は直交する。

これは識別平面上の異なる適当な2点を{\mbox{\boldmath $x$}}_A, \mbox{\boldmath $x$}}_Bとおいたときに、

    \begin{eqnarray*} \left\{ \begin{array}{l} {\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}_A} - b=0 \\ {\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}_B} - b=0 \end{array} \right. \end{eqnarray*}

が成り立つことを利用して示すことができます。1つめの式から2つめの式を引くことで{\mbox{\boldmath $w$}}^T({\mbox{\boldmath $x$}_A}- {\mbox{\boldmath $x$}_B} ) =0が得られ、{\mbox{\boldmath $w$}}と{\mbox{\boldmath $x$}_A}- {\mbox{\boldmath $x$}_B}が直交することがわかります。{\mbox{\boldmath $x$}_A}- {\mbox{\boldmath $x$}_B}は下の図のように識別平面と平行なベクトルですので、{\mbox{\boldmath $w$}}は識別平面と直交するといえます。
ocsvm_param_orth

次に原点から識別平面までの距離を数式として求めていきます。
まず長さがd(>0)で{\mbox{\boldmath $w$}}と同じ向きであるようなベクトル{\mbox{\boldmath $x$}}について考えてみます。変数を色々と定義しますので、次の図を適宜参照下さい。
ocsvm_param_orth
{\mbox{\boldmath $x$}}は長さdで{\mbox{\boldmath $w$}}と同じ向きのベクトルであるという定義から以下のようにあらわされます。

    \begin{eqnarray*}{\mbox{\boldmath $x$}} = d \frac{{\mbox{\boldmath $w$}}}{{||\mbox{\boldmath $w$}}||_2 }. \end{eqnarray*}

ここで||\mbox{\boldmath $w$}}||_2はベクトル\mbox{\boldmath $w$}}の長さをあらわします。
両辺に対して{\mbox{\boldmath $w$}}との内積をとれば、

(1)   \begin{eqnarray*}d = \frac{{\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}}}{{||\mbox{\boldmath $w$}}||_2 }\end{eqnarray*}

という関係を得ることができます。
ここで、この{\mbox{\boldmath $x$}}の長さが原点と識別平面までの距離（rと置いておきます）であるケースを考えてみます。そのようなベクトルを{\mbox{\boldmath $x$}_C}とおくと、{\mbox{\boldmath $x$}_C}は識別平面の上にありますので、{\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}_C} - b=0となります。式(1)にこの関係を当てはめると、次が求まります。

    \begin{eqnarray*}r = \frac{b}{||{\mbox{\boldmath $w$}}||_2}.\end{eqnarray*}

ついでとなりますが、ここで識別平面から任意の{\mbox{\boldmath $x$}}までの符号付きの距離を以下のように求めておきます。

(2)   \begin{eqnarray*}d - r = \frac{{\mbox{\boldmath $w$}}^T{\mbox{\boldmath $x$}}-b}{||{\mbox{\boldmath $w$}}||_2} = \frac{y}{||{\mbox{\boldmath $w$}}||_2}. \end{eqnarray*}

以上から原点から識別平面までの距離はr=b/||{\mbox{\boldmath $w$}}||_2とわかりましたので、これを最大化したときに目的の{\mbox{\boldmath $w$}とbが求まります。ただし、後々の計算の利便さのために式を少し書き換えます。式をよくみてみると、rを最大化することは||{\mbox{\boldmath $w$}}||_2 - bを最小化することと等しいことがわかります。また||{\mbox{\boldmath $w$}}||_2の部分は||{\mbox{\boldmath $w$}}||_2^2 / 2としても最小化問題には影響を及ぼさないため、便宜上このように置きます。
以上のような最大化問題の書き換えの結果、One Class SVMで達成するべき目標1の内容は次のようにあらわされます。

目標1
次の最小化問題を解く。

    \begin{eqnarray*}\min_{b, {\mbox{\boldmath $w$}}} \frac{1}{2}||{\mbox{\boldmath $w$}}||_2^2 - b.\end{eqnarray*}

ただしすべてのデータ{\mbox{\boldmath $x$}_i}に対して、

    \begin{eqnarray*}{\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}_i} - b \geq 0,\ i=0, 1,\cdots,N.\end{eqnarray*}

この問題を（機械的に）解くことで、はじめに示した図にあるような識別平面を求めることができます。

ここまでで労力をかけて式変形などを色々とおこなってきましたが、実は紹介してきた方法には問題があります。次に問題点について述べ、これを解決するソフトマージン最大化のOne Class SVMの説明に移ります。

ハードマージン最大化のOne Class SVMの問題点

はじめにデータの集合{\mbox{\boldmath $x$}}_1,\cdots,{\mbox{\boldmath $x$}}_Nは大多数が正常データであると仮定をしました。この仮定にのっとり、例えば2つだけ異常なデータが混ざっているとしたらどうなるかを考えてみます。図示すると次のようなケースです。
ocsvm_param_orth
このような状況で目標1の最小化問題を解くと、次のオレンジ色のような識別平面が引かれることになります。
ocsvm_param_orth
見てわかる通り、オレンジ色の識別平面は異常データの影響を大きく受けて極端に原点に近くなります。実際には異常データであっても、異常と判定されないように識別平面を求めているからです。このようなケースでは異常と判定したいデータの多くが正常と判定されてしまう恐れがあります。理想的にはデータの中に異常データがあったとしても、これらの影響をあまり受けずに赤い点線に近い識別平面を引きたいところです。次に紹介するソフトマージン最大化は異常データの影響を大きく受ける問題を回避することができます。

ソフトマージン最大化

先程まで考えていた目標1では識別平面と原点の間には学習に用いたデータ点が存在しないように識別平面を求めていました。この条件を緩めて、識別平面を求める際に学習に用いたデータが識別平面から原点の間に位置することを許容するようにしてしまいます。これをソフトマージン最大化といいます。一方で識別平面と原点の間にデータが位置しないようにする目標1のことはハードマージン最大化といいます。

ソフトマージン最大化ではそれぞれのデータ{\mbox{\boldmath $x$}_i}は\xi_i/ {||\mbox{\boldmath $w$}}||}_2\ (\xi_i >0) の長さだけ識別平面を超えてもよいとします。この\xi_i自身も学習によって求める量であり、なるべく小さくします（＝原点側にデータが位置するのを許容するといっても、その量は多くないほうがよい）。\xi_iができるだけ小さくなるように、目標1の最小化するべき式を次のように書き換えます。

(3)   \begin{eqnarray*}\min_{b,\mbox{\boldmath $w$}, \xi_1,\cdots, \xi_N} \frac{1}{2}||\mbox{\boldmath $w$}}||_2^2 - b + \frac{1}{\nu N} \sum_{i=1}^N \xi_i. \end{eqnarray*}

ここで\nu\ (0< \nu <1)は原点側にデータが超えるのをどの程度許容するのかをあらわす値になり、小さいほど原点側により多くのデータが位置することになります（なぜそう言えるのかは最後に示します）。この値は事前に人が与える必要があります。
目標1の条件の部分{\mbox{\boldmath $w$}}^T {\mbox{\boldmath $x$}_i} - b \leq 0はどうなるでしょうか。\xi_i/ {||\mbox{\boldmath $w$}}||}_2までは識別平面を超えてもよいということから、式(2)のd - rを-\xi_i/ {||\mbox{\boldmath $w$}}||}_2に置き換えることで（原点側に超えるため、マイナスがついています）

(4)   \begin{align*} -\frac{\xi_i}{ {||\mbox{\boldmath $w$}||}_2} & \leq \frac{{\mbox{\boldmath $w$}}^T{\mbox{\boldmath $x$}_i}-b}{||{\mbox{\boldmath $w$}}||_2} \nonumber \\ -\xi_i & \leq {\mbox{\boldmath $w$}}^T{\mbox{\boldmath $x$}_i}-b \nonumber \\ {\mbox{\boldmath $w$}}^T{\mbox{\boldmath $x$}}- b & \geq - \xi_i \end{align*}

という条件が導かれます。
最小化するべき式(3)と条件(4)から、ソフトマージン最大化でのOne Class SVMで解くべき問題が定まります。

目標2
次の最小化問題を解く。

    \begin{eqnarray*}\min_{b,\mbox{\boldmath $w$}, \xi_1,\cdots, \xi_N} \frac{1}{2}||\mbox{\boldmath $w$}}||_2^2 - b + \frac{1}{\nu N} \sum_{i=1}^N \xi_i.\end{eqnarray*}

ただしすべてのデータ{\mbox{\boldmath $x$}_i}に対して、

    \begin{eqnarray*}{\mbox{\boldmath $w$}}^T{\mbox{\boldmath $x$}}- b & \geq & - \xi_i,\ \xi_i \geq 0 , \ i=0, 1,\cdots,N.\end{eqnarray*}

以上でソフトマージン最大化での定式化ができました。この目標2に沿って識別平面を求めていくことで、学習に用いるデータに異常データが含まれていてもその影響を緩和することができます。

実際にはこの最小化問題をこのまま解くのではなく、ラグランジュの未定乗数法を用いて二次計画問題へ落とし込みます。ラグランジュの未定乗数法自身の話と計算の詳細は割愛しますが、計算を進めることで次のような最小化問題が導かれます。

目標2′
次の最小化問題を解く。

    \begin{eqnarray*}\min_{\alpha_1, \dots, \alpha_N}\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j {\mbox{\boldmath $x$}_i}^T {\mbox{\boldmath $x$}_j}.\end{eqnarray*}

ただし、

    \begin{eqnarray*}0 \leq \alpha_i \leq \frac{1}{\nu N},\ \sum_{i=1}^N \alpha_i = 1.\end{eqnarray*}

この最小化問題を解いて\alpha_iを求めることで、もともと求めたかったパラメータ\mbox{\boldmath $w$}}とbは

    \begin{eqnarray*} \mbox{\boldmath $w$} &=& \sum_{i=1}^N \alpha_i \mbox{\boldmath $x$}_i \\ b &=& \mbox{\boldmath $w$}^T \mbox{\boldmath $x$}_{i*} \end{eqnarray*}

のようにして得られます。ここでbを求める際にあらわれるi*は

    \begin{eqnarray*} \ 0 < \alpha_{i*} < \frac{1}{\nu N} \end{eqnarray*}

となるようなデータの番号になります。
y= \mbox{\boldmath $w$}^T \mbox{\boldmath $x$} - bでしたので、 y= (\sum_{i=1}^N \alpha_i \mbox{\boldmath $x$}_i)^T \mbox{\boldmath $x$} - bが成り立ちます。 \alpha_i=0に対応している\mbox{\boldmath $x$}_iは予測yに全く影響を与えません。一方で \alpha_i \neq 0となる\mbox{\boldmath $x$}_iは予測に影響を与え、このような\mbox{\boldmath $x$}_iをサポートベクトルといいます。
最後に\nuの意味について補足します。ラグランジュの未定乗数法の計算過程からわかりますが、\alpha_i=1/(\nu N)となるような\alpha_iに対応する\mbox{\boldmath $x$}_iは識別平面と原点の間に位置するデータとなります。識別平面と原点の間に位置するデータの数をN_Eとおくと、次が導かれます。

    \begin{eqnarray*}1 \geq \sum_{i=1}^N \alpha_i \geq \frac{N_E}{\nu N} \Rightarrow \nu \geq \frac{N_E}{N}\end{eqnarray*}

よって\nuは学習に用いたデータの中で識別平面と原点との間に位置するデータの割合の上限となります。このことから、\nuを小さくすると識別平面を超えて原点側に位置するデータの数が少なくなるといえます。逆に、大きくすることで原点側に位置するデータの数が多くなるような識別平面ができます。

まとめ

今回はOne Class SVMとその導出を紹介しました。One Class SVMはscikit-learnで気軽に試すことが可能ですので、気になった方はぜひ遊んでみて下さい。なお、今回はデータ点{\mbox{\boldmath $x$}}_iをそのまま使用しましたが、一般にはある関数\phiで{\mbox{\boldmath $x$}}_iを射影した\phi({\mbox{\boldmath $x$}}_i)を扱います。これにより、データの分布が複雑な問題も解けるようになります。実際に使用する場合にはお気をつけ下さい。

参考文献：
Support Vector Method for Novelty Detection

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP