オンラインバギング
- 提唱者
- Oza, N. C. & Russell, S.
- 年
- 2001
- 種類
- Online ensemble (streaming bagging)
- 系統
- Machine learning
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
オンラインバギングは、OzaとRussellが2001年に発表したストリーミングアンサンブル法であり、古典的なブートストラップ集約(Bagging)フレームワークをオンライン学習設定に適用したものです。固定されたデータセットを再サンプリングする代わりに、入力される各インスタンスは、ポアソン分布Poisson(1)に従って分布する回数だけすべてのベース学習器に供給され、ストリームの進行とともにブートストラップサンプリングを忠実に近似します。その結果、データセット全体を保存することなく、コンセプトドリフトと連続的なデータ到着に対応できる、堅牢でインクリメンタルに更新されるアンサンブルが実現します。
手法の背後にある直感
古典的なバギングは、固定されたデータセットからランダムなブートストラップサンプルを抽出し、各サンプルごとに1つのツリーを訓練します。オンラインバギングは、データセット全体を一度に見ることなくこれを模倣します。新しい例が到着すると、平均1のポアソン分布から抽出されたランダムな回数だけ、各ベース学習器に渡されます。平均して、各学習器は例を1回見ることになります。これはバッチモードでのブートストラップ再サンプリングが達成することと全く同じですが、このランダム性が学習器間の相関を低減します。データを保存する必要がないため、アンサンブルはストリームとともに無限に成長し、時間の経過とともに変化する分布に自然に適応できます。
歴史学
オンラインバギングは、Nitesh OzaとStuart RussellによってAISTATS 2001で、Breimanの1996年のバギングアルゴリズムをオンライン設定に理論的および実践的に拡張したものとして発表されました。その主要な洞察 — ブートストラップ再サンプリングをインスタンスごとのPoisson(1)重み付けに置き換えること — は、近似を数学的に厳密なものにしました。これはストリーミング機械学習の文献における基礎的なアルゴリズムとなり、MOA (Massive Online Analysis) のようなプラットフォームにおけるベースラインアンサンブルとなっています。MOAは2010年以降、ストリーム分類器のほとんどの経験的評価を推進してきました。
使うべき場面
データが連続的なストリームとして到着し、データセット全体を保存することが非現実的または禁止されている場合(例:センサーログ、クリックストリーム、金融ティックデータ、リアルタイム監視)にオンラインバギングを使用します。新しい観測ごとに更新され、軽度のコンセプトドリフトを許容し、メモリ効率を維持する分類または回帰が必要な場合に適切です。固定された中小規模のデータセットに対して、バッチRandom Forestの代替としてオンラインバギングを使用しないでください。その場合、交差検定を用いたバッチアンサンブルの方が優れた性能を発揮します。また、明示的なドリフト検出メカニズムを追加せずに、データストリームが深刻な急激なドリフトを示す場合も避けてください。
限界と注意点
- 静的データセットでは、Random ForestやXGBoostのようなバッチメソッドは、完全な交差検定と最適な分割を使用できるため、オンラインバギングを一貫して上回ります。
- 基本的なオンラインバギングは、深刻なコンセプトドリフトに対する限定的な回復力しか提供しません。専用のドリフト検出器(例:ADWIN)を外部から追加する必要があります。
- ポアソン重み付けはインスタンスごとに余分な分散を導入するため、短いストリームでは収束が遅くなる可能性があります。
- 解釈性が低い:多くのインクリメンタルに成長したツリーのアンサンブルは、単一の決定木よりも検査が困難です。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- データを一度に1インスタンスずつ一定のメモリで処理し、真に無制限のストリームを可能にします。
- ポアソン重み付けはブートストラップ再サンプリングを厳密に近似し、バッチバギングに匹敵するアンサンブルの分散低減をもたらします。
- 自然な並列化が可能:各ベース学習器は独立して更新されるため、分散ストリーミングアーキテクチャに適しています。
- ツリーの深さほど敏感なハイパーパラメータはありません。アンサンブルは多様性を通じて自己調整します。
- 構造的な変更なしに、多クラス分類および回帰に直接拡張できます。
応用
- 連続的なトランザクションストリームにおけるリアルタイム不正検出。
- 産業用IoT設定におけるセンサーデータストリームからの予知保全。
- ユーザー行動が継続的に変化するオンライン広告におけるクリック率予測。
- 高スループットのパケットストリームにおけるネットワーク侵入検知。
- 環境モニタリング:空気品質または気象センサーの読み取り値のインクリメンタル分類。
使い方
使い方
到着する各インスタンスについて、すべてのベース学習器に対して、ポアソン分布Poisson(1)から独立して重みkがサンプリングされます。重みが0の場合、学習器はこのインスタンスを完全にスキップします。重みが2の場合、インスタンスから2回学習します。この確率的重み付けは、ブートストラップ再サンプリングのオンライン版であり、アルゴリズムの数学的核となります。
数式
k \sim \text{Poisson}(1)各ベース学習器(通常はHoeffding Treeのようなインクリメンタル決定木)は、割り当てられた重みを持つ現在のインスタンスを受け取り、その内部モデルを直ちに更新します。処理後、インスタンスは保存されません。このシングルパス特性により、メモリが一定に保たれ、アンサンブルが任意の長さのストリームにスケールできるようになります。
予測が必要な場合、M個すべてのベース学習器がクエリインスタンスに対して個々の出力を生成します。アンサンブルは、分類の場合は多数決、回帰の場合は算術平均によってこれらを結合します。これはバッチバギングと同じ集約ロジックですが、インクリメンタルに訓練されたモデルで計算されます。
数式
\hat{y} = \text{mode/mean of } M \text{ base learners}よくある落とし穴
- 訓練開始前に作成されたホールドアウトテストセットでオンラインバギングを評価すること — 代わりに、ストリーミング機械学習の標準であるプレクエンシャル(テスト・アンド・トレイン)評価を使用してください。
- ベース学習器のデフォルト数(通常10)で十分であると仮定すること。安定した予測には、通常50〜100以上の学習器のアンサンブルが必要です。
- コンセプトドリフトを無視すること:ドリフト検出なしにドリフトするストリームにオンラインバギングをデプロイすると、精度が静かに劣化します。
- 静的ベンチマークでの精度をバッチメソッドと比較し、オンラインバギングが劣っていると結論付けること — 正しい比較は、ストリーミングベンチマークで観測されたインスタンスごとの精度です。
- 真にインクリメンタルではないベース学習器(例:再訓練されたバッチツリー)を使用すること。これはオンラインフレームワークのメモリと速度の利点を打ち消します。
よくある質問
なぜ特にPoisson(1)なのですか?
平均1のポアソン分布は、nが無限大に近づくにつれて、サイズnのブートストラップサンプルに観測値が出現する回数を近似します。学習器ごとにインスタンスごとにPoisson(1)を使用することで、この極限挙動を正確に再現し、オンライン近似を理論的に健全なものにします。
オンラインバギングはAdaptive Random Forestとどう異なりますか?
Adaptive Random Forest (Gomes et al., 2017) は、各分割でのランダムな特徴サブサンプリング(バッチRandom Forestと同様)を追加し、コンセプトドリフトが検出されたときに個々の学習器をリセットするツリーごとのドリフト検出器を統合することで、オンラインバギングを拡張したものです。オンラインバギングはより単純な基盤であり、Adaptive Random Forestはその上に構築された現在の最先端のストリーミングアンサンブルです。
どのベース学習器を使用すべきですか?
最も一般的な選択肢はHoeffding Tree(VFDTとも呼ばれる)で、これは典型的なインクリメンタル決定木です。これはHoeffding境界を使用して、ノードで分割するのに十分なデータがいつ見られたかを決定し、過去のインスタンスを保存することなくツリーを更新可能に保ちます。
いくつのベース学習器が必要ですか?
MOAフレームワークにおける経験的ベンチマークは、ほとんどのストリーミングタスクで安定したアンサンブル性能を得るために50〜100個のベース学習器を推奨しています。学習器の数を減らすと計算コストは削減されますが、特にストリームの初期段階では予測の分散が増加します。
オンラインバギング分類器をどのように評価すべきですか?
プレクエンシャル評価を使用してください。入力される各インスタンスについて、まずそのラベルを予測し、次にモデルを更新します。精度は、正解予測の移動平均として計算されます。これにより、先読みバイアスが回避され、実際のデプロイ条件が反映されます。
関連する手法
参考文献
Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.
出版物の文献を開くコピーしました。Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.
出版物の文献を開くコピーしました。