Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

本論文は、決定木分類器における観測的多様性を「葉の後悔」と「構造の後悔」に分解する理論的枠組みを提示し、構造の後悔が主要な要因であることを実証するとともに、これらを棄却メカニズムとして活用することでモデルの安全性を向上させる手法を提案しています。

要約

🌳 1. 物語の舞台：「AI の森」と「迷う木々」

まず、決定木という AI を**「森の案内人」**だと想像してください。
この案内人は、お客様（データ）の質問（特徴量）に対して、「左に行けば A、右に行けば B」と分岐しながら、最終的に「Yes」か「No」を答えます。

しかし、この案内人には**「予測の多重性（Predictive Multiplicity）」という問題があります。
それは、「同じお客様に対して、案内人が違う木（モデル）を選んだだけで、答えが『Yes』になったり『No』になったりしてしまう」**という現象です。

なぜこうなるのか？
実は、案内人が使う**「地図（トレーニングデータ）」自体が、少しだけランダムに書き換えられていたからなのです。
例えば、ある人の属性が「借金を返す確率 60%」だとします。でも、実際のデータ収集では「たまたま返した（1）」か「たまたま返さなかった（0）」かのどちらかしか記録されません。この「偶然の記録（ラベルの揺らぎ）」**が原因で、案内人が作る「森の形」が微妙に変わってしまうのです。

この論文は、その「答えが変わってしまう原因」を、**2 つの異なる「後悔（レグレイト）」**に分けて分析しました。

---

🔍 2. 2 つの「後悔」の正体

この研究は、AI が迷う原因を大きく 2 つに分けました。

① 葉の後悔（Leaf Regret）：「同じ部屋での小さな揺らぎ」

• イメージ： 案内人がお客様を**「同じ部屋（葉）」**に案内したとします。その部屋の中には、同じような属性を持つ人たちが集まっています。
• 問題： その部屋の中で、「たまたま『返した』人が多かったから Yes にした」という**「その瞬間の偶然」**による揺らぎです。
• 例え： 部屋に 10 人がいて、6 人が「返す」と言ったら「返す確率 60%」と判断します。でも、もしその 10 人の誰かがたまたま「返さない」と言っていたら、判断が「50%」に変わってしまうかもしれません。これは**「部屋の中での小さなノイズ」**です。

② 構造の後悔（Structural Regret）：「森の形そのものが変わる」

• イメージ： これが今回の発見の**「主役」です。データが少し変わっただけで、「森の分岐点（枝）」そのものが大きく変わってしまう**現象です。
• 問題： 「A さんは左の枝へ」「B さんは右の枝へ」という**「森の地図そのもの」**が、データの偶然によってガクッと変わってしまいます。
• 例え： 昨日は「身長 170cm 以上なら左」というルールでしたが、今日データが少し変わっただけで「身長 171cm 以上なら左」にルールが変わり、同じ 170cm の人が**全く違う部屋（葉）**に案内されてしまうのです。
• 結論： この研究で驚いたのは、**「答えが変わる原因の 9 割以上は、この『森の形が変わってしまうこと（構造の後悔）』だった」**ということです。部屋の中の小さな揺らぎよりも、地図自体がぐらぐらしている方が遥かに危険なのです。

---

🛡️ 3. 解決策：「自信がないときは『保留』する」

では、この「森の揺らぎ」をどうすればいいのでしょうか？
論文は、**「自信がないときは、無理に答えを出さず『保留（Abstention）』する」**という戦略を提案しています。

• 仕組み： AI は「この人は、森の形が変わると答えがコロコロ変わる（構造の後悔が大きい）」と計算できます。
• アクション： そういう「不安定な人」には、AI が「わかりません」と答え、人間の専門家（医師や審査員）に任せるようにします。
• 効果：
  • 無理に答えを出そうとして間違うリスクを減らせます。
  • 実験では、この方法を使うと、「最も安定している人々」に対する正解率（リコール）が 92% から 100% に向上しました。
  • つまり、「AI が『これは危ない（答えにくい）』と判断した人」を除外することで、残った人に対する判断は極めて信頼できるものになります。

---

💡 まとめ：この研究が教えてくれること

1. AI のミスは「偶然」のせいだけじゃない：
   データの小さな揺らぎが、AI の「森の地図（構造）」を大きく変えてしまい、同じ人に対して全く違う判断を下す原因になります。
2. 一番の犯人は「構造の不安定さ」：
   部屋の中の小さなノイズよりも、**「分岐ルールそのものが不安定」**であることが、判断の揺らぎの最大の原因でした。
3. 「わからない」と言う勇気が安全につながる：
   AI が「この判断は不安定だから、人間に任せてください」と言える仕組み（保留）を作れば、医療や金融などの重要な場面で、**「絶対に間違えてはいけない」**という安全基準を大幅に高められます。

一言で言えば：
「AI に『絶対正解』を求めず、**『いつなら AI に任せても安全か』**を見極める基準を作ろう」という、より賢く、安全な AI 活用のための指針を示した論文です。

技術概要

論文サマリー：決定木における観測的多様性の分解

1. 背景と問題定義

機械学習モデルの展開、特に医療や信用スコアリングなどの高リスク分野において、**予測的多様性（Predictive Multiplicity）**が重要な課題となっています。これは、ほぼ同等の精度を持つ複数のモデルが存在し、同じ個人に対して矛盾する予測を行う現象です。

