論文の概要: The Tractability of SHAP-Score-Based Explanations over Deterministic and
Decomposable Boolean Circuits
- arxiv url: http://arxiv.org/abs/2007.14045v3
- Date: Sat, 3 Apr 2021 16:34:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-06 02:37:06.068811
- Title: The Tractability of SHAP-Score-Based Explanations over Deterministic and
Decomposable Boolean Circuits
- Title（参考訳）: 決定論的・分解可能なブール回路におけるSHAPスコアベース説明のトラクタビリティ
- Authors: Marcelo Arenas, Pablo Barcel\'o Leopoldo Bertossi, Mika\"el Monet
- Abstract要約: SHAPスコアは決定木のクラス上で時間的に計算可能であることを示す。
また、SHAPスコアの概念の計算限界を確立する。
- 参考スコア（独自算出の注目度）: 2.8682942808330703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Scores based on Shapley values are widely used for providing explanations to
classification results over machine learning models. A prime example of this is
the influential SHAP-score, a version of the Shapley value that can help
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 a
computationally intractable problem, it has recently been claimed that the
SHAP-score can be computed in polynomial time over the class of decision trees.
In this paper, we provide a proof of a stronger result over Boolean models: the
SHAP-score can be computed in polynomial time over deterministic and
decomposable Boolean circuits. Such circuits, also known as tractable Boolean
circuits, generalize a wide range of Boolean circuits and binary decision
diagrams classes, including binary decision trees, Ordered Binary Decision
Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs). We also establish
the computational limits of the notion of SHAP-score by observing that, under a
mild condition, 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, as removing one or the other renders the problem of
computing the SHAP-score intractable (namely, #P-hard).
- Abstract（参考訳）: Shapley値に基づくスコアは、機械学習モデルよりも分類結果の説明に広く使用されている。
影響のあるshap-scoreは、shapley値のバージョンで、各機能にスコアを割り当てることで、特定のエンティティにおける学習モデルの結果を説明するのに役立つ。
一般に、Shapley値は計算的に難解な問題であるが、近年、SHAPスコアは決定木のクラスよりも多項式時間で計算できると主張している。
本稿では,booleanモデルよりも強い結果の証明を提供する。shap-scoreは決定論的かつ分解可能なboolean回路よりも多項式時間で計算できる。
このような回路は、抽出可能なブール回路としても知られ、二分決定木、順序付き二分決定図(OBDD)、自由二分決定図(FBDD)を含む幅広いブール回路と二分決定図を一般化する。
また, SHAPスコアの概念の計算限界は, 穏やかな条件下では, ブールモデルのクラス上での計算が, そのクラスのモデルカウント問題と同じくらい多項式的に難しいことを観察することによって確立する。
これは、決定論と分解可能性の両方が、どちらか一方を取り除くことによって、SHAPスコアの難解性(つまり#P-hard)を計算する問題を引き起こすと考える回路にとって不可欠な性質であることを意味する。
関連論文リスト
- Bisimulation Learning [55.859538562698496]
我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。
提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
論文 参考訳（メタデータ） (2024-05-24T17:11:27Z) - On the Tractability of SHAP Explanations under Markovian Distributions [0.1578515540930834]
SHAPフレームワークはMLモデルの局所的な説明可能性のための最も広く利用されているフレームワークの1つである。
その人気にもかかわらず、その正確な計算は非常に困難であることが知られ、様々な構成においてNP-Hardであることが証明されている。
近年の研究では、特定のモデルファミリーに対するSHAPスコアの計算に関して、肯定的な複雑性の結果が明らかにされている。
論文 参考訳（メタデータ） (2024-05-05T13:56:12Z) - Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases [3.386124605656362]
私たちはShapleyのようなスコアを確率的設定に適応させ、期待値を計算することを目的としています。
本稿では,期待値のシェープ値とブール関数の期待値の計算が時間内に解釈可能であることを示す。
本稿では,データベースの証明を通じてデータベースに適用し,このアルゴリズムをProvableシステム内で効果的に実装する。
論文 参考訳（メタデータ） (2024-01-12T10:34:31Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - Oracle Inequalities for Model Selection in Offline Reinforcement
Learning [105.74139523696284]
本稿では,値関数近似を用いたオフラインRLにおけるモデル選択の問題について検討する。
対数係数まで最小値の速度-最適不等式を実現するオフラインRLの最初のモデル選択アルゴリズムを提案する。
そこで本研究では,優れたモデルクラスを確実に選択できることを示す数値シミュレーションを行った。
論文 参考訳（メタデータ） (2022-11-03T17:32:34Z) - Exact Shapley Values for Local and Model-True Explanations of Decision
Tree Ensembles [0.0]
決定木アンサンブルの説明にShapley値を適用することを検討する。
本稿では,無作為林に適応し,決定木を増強できる,Shapley値に基づく特徴属性に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2021-12-16T20:16:02Z) - Structural Learning of Probabilistic Sentential Decision Diagrams under
Partial Closed-World Assumption [127.439030701253]
確率感性決定図は構造化分解可能な回路のクラスである。
本稿では,回路の論理的基盤を暗黙的に提供する部分閉世界仮定に基づく新しいスキームを提案する。
予備実験では、提案手法がトレーニングデータに適切に適合し、基礎となる論理的基盤と整合性を維持した上で、テストデータによく適合することを示した。
論文 参考訳（メタデータ） (2021-07-26T12:01:56Z) - Accurate Shapley Values for explaining tree-based models [0.0]
木構造を効率的に利用し,最先端の手法よりも精度の高い2つのシェープ値推定器を導入する。
これらのメソッドはPythonパッケージとして利用できる。
論文 参考訳（メタデータ） (2021-06-07T17:35:54Z) - On the Complexity of SHAP-Score-Based Explanations: Tractability via
Knowledge Compilation and Non-Approximability Results [2.552090781387889]
Machine Learningでは、$mathsfSHAP$-scoreを使用して、特定のエンティティ上で学習されたモデルの結果を説明する。
決定論的かつ分解可能な回路上で,$mathsfSHAP$-scoreを時間で計算できることを実証する。
論文 参考訳（メタデータ） (2021-04-16T10:22:32Z) - Fast Hierarchical Games for Image Explanations [78.16853337149871]
本稿では,シェープリー係数の階層的拡張に基づく画像分類のモデル非依存な説明法を提案する。
他のShapleyベースの説明手法とは異なり、h-Shapはスケーラブルで近似を必要とせずに計算できる。
本手法は,合成データセット,医用画像シナリオ,一般コンピュータビジョン問題において,一般的なシャプリーベースおよび非サプリーベース手法と比較した。
論文 参考訳（メタデータ） (2021-04-13T13:11:02Z) - Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。
我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。
まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
論文 参考訳（メタデータ） (2020-08-19T16:04:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。