Optimized Sequential Testing for Binary Ensemble Classifiers

問題提起
ランダムフォレストのようなアンサンブル分類器は、多数決によって複数の基底モデル（決定木など）の予測を組み合わせ、高い精度を実現します。しかし、大規模なアンサンブルは推論時の計算コストが非常に高く、低電力デバイスや高頻度なアプリケーションにおいて問題となります。本研究が取り組む核心的な問題は、精度を大幅に損なうことなく、バイナリ・アンサンブル分類器のテスト時の計算コストをいかに削減するかです。具体的には、全 $N$ 個のモデルを実行するのではなく、「明確な過半数」が現れた時点で基底モデルの評価を逐次停止させる戦略を調査しています。目標は、期待される基底モデルの実行数（実行時間）を最小化しつつ、「不一致率（disagreement rate）」、すなわち早期停止したアンサンブルの結果がフルアンサンブルの結果と異なる確率を厳密に制御することです。

手法
本論文では、早期停止問題を、実行された基底モデルの数を $i$、正の票数を $j$ とする状態 $(i, j)$ で定義される逐次テスト問題として定式化しています。著者らは、基底モデルがランダムな順序で実行されると仮定しており、これにより、基底モデル間の独立性を仮定することなく、超幾何分布を用いて任意の状態に到達する確率をモデル化することを可能にしています。

最適な停止戦略を見出すために、著者らは3つの異なる最適化フレームワークを提案しています。これらはすべて、計算効率を確保するために線形計画法（LP）として定式化されています。

1. Minimax（ミニマックス）: 最悪のケースにおける不一致率の制約条件下で、最悪のケースにおける期待実行時間を最小化します。この手法は、正の票数（$n$）の分布に関する事前知識を必要としません。
2. Minimean（ミニミーン）:既知または推定された分布 $\hat{D}$ を仮定し、期待される不一致率の制約条件下で、期待実行時間を最小化します。
3. Minimixed（ミニミクスト）: $n$ の分布を仮定し、最悪のケースにおける不一致率の制約条件下で、期待実行時間を最小化します。

著者らは、元の非線形最適化問題が条件付き確率決定変数（$p_{ij}, \pi_{ij}, \bar{\pi}_{ij}$）を用いて再定式化できることを示しています。この再定式化により、問題は $O(N^3)$ の決定変数を持つ線形計画法へと変換され、数百の決定木を持つアンサンブルに対しても効率的に解くことが可能になります。得られる戦略は概して決定論的であり、「エンベロープ（包絡線）」ルールに従います。すなわち、特定のステップ $i$ において、正の票数が上限の閾値を超えたか、あるいは下限の閾値を下回った場合に停止します。

主な貢献

• 理論的定式化: 本論文は、多数決ベースのバイナリ・アンサンブル分類器における早期停止の厳密な数学的枠組みを提供し、停止戦略と指標（実行時間および不一致率）を形式的に定義しています。
• 最適線形計画法による解法: 著者らは、3つの異なる最適性の概念（minimax, minimean, minimixed）に対する最適な停止戦略が、線形計画法を解くことで得られることを示しています。これは、ヒューリスティックに依存したり、基底モデル間の独立性を仮定したりすることが多かった従来の研究とは対照的です。
• 独立性の仮定の排除: Schwingら（2011）による従来のアンサンブル向けの逐次テスト法とは異なり、本手法は基底モデルが独立であると仮定していません。これにより、決定木の予測が相関しているランダムフォレストに直接適用することが可能となっています。
• 事前計算可能な戦略: 著者らは、様々なアンサンブルサイズと許容不一致率（ADR）に対して最適な戦略を事前計算しており、新しいデータセットごとに再最適化することなく、即座に適用できるようになっています（特にMinimaxアプローチにおいて）。

実証結果
提案手法は、101個の決定木（$N=101$）を用いたランダムフォレストを用い、UCI Machine Learning RepositoryおよびGrinsztajnらによって提案されたベンチマークの27の現実世界のデータセットで評価されました。

• 加速: ほとんどのデータセットにおいて、提案手法は不一致率0.1%（$10^{-3}$）を維持しながら、4倍以上のスピードアップ（実行時間をフルアンサンブルの10〜20%に削減）を達成しました。
• パフォーマンスの分散: キャリブレーション・セットを用いて票の分布を推定する Minimean アプローチが一般に最も高いスピードアップを実現し、次いで Minimixed、そして Minimax が最も保守的な結果となりました。
• データセットの特性: 早期停止の有効性は、決定木の票の分布と相関していました。決定木が一方のクラスに対して圧倒的な票を得る（二峰性分布）データセットでは、積極的な早期停止が可能でした。逆に、基底エラー率が高く、票の分布が中央に集中しているデータセット（例：「Dota2」や「Hospitalization」）では、合意形成に時間がかかるため、スピードアップの効果は小さくなりました。
• 比較: 提案手法は、二項信頼帯と独立性の仮定に依存するSchwingら（2011）のベースライン手法を上回りました。

意義と主張
本論文は、基底モデル間の独立性を仮定せずに、多数決ベースのバイナリ・アンサンブル分類器に対して証明可能な最適な早期停止戦略を実現した初めての手法であると主張しています。著者らは、本手法を用いることで、より大規模で高精度なアンサンブルを訓練し、各推論に特有の計算リソースのみを利用するように停止戦略を活用できる点を強調しています。

また、本論文は以下の限界についても謙虚に述べています。本手法はバイナリ分類および重みなしの多数決アンサンブルに限定されています。マルチクラス問題、回帰、または基底モデルに特定の重みや実行順序があるアンサンブルには直接適用できません。さらに、本手法はプルーニング（枝刈り）と互換性がありますが、プニングは早期停止を効果的にしている冗長性（相関のある票）の削減を目的としているため、プルーニングされたフォレストでは効果が劇的に減少する可能性があることも示唆されています。今後の課題として、マルチクラスや重み付きアンサンブルへの理論の拡張が挙げられています。