論文の概要: TT-FSI: Scalable Faithful Shapley Interactions via Tensor-Train

• arxiv url: http://arxiv.org/abs/2601.01903v1
• Date: Mon, 05 Jan 2026 08:49:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:22.870506
• Title: TT-FSI: Scalable Faithful Shapley Interactions via Tensor-Train
• Title（参考訳）: TT-FSI:テンソル・トレインによるスケーラブルな忠実なシャプリー相互作用
• Authors: Ungsik Kim, Suwon Lee,
• Abstract要約: 本稿では Matrix Product Operators (MPO) を介してFSI(Fithful Shapley Interaction)指標を利用するTT-FSIを提案する。 6つのデータセットの実験では、ベースラインを280$times$スピードアップし、SHAP-IQを85$times、メモリを290$times$ダウンする。 TT-FSIは、競合するすべてのメソッドが失敗する、$d(100万の連立)までスケールする。
• 参考スコア（独自算出の注目度）: 1.0742675209112622
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Faithful Shapley Interaction (FSI) index uniquely satisfies the faithfulness axiom among Shapley interaction indices, but computing FSI requires $O(d^\ell \cdot 2^d)$ time and existing implementations use $O(4^d)$ memory. We present TT-FSI, which exploits FSI's algebraic structure via Matrix Product Operators (MPO). Our main theoretical contribution is proving that the linear operator $v \mapsto \text{FSI}(v)$ admits an MPO representation with TT-rank $O(\ell d)$, enabling an efficient sweep algorithm with $O(\ell^2 d^3 \cdot 2^d)$ time and $O(\ell d^2)$ core storage an exponential improvement over existing methods. Experiments on six datasets ($d=8$ to $d=20$) demonstrate up to 280$\times$ speedup over baseline, 85$\times$ over SHAP-IQ, and 290$\times$ memory reduction. TT-FSI scales to $d=20$ (1M coalitions) where all competing methods fail.
• Abstract（参考訳）: Faithful Shapley Interaction (FSI) インデックスは、Shapley 相互作用指標の忠実性公理を一意に満足するが、計算用 FSI は $O(d^\ell \cdot 2^d)$時間を必要とし、既存の実装では $O(4^d)$メモリを使用する。 本稿では Matrix Product Operators (MPO) を介して FSI の代数構造を利用する TT-FSI を提案する。 線形作用素 $v \mapsto \text{FSI}(v)$ が TT-rank $O(\ell d)$ で MPO 表現を認め、$O(\ell^2 d^3 \cdot 2^d)$ time と $O(\ell d^2)$コアストレージが既存のメソッドよりも指数関数的に改善されていることを証明している。 6つのデータセット($d=8$から$d=20$)の実験では、280$\times$ベースライン上のスピードアップ、85$\times$ over SHAP-IQ、290$\times$メモリリダクションが示されている。 TT-FSIは、競合するすべてのメソッドが失敗する$d=20$(1百万の連立)までスケールする。

関連論文リスト

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• SGD with memory: fundamental properties and stochastic acceleration [15.25021403154845]
  非確率設定では、損失収束$L_tsim C_Lt-xiの最適指数$xi$は、平滑なGDの倍である。 メモリ1のアルゴリズムでは、安定性を維持しながら、任意に$C_L$を小さくすることができる。
  論文  参考訳（メタデータ） (2024-10-05T16:57:40Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Compressed Deep Networks: Goodbye SVD, Hello Robust Low-Rank Approximation [23.06440095688755]
  ニューラルネットワークを圧縮する一般的な手法は、完全に接続された層(または埋め込み層)に対応する行列$AinmathbbRntimes d$の$k$-rank $ell$近似$A_k,2$を計算することである。 ここで$d$は層内のニューロンの数、$n$は次のニューロンの数、$A_k,2$は$O(n+d)k)$メモリに格納できる。 これ
  論文  参考訳（メタデータ） (2020-09-11T20:21:42Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications [28.54236118020831]
  本稿では,最適な$O(n log (kappa))$オアラーク評価を用いた新しい切削平面アルゴリズムを提案する。 また、評価毎に$n2$の時間を改善できないため、実行時間が最適であることを示す。
  論文  参考訳（メタデータ） (2020-04-08T20:56:40Z)

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

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