技術要約: P2CE – モデルに依存しない妥当なパレート最適反事実説明

問題提起

信用スコアリング、採用、健康診断などの高リスクな領域における機械学習の導入が進むにつれ、透明性と公平性が不可欠となっています。反事実説明（Counterfactual Explanations, CEs）は、望ましくない結果から望ましい結果へとモデルの予測を変更するために、入力特徴量に対して最小限の変更（$x \to x'$）を提案することで、この問題に対処します。しかし、既存の手法には以下の3つの重要な課題があります。

1. 妥当性（Plausibility）: 多くのアルゴリズムは、入力に対して数学的には近いものの、自然なデータ分布の外側（外れ値）に位置する解を生成してしまい、個人にとって実現不可能な非現実的なものになってしまいます。
2. 実現可能性のトレードオフ（Feasibility Trade-offs）: 「実現可能性」には単一の指標が存在しません。多くの特徴量をわずかに変化させることを好むユーザーもいれば、少数の特徴量を中程度に変化させることを好むユーザーもいます。単一目的最適化では、こうした多様な好みを捉えることができません。
3. モデル非依存性と効率性（Model Agnosticism and Efficiency）: 一部の手法はモデルに依存しませんが、計算効率に難があったり、複雑な非線形モデル（ニューラルネットワークやSVMなど）には当てはまらない仮定（単調性など）に依存したりすることがあります。

手法

著者らは、Plausible Pareto-Optimal Counterfactual Explanations（妥当なパレート最適反事実説明）を生成するために設計されたアルゴリズムであるP2CEを提案しています。このアプローチは、ブラックボックスモデル全体における妥当性と効率性を確保するために、分岐限定探索（branch-and-bound search）戦略と2つの主要な革新技術を組み合わせています。

1. 探索戦略と多目的最適化

P2CEは、特徴量の変化の離散化されたグリッド（$A = A^{(1)} \times \dots \times A^{(d)}$）を探索し、$f(x+a) \geq \tau$ を満たすアクション $a$ の集合を見つけ出します。以下の複数の目的を同時に最適化します。

• 平均連続距離 ($c_1$): 数値特徴量における変化の正規化された平均的な大きさ。
• 最大連続距離 ($c_2$): 単一の数値特徴量における変化の最大幅。
• 変化の数 ($c_3$): 変更された特徴量の数（スパース性）。

アルゴリズムはパレート最適集合を返します。これにより、すべての目的において他の解よりも優れている、あるいは同等であるような解が存在しないことが保証されます。

2. 外れ値検知による妥当性の確保

解がデータの分布から外れた外れ値（outliers）になるのを防ぐため、P2CEは**孤立フォレスト（Isolation Forest）**による外れ値検知器（$u$）を統合しています。

• 探索中に候補となる解 $x+a$ が見つかるたびに、$u(x+a)$ が評価されます。
• もし $u(x+a)$ が外れ値であることを示した場合、その解は破棄されます。
• 効率性の向上: P2CEは、孤立フォレストが欠損値を扱える特性を活用します。部分的な解（一部の特徴量が未定義の状態）がすでに外れ値であると分類された場合、アルゴリズムはその探索ツリーの枝全体を切り捨て（プルーニング）、不要な計算を回避します。

3. モデル非依存の分岐限定プルーニング

計算効率を維持しつつ、単調性を仮定しない（MAPOCAMのような手法が持つ制約を回避する）ために、P2CEは部分的なアクション $a$ から到達可能な最大予測値（$f_a$）を推定します。

• SHAPに基づく推定: アルゴリズムは、SHAP値の加法的な性質 $f(x) = E[f(x)] + \sum \phi_i$ を利用します。
• まだ確定していない特徴量（探索において未決定のままの機能）について、「ベストケース」のシナリオを想定することで、予測の上限を計算します。
• 上限は以下のように定式化されます：
  $$\max f(x+\tilde{a}) \leq f(x) - \sum_{i \in O_k} \phi_i(x) + \sum_{i \in O_k} \bar{\phi}_i + R(x, O_k)$$
  ここで、$O_k$ は最も高い潜在的な寄与を持つ $k$ 個の特徴を表し、$\bar{\phi}_i$ は特徴量 $i$ の最大可能な寄与、$R$ は残差項です。
