逐次最小問題最適化法

逐次最小問題最適化法（, SMO）はサポートベクターマシン (SVM) の訓練で生じる2次計画問題 (QP) を解くためのアルゴリズムである。1998年にマイクロソフトリサーチのによって発明された。SMOはサポートベクターマシンの訓練のために広く使われ、人気のLIBSVMツールによって実装される。以前から利用できたSVM訓練法はより一層複雑で、高価なサードパーティーのQPソルバーを必要としたので、1998年のSMOアルゴリズムの公表はSVMコミュニティでたくさんの興奮を引き起こした。
最適化問題.
データセット ("x"1, "y"1), ..., ("x""n", "y""n") に関する二項分類問題を考える。ここで "x""i" は入力ベクトル、はそれに対応する2値ラベルである。ソフトマージンサポートベクターマシンは以下の双対問題で表される2次計画問題を解くことによって訓練される:
ここで "C" は SVM hyperparameter、"K"("x""i", "x""j") はで、どちらもユーザが与える。変数 formula_1 はラグランジュ乗数である。
アルゴリズム.
SMOは上記の最適化問題を解くための反復型アルゴリズムである。SMOはこの問題をその時解析的に解かれる一連の最小の可能な部分問題に分割する。ラグランジュ乗数 formula_1 を伴う線形等式制約のため、最小の可能な問題はそのような2つの乗数を含む。そして、任意の2つの乗数 formula_3、formula_4 について、次の制約に分解される:
formula_5 は前述の和の等式より導かれる定数である。そしてこの問題は解析的に解くことができる。
アルゴリズムは次のように進行する:
すべてのラグランジュ乗数がKKT条件を十分に満たすとき、全体の最適化が終了する。このアルゴリズムは収束することが保証されている。しかし、データセットが大きくなると、組 formula_8の選び方がformula_10で大きくなるので、より速く収束させるために、部分問題を構成する変数を選び出すためのヒューリスティックを使うことが重要となる。