従来の研究は、モデルのアーキテクチャや最適化プロセスに起因する「モデルの未特定性（underspecification）」に焦点を当てていましたが、近年**観測的多様性（Observational Multiplicity）**が独立した主要な要因として注目されています。これは、訓練データのラベルが、潜在的な真の確率分布からの単一の確率的実現（サンプリング）に過ぎないことに起因します。つまり、同じ分布から異なるラベルの引き出し（実現）が行われれば、異なるモデルが学習され、予測が変動します。

しかし、ロジスティック回帰などの滑らかなモデルに対する理論的枠組みは確立されているものの、決定木のような非滑らかで分割ベースのモデルにおける観測的多様性の影響は十分に解明されていませんでした。決定木はデータの変動に対して非常に敏感であり、その不安定性の源泉を特定する枠組みが必要とされていました。

2. 手法と理論的枠組み

著者は、決定木分類器における観測的多様性を、以下の 2 つの相補的な概念に分解する新しい枠組みを提案しました。

• 葉の後悔（Leaf Regret）:

  • 定義: 固定された決定木の構造（特定の葉）内における予測の内在的な変動性。
  • 原因: 有限サンプルによるラベルの確率的変動（アレイトリック不確実性）。
  • 定式化: 葉 $L$ における真の確率 $p^*_L$ と、その推定値 $\hat{p}_L$ の分散として定義されます（$R_{leaf} = \text{Var}(\hat{p}_L | L)$）。
  • 理論的保証: 葉のサンプルサイズ $n_L$ が大きくなるにつれて、葉の後悔は $O(1/n_L)$ の割合で 0 に収束することが示されました（大数の法則と集中不等式に基づく）。

• 構造の後悔（Structural Regret）:

  • 定義: 学習された決定木の構造そのものが変動することによって引き起こされる予測の追加的な変動性。
  • 原因: ラベルの異なる実現により、分割点や木構造自体が不安定に変化すること（認識論的不確実性）。
  • 定式化: 入力 $x$ に対する予測値 $\hat{p}(x; T)$ の、木 $T$ のランダム性に対する分散として定義されます（$R_{struct}(x) = \text{Var}_T(\hat{p}(x; T))$）。
  • 特徴: 葉の後悔とは異なり、木学習アルゴリズムの安定性に依存し、解析的な閉形式解を得るのは困難なため、モンテカルロ法による近似が提案されています。

総予測変動の分解:
これらの 2 つの概念を用いることで、総予測変動を以下のように厳密に分解できます。
$$\text{Var}(\hat{p}(x)) = E_T [R_{leaf}^{L(x;T)}] + R_{struct}(x)$$
（第 1 項は期待される葉の後悔、第 2 項は構造の後悔）

3. 主要な貢献

1. 観測的多様性の理論的分解: 決定木における予測変動を「局所的な葉内ノイズ（葉の後悔）」と「大域的な構造不安定性（構造の後悔）」に明確に分解する初の枠組みを提供しました。
2. 統計的保証と推定量の提案: 葉の後悔に対して集中不等式と漸近的な消滅性を証明し、構造の後悔に対してブートストラップ再サンプリングを用いたモンテカルロ推定アルゴリズムを提案しました。
3. 選択的予測（Selective Prediction）への応用: 算出された後悔値を「棄権（Abstention）」の指標として利用し、モデルが「推測」している不確実な領域を特定する手法を提示しました。

4. 実験結果

複数の信用リスク評価データセット（Taiwan Credit, HMEQ, Bank Marketing など）を用いた実験により、以下の結果が得られました。

• 分解の精度: 理論的に計算された後悔の和（葉の後悔＋構造の後悔）と、シミュレーションによって得られた真の予測分散の間には、ほぼ完全な一致（$y=x$ 線上）が確認されました。
• 構造の後悔の支配性: 観測的多様性の主要な駆動力は、葉内のノイズではなく構造の不安定性であることが判明しました。
  • 例：Taiwan Credit データセットでは、構造の後悔が葉の後悔の約15 倍の大きさを持っていました。
  • 最小葉サイズ（$n_L$）を増やすと葉の後悔は減少しますが、構造の後悔はデータ分割の不安定性に起因するため、単純な葉サイズの増加だけでは解決されません。
• 選択的予測による安全性向上: 後悔値が高いサンプル（モデルが不安定な領域）を除外する（棄権する）アプローチを適用しました。
  • German Credit データセットにおいて、カバレッジ（対象とするサンプルの割合）を調整しながら最も安定したサンプルのみを選択した場合、リコール（Recall）が92% から 100% に向上しました。
  • 構造の後悔に基づくフィルタリングは、葉の後悔に基づくフィルタリングよりも、困難な陽性サンプル（Hard-to-miss positives）の特定において効果的でした。

5. 意義と結論

本研究は、決定木モデルにおける予測の不確実性を、単なる「精度」の問題ではなく、「どの要因（局所ノイズか構造不安定さか）によるものか」を特定可能な形で定量化する厳密な枠組みを提供しました。

• 安全性への示唆: 高リスク分野において、モデルが「推測」を行っている領域を特定し、人間の判断に委ねる（エスカレーションする）ための客観的な指標となります。
• モデル設計への示唆: 観測的多様性を抑制するには、単に葉のサンプル数を増やすだけでなく、木構造の安定化（正則化、剪定、アンサンブル手法など）が不可欠であることを示唆しています。
• 解釈可能性: 「なぜこの予測が不安定なのか」を構造的な観点から説明可能にし、アルゴリズムの透明性と信頼性を高めます。

結論として、この枠組みは、高リスク環境下での個別レベルの意思決定を、より安定し、正当化可能なものにするための重要な基盤となります。