アダブースト

AdaBoost （ Adaptive Boostingの略）は、1995年にYoav FreundとRobert Schapireによって考案された統計的分類メタアルゴリズムであり、彼らはその功績により2003年のゲーデル賞を受賞しました。これは、パフォーマンスを向上させるために、多くの種類の学習アルゴリズムと組み合わせて使用​​できます。複数の弱学習器の出力は、ブーストされた分類器の最終出力を表す重み付き和に結合されます。通常、AdaBoostは二値分類のために提示されますが、複数のクラスまたは実数値の境界区間に一般化することもできます。^{[ 1 ] [ 2 ]}

AdaBoostは、後続の弱い学習器（モデル）が、前のモデルによって誤分類されたインスタンスを優先するように調整されるという意味で適応的です。問題によっては、他の学習アルゴリズムよりも過学習を起こしにくい場合があります。個々の学習器は弱くても構いませんが、それぞれの性能がランダムな推測よりもわずかに優れていれば、最終的なモデルは強い学習器に収束することが証明されています。

AdaBoostは通常、弱いベース学習器（決定スタンプなど）を組み合わせるために使用されますが、強力なベース学習器（より深い決定木など）を効果的に組み合わせ、さらに正確なモデルを生成することも示されています。^{[ 3 ]}

どの学習アルゴリズムも、特定の問題タイプには適しているものの、他の問題タイプには適していない傾向があります。また、データセットで最適なパフォーマンスを達成するには、通常、調整すべきさまざまなパラメータや構成が多数存在します。AdaBoost（弱学習器として決定木を使用）は、すぐに使える最良の分類器としてよく言及されます。^{[ 4 ] [ 5 ]}決定木学習で使用する場合、AdaBoostアルゴリズムの各段階で収集された、各トレーニングサンプルの相対的な「難しさ」に関する情報がツリー成長アルゴリズムに入力され、後のツリーは分類が難しい例に焦点を当てる傾向があります。

AdaBoostとは、ブースト分類器を訓練する特定の方法を指します。ブースト分類器とは、次の形式の分類器です。 $${\displaystyle F_{T}(x)=\sum _{t=1}^{T}f_{t}(x)}$$ それぞれ${\displaystyle f_{t}}$オブジェクトを受け取る弱い学習者${\displaystyle x}$入力としてオブジェクトを受け取り、オブジェクトのクラスを示す値を返します。例えば、2クラス分類問題では、弱学習器の出力の符号が予測されたオブジェクトのクラスを示し、絶対値はその分類に対する信頼度を示します。

各弱学習器は出力仮説を生成する${\displaystyle h}$予測を修正する${\displaystyle h(x_{i})}$トレーニングセット内の各サンプルについて。各反復で${\displaystyle t}$弱い学習器が選択され、係数が割り当てられます。$\displaystyle \alpha _{t}}$総訓練誤差${\displaystyle E_{t}}$結果として生じる${\displaystyle t}$-ステージブースト分類器が最小化されます。

$${\displaystyle E_{t}=\sum _{i}E[F_{t-1}(x_{i})+\alpha _{t}h(x_{i})]}$$

ここ${\displaystyle F_{t-1}(x)}$これは、前のトレーニング段階まで構築されたブースト分類器であり、${\displaystyle f_{t}(x)=\alpha _{t}h(x)}$これは、最終的な分類器に追加することが検討されている弱い学習器です。

この導出はロハス（2009）に従っている：^{[ 6 ]}

データセットがあると仮定します${\displaystyle \{(x_{1},y_{1}),\ldots ,(x_{N},y_{N})\}}$各アイテム${\displaystyle x_{i}}$関連クラスがあります$\displaystyle y_{i}\in \{-1,1\}}$、および一連の弱い分類器${\displaystyle \{k_{1},\ldots ,k_{L}\}}$それぞれが分類結果を出力する${\displaystyle k_{j}(x_{i})\in \{-1,1\}}$各項目について。${\displaystyle (m-1)}$第 1 回目の反復では、ブースト分類器は次の形式の弱分類器の線形結合になります。 $${\displaystyle C_{(m-1)}(x_{i})=\alpha _{1}k_{1}(x_{i})+\cdots +\alpha _{m-1}k_{m-1}(x_{i}),}$$ クラスは${\displaystyle C_{(m-1)}(x_{i})}$.${\displaystyle m}$第 1 回目の反復では、別の弱分類器を追加することで、これをより優れたブースト分類器に拡張します。${\displaystyle k_{m}}$別の重りと共に$\displaystyle \alpha _{m}}$: $${\displaystyle C_{m}(x_{i})=C_{(m-1)}(x_{i})+\alpha _{m}k_{m}(x_{i})}$$

