技術的概要：局所適応型不確実性領域を備えた三値決定木

問題定義

標準的な決定木、特に CART アルゴリズムに基づくものは、ハードな二値閾値を用いて特徴空間を分割する。このメカニズムは、決定境界からの近接性に関わらず、インスタンスに対して同一の信頼度を割り当てる。その結果、最適閾値 $\theta$ から遠く離れたインスタンスは、その閾値上に直接位置するインスタンスと同等の確信度で扱われる。この「ハードなコミットメント」は既知の弱点を生み出す：学習された分割が最も信頼できない境界付近のインスタンスに対して確信度を過大評価し、予測が曖昧である可能性を downstream アプリケーションに伝達できない点である。

不確実性に対処する既存のアプローチは、しばしば外部のノイズ仕様（例：既知のセンサー誤差）や、データセットレベルの統計から導出されたグローバルな閾値に依存する。これらの手法は、各ノードにおける特定の分割の質やデータ分布に局所的に適応しない。さらに、ファジー決定木やソフト決定木のようなアプローチは、局所的な分割統計から導出された明示的で解釈可能な不確実性領域を欠いていることが多い。

手法

本論文は、最適閾値 $\theta^*$ の中心に半幅 $\delta$ の局所適応型不確実性領域を追加した標準的な二値分割を拡張する三値決定木を導入する。

三値評価

特徴 $x_f$ と閾値 $\theta^*$ に対して、決定ロジックは以下のように定義される：

• True（決定的）: $x_f > \theta^* + \delta$
• False（決定的）: $x_f \leq \theta^* - \delta$
• Undec（境界不確実）: $\theta^* - \delta < x_f \leq \theta^* + \delta$

Undec 領域に属するインスタンスは予測を保留するのではなく、両方の子サブツリーの確率出力を距離重み付けでブレンドした予測を受け取る。重要なのは、これらのインスタンスが「境界不確実」としてフラグ付けされ、クラス予測を保留することなく、downstream システムがそれらを異なって処理（例：人間のレビューへのルーティング）できるようにする点である。

局所的な $\delta$ の計算

核心的な技術的貢献は、標準的な CART 分割探索中に既に計算される統計量のみを用いて、各ノードで局所的に $\delta$ を導出することであり、外部データやノイズモデルを必要としない。本論文は 5 つの手法を提案し、評価する：

1. Quality-Plateau（$\delta_{QP}$）: 最適閾値 $\theta^*$ 周辺の分割基準曲線（例：ジニ利得）における「プラトー」の幅を測定する。幅広のプラトーは、データが最適分割位置を精密に制約していないことを示す。
2. Class-Overlap（$\delta_{CO}$）: 経験的パーセンタイルに基づき、クラス条件付き特徴分布が重なる領域の幅を計算する。
3. Gain-Ratio（$\delta_{GR}$）: 特徴の範囲をゲイン比（分割エントロピーに対する情報利得）で逆比例スケーリングする。低いゲイン比は曖昧な分割を示し、より大きな $\delta$ につながる。
4. Node-Bootstrap（$\delta_{NB}$）: ノードの訓練データのブートストラップ再サンプリングにおける最適閾値 $\theta^*$ の標準偏差を測定する。これは閾値の不安定性を直接定量化する。
5. Margin（$\delta_{M}$）: サポートベクターマシンに着想を得て、$\delta$ を $\theta^*$ から最も近い異クラス訓練サンプル（そのノードにおける「サポートベクター」）までの距離として定義する。分割が完全にクリーンな場合、隣接するデータポイント間の物理的なギャップを使用する。

ルーティングアーキテクチャ

不確実なインスタンスを伝播させるための 2 つのアーキテクチャが評価された：

• 確率的ルーティング: 木構造は二値のまま維持される。予測時に、不確実性領域内のインスタンスは閾値からの距離に逆比例する重みで両方の子ノードへルーティングされ、出力がブレンドされる。
• ハードミドルブランチ: 木構造に、不確実性領域内のインスタンスのみに訓練された 3 つ目の子ノードが追加される。
  実験結果は、確率的ルーティングが一般的にハードミドルアプローチを上回ることを示した。後者は、不確実なサンプルを左および右ブランチの訓練セットから除去し、それらの質を低下させるためである。

主要な貢献

