ブースティング（機械学習）

機械学習（ML）において、ブースティングは主にバイアス（分散ではなく）を減らすためのアンサンブル メタヒューリスティックです。^[1]また、 ML分類および回帰アルゴリズムの安定性と精度を向上させることもできます。そのため、弱い学習者を強い学習者に変換するための教師あり学習で広く使用されています。 ^[2]

ブースティングの概念は、カーンズとヴァリアント（1988、1989）が提起した疑問に基づいています。^{[3] [4]}「弱い学習者の集合から、強い学習者を 1 人作成できるか？」弱い学習者は、真の分類とわずかにしか相関しない分類器として定義されます。強い学習者は、真の分類と任意によく相関する分類器です。ロバート・シャピレは、1990 年に発表された論文でこの疑問に肯定的に答えました。^{[5]これは機械学習と}統計に大きな影響を与え、最も顕著なのはブースティングの開発につながりました。^[6]

当初、仮説ブースティング問題は、単に弱い学習者を強い学習者に変えるプロセスを指していました。^[3]これを実現するアルゴリズムはすぐに「ブースティング」として知られるようになりました。フロイントとシャピレのアーク法（適応的再サンプリングと結合）^[7]は、一般的な手法として、ブースティングとほぼ同義です。^[8]

ブースティングはアルゴリズム的に制約されていませんが、ほとんどのブースティング アルゴリズムは、分布に関して弱い分類器を繰り返し学習し、それらを最終的な強い分類器に追加することで構成されます。これらが追加されると、弱い学習器の精度に関連する方法で重み付けされます。弱い学習器が追加された後、データの重みが再調整されます。これは「再重み付け」と呼ばれます。誤分類された入力データはより高い重みを獲得し、正しく分類された例は重みが減ります。^{[注 1]}したがって、将来の弱い学習器は、以前の弱い学習器が誤分類した例に重点を置きます。

ブースティングアルゴリズムは数多く存在します。ロバート・シャピレ（再帰的多数決ゲート定式化）^[5]とヨアヴ・フロイント（多数決によるブースト）^{[9]が提案したオリジナルのアルゴリズムは}適応型ではなく、弱学習者の利点を十分に生かすことができませんでした。その後、シャピレとフロイントは適応型ブースティングアルゴリズムであるAdaBoostを開発し、権威あるゲーデル賞を受賞しました。

おそらくほぼ正しい学習定式化における証明可能なブースティングアルゴリズムだけが、^正確にブースティングアルゴリズムと呼ぶことができます。^{ブースティング}アルゴリズムと精神が似ている他のアルゴリズムは「レバレッジアルゴリズム」と呼ばれることもありますが、誤ってブースティングアルゴリズムと呼ばれることもあります。^[9]

多くのブースティングアルゴリズム間の主な違いは、トレーニングデータポイントと仮説の重み付け 方法です。AdaBoostは非常に人気があり、弱い学習者に適応できる最初のアルゴリズムであったため、歴史的に最も重要なものです。大学の機械学習コースでは、ブースティングの入門編の基礎となることがよくあります。^[10] LPBoost、TotalBoost、BrownBoost、xgboost、MadaBoost、LogitBoostなど、より新しいアルゴリズムも多数あります。多くのブースティングアルゴリズムはAnyBoostフレームワークに適合します。^{[9]これは、ブースティングが}凸コスト関数を使用して関数空間で勾配降下を実行することを示しています。

世の中のさまざまな既知の物体を含む画像が与えられれば、それらから分類器を学習して、将来の画像内の物体を自動的に分類することができます。物体の画像特徴に基づいて構築された単純な分類器は、分類性能が弱い傾向があります。物体分類にブースティング法を使用することは、弱い分類器を特別な方法で統合して、分類の全体的な能力を高める方法です。^{[引用が必要]}

物体分類は、画像に特定のカテゴリの物体が含まれているかどうかを判断するというコンピュータビジョンの典型的なタスクです。この考え方は、認識、識別、検出と密接に関連しています。外観に基づく物体分類には、通常、特徴抽出、分類器の学習、分類器の新しい例への適用が含まれます。物体のカテゴリを表現する方法は多数あり、たとえば、形状分析、バッグオブワードモデル、 SIFTなどのローカル記述子などがあります。教師あり分類器の例としては、ナイーブベイズ分類器、サポートベクターマシン、ガウス分布の混合、ニューラルネットワークなどがあります。ただし、研究^{[ which? ]により、物体のカテゴリと画像内の位置は、}教師なしの方法でも検出できることが示されています。 ^[11]

画像内の物体カテゴリーの認識は、特にカテゴリーの数が多い場合には、コンピュータビジョンにおける困難な問題である。これは、クラス内変動性が高く、同じカテゴリー内の物体のバリエーション全体にわたって一般化する必要があることに起因している。1つのカテゴリー内の物体は、かなり異なって見えることがある。同じ物体であっても、異なる視点、スケール、照明の下では似ていないように見えることがある。背景の乱雑さや部分的な遮蔽も、認識を困難にする。^[12] 人間は何千もの物体タイプを認識できるが、既存の物体認識システムのほとんどは、人間の顔、車、単純な物体など、ほんの数種類の[^{定量化]だけを認識するように訓練されている。 [13] [更新が必要? ]} より多くのカテゴリーを扱い、新しいカテゴリーを段階的に追加できるようにするための研究が非常に活発に行われており、一般的な問題は未解決のままであるが、いくつかのマルチカテゴリー物体検出器（最大数百または数千のカテゴリー^[14]）が開発されている。1つの方法は、特徴共有とブースティングによるものである。

AdaBoost は、バイナリ分類の例として顔検出に使用できます。2 つのカテゴリは顔と背景です。一般的なアルゴリズムは次のとおりです。

