論文の概要: SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
- arxiv url: http://arxiv.org/abs/2510.21599v1
- Date: Fri, 24 Oct 2025 16:02:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-28 09:00:15.535373
- Title: SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
- Title（参考訳）: SHAPがTensor Networksを発表 - おそらく並列処理によるトレーサブルな説明
- Authors: Reda Marzouk, Shahaf Bassan, Guy Katz,
- Abstract要約: より広範かつ表現力のあるモデルである *Tensor Networks (TNs)* の SHAP 説明の計算問題を分析する。
TNが*Tensor Train (TT)*構造に制限されている場合、SHAP計算は*parallel*計算を用いて*poly-logarithmic*時間で実行できることを示す。
TTのパワーのおかげで、この複雑さは決定木、ツリーアンサンブル、線形モデル、線形RNNといった多くの一般的なMLモデルに一般化することができる。
- 参考スコア（独自算出の注目度）: 7.067748466807765
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Although Shapley additive explanations (SHAP) can be computed in polynomial time for simple models like decision trees, they unfortunately become NP-hard to compute for more expressive black-box models like neural networks - where generating explanations is often most critical. In this work, we analyze the problem of computing SHAP explanations for *Tensor Networks (TNs)*, a broader and more expressive class of models than those for which current exact SHAP algorithms are known to hold, and which is widely used for neural network abstraction and compression. First, we introduce a general framework for computing provably exact SHAP explanations for general TNs with arbitrary structures. Interestingly, we show that, when TNs are restricted to a *Tensor Train (TT)* structure, SHAP computation can be performed in *poly-logarithmic* time using *parallel* computation. Thanks to the expressiveness power of TTs, this complexity result can be generalized to many other popular ML models such as decision trees, tree ensembles, linear models, and linear RNNs, therefore tightening previously reported complexity results for these families of models. Finally, by leveraging reductions of binarized neural networks to Tensor Network representations, we demonstrate that SHAP computation can become *efficiently tractable* when the network's *width* is fixed, while it remains computationally hard even with constant *depth*. This highlights an important insight: for this class of models, width - rather than depth - emerges as the primary computational bottleneck in SHAP computation.
- Abstract（参考訳）: Shapley加法的説明(SHAP)は、決定木のような単純なモデルでは多項式時間で計算できるが、残念ながら、ニューラルネットワークのようなより表現力のあるブラックボックスモデルの計算にはNPハードになる。
本研究では,現在正確なSHAPアルゴリズムが保持されているモデルよりも広く,より表現力の高いモデルである *Tensor Networks (TNs)* の SHAP 説明の計算問題を分析し,ニューラルネットワークの抽象化と圧縮に広く利用されている。
まず、任意の構造を持つ一般的なTNに対して、証明可能な正確なSHAP説明を計算するための一般的なフレームワークを提案する。
興味深いことに、TNが*Tensor Train (TT)*構造に制限されている場合、SHAP計算は*parallel*計算を用いて*poly-logarithmic*時間で実行できる。
TTの表現力のおかげで、この複雑性結果は決定木、ツリーアンサンブル、線形モデル、線形RNNといった他の一般的なMLモデルに一般化することができる。
最後に、二項化ニューラルネットワークをテンソルネットワーク表現に還元することにより、ネットワークの*幅*が固定されたとき、SHAP計算が*効率よく引き出せる*となり、一定の*深さ*であっても計算が困難であることを示す。
このクラスのモデルでは、深度ではなく幅が、SHAP計算における主要な計算ボトルネックとして現れます。
関連論文リスト
- Implicit Models: Expressive Power Scales with Test-Time Compute [17.808479563949074]
入出力モデルは、新しいモデルクラスであり、単一のパラメータブロックを固定点に反復することで出力を計算します。
我々はこのギャップを表現力の非パラメトリック解析を通して研究する。
幅広い種類の暗黙的モデルに対して、このプロセスはテスト時間計算によるモデルの表現力尺度を可能にすることを証明している。
論文 参考訳（メタデータ） (2025-10-04T02:49:22Z) - Front-propagation Algorithm: Explainable AI Technique for Extracting Linear Function Approximations from Neural Networks [0.0]
本稿では、深層ニューラルネットワークの意思決定ロジックの解明を目的とした、新しいAI技術であるフロントプロパゲーションアルゴリズムを紹介する。
積分グラディエントやシェープ値などの他の一般的な説明可能性アルゴリズムとは異なり、提案アルゴリズムはネットワークの正確で一貫した線形関数説明を抽出することができる。
公開されているベンチマークデータセットに基づいてトレーニングされた3つの異なるニューラルネットワークアーキテクチャで、正確な線形関数を提供することの有効性を実証する。
論文 参考訳（メタデータ） (2024-05-25T14:50:23Z) - Predictions Based on Pixel Data: Insights from PDEs and Finite Differences [0.0]
本稿では,各観測が行列である時間列の近似を扱う。
比較的小さなネットワークでは、直線法に基づいて、PDEの数値的な離散化のクラスを正確に表現できることが示される。
我々のネットワークアーキテクチャは、典型的に時系列の近似に採用されているものから着想を得ている。
論文 参考訳（メタデータ） (2023-05-01T08:54:45Z) - A Recursively Recurrent Neural Network (R2N2) Architecture for Learning
Iterative Algorithms [64.3064050603721]
本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。
本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
論文 参考訳（メタデータ） (2022-11-22T16:30:33Z) - Bayesian Deep Learning with Multilevel Trace-class Neural Networks [0.5892638927736115]
我々は、ディープニューラルネットワーク(DNN)、特にトレースクラスニューラルネットワーク(TNN)に関連付けられた推論について検討する。
TNN事前は無限個の隠れ単位を持つ関数上で定義され、有限個の隠れ単位を持つ強い収束近似を持つ。
本稿では,TNNの強い収束を利用して,これらのモデルにマルチレベルモンテカルロ(MLMC)を適用する。
論文 参考訳（メタデータ） (2022-03-24T09:49:27Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - Mitigating Performance Saturation in Neural Marked Point Processes:
Architectures and Loss Functions [50.674773358075015]
本稿では,グラフ畳み込み層のみを利用するGCHPという単純なグラフベースのネットワーク構造を提案する。
我々は,GCHPがトレーニング時間を大幅に短縮し,時間間確率仮定による確率比損失がモデル性能を大幅に改善できることを示した。
論文 参考訳（メタデータ） (2021-07-07T16:59:14Z) - PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。
我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。
回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
論文 参考訳（メタデータ） (2021-03-23T17:03:10Z) - Connecting Weighted Automata, Tensor Networks and Recurrent Neural
Networks through Spectral Learning [58.14930566993063]
我々は、形式言語と言語学からの重み付き有限オートマトン(WFA)、機械学習で使用されるリカレントニューラルネットワーク、テンソルネットワークの3つのモデル間の接続を提示する。
本稿では,連続ベクトル入力の列上に定義された線形2-RNNに対する最初の証明可能な学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-19T15:28:00Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。