初めてのSVM - yasuhisa's blog

ゼミでid:reposeがSVMについて話しました。SVRとかそういうのはとりあえずやらないで、マージン最大化とヒンジ関数を使った誤差最小化の枠組みを見たり、解のスパースネスがどうして導けるのかとかについて勉強しました。

参考にしてたのはこの2冊。

作者: C. M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
出版社/メーカー: シュプリンガー・ジャパン株式会社
発売日: 2008/07/11
メディア: 単行本
購入: 19人クリック: 443回
この商品を含むブログ (64件) を見る

作者: 赤穂昭太郎
出版社/メーカー: 岩波書店
発売日: 2008/11/27
メディア: 単行本
購入: 7人クリック: 180回
この商品を含むブログ (32件) を見る

SVMはアプリケーションとしては使ったことがある感じで、SVM-Light Support Vector Machineとか使ったりしてました。が、とりあえず素性をフォーマットにある形にして、投げるだけ、、、というなんともひどい状態だったので、これでちょっとは分かって使えるようになるはず。

ガウス過程との比較

PRML6章にあったガウス過程は無限個の基底関数を扱えたり、特徴ベクトルどうしようとか考えずによくて、カーネルの設計のみ考えればよいというのがメリットとしてありました。

ガウス過程についてのメモ - yasuhisa's blog

しかし、類似度に相当するものをカーネル関数で計算するために、いままでのデータを全てもっておかないといけないし、計算量もデータの個数に大きく依存しているというのがデメリットとしてありました。

SVMの特徴としては、データを全部持っておく必要はなく、「サポートベクター」になるようなデータのみを保持しておけばよいという性質があります。そして、一般にサポートベクターの数というのはデータ数より大分小さくなるので、疎な解を持つことが多くなります。この辺がガウス過程と比較した際のSVMの特徴や利点。

マージン最大化

まず、線形判別できるような例から見ていく。

マージン最大化の視点から見たSVMは、PRML4.1の識別関数で出てきたのと似たようなことをやります。つまり、識別平面を決めてあげて、 $y(x)=1$ 、 $y(x)=-1$ との距離を最大化してあげようとする。何も考えないで定式化すると
$\frac{1}{||w||} \min_n [t_n (\mathbf{w}^T \phi(\mathbf{x}_n) + b)]$
を最大にするような $\mathbf{w}$ と $b$ を求めなければならない。しかし、こんなものの最適化を直接解こうと思うと非常に複雑。ここで発想を転換する。境界に最も近い点では $t_n (\mathbf{w}^T \phi(\mathbf{x}_n) + b) \geq 1$ が成立している。なので、上の無制約最大化問題を制約付き最小化問題へと変形することを考える。

具体的にはこんな感じ。境界に一番近い点では、 $t_n (\mathbf{w}^T \phi(\mathbf{x}_n) + b) = 1$ となっているので、minの中は1と置いてあげよう(その代わり制約としておいてあげる)。割り算されたやつの最大化問題は割られるやつの最小化問題とできるので、この問題は、全てのデータについて $t_n (\mathbf{w}^T \phi(\mathbf{x}_n) + b) \geq 1$ という制約のもとで、 $\frac{1}{2} ||w||^2$ を最大化する問題と等価となる。

この形に持っていければ、なじみのあるラグランジュ関数を使うことができて、それは
$L(\mathbf{w}, b, \mathbf{a}) = \frac{1}{2} ||w||^2 - \sum_{n=1}^N a_n \{t_n (\mathbf{w}^T \phi(\mathbf{x}_n) + b) -1\}$
となる。ここで、 $\mathbf{a}$ はラグランジュの未定乗数である。ここからもうちょっと頑張る。

ラグランジュ関数を $\mathbf{w}$ と $b$ について偏微分をして、0とおき、それを上のラグランジュ関数に代入すると次の式を得る。
$\bar{L}(\mathbf{a}) = \sum_{n=1}^N a_n - \frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N a_n a_m t_n t_m k(\mathbf{x}_n, \mathbf{x}_m)$
ただし、 $\mathbf{a}$ については以下の制約がある。

全てのnについて $a_n \geq 0$
$\sum_{n=1}^N a_n t_n = 0$

さて、ここでカーネル関数さんのご登場というわけである。カーネル関数として正定値対称性を満たすようなものを持ってくれば、凸二次計画な問題となって「大域的な」最適解を求めることができる。

解のスパースさ

さっき計算した $\mathbf{w}$ を $y(\mathbf{x})$ に代入してあげると $y(\mathbf{x}) = \sum_{n=1}^N a_n t_n k(\mathbf{x}, \mathbf{x}_n) + b$ を得る。

KKT条件

なんか名前を聞くと3歩下ってしまいそうになりますが。。。

定理の主張としてはこんなもの。m個の不等式制約があるような制約付き最小化問題について考える。目的関数は $f(\mathbf{x})$ 、制約は $g_i(\mathbf{x}) \leq 0 \, (i=1,\cdots, m)$ 。ここで、 $f$ と $g_i$ は微分可能で凸な関数とする。ラグランジュ関数を
$L(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \lambda_i g_i(\mathbf{x})$
とおく(凸関数の和だから、ラグランジュ関数も凸関数になることに注意)。このとき正則条件と呼ばれる(緩そうな)仮定を満たすと仮定すると
$\nabla L(\mathbf{x}^*, \mathbf{\lambda}^*) = 0$
$\lambda_i^* \geq 0, g_i(\mathbf{x}^*) \leq 0, \lambda_i^* g_i(\mathbf{x}_i^*) = 0, i = 1, \cdots, m$
を満たすような $\mathbf{x}^*$ と $\mathbf{\lambda}$ が存在することと、 $\mathbf{x}^*$ が大域的最適解であるということが等価である、というのがこの定理(条件)の主張である。