LPブースト

線形計画ブースティング( LPBoost ) は、ブースティング分類器ファミリーの教師あり 分類器です。LPBoost は、異なるクラスのトレーニング サンプル間のマージンを最大化するため、マージン分類器アルゴリズムのクラスにも属します。

空間からのサンプルを、それぞれ 1 と -1 のラベルが付けられた 2 つのクラスのいずれかに分類する分類関数を考えてみましょう。LPBoost は、既知のクラス ラベルを持つ一連のトレーニング例が与えられた場合に、このような分類関数を学習するアルゴリズムです。LPBoost は、構造化されたドメインでの結合分類と特徴選択に特に適した機械学習手法です。 ${\displaystyle f:{\mathcal {X}}\to \{-1,1\},}$${\displaystyle {\mathcal {X}}}$

すべてのブースティング分類器と同様に、最終的な分類関数は次の形式になります。

${\displaystyle f({\boldsymbol {x}})=\sum _{j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}}),}$

ここで、 は弱分類器の非負の重みです。個々の弱分類器はランダムよりもわずかに優れているかもしれませんが、多くの弱分類器の結果として得られる線形結合は非常に優れたパフォーマンスを発揮します。 ${\displaystyle \alpha_{j}}$${\displaystyle h_{j}:{\mathcal {X}}\to \{-1,1\}}$${\displaystyle h_{j}}$

LPBoost は、弱い分類器の空のセットから開始して構築されます。反復的に、検討対象の弱い分類器のセットに追加する単一の弱い分類器が選択され、追加され、現在の弱い分類器のセットのすべての重みが調整されます。追加する弱い分類器がなくなるまで、これが繰り返されます。 ${\displaystyle f}$${\displaystyle {\boldsymbol {\alpha }}}$

すべての分類器の重みが各反復で調整されるという特性は、完全修正特性として知られています。AdaBoost などの初期のブースティング手法にはこの特性がなく、収束が遅くなります。

より一般的には、 を弱分類器の無限の可能性がある集合（仮説とも呼ばれる）とします。LPBoost が解決する問題を記述する 1 つの方法は、無限に多くの変数を持つ線形計画として記述することです。 ${\displaystyle {\mathcal {H}}=\{h(\cdot ;\omega )|\omega \in \Omega \}}$

非負の重みベクトル、スラック変数の非負のベクトル、およびマージンを最適化する LPBoost の主線形計画は次のとおりです。 ${\displaystyle {\boldsymbol {\alpha }}}$${\displaystyle {\boldsymbol {\xi }}}$ ${\displaystyle \rho}$

${\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {\alpha }},{\boldsymbol {\xi }},\rho }{\min }}&-\rho +D\sum _{n=1}^{\ell }\xi _{n}\\{\textrm {sb.t.}}&\sum _{\omega \in \Omega }y_{n}\alpha _{\omega }h({\boldsymbol {x}}_{n};\omega )+\xi _{n}\geq \rho ,\qquad n=1,\dots , \ell ,\\&\sum _{\omega \in \Omega }\alpha _{\omega }=1,\\&\xi _{n}\geq 0,\qquad n=1,\dots ,\ell ,\\&\alpha _{\omega }\geq 0,\qquad \omega \in \Omega ,\\&\rho \in {\mathbb {R} }.\end {配列}}}$

スラック変数の効果に注意してください。それらの 1 ノルムは、目的関数で定数係数 によってペナルティを受けます。この係数が十分に小さい場合、常に主要な実行可能線形計画につながります。 ${\displaystyle {\boldsymbol {\xi }}\geq 0}$${\displaystyle D}$

ここでは、選択に対して弱分類器が一意に定義されるようなパラメータ空間の表記法を採用しました。 ${\displaystyle \オメガ}$${\displaystyle \omega \in \Omega }$${\displaystyle h(\cdot ;\omega ):{\mathcal {X}}\to \{-1,1\}}$

上記の線形計画法がブースティング法に関する初期の出版物に初めて記載されたとき、変数の数が多いため扱いにくいものとして無視されました。後になって、このような線形計画法は、列生成という古典的な手法を使用して効率的に解くことができることが発見されました。 ${\displaystyle {\boldsymbol {\alpha }}}$

