論文の概要: Computing Exact Shapley Values in Polynomial Time for Product-Kernel Methods

• arxiv url: http://arxiv.org/abs/2505.16516v1
• Date: Thu, 22 May 2025 10:53:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-23 17:12:48.238065
• Title: Computing Exact Shapley Values in Polynomial Time for Product-Kernel Methods
• Title（参考訳）: 製品カーネル法における実時間特異値の計算
• Authors: Majid Mohammadi, Siu Lun Chau, Krikamol Muandet,
• Abstract要約: PKeX-Shapleyは、Shapley値の正確な計算を可能にする新しいアルゴリズムである。 PKeX-Shapleyは計算効率を向上し,カーネル学習における解釈可能性を向上させる。
• 参考スコア（独自算出の注目度）: 11.743255602108775
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Kernel methods are widely used in machine learning due to their flexibility and expressive power. However, their black-box nature poses significant challenges to interpretability, limiting their adoption in high-stakes applications. Shapley value-based feature attribution techniques, such as SHAP and kernel-specific variants like RKHS-SHAP, offer a promising path toward explainability. Yet, computing exact Shapley values remains computationally intractable in general, motivating the development of various approximation schemes. In this work, we introduce PKeX-Shapley, a novel algorithm that utilizes the multiplicative structure of product kernels to enable the exact computation of Shapley values in polynomial time. We show that product-kernel models admit a functional decomposition that allows for a recursive formulation of Shapley values. This decomposition not only yields computational efficiency but also enhances interpretability in kernel-based learning. We also demonstrate how our framework can be generalized to explain kernel-based statistical discrepancies such as the Maximum Mean Discrepancy (MMD) and the Hilbert-Schmidt Independence Criterion (HSIC), thus offering new tools for interpretable statistical inference.
• Abstract（参考訳）: カーネルメソッドは、柔軟性と表現力のために機械学習で広く使用されている。 しかしながら、ブラックボックスの性質は解釈可能性に重大な課題をもたらし、高い精度のアプリケーションでの採用を制限する。 SHAPやRKHS-SHAPのようなカーネル固有の特徴属性技術は、説明可能性への有望な道を提供する。 しかし、正確なShapley値の計算は一般に計算的に難解であり、様々な近似スキームの開発を動機付けている。 本稿では,製品カーネルの乗算構造を利用して,多項式時間におけるShapley値の正確な計算を可能にする新しいアルゴリズムであるPKeX-Shapleyを紹介する。 製品カーネルモデルはシャプリー値の再帰的な定式化を可能にする機能的分解を許容することを示す。 この分解によって計算効率が向上するだけでなく、カーネルベースの学習における解釈可能性も向上する。 また,我々のフレームワークが,最大平均離散性 (MMD) やヒルベルト・シュミット独立基準 (HSIC) などのカーネルベースの統計的不一致を説明するためにどのように一般化できるかを示す。

関連論文リスト

• Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes [12.496136169054541]
  シェープ値は、機械学習において入力特徴に重要性をもたらすための原則的手法として広く認識されている。 また,Shapley値の正確な計算量は特徴数とともに指数関数的にスケールすることを示した。 我々の研究は、構造化確率モデルによって生成される予測について、よりスケーラブルで、公理的に、そして不確実性を考慮した説明を提供する。
  論文  参考訳（メタデータ） (2025-08-20T07:39:14Z)
• Scaling Probabilistic Circuits via Monarch Matrices [109.65822339230853]
  確率回路(PC)は確率分布の抽出可能な表現である。 そこで本研究では,PCの和ブロックに対する新しいスパースパラメータと構造化パラメータ化を提案する。
  論文  参考訳（メタデータ） (2025-06-14T07:39:15Z)
• SIM-Shapley: A Stable and Computationally Efficient Approach to Shapley Value Approximation [10.009607907227293]
  共有値(SV)法は、複雑なモデルにおける特徴帰属の原則的な枠組みを提供するが、高い計算コストがかかる。 最適化にインスパイアされた安定かつ効率的な近似法である,共有値近似のための反復モーメント(SIM-Shapley)を提案する。 我々の数値実験では、SIM-Shapleyは最先端のベースラインと比較して計算時間を最大85%削減する。
  論文  参考訳（メタデータ） (2025-05-13T03:23:10Z)
• Toward Efficient Kernel-Based Solvers for Nonlinear PDEs [19.975293084297014]
  本稿では,非線形偏微分方程式(PDE)を効率的に解くための新しいカーネル学習フレームワークを提案する。 カーネルに微分演算子を埋め込む最先端のカーネルソルバとは対照的に,本手法ではこれらの演算子をカーネルから排除する。 我々は、標準カーネル形式を用いて解をモデル化し、導関数を計算するために補間剤を区別する。
  論文  参考訳（メタデータ） (2024-10-15T01:00:43Z)
