🤖 AI

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

本論文は、因果グラフを活用することで非対称シャプレー値を計算するための効率的なアルゴリズムを導入し、根付き有向木においては厳密な計算が多項式時間で可能であることを実証するとともに、標準的なシャプレー値計算の#P困難性を克服するために、任意の因果DAGに対する一様なサンプリングに基づく近似手法を提案するものである。

原著者： Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

公開日 2026-06-25

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Ezequiel Companeetz, Santiago Cifuentes, Sergio Abriola

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、チームのプレイヤー（特徴量）が協力してゲームに勝つ（予測を行う）場面を想像してみてください。あなたは、各プレイヤーが勝利に対してどれほどの貢献をしたのかを正確に知りたいと考えています。AIの世界では、これを**説明可能性（Explainability）**と呼びます。

最も有名な手法の一つに、**シャプレー値（Shapley Values）**があります。これは、プレイヤーがどのような順番でゲームに参戦したかという、あらゆる可能な順序を検証する公平な審判のようなものです。もしプレイヤーAが最初、2番目、あるいは最後に入った場合、そのプレイヤーによってチームのスコアがどれだけ変化したかを審判は計算します。プレイヤーAの最終的なスコアは、これらすべての変化の平均となります。

従来の方法の問題点
問題は、これらすべての可能な順序を計算するのは悪夢のような作業だということです。もしプレイヤーが20人いれば、チェックすべき順序は数十億通りにも及びます。複雑なAIモデルの場合、この計算を正確に行うことは実質的に不可能です。

また、従来の方法はすべてのプレイヤーを平等に扱います。もしプレイヤーBがプレイヤーAのコピーであったとしても、両者は同じスコアを受け取ります。しかし現実の世界では、あるプレイヤーが別のプレイヤーの動きを引き起こすことがあります。もしプレイヤーAがプレイヤーBを「動かす」原因となっているなら、プレイヤーAこそが真の主導権を握っていると言えます。従来の方法では、この「因果関係」を見落としてしまうのです。

新しい解決策：非対称シャプレー値（Asymmetric Shapley Values: ASV）
この論文では、より賢い審判である**非対称シャプレー値（ASV）**を紹介しています。ASVの審判は、あらゆる順序を調べるのではなく、因果マップ（Causal Map）（誰が誰を引き起こすかを示す図）に従って意味のある順序のみを調べます。

比喩： 工場の組み立てラインを想像してください。車のフレームを作る前に、塗装することはできません。因果マップは「フレームを先に作り、その後に塗装する」と指示しています。ASVの審判は、フレームを作る前に塗装しようとするような、論理に合わない順序は無視します。彼らは、論理的な因果関係に基づいた順序のみをカウントします。
メリット： これにより、結果を実際に引き起こしたのが誰であるかについて、より誠実な説明が可能になります。さらに驚くべきことに、従来の方法では不可能だったケースにおいて、この手法は数学的な計算を容易にします。

いかにして高速化したか（魔法の手品）
因果マップを用いたとしても、すべての有効な順序をチェックするのは依然として時間がかかりすぎる可能性があります。著者らは、計算を高速化するための2つの巧妙なトリックを考案しました。

「グルーピング」のトリック（等価類）：
人がどのように列を作るかを数えている場面を想像してください。計算の目的においては、二人の人がメインのボスよりも後ろに立っている場合、二人が場所を入れ替えたとしても、彼らは同じ「グループ」に属しているため、問題にならないことに気づきます。
著者らは、何千もの似たような順序を一つの「バケツ」（等価類と呼ばれます）にまとめる方法を見つけました。1,000,000個の順序をチェックする代わりに、わずか500個のグループをチェックするだけで済むかもしれません。これにより、特に因果マップが単純なツリー構造（家系図のようなもの）である場合、不可能だったタスクを迅速なタスクへと変えることができます。
「サンプリング」のトリック（サンプルによる推測）：
もしマップが整理してグループ化するには複雑すぎる場合は、サンプリング手法を使用します。有効な順序をすべてチェックする代わりに、ルールに従った順序をランダムに数百個選び、その平均を計算します。