したがって、どの弱分類器が最適かを決定する必要がある。${\displaystyle k_{m}}$、そしてその重さは$\displaystyle \alpha _{m}}$そうあるべきです。総誤差を定義します${\displaystyle E}$の${\displaystyle C_{m}}$各データポイントにおける 指数関数的損失の合計として、以下のように表されます。$${\displaystyle E=\sum _{i=1}^{N}e^{-y_{i}C_{m}(x_{i})}=\sum _{i=1}^{N}e^{-y_{i}C_{(m-1)}(x_{i})}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}}$$

賃貸${\displaystyle w_{i}^{(1)}=1}$そして${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}}$のために${\displaystyle m>1}$、 我々は持っています： $${\displaystyle E=\sum _{i=1}^{N}w_{i}^{(m)}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}}$$

この合計は、正しく分類されたデータポイント間で分割できます。${\displaystyle k_{m}}$（それで${\displaystyle y_{i}k_{m}(x_{i})=1}$）そして誤分類されたもの（そのため${\displaystyle y_{i}k_{m}(x_{i})=-1}$): $${\displaystyle {\begin{aligned}E&=\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}\\&=\sum _{i=1}^{N}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}\left(e^{\alpha _{m}}-e^{-\alpha _{m}}\right)\end{aligned}}}$$

この方程式の右辺のうち、に依存する部分は${\displaystyle k_{m}}$は${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$すると、${\displaystyle k_{m}}$最小限に抑える${\displaystyle E}$セットの中の1つです${\displaystyle \{k_{1},\ldots ,k_{L}\}}$最小限に抑える${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$[${\displaystyle \alpha _{m}>0}$]、つまり重み付き誤差が最も低い弱分類器（重み付き）${\displaystyle w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}}$)

希望する重量を決定する${\displaystyle \alpha _{m}}$最小限に抑える${\displaystyle E}$と共に${\displaystyle k_{m}}$先ほど決定したように、以下のように区別します。 $${\displaystyle {\frac {dE}{d\alpha _{m}}}={\frac {d(\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}})}{d\alpha _{m}}}}$$

価値${\displaystyle \alpha _{m}}$上記の式を最小化する式は次のとおりです。 $${\displaystyle \alpha _{m}={\frac {1}{2}}\ln \left({\frac {\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}}\right)}$$

弱分類器の重み付きエラー率を計算すると次のようになります。${\displaystyle \epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}}$したがって、次のことが導かれる。 $${\displaystyle \alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m}}}\right)}$$ これは負のロジット関数に0.5を掛けたものです。凸性のため、${\displaystyle E}$関数として${\displaystyle \alpha _{m}}$この新しい表現は${\displaystyle \alpha _{m}}$損失関数のグローバル最小値を与える。

注：この導出は、次の場合にのみ適用されます。${\displaystyle k_{m}(x_{i})\in \{-1,1\}}$ただし、弱い学習器が偏っている場合など、他のケースでは良い初期推測となる可能性があります（${\displaystyle k_{m}(x)\in \{a,b\},a\neq -b}$）は複数の葉を持つ（${\displaystyle k_{m}(x)\in \{a,b,\dots ,n\}}$）または他の関数${\displaystyle k_{m}(x)\in \mathbb {R} }$。

このようにして、AdaBoostアルゴリズムを導出しました。各反復で、分類器を選択します。${\displaystyle k_{m}}$これは、加重誤差の合計を最小化する。${\textstyle \sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}$これを使用してエラー率を計算します${\displaystyle \epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}}$これを使って重量を計算します${\displaystyle \alpha _{m}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{m}}{\epsilon _{m}}}\right)}$そして最後に、これを利用してブースト分類器を改善する。${\displaystyle C_{m-1}}$に${\displaystyle C_{m}=C_{(m-1)}+\alpha _{m}k_{m}}$。

ブースティングは、各サンプルの特徴を線形回帰の一種として用いるものです。${\displaystyle x_{i}}$弱い学習器の出力です${\displaystyle h}$適用された${\displaystyle x_{i}}$。

回帰分析は適合させようとするが、${\displaystyle F(x)}$に${\displaystyle y(x)}$一般性を損なうことなく可能な限り正確に、通常は最小二乗誤差を用いて${\displaystyle E(f)=(y(x)-f(x))^{2}}$一方、AdaBoostのエラー関数は${\displaystyle E(f)=e^{-y(x)f(x)}}$最終結果の符号のみが使用されるという事実を考慮すると、${\displaystyle |F(x)|}$誤差を増加させることなく 1 よりはるかに大きくなる可能性があります。ただし、サンプルの誤差の指数関数的増加${\displaystyle x_{i}}$として${\displaystyle -y(x_{i})f(x_{i})}$増加することで、外れ値に過剰な重みが割り当てられることになる。

指数誤差関数を選択する特徴の一つは、最終的な加法モデルの誤差が各段階の誤差の積である、つまり、${\displaystyle e^{\sum _{m}-y_{i}f_{m}(x_{i})}=\prod _{m}e^{-y_{i}f_{m}(x_{i})}}$したがって、AdaBoost アルゴリズムの重み更新は、誤差の再計算に相当することがわかります。${\displaystyle F_{t}(x)}$各段階の後。

