論文の概要: On the Tractability of SHAP Explanations under Markovian Distributions

• arxiv url: http://arxiv.org/abs/2405.02936v2
• Date: Fri, 24 May 2024 23:45:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-29 05:37:42.395248
• Title: On the Tractability of SHAP Explanations under Markovian Distributions
• Title（参考訳）: マルコフ分布下におけるSHAP説明のトラクタビリティについて
• Authors: Reda Marzouk, Colin de La Higuera,
• Abstract要約: SHAPフレームワークはMLモデルの局所的な説明可能性のための最も広く利用されているフレームワークの1つである。 その人気にもかかわらず、その正確な計算は非常に困難であることが知られ、様々な構成においてNP-Hardであることが証明されている。 近年の研究では、特定のモデルファミリーに対するSHAPスコアの計算に関して、肯定的な複雑性の結果が明らかにされている。
• 参考スコア（独自算出の注目度）: 0.1578515540930834
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Thanks to its solid theoretical foundation, the SHAP framework is arguably one the most widely utilized frameworks for local explainability of ML models. Despite its popularity, its exact computation is known to be very challenging, proven to be NP-Hard in various configurations. Recent works have unveiled positive complexity results regarding the computation of the SHAP score for specific model families, encompassing decision trees, random forests, and some classes of boolean circuits. Yet, all these positive results hinge on the assumption of feature independence, often simplistic in real-world scenarios. In this article, we investigate the computational complexity of the SHAP score by relaxing this assumption and introducing a Markovian perspective. We show that, under the Markovian assumption, computing the SHAP score for the class of Weighted automata, Disjoint DNFs and Decision Trees can be performed in polynomial time, offering a first positive complexity result for the problem of SHAP score computation that transcends the limitations of the feature independence assumption.
• Abstract（参考訳）: そのしっかりとした理論的な基盤のおかげで、SHAPフレームワークは間違いなくMLモデルの局所的な説明可能性のための最も広く使われているフレームワークの1つである。 その人気にもかかわらず、その正確な計算は非常に困難であることが知られ、様々な構成においてNP-Hardであることが証明されている。 近年の研究では、決定木、無作為林、ブール回路のクラスを含む、特定のモデルファミリーに対するSHAPスコアの計算に関して、肯定的な複雑性の結果が明らかにされている。 しかし、これらの肯定的な結果は、機能独立の仮定を暗示しており、現実のシナリオでは多くの場合、単純である。 本稿では,この仮定を緩和し,マルコフ視点を導入することで,SHAPスコアの計算複雑性を考察する。 マルコフの仮定では、重み付きオートマトン、解離DNF、決定木に対するSHAPスコアの計算は多項式時間で行うことができ、特徴独立仮定の限界を超越するSHAPスコア計算の問題に対して、最初の正の複雑性結果を提供する。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• The Distributional Uncertainty of the SHAP score in Explainable Machine Learning [2.655371341356892]
  本稿では,未知の実体集団分布下でのSHAPスコアの推論の原理的枠組みを提案する。 我々は,この関数の最大値と最小値を求める基本的な問題について検討し,すべての特徴のSHAPスコアに対して厳密な範囲を決定できることを示した。
  論文  参考訳（メタデータ） (2024-01-23T13:04:02Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• A $k$-additive Choquet integral-based approach to approximate the SHAP values for local interpretability in machine learning [8.637110868126546]
  本稿では,Shapley値に基づく機械学習モデルに対する解釈可能性の提供を目的とする。 Kernel SHAPと呼ばれるSHAPベースの手法は、計算労力を少なくしてそのような値を近似する効率的な戦略を採用する。 得られた結果から,提案手法ではSHAP値に近似するために属性の連立性に関する計算がより少ないことが確認された。
  論文  参考訳（メタデータ） (2022-11-03T22:34:50Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。 我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
  論文  参考訳（メタデータ） (2022-09-29T17:56:25Z)
• Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
  我々は構造化出力予測(SOP)のための予測層を設計する。 予測が事前に定義されたシンボリック制約のセットと一致していることを保証するため、任意のニューラルネットワークにプラグインすることができる。 我々のセマンティック確率層(SPL)は、構造化された出力空間上で複雑な相関や制約をモデル化することができる。
  論文  参考訳（メタデータ） (2022-06-01T12:02:38Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• On the Tractability of SHAP Explanations [40.829629145230356]
  SHAPの説明は、説明可能なAIの一般的な機能帰属メカニズムである。 SHAP説明の計算の複雑さは、モデルが期待する値の計算の複雑さと同じであることを示す。 完全に分解された分布を超えて、SHAP説明の計算は、非常に単純な設定で既に難解であることが示される。
  論文  参考訳（メタデータ） (2020-09-18T05:48:15Z)
• The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits [2.8682942808330703]
  SHAPスコアは決定木のクラス上で時間的に計算可能であることを示す。 また、SHAPスコアの概念の計算限界を確立する。
  論文  参考訳（メタデータ） (2020-07-28T08:04:28Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)

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

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