逐次最小問題最適化法

逐次最小問題最適化法

クラス	サポートベクターマシンの訓練のための最適化アルゴリズム
最悪計算時間	O(n³)

逐次最小問題最適化法（英: Sequential Minimal Optimization, SMO）はサポートベクターマシン (SVM) の訓練で生じる2次計画問題 (QP) を解くためのアルゴリズムである。1998年にマイクロソフトリサーチのJohn Plattによって発明された。SMOはサポートベクターマシンの訓練のために広く使われ、人気のLIBSVMツールによって実装される。以前から利用できたSVM訓練法はより一層複雑で、高価なサードパーティーのQPソルバーを必要としたので、1998年のSMOアルゴリズムの公表はSVMコミュニティでたくさんの興奮を引き起こした。

最適化問題

→詳細は「サポートベクターマシン」を参照

データセット (x₁, y₁), ..., (x_n, y_n) に関する二項分類問題を考える。ここで x_i は入力ベクトル、y_i ∈ {-1, +1} はそれに対応する2値ラベルである。ソフトマージンサポートベクターマシンは以下の双対問題で表される2次計画問題を解くことによって訓練される:

$\max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},$

ただし

$0\leq \alpha _{i}\leq C,\quad {\mbox{ for }}i=1,2,\ldots ,n,$

$\sum _{i=1}^{n}y_{i}\alpha _{i}=0$

ここで C は SVM hyperparameter、K(x_i, x_j) はカーネル関数で、どちらもユーザが与える。変数 $\alpha _{i}$ はラグランジュ乗数である。

アルゴリズム

SMOは上記の最適化問題を解くための反復型アルゴリズムである。SMOはこの問題をその時解析的に解かれる一連の最小の可能な部分問題に分割する。ラグランジュ乗数 $\alpha _{i}$ を伴う線形等式制約のため、最小の可能な問題はそのような2つの乗数を含む。そして、任意の2つの乗数 $\alpha _{1}$、$\alpha _{2}$ について、次の制約に分解される:

$0\leq \alpha _{1},\alpha _{2}\leq C,$

$y_{1}\alpha _{1}+y_{2}\alpha _{2}=k,$

$k$ は前述の和の等式より導かれる定数である。そしてこの問題は解析的に解くことができる。

アルゴリズムは次のように進行する:

1. 最適化問題のKKT条件を破るラグランジュ乗数 $\alpha _{1}$ を見つける。
2. 第2の乗数 $\alpha _{2}$ を選び、組 $(\alpha _{1},\alpha _{2})$ を最適化する。
3. 収束するまでステップ1、2を繰り返す。

すべてのラグランジュ乗数がKKT条件を十分に満たすとき、全体の最適化が終了する。このアルゴリズムは収束することが保証されている。しかし、データセットが大きくなると、組 $(\alpha _{1},\alpha _{2})$の選び方が$O(n^{2})$で大きくなるので、より速く収束させるために、部分問題を構成する変数を選び出すためのヒューリスティックを使うことが重要となる。

関連項目

• サポートベクターマシン