技術概要：一般な結果空間における条件付き密度推定のためのパーティション木

問題定義

決定木は、点予測（分類および回帰）における解釈性と効率性から広く評価されています。しかし、連続変数とカテゴリカル変数を同時にサポートする一般な結果空間における条件付き密度推定への木ベース手法の拡張は、依然として課題となっています。既存のアプローチには特定の限界があります：

• パラメトリック仮定： CADET などの手法は、葉ノードでパラメトリックな条件付き密度を採用しており、複雑な非ガウス分布を捉えられない可能性があります。
• スケーラビリティ： 分割と葉ごとのヒストグラムを同時に最適化する CDTree などの手法は、計算集約的であり、大規模データセットへの適用を制限しています。
• 統合的な定式化： 対象分布にパラメトリックな制約を課すことなく、分類と回帰を条件付き密度推定の特殊なケースとして扱う統合的な枠組みが不足しています。

手法

1. 理論的枠組み：測度論的定式化

著者は、測度論に基づいたパーティション木という枠組みを提案します。

• 結合空間のパーティショニング： 共変量空間 $X$ のみを分割する従来の木とは異なり、パーティション木は共変量 - 結果の結合空間 $Z = X \times Y$ のデータ適応型パーティション $\pi_N$ を構築します。
• 区分的定数推定： 条件付き密度 $f(y|x)$ は、これらのパーティション上で定義された区分的定数関数としてモデル化されます。
• ラドン・ニコディム微分： この手法は、積測度 $\nu = P_X \otimes \mu_Y$ に対するラドン・ニコディム微分を通じて条件付き密度を定義します。ここで、$\mu_Y$ は参照測度（離散結果の場合は数え上げ測度、連続の場合はルベーグ測度）です。
• 推定量： パーティション内のセル $A = A_X \times A_Y$ に対して、密度推定量は以下の通りです：
  $$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$$
  ここで、$n_{XY}$ と $n_X$ は経験的カウントです。この定式化は、混合タイプの結果を自然に処理し、分類と回帰を特殊なケースとして導き出します。

2. 木構築アルゴリズム

木は、条件付き負対数尤度を直接最小化する貪欲な最良優先戦略を用いて成長させます。

• 目的： 分割基準は、対数損失における経験的利得を最大化します：
  $$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$$
• 分割タイプ：
  • 共変量分割（$X$）： 共変量空間を精緻化します（標準的な木分割）。
  • 結果分割（$Y$）： 固定された共変量領域内の結果ビン（bin）を精緻化します。これにより、木は結果分布のヒストグラムを適応的に構築できます。
• 効率性： このアルゴリズムは効率的なソートとプレフィックス和の技術を利用し、候補分割を $O(d_Z N \log N)$ 時間（平衡木の場合は $O(d_Z N \log^2 N)$）で評価します。これは標準的な CART のスケーラビリティと同等です。
• 切り捨て： 有界でない連続結果に対して、有限測度を確保するためにデータ依存の切り捨て（最小 - 最大ボックス）を採用し、切り捨てが漸近的にすべての確率質量を捉えるという理論的保証を有しています。

3. パーティションフォレスト

安定性と予測性能を向上させるため、著者はパーティションフォレストというアンサンブル手法を導入します。これは、ブートストラップサンプル（バギング）上で訓練された複数のパーティション木からの条件付き密度推定量を平均化するもので、オプションとしてランダムな特徴量部分サンプリングを伴います。

4. 理論的保証

論文は、推定量の$L^1(\nu)$-一致性のための十分条件を確立しています。パーティション列が以下の条件を満たす場合、一致性が保証されます：

1. セルの数が $N$ に対して亜線形的に増加すること。
2. パーティション族の成長関数が特定の VC 次元の上限を満たすこと。
3. セルの直径がゼロに収束すること。
4. 異なる共変量射影の数が $\sqrt{\log N / N}$ に対して十分に緩やかに増加すること。

主要な貢献

1. 統合的な枠組み： パラメトリックな仮定なしに、連続、カテゴリカル、および混合タイプの結果を扱う条件付き密度推定のための単一の非パラメトリック枠組み。
2. 直接最適化： 貪欲な最良優先探索を通じて条件付き対数損失を直接最適化する木構築アルゴリズム。これにより、先行研究で見られた分割 - ヒストグラム同時最適化の計算ボトルネックを回避します。
3. スケーラビリティ： 標準的な CART と同等の計算複雑性を持つ実装により、大規模データセットへの適用を可能にします。
4. アンサンブル拡張： 単一木よりも確率的予測が改善されることを示すパーティションフォレストの導入。
5. 理論的分析： 標準的な複雑性と収縮の仮定の下での、提案された推定量に対する厳密な一致性証明。

実験結果

著者は、分類および回帰の多様なベンチマークにおいてパーティション木とパーティションフォレストを評価し、CART、ランダムフォレスト、CADET、CDTree と比較しました。

• 分類：
  • 単一木： パーティション木は、対数損失の観点から、9 _dataset のうち 8_で CART を上回りました。
  • アンサンブル： パーティションフォレストは、ほとんどのデータセットでランダムフォレストよりも低い対数損失を達成し、優れた確率的較正を示しました。
• 回帰：
  • 単一木： パーティション木は競争力のある点予測と強力な確率的性能を提供しました。特に、大規模データセット（Air、Power、California、Protein など）においてパラメトリックな CADET を上回り、スケーラビリティとサンプルサイズへの適応性の優位性を示唆しました。
  • アンサンブル： パーティションフォレストは、対数損失に関して、回帰ベンチマークの大部分（10 のうち 8）でランダムフォレストを一貫して上回りました。
• 頑健性：
  • ノイズ： この手法は、等分散および異分散ノイズの両方に対して頑健であり、性能の低下は CDTree と同等で、CADET よりも安定性が高かったです。
  • 冗長な特徴量： CDTree は相関する特徴量の重複に対してわずかに優れた安定性を示しましたが、パーティション木は特徴量の汚染下で CADET よりも一貫性のある予測（分散が低い）をもたらしました。
• 効率性： Physicochemical Protein データセットにおける実行時間の比較では、$N=10,000$ において、パーティション木は CADET より約 5 倍、CDTree より 25 倍高速でした。

意義と主張

この論文は、パーティション木が既存の確率的木手法に対するスケーラブルで非パラメトリックな代替手段を提供すると主張しています。その主な意義は以下の点にあります：

• 柔軟性： 特定のパラメトリック形式（例：ガウス分布）を仮定することなく、一般な結果空間上の複雑な条件付き分布をモデル化する能力。
• 解釈性： 利得ベースの特徴量重要度や区分的定数密度の可視化を通じて、決定木固有の解釈性を維持しつつ、完全な確率的出力を提供すること。
• 性能： 非パラメトリックで密度ベースの木アンサンブルが、従来の点予測アンサンブル（ランダムフォレスト）およびパラメトリックな密度ベースの木（CADET）を上回ることを実証し、特にデータセットサイズが増加するにつれて顕著であること。

著者は、パーティション木を、柔軟な条件付き密度推定を必要とする因果推論パイプラインや他のアプリケーションへの統合の自然な候補として位置づけており、将来の研究ではブースティングの枠組みや特化した剪定戦略の探求が可能であると認めています。