技術要約：非復元抽出と新しいブートストラップ分散推定法を用いた近似シャプレイ値の推定

1. 問題提起

古典的なKernelSHAPフレームワーク（Lundberg and Lee, 2017）は、すべての $2^p$ 個の部分集合に対して寄与関数を評価する代わりに、部分集合のサブセットをサンプリングすることで、シャプレイ値推定の計算コストを削減することを目指している。しかし、既存の実装は通常、**復元抽出（with replacement）**によって連合（coalition）をサンプリングする。このアプローチは、以下の特定の統計的課題をもたらす：

1. サンプリングの非効率性： 復元抽出によるサンプリングは、クーポンコレクター問題の重み付きバージョンを招き、サンプルサイズが増大するにつれて、特に重みの低い連合において、一意の連合を得ることがますます困難になる。
2. 分散推定の限界： 従来のブートストラップ法は、独立同一分布（i.i.d.）サンプルを仮定している。しかし、有限母集団（すべての可能な連合の集合）からの非復元抽出を行う場合、この仮定は崩れる。その結果、標準的なブートストラップ手法は、シャプレイ値の不適切な分散推定値をもたらす可能性がある。これは、すべての連合が評価された場合に分散が理論的にゼロに近づくという有限母集団の制約を考慮できていないためである。

本論文は、**非復元抽出（without replacement）**を利用するフレームワークを提案し、近似されたシャプレイ値の分散を正確に推定するために、有限母集団理論と互換性のある新しいブートストラップ手法を導入することで、これらの問題に対処する。

2. 手法

2.1 Wallenius分布による非復元抽出

提案するアルゴリズムは、KernelSHAPの手順を修正し、連合を非復元抽出するように改良している。プロセスは主に2つのステップで構成される：

1. 層化（Stratification）： 連合を、それが含む特徴量の数（サイズ）によってグループ化する。
2. サンプルサイズの決定： 連合を確率的に一つずつサンプリングする代わりに、アルゴリズムはWalleniusの非中心型超幾何分布を用いて、各グループから抽出されるべき期待連合数を計算する。この分布は、アイテムが異なる重みを持つ、偏った非復元抽出をモデル化するものである。
   • アルゴリズムは、この分布の期待値を使用し、最も近い整数に丸めることで、各層からサンプリングする連合の数を決定する。
   • カウントが決定された後、各グループ内で連合を非復元抽出する。
   • ペアリング戦略： 分散をさらに低減するため、本手法はペアリング戦略（Kroese et al., 2013）を採用する。ある連合 $S$ がサンプリングされた場合、その補集合 $S^c$ も計算に含めることで、ペアリングされたグループ内の特徴量の総和が一定に保たれることを保証する。

2.2 ブートストラップ法による分散推定

本論文では、新しいサンプリング設計下でのシャプレイ値の標準偏差を推定するための3つのアプローチを評価している：

1. 不適切な直感的メソッド（Invalid Intuitive Method）： 重み付き最小二乗問題に直接適用された標準的なHorvitz-Thompson分散推定器。著者は、これが不適切であることを示している。なぜなら、ペアリング戦略によって導入される特定の依存関係や、KernelSHAPの文脈における $Z^T W Z$ 行列の構造を考慮できていないためである。
2. 倍半ブートストラップ（Doubled Half Bootstrap; Antal and Tillé, 2014）： 単位がベルヌーイ・サンプリングによって選択され、選択されなかった単位がランダムに2回選択される有限母集団における既知の手法。比較のために実装されている。
3. 対称ブートストラップ（Symmetric Bootstrap; 新規貢献）： この文脈に特化して開発された新しいブートストラップ手法。
   • メカニズム： 各ブートストラップ・サンプルにおいて、元のサンプル内のすべての単位は、0回、1回、または2回出現することができる。
   • 対称性： この手法は、0回出現する単位の総数と2回出現する単位の総数が等しくなることを保証する。
   • 確率： 単位 $k$ が $S_k$ 回出現する確率は以下のように定義される：
     • $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
     • $Pr(S_k = 1) = \frac{n}{N}$
   • 特性： この構成により、$E(S_k) = 1$ および $Var(S_k) = 1 - \frac{n}{N}$ が保証され、有限母集団サンプリングにおける必要な条件（Horvitz-Thompsonの一致性）を満たす。
   • 非整数の処理： 「0」または「2」の出現期待数が整数でない場合、隣接する整数値を交互に選択するためのベルヌーイ変数が導入され、手順が完全に自動的であることを保証する。