線形計画では、列は主変数に対応します。 列生成は、大規模な線形計画を解くための手法です。通常、制限された問題で機能し、変数のサブセットのみを扱います。主変数を反復的にオンデマンドで生成することで、最終的にすべての変数を含む元の制限のない問題が回復されます。列を巧みに選択して生成することで、得られたソリューションが元の完全な問題に最適であることを保証しながら、列のごく一部を作成するだけで問題を解決できます。

主線形計画法の列は、双対線形計画法の行に対応します。LPBoost と同等の双対線形計画法は次の線形計画法です。

${\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {\lambda }},\gamma }{\max }}&\gamma \\{\textrm {sb.t.}}&\ sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}+\gamma \leq 0,\qquad \omega \in \Omega ,\\&0\leq \lambda _{n}\leq D,\qquad n=1,\dots ,\ell ,\\& \sum _{n=1}^{\ell }\lambda _{n}=1,\\&\gamma \in \mathbb {R} .\end{配列}}}$

線形計画の場合、主問題と双対問題の最適値は等しくなります。上記の主問題と双対問題の場合、最適値は負の「ソフト マージン」に等しくなります。ソフト マージンは、正のトレーニング インスタンスと負のトレーニング インスタンスを分けるマージンのサイズから、マージン違反サンプルにペナルティを課す正のスラック変数を引いたものです。したがって、すべてのサンプルが分類関数によって線形に分離されるわけではない場合でも、ソフト マージンは正になる可能性があります。後者は「ハード マージン」または「実現マージン」と呼ばれます。

双対問題で満たされている制約のサブセットを考えてみましょう。任意の有限サブセットに対して、線形計画法を解くことができ、すべての制約を満たすことができます。双対問題に追加しなかったすべての制約のうち、1つも違反していないことを証明できれば、制限された問題を解くことは元の問題を解くことと同等であることを証明したことになります。より正式には、任意の制限されたインスタンスに対する最適な目的関数値とします。すると、元の問題空間で「最も違反されている制約」を検索する問題を定式化できます。つまり、次のように 見つけます。${\displaystyle \gamma^{*}}$${\displaystyle \omega ^{*}\in \Omega }$

