ブラウンブースト
ブースティングアルゴリズム

BrownBoostは、ノイズの多いデータセットに対して堅牢性を持つ可能性のあるブースティングアルゴリズムです。BrownBoostは、多数決によるブーストアルゴリズムの適応型です。他のブースティングアルゴリズムと同様に、BrownBoostは他の機械学習手法と組み合わせて使用​​されます。BrownBoostは2001年にYoav Freundによって導入されました。 [1]

モチベーション

AdaBoostは様々なデータセットで良好なパフォーマンスを発揮しますが、ノイズの多いデータセットでは良好なパフォーマンスを発揮しないことが示されています。[2] これは、AdaBoostが繰り返し誤分類される例に焦点を当てているためです。対照的に、BrownBoostは繰り返し誤分類される例を事実上「見捨てる」ことになります。BrownBoostの中心的な前提は、ノイズの多い例は弱仮説によって繰り返し誤分類され、ノイズのない例は「見捨てられない」ほど頻繁に正しく分類されるというものです。したがって、ノイズの多い例だけが「見捨てられる」一方で、ノイズのない例は最終的な分類器に寄与します。つまり、最終的な分類器をノイズのない例から学習した場合、最終的な分類器の汎化誤差は、ノイズのある例とノイズのない例の両方から学習した場合よりもはるかに良好になる可能性があります。

アルゴリズムのユーザーは、トレーニングセットで許容されるエラーの量を設定できます。例えば、トレーニングセットにノイズが多い場合（例えば、全サンプルの10%が誤ってラベル付けされていると想定される場合）、ブースターに10%のエラー率を受け入れるように指示することができます。ノイズの多いサンプルは無視できるため、真のサンプルのみが学習プロセスに寄与します。

アルゴリズムの説明

BrownBoostは非凸なポテンシャル損失関数を使用するため、 AdaBoostフレームワークには適合しません。非凸最適化は、ノイズの多いデータセットへの過適合を回避する手法を提供します。しかし、凸損失関数を解析的に最小化するブースティングアルゴリズム（ AdaBoostやLogitBoostなど）とは異なり、BrownBoostは標準的な数値計算手法を用いて、2つの方程式と2つの未知数からなる連立方程式を解きます。

BrownBoost（アルゴリズム内）の唯一のパラメータは、アルゴリズムの実行時間です。BrownBoostの理論によれば、各仮説はアルゴリズム内で可変の時間を必要とし、その時間は仮説に与えられる重みに直接関係します。BrownBoostにおける時間パラメータは、 AdaBoostにおける 反復回数に相当します。 c {\displaystyle c} t {\displaystyle t} α {\displaystyle \alpha} T {\displaystyle T}

の値が大きいほど、BrownBoostはデータのノイズが少ないとみなし、より多くの例を除外します。逆に、の値が小さいほど、BrownBoostはデータのノイズが多いとみなし、より多くの例を除外します。 c {\displaystyle c} c {\displaystyle c}

アルゴリズムの各反復処理において、ランダムな推測よりも有利な仮説が選択されます。この仮説の重みと、反復処理中の「経過時間」は、2つの未知数（仮説の重みと経過時間）を持つ2つの非線形方程式（1. 仮説と例の重みの相関なし、2. ポテンシャルを一定に保つ）の連立方程式で同時に解かれます。この方程式は、二分法（JBoostソフトウェアパッケージに実装されている方法）またはニュートン法（Freundの原著論文に記載されている方法）によって解くことができます。これらの方程式が解かれると、各例のマージン（アルゴリズム内）と残り時間が適切に更新されます。このプロセスは、残り時間がなくなるまで繰り返されます。 α {\displaystyle \alpha} t {\displaystyle t} α {\displaystyle \alpha} t {\displaystyle t} r 私 （ × j ） {\displaystyle r_{i}(x_{j})} s {\displaystyle s}

初期ポテンシャルは と定義されます。各反復処理の制約としてポテンシャルを一定に保つ必要があるため、最終的なポテンシャルは となります。したがって、最終的な誤差はに近くなる可能性があります。ただし、最終的なポテンシャル関数は、0–1損失誤差関数ではありません。最終的な誤差が正確に となるためには 、損失関数の分散が時間に対して線形に減少し、ブースティング反復処理の終了時に0–1損失関数を形成する必要があります。この点については文献ではまだ議論されておらず、以下のアルゴリズムの定義にも含まれていません。 1 メートル ∑ j ＝ 1 メートル 1 − エルフ （ c ） ＝ 1 − エルフ （ c ） {\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})} 1 メートル ∑ j ＝ 1 メートル 1 − エルフ （ r 私 （ × j ） / c ） ＝ 1 − エルフ （ c ） {\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})} 1 − エルフ （ c ） {\displaystyle 1-{\mbox{erf}}({\sqrt {c}})} 1 − エルフ （ c ） {\displaystyle 1-{\mbox{erf}}({\sqrt {c}})}