比喩： 巨大な米の鍋が塩辛いかどうかを確認するために、米の一粒一粒を味わうのではなく、あちこちからスプーンで数回すくい取ることを想像してください。もし数回分が塩辛ければ、鍋全体が塩辛いことがわかります。論文では、この「スプーンですくう」手法が高速であり、非常に優れた推測値を与えることを示しています。

何をテストしたのか
著者らは、これらのアイデアを実際のデータ構造（がんや子供の発達を予測するために使用されるネットワークなど）や、作られたツリー構造を用いてテストしました。

ツリー型の構造については、彼らの「グルーピング」手法が驚異的に速く、従来の方法と比較して作業量を数百万分の1に削減できることを見出しました。
より複雑な構造については、彼らの「サンプリング」手法が、実用的なレベルで十分に高速かつ正確であることを示しました。

結論
この論文は、データの「因果関係」のルールを尊重することで、AIモデルをより正確に、かつより速く説明できることを証明しています。特定の種類のデータにおいては、以前は正確な計算が不可能だった手法が迅速に実行可能になり、その他のデータにおいては、高速で正確な推測が容易にできることを彼らは示しました。

技術要約：Shapleyを超えて：非対称Shapley値の効率的な計算

問題提起

本論文は、説明可能なAI（XAI）における特徴量への属性付与に関連する、計算量および解釈性の課題に対処している。Shapley値（およびその機械学習への実装であるSHAP）は、モデルの予測を入力特徴量に分配するための理論的根拠に基づいた手法であるが、主に以下の2つの制限を抱えている：

計算の困難性（計算量的不備）： 正確なShapley値を計算することは、特に表現力の高いモデル（例：ニューラルネットワーク）や、基礎となるデータ分布が複雑な場合（例：ナイーブベイズ分布）、多くの場合において#P困難である。
解釈性の欠如： 標準的なShapley値は、すべての特徴量を対称的に扱う。これは因果関係を捉えることができず、原因とその決定論的な結果に対して等しい重要性を割り当てる可能性があり、それによって真のデータ生成プロセスを隠蔽してしまう。

第二の課題に対処するため、与えられた因果グラフ（有向非巡回グラフ、すなわちDAG）に従う特徴量の置換（パーミュテーション）に計算を限定する「非対称Shapley値（ASV）」が提案された。しかし、ASVの計算複雑性は十分に調査されていなかった。本論文は、因果制約を組み込むことが、特定の文脈において、標準的なShapley値よりもASVの計算をより扱いやすく（計算可能に）できるかどうかを調査している。

手法

著者らは、因果グラフの構造と、基礎となる確率分布（ベイジアンネットワークとしてモデル化される）を活用して、ASVを正確または近似的に計算するための一連のアルゴリズムを提案している。

1. 理論的な計算可能性の分析

著者らは、ナイーブベイズ分布下におけるASVの複雑性に関する理論的な結果を確立している。彼らは、ナイーブベイズ分布の下での特定のモデルファミリーにおいて、標準的なShapley値の計算は困難であるが、もしASVに使用される因果グラフがナイーブベイズネットワークの構造と同一であれば、ASVの計算は多項式時間で実行可能であることを証明した。これは、分布による因果制約が、本来ならば問題を困難にする対称性を打破できることを示唆している。

2. 同値類を用いた厳密な計算

より一般的な因果構造、具体的には**根付き有向木（rooted directed trees）**へと計算可能性を拡張するために、著者らは置換の探索空間を削減する手法を導入している：