1. 単純な機能の大きなセットを形成する
2. トレーニング画像の重みを初期化する
3. Tラウンドの場合
   1. 重みを正規化する
   2. セットから利用可能な特徴について、単一の特徴を使用して分類器をトレーニングし、トレーニングエラーを評価する
   3. 誤差が最も少ない分類器を選択する
   4. トレーニング画像の重みを更新します。この分類器によって誤って分類された場合は重みを増やし、正しく分類された場合は重みを減らします。
4. T分類器の線形結合として最終的な強力な分類器を形成する（トレーニングエラーが小さい場合は係数が大きくなる）

ブースティング後、200個の特徴から構築された分類器は、偽陽性率の下で95%の検出率を達成できる可能性がある。^[15]${\displaystyle 10^{-5}}$

バイナリ分類におけるブースティングのもう一つの応用は、動きと外観のパターンを使用して歩行者を検出するシステムです。 ^[16]この研究は、歩行者を検出するために動きの情報と外観の情報の両方を特徴として組み合わせた初めての研究です。これは、Viola-Jones物体検出フレームワークと同様のアプローチを採用しています。

バイナリ分類と比較すると、マルチクラス分類は、同時にカテゴリ間で共有できる共通の特徴を探します。これらは、より一般的なエッジのような特徴になります。学習中、各カテゴリの検出器は共同でトレーニングできます。個別にトレーニングする場合と比較すると、より一般化され、必要なトレーニング データが少なくなり、同じパフォーマンスを達成するために必要な特徴が少なくなります。

アルゴリズムの主な流れはバイナリの場合と同様です。異なるのは、共同トレーニングエラーの尺度が事前に定義されることです。各反復中に、アルゴリズムは単一の特徴の分類器を選択します（より多くのカテゴリで共有できる特徴が推奨されます）。これは、マルチクラス分類をバイナリ分類（カテゴリのセットと残りのもの）に変換するか、^[17]分類器の特徴を持たないカテゴリからペナルティエラーを導入することによって実行できます。^[18]

論文「マルチクラスおよびマルチビュー オブジェクト検出のための視覚的特徴の共有」では、A. Torralba らがブースティングに GentleBoost を使用し、トレーニング データが限られている場合、同じブースティング ラウンドであれば、共有特徴による学習は共有しない場合よりもはるかに優れた結果になることを示しました。また、特定のパフォーマンス レベルでは、特徴共有検出器に必要な特徴の総数 (したがって分類器の実行時間コスト) は、クラス数にほぼ対数的に比例することが観察されています。つまり、共有しない場合は線形増加よりも遅くなります。論文「視覚的形状アルファベットを使用したオブジェクト検出器の増分学習」でも同様の結果が示されていますが、著者らはブースティングにAdaBoost を使用しています。

ブースティングアルゴリズムは、凸最適化アルゴリズムまたは非凸最適化アルゴリズムに基づくことができます。AdaBoostやLogitBoostなどの凸アルゴリズムは、ランダムノイズによって「打ち負かされる」可能性があり、弱い仮説の基本的かつ学習可能な組み合わせを学習することができません。^{[19] [20]この制限は、2008年にLong＆Servedioによって指摘されました。しかし、2009年までに、複数の著者が、} BrownBoostなどの非凸最適化に基づくブースティングアルゴリズムは、ノイズの多いデータセットから学習でき、特にLong–Servedioデータセットの基礎となる分類器を学習できることを実証しました。

• scikit-learn 、 Python用のオープンソース機械学習ライブラリ
• Orange、無料のデータマイニングソフトウェアスイート、モジュール Orange.ensemble
• Wekaは、 AdaBoostやLogitBoostなどのブースティングアルゴリズムのさまざまな実装を提供する機械学習ツールセットです。
• Rパッケージ GBM (一般化ブースト回帰モデル) は、Freund と Schapire の AdaBoost アルゴリズムと Friedman の勾配ブースティング マシンの拡張を実装します。
• jboost; AdaBoost、LogitBoost、RobustBoost、Boostexter、交互決定木
• R パッケージ adabag: マルチクラス AdaBoost.M1、AdaBoost-SAMME、バギングを適用します
• R パッケージ xgboost: 線形およびツリーベースのモデルに対する勾配ブースティングの実装。

• Freund, Yoav; Schapire, Robert E. (1997). 「オンライン学習の意思決定理論による一般化とブースティングへの応用」(PDF) . Journal of Computer and System Sciences . 55 (1): 119–139. doi :10.1006/jcss.1997.1504.
• Schapire, Robert E. (1990). 「弱い学習可能性の強さ」.機械学習. 5 (2): 197–227. doi : 10.1007/BF00116037 . S2CID  6207294.
• Schapire, Robert E.; Singer, Yoram (1999). 「信頼度評価予測子を使用したブースティングアルゴリズムの改善」.機械学習. 37 (3): 297–336. doi : 10.1023/A:1007614523901 . S2CID  2329907.
• Zhou, Zhihua (2008) 「ブースティング アルゴリズムのマージン説明について」(PDF)。第 21 回学習理論年次会議 (COLT'08) の議事録: 479–490。
• Zhou, Zhihua (2013). 「ブースティングのマージン説明に関する疑問について」(PDF) .人工知能. 203 : 1–18. arXiv : 1009.3613 . doi :10.1016/j.artint.2013.07.002. S2CID  2828847.

• Robert E. Schapire (2003); 機械学習へのブースティングアプローチ：概要、MSRI（数学科学研究所）非線形推定と分類に関するワークショップ
• 周志華(2014) Boosting 25 years Archived 2016-08-20 at the Wayback Machine、CCL 2014 基調講演。