• この上限が決定閾値 $\tau$ を下回る場合、その枝はプルーニングされます。これにより、P2CEはニューラルネットワークのような非単調なモデルに対しても効率的に機能することができます。

主な貢献

1. P2CEアルゴリズム: 外れ値検知を通じてデータの分布における妥当性を厳格に強制しながら、パレート最適な反事実説明を生成する、新しいモデル非依存のアルゴリズム。
2. SHAP特性の活用: 分岐限定の文脈で最大予測値を推定するためにSHAP値を使用する方法を導入し、従来の最先端手法が求めていた単調性の制約を取り除きました。
3. 包括的な評価: 3つのデータセット（German Credit, Taiwan Credit, Adult）と3つの分類器（Logistic Regression, LightGBM, MLP）を用いて、MAPOCAM、DiCE、NICEと比較する広範な実証研究を実施しました。
4. オープンソース: 再現性を促進するため、実装を公開しています。

実験結果

評価は、解の質（パレート境界のハイパーボリューム）、妥当性（外れ値の割合）、および計算効率に焦点を当てて行われました。

• 妥当性: P2CEは、競合手法と比較して、一貫して有意に少ない外れ値の解を生成しました。例えば、MLPを用いたAdultデータセットにおいて、DiCEが87%、MAPOCAMが58%の外れ値を生成したのに対し、P2CEはわずか11%でした。場合によっては、DiCEは不可能に近いシナリオ（例：週に97時間の労働）を提案することもありました。
• 解の質: P2CEは、MAPOCAM（パレート最適性の理論的ゴールドスタンダード）に匹敵するハイパーボリュームスコアを達成し、DiCEやNICEを大幅に上回りました。MAPOCAMが時としてわずかに高いハイパーボリュームを達成することもありましたが、それには膨大な計算コストが伴いました。
• 効率性: P2CEは、特に複雑な非線形モデルにおいて優れた計算効率を示しました。
  • TaiwanデータセットのMLPにおいて、MAPOCAMの平均所要時間は 118.5秒 であったのに対し、P2CEは 0.81秒 でした。
  • AdultデータセットのMLPにおいて、MAPOCAMは 6.24秒 かかりましたが、P2CEは 2.34秒 でした。
  • P2CEは、生の実行時間においてはDiCEやNICEよりも遅かったものの、それらの高速な手法が欠いていた「パレート最適性」と「妥当性」の保証を提供しました。

意義と主張

本論文は、反事実説明が実行可能（ユーザーにとって実現可能）かつ妥当（現実世界のデータと一致している）である必要がある実世界のアプリケーションにおいて、P2CEを実用的なソリューションとして位置付けています。

著者らは、P2CEが理論的な最適性と実用的な有用性の間の溝を埋めることに成功したと主張しています。解が「インライア（内側にあるもの）」であることを保証することで、誤った助言（例：収入を1000%増やす、あるいは不可能な労働時間を提案するなど）を生成することを防ぎます。さらに、SHAP値を利用してプルーニングを行うことで、P2-CEは単調性や特定のモデルタイプに制限されていた従来の手法の限界を克服し、あらゆるブラックボックスモデルに対して最適な反事実を生成する能力を拡張しました。

結論として、P2CEは、モデル固有の適応を必要とせずに、高品質で妥当なトレードオフの多様なセットを提供することで、実世界のアプリケーションにおけるより迅速で情報に基づいた意思決定を可能にすると述べています。

限界と今後の課題

著者らは、主に2つの限界を認めています。

1. SHAPへの依存: プルーニング戦略の効率性はSHAP近似に依存しています。正確なシャプレー値を計算することは計算コストが高いため（特徴量の数に対して指数関数的）、近似値が使用されています。これらの近似による誤差が理論的にはプルーニングに影響を与える可能性がありますが、実験結果によれば、得られる速度向上と比較してその影響は最小限であると考えられます。
2. 離散化されたグリッド: 探索は離散的なグリッドに制約されています。これはほとんどのアプリケーション（例：1,000ドルの収入増加を提案することと998ドルの収入増加を提案することは機能的に同等である）においては実用的ですが、極端に細かい粒度は探索時間を増加させます。著者らは、将来的な課題として、SHAP値に導かれる形で特徴の影響度に基づいて粒度を調整する**適応型グリッド（adaptive grids）**の研究を挙げています。