同値類（Equivalence Classes）： 彼らは、因果グラフのトポロジカル順序の集合に対する同値関係を定義している。ある特徴量 $x$ に関して、2つの順序が同値であるとは、 $x$ の前にある特徴量の集合が両方の順序において同一であることを指す。
アルゴリズム： すべてのトポロジカル順序を反復する代わりに（これは指数関数的になり得る）、アルゴリズムは同値類の集合（ $\Lambda_x^C$ ）とその各クラスのサイズを計算する。そして、各同値類のサイズで重み付けされた限界貢献度を合計することで、ASVを計算する。
計算量： 根付き有向木の場合、同値類の数は $h \cdot l + 1$ （ $h$ は深さ、 $l$ は葉の数）によって抑えられる。著者らは、これらのクラスとそのサイズを計算するための多項式時間アルゴリズムを提供している。

3. サンプリングによる近似計算

厳密な計算が困難な可能性がある任意の因果DAGに対して、著者らはサンプリングに基づく近似スキームを提案している。

トポロジカル順序のサンプリング： この手法は、トポロジカル順序を一様ランダムにサンプリングすることに依存している。著者らは、以下の2つのアプローチを実装している：
1. ポリツリー（polytrees）（任意の2ノード間に高々1つのパスが存在するグラフ）のための再帰的カウントアルゴリズム。これは、ソースノードを正しく重み付けするためにトポロジカル順序をカウントする。
  2 一般的なDAGのための、ランダムウォークベースのアルゴリズム（Bubley & Dyer, 1999に基づく）。
誤差範囲： トポロジカル順序サンプラーが一様分布に $\epsilon_{samp}$ 近く、特性関数（期待モデル値）が誤差 $\epsilon_{\nu}$ で近似されている場合、得られるASV推定値の加法的誤差は $O(\epsilon_{samp} + \epsilon_{\nu})$ であることを定式化している。

主な結果

著者らは、実世界のベイジアンネットワーク（Cancer, Child）および人工的な構造（平衡木、ナイーブベイズ、マルチパス）を用いて、提案手法を評価した。

探索空間の削減： 同値類のアプローチは、すべてのトポロジカル順序を列挙する場合と比較して、計算負荷を大幅に軽減した。「Child」ネットワークでは、トポロジカル順序の数は約 $7.41 \times 10^{11}$ であったが、同値類の数は平均してわずか約 2003 であった。
実行時間の効率性：
- 実用的なグラフサイズに対する同値類の計算には、1秒もかからなかった。
- 厳密なアルゴリズムの実行時間は、同値類の数と強く相関しており、クラス数の事前計算が計算コストの予測因子として機能することが示された。
- より大きなグラフでは、すべてのトポロジカル順序を列挙することは不可能となったが、同値類を用いた手法は実行可能な状態を維持した。
サンプリングの性能：
- ポリツリー用のカスタム再帰サンプリングアルゴリズムは、候補生成の並列化により、サンプル数に対して非線形なスケーリングを示す効率的なものであった。
- 1,000個のサンプルを使用した場合、ASV値の平均相対誤差は約8%であった。誤差は、真のASV値が大きい場合には小さくなり、非常に小さい場合には大きくなる傾向があった。

意義と主張

本論文は、因果構造が関連する場合、ASVは説明可能性のための実行可能かつ潜在的に優れたフレームワークであると主張している。なぜなら、ASVは標準的なSHAPが見逃してしまう依存関係を捉えることができるからである。主要な貢献は、因果制約が、特定のモデルと分布のペア（例：ナイーブベイズ下の決定木）において、困難な問題を扱いやすい問題へと変容させ得ることを示した点にある。

著者らは、ASVがこれらの理論的・実践的な利点を提供している一方で、そのスケーラビリティは因果グラフのトポロジーに大きく依存することを強調している：

根付き有向木およびポリツリーについては、同値類を用いた厳密な計算が可能である。
高密度または大規模なDAGについては、同値類の数が依然として大きくなりすぎる可能性があり、サンプリングベースの近似が必要となる。

本研究は、因果グラフが既知であり、かつグラフ構造が効率的な列挙またはサンプリングを許容する場合において、ASVがXAIの有望な方向性であることを結論付けている。今後の課題として、より広範なクラスのグラフ（例：一般的なポリツリー）への厳密なアルゴリズムの一般化、およびサンプリングメカニズムの最適化が示唆されている。