論文の概要: On the Computational Tractability of the (Many) Shapley Values

• arxiv url: http://arxiv.org/abs/2502.12295v1
• Date: Mon, 17 Feb 2025 20:08:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:05:27.958115
• Title: On the Computational Tractability of the (Many) Shapley Values
• Title（参考訳）: 多数)シェープ値の計算的トラクタビリティについて
• Authors: Reda Marzouk, Shahaf Bassan, Guy Katz, Colin de la Higuera,
• Abstract要約: 最近の研究では、様々なモデルと分布にわたるShapley加法的説明(SHAPとも呼ばれる)の計算複雑性について検討している。 これらの研究は主に条件付きSHAPと呼ばれる特定の変種に焦点を当てたが、他の多くの変種が存在し、異なる制限に対処する。 本研究では,Conditional,Interventional,Baseline SHAPなど,より広い範囲での計算の複雑さを分析する。
• 参考スコア（独自算出の注目度）: 1.0035342658750597
• License:
• Abstract: Recent studies have examined the computational complexity of computing Shapley additive explanations (also known as SHAP) across various models and distributions, revealing their tractability or intractability in different settings. However, these studies primarily focused on a specific variant called Conditional SHAP, though many other variants exist and address different limitations. In this work, we analyze the complexity of computing a much broader range of such variants, including Conditional, Interventional, and Baseline SHAP, while exploring both local and global computations. We show that both local and global Interventional and Baseline SHAP can be computed in polynomial time for various ML models under Hidden Markov Model distributions, extending popular algorithms such as TreeSHAP beyond empirical distributions. On the downside, we prove intractability results for these variants over a wide range of neural networks and tree ensembles. We believe that our results emphasize the intricate diversity of computing Shapley values, demonstrating how their complexity is substantially shaped by both the specific SHAP variant, the model type, and the distribution.
• Abstract（参考訳）: 最近の研究では、様々なモデルや分布にまたがるShapley加法的説明(SHAPとも呼ばれる)の計算複雑性を調べ、異なる設定でそれらのトラクタビリティやイントラクタビリティを明らかにしている。 しかしながら、これらの研究は主に条件付きSHAPと呼ばれる特定の変種に焦点を当てているが、他の多くの変種が存在し、異なる制限に対処する。 本研究では、ローカルおよびグローバルな計算を探索しながら、Conditional、Interventional、Baseline SHAPなど、より広範な種類の計算の複雑さを分析する。 局所的およびグローバルなインターベンショナルおよびベースラインSHAPは、Hidden Markov Model 分布の下で様々なMLモデルに対して多項式時間で計算できることを示し、TreeSHAP のような一般的なアルゴリズムを経験的分布を超えて拡張する。 欠点として、ニューラルネットワークや木のアンサンブルの幅広い範囲において、これらの変種に対する難易度が証明される。 本研究の結果は,Shapley値の複雑な多様性を強調し,その複雑性が特定のSHAP変種,モデルタイプ,分布によってどのように大きく形成されているかを示すものである。

関連論文リスト

• Partial-Multivariate Model for Forecasting [28.120094495344453]
  本稿では,問題予測のためのトランスフォーマーに基づく部分多変量モデルPMformerを提案する。 PMformerは様々な単変量モデルと完全多変量モデルより優れていることを示す。 また、PMformerの他の利点として、機能不足による効率性と堅牢性を強調します。
  論文  参考訳（メタデータ） (2024-08-19T05:18:50Z)
• On the Tractability of SHAP Explanations under Markovian Distributions [0.1578515540930834]
  SHAPフレームワークはMLモデルの局所的な説明可能性のための最も広く利用されているフレームワークの1つである。 その人気にもかかわらず、その正確な計算は非常に困難であることが知られ、様々な構成においてNP-Hardであることが証明されている。 近年の研究では、特定のモデルファミリーに対するSHAPスコアの計算に関して、肯定的な複雑性の結果が明らかにされている。
  論文  参考訳（メタデータ） (2024-05-05T13:56:12Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  文脈決定プロセス(CMDP)は、遷移カーネルと報酬関数がコンテキスト変数によってインデックス付けされた異なるMDPで時間とともに変化できる強化学習のクラスを記述する。 CMDPは、時間とともに変化する環境で多くの現実世界のアプリケーションをモデル化するための重要なフレームワークとして機能する。 CMDPを2つの線形関数近似モデルで検討する: 文脈変化表現とすべての文脈に対する共通線形重み付きモデルIと、すべての文脈に対する共通表現と文脈変化線形重み付きモデルIIである。
  論文  参考訳（メタデータ） (2024-02-05T03:25:04Z)
• Algorithms to estimate Shapley value feature attributions [11.527421282223948]
  Shapley値に基づく特徴属性は、機械学習モデルを説明するために人気がある。 我々は,この複雑さを,(1)特徴情報の除去アプローチ,(2)抽出可能な推定戦略の2つの要因に分解する。
  論文  参考訳（メタデータ） (2022-07-15T17:04:41Z)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  部分的に観察可能な力学系におけるオンライン強化学習(RL)について検討する。 我々は、他のよく知られたモデルをキャプチャする表現モデルである予測状態表現(PSR)モデルに焦点を当てる。 我々は,サンプル複雑性のスケーリングにおいて,ほぼ最適なポリシを学習可能な,PSRのための新しいモデルベースアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-12T17:57:17Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Redefining Neural Architecture Search of Heterogeneous Multi-Network Models by Characterizing Variation Operators and Model Components [71.03032589756434]
  複素領域における異なる変動演算子の効果について検討する。 モデルの複雑さと性能に影響を及ぼす変化演算子と、それを構成する異なる部分の質を推定する様々な指標に依存するモデルの両方を特徴付ける。
  論文  参考訳（メタデータ） (2021-06-16T17:12:26Z)
• Fast Hierarchical Games for Image Explanations [78.16853337149871]
  本稿では,シェープリー係数の階層的拡張に基づく画像分類のモデル非依存な説明法を提案する。 他のShapleyベースの説明手法とは異なり、h-Shapはスケーラブルで近似を必要とせずに計算できる。 本手法は,合成データセット,医用画像シナリオ,一般コンピュータビジョン問題において,一般的なシャプリーベースおよび非サプリーベース手法と比較した。
  論文  参考訳（メタデータ） (2021-04-13T13:11:02Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  変分法による離散的グラフィカルモデルの推論は困難である。 エビデンス・ロウアーバウンド(ELBO)を推定するためのサンプリングに基づく多くの手法が提案されている。 Sum Product Networks (SPN) のような確率的回路モデルのトラクタビリティを活用する新しい手法を提案する。 選択的SPNが表現的変動分布として適していることを示し、対象モデルの対数密度が重み付けされた場合、対応するELBOを解析的に計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-10-22T05:04:38Z)
• Stochastic spectral embedding [0.0]
  確率スペクトル埋め込み(SSE)に基づく新しい逐次適応サロゲートモデリング法を提案する。 本手法は,複雑性と入力次元の異なるモデルの集合上で,最先端のスパースカオス展開に対して,どのように好意的に比較されるかを示す。
  論文  参考訳（メタデータ） (2020-04-09T11:00:07Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。