最終的な分類器は弱い仮説の線形結合であり、他のほとんどのブースティング アルゴリズムと同じ方法で評価されます。

BrownBoost学習アルゴリズムの定義

入力：

  • メートル {\displaystyle m} トレーニング例 （ × 1 、 y 1 ） 、 … 、 （ × メートル 、 y メートル ） {\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})} × j ∈ X 、 y j ∈ はい ＝ { − 1 、 + 1 } {\displaystyle x_{j}\in X,\,y_{j}\in Y=\{-1,+1\}}
  • パラメータ c {\displaystyle c}

初期化:

  • s ＝ c {\displaystyle s=c} （の値はゲームの残り時間です） s {\displaystyle s}
  • r 私 （ × j ） ＝ 0 {\displaystyle r_{i}(x_{j})=0}   た j {\displaystyle \forall j} の値は、たとえば反復におけるマージンです。 r 私 （ × j ） {\displaystyle r_{i}(x_{j})} 私 {\displaystyle i} × j {\displaystyle x_{j}}

その間： s > 0 {\displaystyle s>0}

  • 各例の重みを設定します。ここで、は例のマージンです。 W 私 （ × j ） ＝ e − （ r 私 （ × j ） + s ） 2 c {\displaystyle W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}} r 私 （ × j ） {\displaystyle r_{i}(x_{j})} × j {\displaystyle x_{j}}
  • 次のような分類器を見つける h 私 : X → { − 1 、 + 1 } {\displaystyle h_{i}:X\to \{-1,+1\}} ∑ j W 私 （ × j ） h 私 （ × j ） y j > 0 {\displaystyle \sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0}
  • 方程式を満たす値を求めよ。 （これは、SchapireとSingerによって提示された条件に似ていることに注意。 [3] この設定では、となるような を数値的に求めている。）この更新は制約 に従う 。 ここで 、はマージンのある点の潜在的損失である。 α 、 t {\displaystyle \alpha,t}
    ∑ j h 私 （ × j ） y j e − （ r 私 （ × j ） + α h 私 （ × j ） y j + s − t ） 2 c ＝ 0 {\displaystyle \sum _{j}h_{i}(x_{j})y_{j}e^{-{\frac {(r_{i}(x_{j})+\alpha h_{i}(x_{j})y_{j}+st)^{2}}{c}}}=0}
    E W 私 + 1 [ h 私 （ × j ） y j ] ＝ 0 {\displaystyle E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0} W 私 + 1 ＝ 経験 ⁡ （ ⋯ ⋯ ） {\displaystyle W_{i+1}=\exp \left({\frac {\cdots }{\cdots }}\right)} E W 私 + 1 [ h 私 （ × j ） y j ] ＝ 0 {\displaystyle E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0}

    ∑ （ Φ （ r 私 （ × j ） + α h （ × j ） y j + s − t ） − Φ （ r 私 （ × j ） + s ） ） ＝ 0 {\displaystyle \sum \left(\Phi \left(r_{i}(x_{j})+\alpha h(x_{j})y_{j}+st\right)-\Phi \left(r_{i}(x_{j})+s\right)\right)=0}
    Φ （ z ） ＝ 1 − エルフ （ z / c ） {\displaystyle \Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})} r 私 （ × j ） {\displaystyle r_{i}(x_{j})}
  • 各例の余白を更新します。 r 私 + 1 （ × j ） ＝ r 私 （ × j ） + α h （ × j ） y j {\displaystyle r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}}
  • 残り時間を更新します: s ＝ s − t {\displaystyle s=st}

出力： H （ × ） ＝ サイン （ ∑ 私 α 私 h 私 （ × ） ） {\displaystyle H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)}

実証的結果

ノイズの多いデータセットを用いた予備実験の結果、BrownBoostはAdaBoostの一般化誤差を上回りました。しかし、LogitBoostもBrownBoostと同等の性能を示しました。[4] BrownBoostの実装はオープンソースソフトウェアJBoostにあります。

参照

参考文献

  1. ^ Yoav Freund. 多数決ブーストアルゴリズムの適応型バージョン. 機械学習, 43(3):293--318, 2001年6月.
  2. ^ Dietterich, TG, (2000). 決定木のアンサンブル構築における3つの手法（バギング、ブースティング、ランダム化）の実験的比較. 機械学習, 40 (2) 139-158.
  3. ^ Robert SchapireとYoram Singer. 信頼度評価予測を用いたブースティングの改善. Journal of Machine Learning, Vol 37(3), 297-336ページ. 1999
  4. ^ Ross A. McDonald、David J. Hand、Idris A. Eckley. 人工クラスノイズを含む実データセットにおける3つのブースティングアルゴリズムの実証的比較。Multiple Classifier Systems、Lecture Notes in Computer Scienceシリーズ、35-44ページ、2003年。
  • JBoost
「https://en.wikipedia.org/w/index.php?title=BrownBoost&oldid=1314913228」から取得