技術的概要：PACE（剪定と圧縮を組み合わせたアンサンブルモデル）

問題定義

アンサンブルモデル、特に決定木に基づくもの（ランダムフォレスト、ブースティングなど）は、最先端の予測性能を達成しますが、多数の弱学習器の集積により、しばしば過大なサイズに陥ります。この冗長性は、遅延に敏感でリソースが制約された環境での展開に対する重大な障壁となり、メモリフットプリントを増大させ、ロバスト性検証や解釈性といった下流タスクを複雑化します。

既存の解決策は一般的に 2 つのカテゴリーに分類されます：

1. 剪定（Pruning）： 再重み付けまたは削除によって、訓練済みのアンサンブルから冗長な学習器を破棄すること。効果的ではあるものの、破棄された学習器を置き換える新たな学習器を生成できないため、圧縮の可能性に上限が生じる可能性があります。
2. 圧縮（Compression）： 元のアンサンブルを近似するために、ゼロから新たな学習器を生成すること。高い圧縮率を達成できる場合もありますが、多くの手法は忠実性（正確な予測の一致）を失うか、元のモデルファミリーよりも複雑な学習器を生成することを要求し、モデルの構造的制約を破ります。

核心的な課題は、これらのパラダイムを統合し、無関係なデータ領域によって過度に制約されることなく、忠実性（元のアンサンブルの予測を保持すること）に関する厳密な保証を維持しながら、強力な圧縮を実現することです。

手法：PACE フレームワーク

PACE（Prune-And-Compress Ensemble）は、忠実性制御のフレームワークの下で統一された、能動的学習器生成と剪定を交互に行う 2 段階戦略を導入します。

1. 2 段階戦略

• フェーズ 1：能動的学習器生成（圧縮）： 固定された学習器セットから始めるのではなく、PACE は初期アンサンブルを豊かにするために能動的に新たな学習器を生成します。この段階ではカラム生成技術を利用します。目的は、緩和された剪定問題（$\ell_1$ノルム代替関数を使用）の最適値を低減させる「改善学習器」を見つけることです。
  • このプロセスは、下流のスパース化の可能性を向上させる学習器 $h$ を特定します。
  • 緩和を厳密に改善できる新たな学習器が存在するかを検出するための価格付け問題（pricing problem）が解かれます。そのような学習器が存在しない場合（$L(h) = \emptyset$）、生成フェーズは終了し、強化されたアンサンブルが最良の可能な緩和値を達成するために必要なすべての学習器を含んでいることが保証されます。
• フェーズ 2：剪定： アンサンブルが強化された後、PACE はこの拡張されたセットに対して元の剪定問題（重みの $\ell_0$ノルムを最小化）を解きます。これにより、より多様で規模の大きい学習器プールから重みの疎な部分集合を選択することが可能となり、元のセットのみを剪定する場合よりも、しばしばより小さな最終アンサンブルが得られます。

2. 忠実性の管理

PACE は、サンプル空間全体または固定された経験的セット全体での厳密な一致を強制するものを超えた、微妙な忠実性の定義を導入します。これは、2 つのパラメータによって定義される実用的な関心領域 $X_\eta \cap X_\delta$ においてのみ忠実性を強制します。

• 信頼領域（$X_\eta$）： 元のアンサンブルが代替クラスよりも $\eta$ 以上の信頼マージンを持って予測するサンプル。これは、元のモデルの選択が恣意的である可能性のある低信頼度領域での忠実性強制を回避します。
• 妥当性領域（$X_\delta$）： 孤立森林（Isolation Forest）を通じて計算された、データ分布に対する妥当性スコアが $\ge \delta$ であるサンプル。これは、元の予測を保持することが実用的に関連性が限られる外れ値や分布外サンプルを除外します。

これを強制するために、PACE は「分離サンプル」（現在のモデルが元のモデルと不一致となるサンプル）を反復的に検索するために**制約プログラミング（CP）**を採用します。定義された領域内で分離サンプルが見つかった場合、それを制約セットに追加し、重みを再最適化します。このサイクルは、対象領域に分離サンプルが存在しなくなるまで繰り返されます。

主要な貢献

1. 統合フレームワーク： 本論文は、剪定と圧縮が相補的であることを実証しています。PACE は、まず能動的生成を通じてアンサンブルを強化し、その後結果を剪定することで、両方のアプローチの強みを活用してこれらを統合します。
2. 強化のためのカラム生成： 著者は、新たな学習器を生成するための原理的な戦略としてカラム生成を提供します。これには、それ以上の改善学習器が存在しないことを保証する理論的停止基準が含まれており、その後の剪定の可能性を最大化します。
3. 柔軟な忠実性： 本論文は、忠実性の概念を（高信頼度かつ高妥当性の）意味のある領域のみをターゲットにするように拡張します。このトレードオフにより、厳密な忠実性強制よりも強力な圧縮を可能にしつつ、恣意的な近似の落とし穴を回避します。
4. 制約ベースの分離： PACE は、分離サンプルを見つけるために制約ベースの定式化を利用します。著者は、これが先行研究で使用されていた目的ベースの定式化よりも計算的に優れていることを示しています。

実験結果

著者は、ランダムフォレストおよび AdaBoost アンサンブルを用いて、さまざまなデータセット（COMPAS、FICO、Diabetes、Ionosphere など）で PACE を評価しました。

• 圧縮性能： PACE は、既存の剪定専用手法（FIPE など）およびアブレーション版（生成専用または剪定専用）を一貫して上回ります。多くの場合、最終的なアンサンブルは元の学習器ではなく、ほぼ完全に新たに生成された学習器で構成されます。
• 忠実性制御： パラメータ $\eta$ と $\delta$ を通じて忠実性を緩和することで、最終的なアンサンブルサイズが大幅に減少します。例えば、FICO データセットでは、$\eta$ を増加させることで、厳密な忠実性では達成不可能だった 58 本から 3 本への木数削減を実現しました。
• 計算効率： PACE で使用される制約ベースの分離アプローチは、FIPE などの最先端手法で使用される目的ベースの分離と比較して、大幅な高速化（特定のランダムフォレスト構成では最大 37 倍）を達成します。
• アブレーション研究： 実験により、生成のみまたは剪定のみでは、完全な PACE フレームワークの性能に匹敵しないことが確認され、2 段階アプローチの必要性が実証されました。

意義と主張

本論文は、PACE がアンサンブル圧縮に対する原理的かつ柔軟なアプローチを提供すると主張しています。その主な意義は以下の点にあります：

• 優れた圧縮： 関連領域における予測忠実性を維持しながら、既存の手法よりも小さなアンサンブルサイズを達成すること。
• 理論的保証： 経験的近似に依存するのではなく、ユーザー定義の特定の領域内での忠実性に関する厳密な保証を提供すること。
• 計算の進展： 制約プログラミングが、アンサンブル剪定に内在する分離問題に対する非常に効率的なツールであり、この文脈において従来の混合整数線形計画（MILP）アプローチを上回ることを実証すること。

著者は、$\ell_0$ノルムの組み合わせ的性質と生成フェーズに起因して、PACE が剪定専用手法よりも計算コストが高いという限界を認めています。また、現時点では木ベースの学習器に限定されている点にも言及していますが、適切な数学的モデルが確立できれば、フレームワークは理論的に他のファミリーへ拡張可能であると述べています。今後の課題として、学習器生成のための価格付け問題の最適化と、単純な学習器数を超えた複雑性指標の精緻化が提案されています。