${\displaystyle \omega ^{*}={\underset {\omega \in \Omega }{\textrm {argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}.}$

つまり、双対制約の左側を最大化する単一の決定スタンプの空間を検索します。決定スタンプのどの選択によっても制約に違反できない場合、対応する制約はいずれも元の問題ではアクティブにならず、制限された問題は同等になります。 ${\displaystyle {\mathcal {H}}}$ ${\displaystyle h(\cdot ;\omega ^{*})}$

ペナルティ定数の正の値は、モデル選択技術を使用して見つける必要があります。ただし、（トレーニング サンプルの数）とを選択した場合、新しいパラメータには次の特性があります。 ${\displaystyle D}$${\displaystyle D={\frac {1}{\ell \nu }}}$${\displaystyle \ell }$${\displaystyle 0<\nu <1}$${\displaystyle \nu }$

• ${\displaystyle \nu }$はトレーニングエラーの割合の上限です。つまり、が誤分類されたトレーニングサンプルの数を表す場合、 となります。${\displaystyle k}$${\displaystyle {\frac {k}{\ell }}\leq \nu }$
• ${\displaystyle \nu }$外側または境界上のトレーニング サンプルの割合の下限です。

• 入力：
  • トレーニングセット、${\displaystyle X=\{{\boldsymbol {x}}_{1},\dots ,{\boldsymbol {x}}_{\ell }\}}$${\displaystyle {\boldsymbol {x}}_{i}\in {\mathcal {X}}}$
  • トレーニングラベル、${\displaystyle Y=\{y_{1},\dots ,y_{\ell }\}}$${\displaystyle y_{i}\in \{-1,1\}}$
  • 収束閾値${\displaystyle \theta \geq 0}$
• 出力：
  • 分類機能${\displaystyle f:{\mathcal {X}}\to \{-1,1\}}$

1. 初期化
   1. 重量、均一${\displaystyle \lambda _{n}\leftarrow {\frac {1}{\ell }},\quad n=1,\dots ,\ell }$
   2. 角${\displaystyle \gamma \leftarrow 0}$
   3. 仮説数${\displaystyle J\leftarrow 1}$
2. 繰り返し
   1. ${\displaystyle {\hat {h}}\leftarrow {\underset {\omega \in \Omega }{\textrm {argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}}$
   2. もしそうなら ${\displaystyle \sum _{n=1}^{\ell }y_{n}{\hat {h}}({\boldsymbol {x}}_{n})\lambda _{n}+\gamma \leq \theta }$
      1. 壊す
   3. ${\displaystyle h_{J}\leftarrow {\hat {h}}}$
   4. ${\displaystyle J\leftarrow J+1}$
   5. ${\displaystyle ({\boldsymbol {\lambda }},\gamma )\leftarrow }$LPBoost双対の解
   6. ${\displaystyle {\boldsymbol {\alpha }}\leftarrow }$LPBoost 双対問題の解のラグランジアン乗数
3. ${\displaystyle f({\boldsymbol {x}}):={\textrm {sign}}\left(\sum _{j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}})\right)}$

収束しきい値が に設定されている場合、得られる解は上記の線形計画のグローバル最適解であることに注意してください。実際には、良好な解を迅速に得るために、 は小さな正の値に設定されます。 ${\displaystyle \theta =0}$${\displaystyle \theta }$

トレーニングサンプルを分ける実際のマージンは実現マージンと呼ばれ、次のように定義されます。

${\displaystyle \rho ({\boldsymbol {\alpha }}):=\min _{n=1,\dots ,\ell }y_{n}\sum _{\alpha _{\omega }\in \Omega }\alpha _{\omega }h({\boldsymbol {x}}_{n};\omega ).}$

実現マージンは、最初の反復では負になる場合があり、通常は負になります。一般的なケースのように、任意の単一サンプルの抽出を許可する仮説空間の場合、実現マージンは最終的に何らかの正の値に収束します。

上記のアルゴリズムは収束することが証明されていますが、AdaBoostや TotalBoost などの他のブースティング定式化とは対照的に、LPBoost の収束境界はわかっていません。ただし、実際には、LPBoost は他の定式化よりも速く収束することが知られています。

LPBoost はアンサンブル学習法であるため、ベース学習者の選択、仮説空間を指示しません。Demiriz らは、軽度の仮定の下では、どのベース学習者も使用できることを示しました。ベース学習者が特に単純な場合、それらはしばしば決定スタンプと呼ばれます。 ${\displaystyle {\mathcal {H}}}$

文献ではブースティングでよく使われる基本学習器の数は膨大です。例えば、 の場合、基本学習器は線形ソフトマージンサポートベクターマシンになります。あるいはもっと単純な、次のような単純な切り株 です。${\displaystyle {\mathcal {X}}\subseteq {\mathbb {R} }^{n}}$

${\displaystyle h({\boldsymbol {x}};\omega \in \{1,-1\},p\in \{1,\dots ,n\},t\in {\mathbb {R} }):=\left\{{\begin{array}{cl}\omega &{\textrm {if~}}{\boldsymbol {x}}_{p}\leq t\\-\omega &{\textrm {otherwise}}\end{array}}\right..}$

上記の決定スタンプは、入力空間の単一の次元に沿ってのみ調べ、定数しきい値を使用してサンプルのそれぞれの列を単純にしきい値化します。次に、陽性クラスまたは陰性クラスに応じて、どちらの方向にも決定できます。 ${\displaystyle p}$${\displaystyle t}$${\displaystyle \omega }$

トレーニング サンプルの重みが与えられている場合、上記の形式の最適な決定スタンプを構築するには、すべてのサンプル列を検索し、ゲイン関数を最適化するために 、とを決定するだけです。${\displaystyle p}$${\displaystyle t}$${\displaystyle \omega }$

• 列生成による線形計画ブースティング、A. Demiriz、KP Bennett、J. Shawe-Taylor。2002 年に Kluwer Machine Learning 46 の 225 ～ 254 ページに掲載。