損失関数の選択には多くの柔軟性が認められています。損失関数が単調かつ連続的に微分可能である限り、分類器は常に純粋な解へと導かれます。^{[ 7 ]} Zhang (2004) は、最小二乗法に基づく損失関数、修正されたHuber 損失関数を提供しています。 $${\displaystyle \phi (y,f(x))={\begin{cases}-4yf(x)&{\text{if }}yf(x)<-1,\\(yf(x)-1)^{2}&{\text{if }}-1\leq yf(x)\leq 1.\\0&{\text{if }}yf(x)>1\end{cases}}}$$

この関数は、LogitBoostよりも動作が安定しています。${\displaystyle f(x)}$1または-1に近い値で、「過信」予測にペナルティを与えない（${\displaystyle yf(x)>1}$）修正されていない最小二乗法とは異なり、1より大きい信頼度で誤分類されたサンプルに対して、2次または指数関数的ではなく線形的にのみペナルティを課すため、外れ値の影響を受けにくい。

ブースティングは、凸関数集合上の凸損失関数の最小化と見なすことができる。^{[ 8 ]}具体的には、AdaBoostによって最小化される損失は指数損失である。 $${\displaystyle \sum _{i}\phi (i,y,f)=\sum _{i}e^{-y_{i}f(x_{i})},}$$ 一方、LogitBoostはロジスティック回帰を実行し、 $${\displaystyle \sum _{i}\phi (i,y,f)=\sum _{i}\ln \left(1+e^{-y_{i}f(x_{i})}\right).}$$

勾配降下法のアナロジーでは、各トレーニングポイントに対する分類器の出力はポイントとみなされます。${\displaystyle \left(F_{t}(x_{1}),\dots ,F_{t}(x_{n})\right)}$n 次元空間では、各軸がトレーニング サンプルに対応し、各弱学習器は${\displaystyle h(x)}$これは固定された方向と長さのベクトルに対応し、目標はターゲットポイントに到達することです。${\displaystyle (y_{1},\dots ,y_{n})}$（または損失関数の値が${\displaystyle E_{T}(x_{1},\dots ,x_{n})}$最小ステップで、その時点での値よりも小さい値を見つけます。したがって、AdaBoost アルゴリズムは、コーシー(その時点での値を見つける) またはコーシー(その時点での値よりも小さい値を見つけます)を実行します。${\displaystyle h(x)}$最も急な勾配で、${\displaystyle \alpha }$テストエラーを最小限に抑えるため）またはニュートン法（ターゲットポイントを選択し、${\displaystyle \alpha h(x)}$それは${\displaystyle F_{t}}$その点に最も近い）トレーニング誤差の最適化。

と：

• サンプル${\displaystyle x_{1}\dots x_{n}}$
• 望ましい出力${\displaystyle y_{1}\dots y_{n},y\in \{-1,1\}}$
• 初期重み${\displaystyle w_{1,1}\dots w_{n,1}}$設定${\displaystyle {\frac {1}{n}}}$
• エラー関数${\displaystyle E(f(x),y_{i})=e^{-y_{i}f(x_{i})}}$
• 学習能力の低い人${\displaystyle h\colon x\rightarrow \{-1,1\}}$

のために${\displaystyle t}$で${\displaystyle 1\dots T}$:

• 選ぶ${\displaystyle h_{t}(x)}$:
  • 学習能力の低い人を見つける${\displaystyle h_{t}(x)}$最小限に抑える${\displaystyle \epsilon _{t}}$誤分類された点の加重合計誤差${\displaystyle \epsilon _{t}=\sum _{\stackrel {i=1}{h_{t}(x_{i})\neq y_{i}}}^{n}w_{i,t}}$
  • 選ぶ${\displaystyle \alpha _{t}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{t}}{\epsilon _{t}}}\right)}$
• アンサンブルに追加:
  • ${\displaystyle F_{t}(x)=F_{t-1}(x)+\alpha _{t}h_{t}(x)}$
• 重みを更新します:
  • ${\displaystyle w_{i,t+1}=w_{i,t}e^{-y_{i}\alpha _{t}h_{t}(x_{i})}}$のために${\displaystyle i}$で${\displaystyle 1\dots n}$
  • 正規化${\displaystyle w_{i,t+1}}$そのため${\displaystyle \sum _{i}w_{i,t+1}=1}$
  • （注：${\displaystyle {\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i,t+1}}{\sum _{h_{t}(x_{i})\neq y_{i}}w_{i,t+1}}}={\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i,t}}{\sum _{h_{t}(x_{i})\neq y_{i}}w_{i,t}}}}$（各ステップにおいて、新しい重みの計算を簡略化できる。）

• ブートストラップ集計
• コブースト
• ブラウンブースト
• 勾配ブースティング
• 乗法重み更新法 §  AdaBoostアルゴリズム