逐次最小最適化

SVMの訓練から二次計画問題を解くアルゴリズム

逐次最小最適化

クラス	サポートベクターマシンのトレーニングのための最適化アルゴリズム
最悪の パフォーマンス	O( n³ )

逐次最小最適化（SMO ）は、サポートベクターマシン（SVM）の学習中に生じる二次計画問題（QP）を解くアルゴリズムです。 1998年にMicrosoft ResearchのJohn Plattによって発明されました。^{[1] SMOはサポートベクターマシンの学習に広く利用されており、人気の高い}LIBSVMツールによって実装されています。 ^{[2] [3]} 1998年のSMOアルゴリズムの発表は、SVMコミュニティに大きな衝撃を与えました。それ以前のSVM学習方法ははるかに複雑で、高価なサードパーティ製のQPソルバーを必要としていたためです。^[4]

最適化問題

データセット ( x ₁ , y ₁ ), ..., ( x _n , y _n )を用いた2値分類問題を考える。ここで、 x _iは入力ベクトル、y _i ∈ {-1, +1}はそれに対応する2値ラベルである。ソフトマージンサポートベクターマシンは、以下の双対形式で表現される二次計画問題を解くことで学習される。

${\displaystyle \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},}$

以下を条件とする:

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

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

ここで、CはSVMハイパーパラメータ、K(xi、xj )はカーネル関数_であり_、どちらもユーザーが指定します。変数はラグランジュ乗数です。 ${\displaystyle \alpha _{i}}$

アルゴリズム

SMOは、上記の最適化問題を解くための反復アルゴリズムです。SMOは、この問題を可能な限り小さな一連の部分問題に分割し、それらを解析的に解きます。ラグランジュ乗数 を含む線形等式制約により、可能な限り小さな問題は、そのような乗数を2つ含むことになります。そして、任意の2つの乗数 および に対して、制約は次のように簡約されます。 ${\displaystyle \alpha _{i}}$ ${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{2}}$

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

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

この簡約された問題は解析的に解くことができます。1 次元の 2 次関数の最小値を見つける必要があります。は、等式制約の残りの項の合計の負数であり、各反復で固定されます。 ${\displaystyle k}$

アルゴリズムは次のように進行します。

1. 最適化問題のKarush–Kuhn–Tucker (KKT) 条件に違反するラグランジュ乗数を見つけます。 ${\displaystyle \alpha _{1}}$
2. 2 番目の乗数を選択し、ペアを最適化します。 ${\displaystyle \alpha _{2}}$ ${\displaystyle (\alpha _{1},\alpha _{2})}$
3. 収束するまで手順 1 と 2 を繰り返します。

すべてのラグランジュ乗数がKKT条件を満たす場合（ユーザー定義の許容範囲内）、問題は解決されます。このアルゴリズムは収束が保証されていますが、収束速度を加速するために乗数のペアを選択する際にヒューリスティックが用いられます。これは、 と の選択肢が複数存在するため、大規模なデータセットでは非常に重要です。 ${\displaystyle n(n-1)/2}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \alpha _{j}}$

関連研究

大規模なSVM学習問題を一連の小さな最適化タスクに分割する最初のアプローチは、Bernhard Boser、Isabelle Guyon、Vladimir Vapnikによって提案されました。^[5]これは「チャンキングアルゴリズム」として知られています。このアルゴリズムは、データのランダムなサブセットから開始し、この問題を解き、最適性条件に違反する例を反復的に追加します。このアルゴリズムの欠点の1つは、SVの数に応じてスケーリングするQP問題を解く必要があることです。実際のスパースデータセットでは、SMOはチャンキングアルゴリズムよりも1000倍以上高速になる可能性があります。^[1]

1997年、E. Osuna、R. Freund、F. Girosiは、SVMのための全く新しいQPアルゴリズム群を示唆する定理を証明しました。^[6] この定理のおかげで、大規模なQP問題は、一連のより小さなQPサブ問題に分解することができます。Karush –Kuhn–Tucker（KKT）条件に違反する問題を少なくとも1つ追加するQPサブ問題のシーケンスは、収束することが保証されています。チャンキングアルゴリズムは定理の条件に従うため、収束します。^[1] SMOアルゴリズムは、最適化のサイズが2で、両方のラグランジュ乗数が各ステップで適切なヒューリスティックによって選択された新しい乗数に置き換えられる、Osunaアルゴリズムの特殊なケースと考えることができます。^[1]

SMOアルゴリズムは、ブレグマン法または行アクション法と呼ばれる最適化アルゴリズム群と密接に関連しています 。これらの手法は、線形制約を持つ凸計画問題を解きます。これらは反復的な手法であり、各ステップで現在の原点を各制約に投影します。^[1]

参照

• カーネルパーセプトロン

参考文献

1. Platt, John (1998). 「Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines」(PDF) . CiteSeerX  10.1.1.43.4376 .
2. Chang, Chih-Chung; Lin, Chih-Jen (2011). 「LIBSVM: サポートベクターマシン用ライブラリ」. ACM Transactions on Intelligent Systems and Technology . 2 (3). doi :10.1145/1961189.1961199. S2CID  961425.
3. Zanni, Luca (2006). 「マルチプロセッサシステム上で大規模サポートベクターマシンをトレーニングするための並列ソフトウェア」(PDF) .
4. Rifkin, Ryan (2002). Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning (Ph.D. Thesis). マサチューセッツ工科大学. p. 18. hdl :1721.1/17549.
5. Boser, BE; Guyon, IM; Vapnik, VN (1992). 「最適マージン分類器のための訓練アルゴリズム」.第5回計算学習理論ワークショップ COLT '92 議事録. p. 144. CiteSeerX 10.1.1.21.3818 . doi :10.1145/130385.130401. ISBN  978-0897914970. S2CID  207165665。
6. Osuna, E.; Freund, R.; Girosi, F. (1997). 「サポートベクターマシンのための改良型学習アルゴリズム」. Neural Networks for Signal Processing [1997] VII. Proceedings of the 1997 IEEE Workshop . pp.  276– 285. CiteSeerX 10.1.1.392.7405 . doi :10.1109/NNSP.1997.622408. ISBN  978-0-7803-4256-9. S2CID  5667586。

「https://en.wikipedia.org/w/index.php?title=Sequential_minimal_optimization&oldid=1296229278」から取得