論文の概要: On the Complexity of SHAP-Score-Based Explanations: Tractability via
Knowledge Compilation and Non-Approximability Results
- arxiv url: http://arxiv.org/abs/2104.08015v2
- Date: Thu, 30 Mar 2023 08:43:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-31 18:45:52.227914
- Title: On the Complexity of SHAP-Score-Based Explanations: Tractability via
Knowledge Compilation and Non-Approximability Results
- Title（参考訳）: SHAP-Score-based Explanationsの複雑さについて:知識コンパイルによるトラクタビリティと非近似結果
- Authors: Marcelo Arenas, Pablo Barcel\'o, Leopoldo Bertossi, Mika\"el Monet
- Abstract要約: Machine Learningでは、$mathsfSHAP$-scoreを使用して、特定のエンティティ上で学習されたモデルの結果を説明する。
決定論的かつ分解可能な回路上で,$mathsfSHAP$-scoreを時間で計算できることを実証する。
- 参考スコア（独自算出の注目度）: 2.552090781387889
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In Machine Learning, the $\mathsf{SHAP}$-score is a version of the Shapley
value that is used to explain the result of a learned model on a specific
entity by assigning a score to every feature. While in general computing
Shapley values is an intractable problem, we prove a strong positive result
stating that the $\mathsf{SHAP}$-score can be computed in polynomial time over
deterministic and decomposable Boolean circuits. Such circuits are studied in
the field of Knowledge Compilation and generalize a wide range of Boolean
circuits and binary decision diagrams classes, including binary decision trees
and Ordered Binary Decision Diagrams (OBDDs).
We also establish the computational limits of the SHAP-score by observing
that computing it over a class of Boolean models is always polynomially as hard
as the model counting problem for that class. This implies that both
determinism and decomposability are essential properties for the circuits that
we consider. It also implies that computing $\mathsf{SHAP}$-scores is
intractable as well over the class of propositional formulas in DNF. Based on
this negative result, we look for the existence of fully-polynomial randomized
approximation schemes (FPRAS) for computing $\mathsf{SHAP}$-scores over such
class. In contrast to the model counting problem for DNF formulas, which admits
an FPRAS, we prove that no such FPRAS exists for the computation of
$\mathsf{SHAP}$-scores. Surprisingly, this negative result holds even for the
class of monotone formulas in DNF. These techniques can be further extended to
prove another strong negative result: Under widely believed complexity
assumptions, there is no polynomial-time algorithm that checks, given a
monotone DNF formula $\varphi$ and features $x,y$, whether the
$\mathsf{SHAP}$-score of $x$ in $\varphi$ is smaller than the
$\mathsf{SHAP}$-score of $y$ in $\varphi$.
- Abstract（参考訳）: Machine Learningでは、$\mathsf{SHAP}$-scoreはShapley値のバージョンであり、すべての機能にスコアを割り当てることで、特定のエンティティ上で学習したモデルの結果を説明するために使用される。
一般に、Shapley値は難解な問題であるが、$\mathsf{SHAP}$-scoreは決定論的で分解可能なブール回路よりも多項式時間で計算できるという強い正の結果を証明している。
このような回路は知識コンパイルの分野で研究され、二分決定木や順序付き二分決定図(OBDD)を含む幅広いブール回路と二分決定図を一般化する。
また,shap-scoreの計算限界は,ブールモデルのクラス上での計算が,そのクラスのモデルカウント問題と同じくらい多項式的に困難であることを観測することによって確立する。
これは、決定論と分解可能性の両方が、我々が考慮する回路にとって不可欠な性質であることを意味する。
また、$\mathsf{shap}$-scores の計算は dnf の命題公式のクラス上でも扱いがたいことを意味する。
この負の結果に基づいて、そのようなクラス上の$\mathsf{SHAP}$-scoresを計算するための完全多項式ランダム化近似スキーム (FPRAS) の存在を探索する。
FPRASを許容するDNF公式のモデルカウント問題とは対照的に,$\mathsf{SHAP}$-scoresの計算にはそのようなFPRASは存在しない。
驚くべきことに、この負の結果はDNFの単調式でも成り立つ。
広く信じられている複雑性仮定の下では、単調 dnf の公式 $\varphi$ が与えられ、$\mathsf{shap}$-score ($x$ in $\varphi$) が$\mathsf{shap}$-score ($y$ in $\varphi$) よりも小さいかどうかをチェックする多項式時間アルゴリズムは存在しない。
関連論文リスト
- Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。
提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
論文 参考訳（メタデータ） (2024-03-31T02:03:35Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文 参考訳（メタデータ） (2023-11-22T20:27:05Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。
また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
論文 参考訳（メタデータ） (2022-02-11T23:53:43Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - The Tractability of SHAP-Score-Based Explanations over Deterministic and
Decomposable Boolean Circuits [2.8682942808330703]
SHAPスコアは決定木のクラス上で時間的に計算可能であることを示す。
また、SHAPスコアの概念の計算限界を確立する。
論文 参考訳（メタデータ） (2020-07-28T08:04:28Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。