論文の概要: Unifying Formal Explanations: A Complexity-Theoretic Perspective

• arxiv url: http://arxiv.org/abs/2602.18160v1
• Date: Fri, 20 Feb 2026 11:52:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-23 18:01:41.313314
• Title: Unifying Formal Explanations: A Complexity-Theoretic Perspective
• Title（参考訳）: 形式的説明を統一する:複雑性-理論的視点
• Authors: Shahaf Bassan, Xuanxiang Huang, Guy Katz,
• Abstract要約: 計算の複雑さは値関数の3つの重要な性質に影響されていることを示す。 これらの説明の高度に単純化されたバージョンでさえも、対応する局所的説明可能性設定で計算するNPハードとなることを示す。
• 参考スコア（独自算出の注目度）: 9.350838775251075
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Previous work has explored the computational complexity of deriving two fundamental types of explanations for ML model predictions: (1) *sufficient reasons*, which are subsets of input features that, when fixed, determine a prediction, and (2) *contrastive reasons*, which are subsets of input features that, when modified, alter a prediction. Prior studies have examined these explanations in different contexts, such as non-probabilistic versus probabilistic frameworks and local versus global settings. In this study, we introduce a unified framework for analyzing these explanations, demonstrating that they can all be characterized through the minimization of a unified probabilistic value function. We then prove that the complexity of these computations is influenced by three key properties of the value function: (1) *monotonicity*, (2) *submodularity*, and (3) *supermodularity* - which are three fundamental properties in *combinatorial optimization*. Our findings uncover some counterintuitive results regarding the nature of these properties within the explanation settings examined. For instance, although the *local* value functions do not exhibit monotonicity or submodularity/supermodularity whatsoever, we demonstrate that the *global* value functions do possess these properties. This distinction enables us to prove a series of novel polynomial-time results for computing various explanations with provable guarantees in the global explainability setting, across a range of ML models that span the interpretability spectrum, such as neural networks, decision trees, and tree ensembles. In contrast, we show that even highly simplified versions of these explanations become NP-hard to compute in the corresponding local explainability setting.
• Abstract（参考訳）: MLモデル予測の基本的な2種類の説明を導出する計算の複雑さについて検討した。(1) 十分な理由* は入力特徴のサブセットであり、固定すると予測が決定され、(2) 対照的な理由* は入力特徴のサブセットであり、修正されると予測が変更される。 従来の研究では、非確率的対確率的フレームワークや局所的対グローバルな設定など、様々な文脈でこれらの説明を調査してきた。 本研究では、これらの説明を統一的に分析する枠組みを導入し、これら全てを統一確率値関数の最小化により特徴付けることができることを示す。 次に、これらの計算の複雑さは、(1)*単調性*、(2)*半モジュラリティ*、(3)*超モジュラリティ*の3つの重要な性質の影響を受けていることを証明した。 本研究は, これらの特性について, 説明条件の中で, 直感的な結果が得られた。 例えば、*局所*値函数は単調性や部分モジュラリティ/超モジュラリティを示さないが、*global*値函数がこれらの性質を持つことを示す。 この区別により、ニューラルネットワーク、決定木、ツリーアンサンブルなどの解釈可能性スペクトルにまたがるMLモデルの範囲において、グローバルな説明可能性設定において証明可能な保証を持つ様々な説明を演算するための新しい多項式時間結果の一連の証明が可能となる。 対照的に、これらの説明の高度に単純化されたバージョンでさえ、対応する局所的な説明可能性設定で計算するNPハードとなることを示す。

関連論文リスト

• Additive Models Explained: A Computational Complexity Approach [9.380879437204277]
  Generalized Additive Models (GAMs) は ML コミュニティ内では *interpretable* と見なされることが多い。 計算複雑性*を解析し、複数の文脈にまたがる様々な形態のGAMについて、異なる説明を生成する。
  論文  参考訳（メタデータ） (2025-10-24T09:40:30Z)
• Loss-Complexity Landscape and Model Structure Functions [53.92822954974537]
  我々はコルモゴロフ構造関数 $h_x(alpha)$ を双対化するためのフレームワークを開発する。 情報理論構造と統計力学の数学的類似性を確立する。 構造関数と自由エネルギーの間のルジャンドル・フェンシェル双対性を明確に証明する。
  論文  参考訳（メタデータ） (2025-07-17T21:31:45Z)
• A simple probabilistic neural network for machine understanding [0.0]
  本稿では,機械理解のためのモデルとして,確率的ニューラルネットワークと内部表現の固定化について論じる。 内部表現は、それが最大関係の原理と、どのように異なる特徴が組み合わされるかについての最大無知を満たすことを要求して導出する。 このアーキテクチャを持つ学習機械は、パラメータやデータの変化に対する表現の連続性など、多くの興味深い特性を享受している、と我々は主張する。
  論文  参考訳（メタデータ） (2022-10-24T13:00:15Z)
• Explainability in Process Outcome Prediction: Guidelines to Obtain Interpretable and Faithful Models [77.34726150561087]
  本稿では、プロセス結果予測の分野における説明可能性モデルと説明可能性モデルの忠実性を通して、説明可能性を定義する。 本稿では,イベントログの仕様に基づいて適切なモデルを選択することのできる,X-MOPというガイドラインのセットを提案する。
  論文  参考訳（メタデータ） (2022-03-30T05:59:50Z)
• Towards Unifying Feature Attribution and Counterfactual Explanations: Different Means to the Same End [17.226134854746267]
  本稿では,一組の反実例から特徴帰属説明を生成する手法を提案する。 本報告では, 帰属に基づく説明の妥当性を, その必要性と充足性の観点から評価するために, 対実例をいかに活用するかを示す。
  論文  参考訳（メタデータ） (2020-11-10T05:41:43Z)
• The Struggles of Feature-Based Explanations: Shapley Values vs. Minimal Sufficient Subsets [61.66584140190247]
  機能に基づく説明は、自明なモデルでも問題を引き起こすことを示す。 そこで本研究では,2つの一般的な説明書クラスであるシェープリー説明書と十分最小限の部分集合説明書が,基本的に異なる基底的説明書のタイプをターゲットにしていることを示す。
  論文  参考訳（メタデータ） (2020-09-23T09:45:23Z)

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

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