1. フレームワーク: すべての分割に対して原理的かつ局所適応的な不確実性領域を提供する三値決定木の導入。
2. 5 つの推定手法: 外部ノイズモデルを必要とせず、標準的な CART 分割統計のみを用いて $\delta$ を計算する 5 つの異なる手法の導出。
3. ルーティング評価: 確率的ルーティングとハードミドルルーティングの比較分析と、ほとんどの手法において確率的ブレンドの優位性の実証。
4. 広範な実証評価: 72 の OpenML-CC18 データセット、3 つの Breiman 合成ベンチマーク（既知のベイズ誤差を有する）、および 4 つの医療・金融分野の高リスクデータセットにおける評価。
5. 診断フレームワーク: 手法のフラグ付け率がデータセットの理論的不可避誤差とどの程度整合するかを評価するためのUndecided/Bayes（U/B）比の導入。

結果

広範な妥当性（OpenML-CC18）

72 のデータセット全体において、確率的ルーティングを用いた 5 つの手法すべてが、Decided Accuracy（不確実でないインスタンスに限定した精度）において、標準的な CART ベースラインを有意に上回った（$p \leq 0.001$）。

• Margin 手法: 最高の効率（フラグ付け率あたりの精度向上、$\eta = 0.104$）を達成した。72 のデータセットのうち 42 で優勝し、インスタンスの 16.7% のみを不確実としてフラグ付けし、追加のハイパーパラメータを一切必要としなかった。
• Class-Overlap と Gain-Ratio: 高い決定精度を達成したが、インスタンスの大部分（それぞれ 71% と 58%）をフラグ付けしたため、効率は低かった。
• Node-Bootstrap: 良好に機能したが計算コストが高く、$N > 20,000$ のデータセットからは除外された。

理論的分析（Breiman ベンチマーク）

既知のベイズ誤差を持つ合成データセットにおいて：

• Margin: 幾何学的にクリーンなデータにおいて自己較正的な挙動を示し、非常に少数のインスタンスのみを不確実としてフラグ付けした（U/B 比 < 0.5）。境界が明確な場合、実質的に CART のように振る舞った。
• Node-Bootstrap と Quality-Plateau: 比例較正を示し、より困難なデータセット（高いベイズ誤差）ではより多くのインスタンスをフラグ付けしたが、すべての手法は理論的なベイズ誤差に対して過剰にフラグ付けした（U/B > 1）。
• 較正ギャップ: どの手法も U/B 比 1.0 を達成しなかった。これは、局所的な閾値の不確実性が、グローバルなベイズ誤差に直接対応していないことを示している。

ドメイン応用

• マンモグラフィ: Node-Bootstrap は症例の 10.8% を不確実としてフラグ付けしつつ、CART に対して決定精度を 0.71% 向上させた。これは二次レビューを要する症例の特定に価値がある。
• 糖尿病: Node-Bootstrap は +9.8% の精度向上を達成したが、患者の 63.4% をフラグ付けし、精度とフラグ付け率の間のトレードオフを示唆した。Margin 手法はより保守的で実用的な動作点を提供した（+0.4% の向上、9.5% のフラグ付け）。
• 限界: 小規模なクリーブランド心疾患データセット（$N=303$）では、Node-Bootstrap は信頼性の低い分散推定により性能が低下した。ドイツの信用データセットでは、Margin 手法がベースラインを下回り、複雑な経済的特徴の相互作用に対する限界を示唆した。

意義と主張

本論文は、三値木を不確実性を意識した分類のための原理的プリミティブとして確立すると主張する。その意義は以下の点にある：

• 実用性: 予測を保留することなく境界不確実な予測をフラグ付けするメカニズムを提供し、downstream システム（例：医療スクリーニング、信用審査）が異なる処理戦略を適用できるようにする。
• 計算的実用性: 外部データや複雑な再訓練を必要とせず、既存の分割統計から不確実性領域を導出する。
• 理論的基盤: 「Undec」の判定を予測そのものの拒否ではなく、予測信頼性に対する修飾子として扱うフレームワークを提供する。

著者は、これらの手法が決定精度を向上させるものの、フラグ付け率を理論的なベイズ誤差に完全に較正するに至っていないことを控えめに指摘し、この較正を将来の具体的な未解決課題として特定している。