論文の概要: QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature
- arxiv url: http://arxiv.org/abs/2605.05870v1
- Date: Thu, 07 May 2026 08:36:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-08 22:27:11.635843
- Title: QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature
- Title（参考訳）: QuadraSHAP: Gauss-Legendre Quadratureによるプロダクトゲームのための安定的でスケーラブルな共有価値
- Authors: Majid Mohammadi, Grigory Reznikov, Pavel Sinitcyn, Krikamol Muandet, Siu Lun Chau,
- Abstract要約: 本研究では,共役ゲームにおけるシャプリー値の効率的な計算法について検討し,その連立値がプレイヤーごとの項の積として分解されるような協調ゲームについて検討する。
我々の重要な結果は、製品ゲームにおける各プレイヤーのシェープ値が、正確に1次元の表現を持つことである。
- 参考スコア（独自算出の注目度）: 10.640152986359668
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the efficient computation of Shapley values for \emph{product games} -- cooperative games in which the coalition value factorizes as a product of per-player terms. Such games arise in machine learning explainability whenever the value function inherits a multiplicative structure from the underlying model, as in kernel methods with product kernels and tree-based models. Our key result is that the Shapley value of each player in a product game admits an exact one-dimensional integral representation: the weighted sum over exponentially many feature coalitions collapses to the integral of a degree-$(d-1)$ polynomial over $[0,1]$, where $d$ is the total number of features. This yields a Gauss--Legendre quadrature scheme that is \emph{provably exact} whenever the number of nodes satisfies $m_q \geq \lceil d/2 \rceil$, and otherwise provides a \emph{near-exact} approximation with error provably decaying geometrically in $m_q$. In practice, a few hundred nodes can achieve highly precise estimates even with thousands of features. Building on this formulation, we derive a numerically stable implementation via log-space evaluation, together with an efficient parallel implementation based on associative scan primitives that achieves $O(d\,m_q)$ total work and $O(\log d)$ parallel time. Experiments show that \textsc{QuadraSHAP} is the fastest numerically stable method across all tested configurations.
- Abstract（参考訳）: 本研究では, 協調ゲームにおけるShapley値の効率的な計算法について検討する。
このようなゲームは、製品カーネルやツリーベースのモデルを持つカーネルメソッドのように、バリュー関数が基礎となるモデルから乗法的構造を継承するたびに、機械学習で説明可能である。
積ゲームにおける各プレイヤーのShapley値は、正確な1次元積分表現を許容する:指数関数的に多くの特徴連立の重み付け和は、次数-$(d-1)$ polynomial over $[0,1]$の積分に崩壊する。
これはガウス=レーゲンドル二次スキームとなり、これはノードの数が$m_q \geq \lceil d/2 \rceil$を満たすときいつでも \emph{provably exact} となる。
実際には、数百のノードが、何千もの機能があっても、非常に正確な推定を達成できる。
この定式化に基づいて、ログ空間評価による数値的に安定した実装と、$O(d\,m_q)$トータルワークと$O(\log d)$パラレルタイムを実現する連想スキャンプリミティブに基づく効率的な並列実装を導出する。
実験により, テストされたすべての構成に対して最も高速に数値的に安定な方法であることが示された。
関連論文リスト
- On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。
格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。
$d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
論文 参考訳（メタデータ） (2026-04-27T10:23:24Z) - PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression [26.711792479550954]
KernelSHAPは,ゲームを線形関数として近似することにより,Shapley値を近似する指数的コストを回避する。
また、ペアサンプリングは2階のPolySHAPと全く同じ値近似を生成するが、次数2に収まらないことも証明した。
論文 参考訳（メタデータ） (2026-01-26T15:47:45Z) - A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
Lipschitz-of-$nabla f$
$mathcalS_k|p$。
$mathcalS_k|p$。
$nabla f$.
$mathcalS_k|p$。
論文 参考訳（メタデータ） (2024-09-28T18:16:32Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time [13.427128424538502]
ハミルトニアンのモンテカルロ (HMC) はサンプリングにおいて一般的な方法である。
そこで我々は,Chebyshevsのルーツに基づく時間変化積分時間スキームを提案する。
論文 参考訳（メタデータ） (2022-07-05T17:42:22Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - 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) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。