連続最小最適化

逐次最小最適化( 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 )を使用したバイナリ分類問題を考えます。ここで、 x _iは入力ベクトル、y _i ∈ {-1、+1}はそれに対応するバイナリラベルです。ソフトマージンサポートベクターマシンは、次のように双対形式で表現される二次計画問題を解くことによってトレーニングされます。

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

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