2.3 計算実装

寄与関数 $v(S)$ は、サンプリングされた連合を用いた回帰によって推定される。実装は、線形モデルを効率的に扱うために、疎行列（sparse matrices）とCholesky分解（Matrixパッケージ）を活用しており、単一コア上で数分以内に65,000個以上の線形モデルの平均を推定することが可能である（Aanes, 2025）。

3. 主な貢献

1. サンプリング・フレームワーク： Walleniusの非中心型超幾何分布をKernelSHAPフレームワークに統合することで、効率的な非復元抽出を可能にし、復元抽出に伴うクーポンコレクター問題の非効率性を回避した。
2. 対称ブートストラップ： 有限母集団の非復元抽出に特化した、新しい、計算効率の高いブートストラップ手法の導入。これは、この文脈における不偏な分散推定に必要なモーメント条件（平均と分散）を満たしている。
3. 分散推定の分析： 新しい設計に対する分散推定器の厳密な比較を行い、標準的なブートストラップがこの特定の設計においては不適切であること、および新しい対称ブートストラップが既存の倍半ブートストラップ（Antal and Tillé, 2014）と同等または優れた性能を示すことを実証した。

4. 結果

Kaggleの「Life Expectancy」データセットを用い、新しい手法を、復元抽出を行う最新のRパッケージ shapr（バージョン1.0.7）と比較する2つのシミュレーション研究を実施した。

• 小規模シミュレーション研究（5特徴量、16連合）：
  • 新しいサンプリング手法は、shapr と同等の標準偏差を持つシャプレイ値推定値を生成した。
  • Antal-Tillé ブートストラップは性能が悪く、頻繁に非フルランクの行列（$Z^T W Z$）および不正確な分散推定値をもたらした。
  • 対称ブートストラップは Antal-Tillé よりも大幅に優れた性能を示したが、時として真値（すべての連合を再サンプリングした場合）と比較して、わずかに「リベラル（楽観的）」な（小さい）標準偏差を算出することがあった。
• 大規模シミュレーション研究（16特徴量、402連合）：
  • 対称ブートストラップと Antal-Tillé の両方の手法は、標準偏差の推定において区別がつかない結果となった。
  • 両方の新しいブートストラップ手法は、shapr に組み込まれたブートストラップ手順よりもわずかに優れた性能を示した（shapr はいくつかの変数において標準偏差を過小評価する傾向があった）。
  • 新しいサンプリングアルゴリズム（非復元抽出）は、シャプレイ値の推定自体の正確さにおいては、shapr の手法（復元抽出）と同様の性能を示した。

5. 意義と結論

本論文は、Wallenius分布による非復元抽出を組み合わせた提案アルゴリズムが、既存のKernelSHAP実装に対して堅牢な代替案となることを結論付けている。

• パフォーマンス： 新しい手法は、点推定に関して、改良されたKernelSHAP手法である shapr パッケージと「同様」の性能を持つ。
• 分散推定： 対称ブートストラップは、「非常に計算が速く、理解しやすい」手法として強調されており、特に大規模なシミュレーション研究において良好な結果を示した。これは、非復元抽出による有限母集団のランダムサンプリングにおける「定番」のブートストラップ手法に対する、文献上の空白を埋めるものである。
• 限界： 著者は謙虚に、最小の調査において、対称ブートストラップが特定の変数に対して標準偏差をわずかに小さく（リベラルに）算出することがあったと述べているが、最大の標準偏差については一貫して捉えていた。
• 適用可能性： 本手法は、寄与関数が線形または一般化線形モデル（予測が変換されたスケール上で線形である場合）を介して推定されるシナリオ向けに設計されており、高速な計算技術を活用している。

本研究は、有限母集団理論をシャプレイ値推定に適用することで、サンプリング効率を高め、妥当な分散推定を提供できることを確立した。これにより、この領域における従来のi.i.d.ブートストラップ仮定の理論的限界を克服している。