• Improving the Weighting Strategy in KernelSHAP [0.8057006406834466]
  説明可能なAI(XAI)では、Shapley値が、複雑な機械学習モデルによる予測を説明する一般的なフレームワークである。 本稿では,結果のShapley値近似のばらつきを低減するために,決定論的重みを1つに置き換えるKernelSHAPの新たな改良を提案する。 提案手法は, 近似したShapley値と同じ精度を保ちながら, 必要なコントリビューション関数の評価を5%$から50%$に削減することができる。
  論文  参考訳（メタデータ） (2024-10-07T10:02:31Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  冗長な手法を排除し、単純で効率的なシェープリー推定器SimSHAPを提案する。 既存手法の解析において、推定器は特徴部分集合からランダムに要約された値の線形変換として統一可能であることを観察する。 実験により,SimSHAPの有効性が検証され,精度の高いShapley値の計算が大幅に高速化された。
  論文  参考訳（メタデータ） (2023-11-02T06:09:24Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。 カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。 我々は,効率的な後部推論と関数推定のための予測伝搬予測最大化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-10-09T03:55:09Z)
• Computing SHAP Efficiently Using Model Structure Information [3.6626323701161665]
  本稿では, SHAP を時間的あるいはより高速に計算する手法を提案し, 付加性とダミーの仮定を満たす SHAP の定義を提案する。 最初のケースでは、加算特性と低次機能成分からSHAPを計算する方法を示す。 第2のケースでは、時間内にSHAPを計算できる式を導出します。
  論文  参考訳（メタデータ） (2023-09-05T17:48:09Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  本稿では,低速な計算ノードに対して堅牢で,線形演算の近似計算と精度の両立が可能な分散コンピューティングフレームワークを提案する。 本稿では,復号化のための計算複雑性を低く保ちながら,実数値データを扱うための逐次復号アルゴリズムを提案する。 大規模行列乗算やブラックボックス最適化など,様々な文脈において,このフレームワークの潜在的な応用を実証する。
  論文  参考訳（メタデータ） (2023-09-01T18:02:04Z)
• Higher-order topological kernels via quantum computation [68.8204255655161]
  トポロジカルデータ分析(TDA)は、複雑なデータから意味のある洞察を抽出する強力なツールとして登場した。 本稿では,ベッチ曲線の次数増加に基づくBettiカーネルの量子的定義法を提案する。
  論文  参考訳（メタデータ） (2023-07-14T14:48:52Z)
• Monte Carlo Neural PDE Solver for Learning PDEs via Probabilistic Representation [59.45669299295436]
  教師なしニューラルソルバのトレーニングのためのモンテカルロPDEソルバを提案する。 我々は、マクロ現象をランダム粒子のアンサンブルとみなすPDEの確率的表現を用いる。 対流拡散, アレン・カーン, ナヴィエ・ストークス方程式に関する実験により, 精度と効率が著しく向上した。
  論文  参考訳（メタデータ） (2023-02-10T08:05:19Z)
• Improved Random Features for Dot Product Kernels [12.321353062415701]
  我々はドット製品カーネルのランダムな特徴近似の効率を改善するために、いくつかの新しい貢献をしている。 複雑な特徴の利用はこれらの近似のばらつきを著しく減少させることができることを実証的に示す。 一般のドット製品カーネルのランダムな特徴近似を改善するために,データ駆動型最適化手法を開発した。
  論文  参考訳（メタデータ） (2022-01-21T14:16:56Z)
• RKHS-SHAP: Shapley Values for Kernel Methods [17.52161019964009]
  本稿では,エフェクトインターベンショナル値とエフェクトオブザーショナルシェープ値の両方を効率的に計算できるカーネルマシンの属性法を提案する。 提案手法は局所的な摂動に対して頑健であることを示す。
  論文  参考訳（メタデータ） (2021-10-18T10:35:36Z)
• Fast Hierarchical Games for Image Explanations [78.16853337149871]
  本稿では,シェープリー係数の階層的拡張に基づく画像分類のモデル非依存な説明法を提案する。 他のShapleyベースの説明手法とは異なり、h-Shapはスケーラブルで近似を必要とせずに計算できる。 本手法は,合成データセット,医用画像シナリオ,一般コンピュータビジョン問題において,一般的なシャプリーベースおよび非サプリーベース手法と比較した。
  論文  参考訳（メタデータ） (2021-04-13T13:11:02Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  本稿では,2次フーリエ特徴に基づく導関数によるGP回帰のスケーリング手法を提案する。 我々は、近似されたカーネルと近似された後部の両方に適用される決定論的、非漸近的、指数関数的に高速な崩壊誤差境界を証明した。
  論文  参考訳（メタデータ） (2020-03-05T14:33:20Z)

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

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