論文の概要: Learning to Understand: Identifying Interactions via the Möbius Transform
- arxiv url: http://arxiv.org/abs/2402.02631v2
- Date: Sat, 15 Jun 2024 20:22:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-19 06:35:20.376996
- Title: Learning to Understand: Identifying Interactions via the Möbius Transform
- Title（参考訳）: 理解への学習:メビウス変換による相互作用の同定
- Authors: Justin S. Kang, Yigit E. Erginbas, Landon Butler, Ramtin Pedarsani, Kannan Ramchandran,
- Abstract要約: 学習関数の解釈可能な表現を見つけるために、M"obius transform を用いる。
このアルゴリズムの頑健なバージョンはノイズに耐え、この複雑さを維持する。
いくつかの例では、M"obius変換によって生成される表現は元の関数に最大で2倍忠実である。
- 参考スコア（独自算出の注目度）: 18.987216240237483
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the key challenges in machine learning is to find interpretable representations of learned functions. The M\"obius transform is essential for this purpose, as its coefficients correspond to unique importance scores for sets of input variables. This transform is closely related to widely used game-theoretic notions of importance like the Shapley and Bhanzaf value, but it also captures crucial higher-order interactions. Although computing the obius Transform of a function with $n$ inputs involves $2^n$ coefficients, it becomes tractable when the function is sparse and of low-degree as we show is the case for many real-world functions. Under these conditions, the complexity of the transform computation is significantly reduced. When there are $K$ non-zero coefficients, our algorithm recovers the M\"obius transform in $O(Kn)$ samples and $O(Kn^2)$ time asymptotically under certain assumptions, the first non-adaptive algorithm to do so. We also uncover a surprising connection between group testing and the M\"obius transform. For functions where all interactions involve at most $t$ inputs, we use group testing results to compute the M\"obius transform with $O(Kt\log n)$ sample complexity and $O(K\mathrm{poly}(n))$ time. A robust version of this algorithm withstands noise and maintains this complexity. This marks the first $n$ sub-linear query complexity, noise-tolerant algorithm for the M\"obius transform. In several examples, we observe that representations generated via sparse M\"obius transform are up to twice as faithful to the original function, as compared to Shaply and Banzhaf values, while using the same number of terms.
- Abstract（参考訳）: 機械学習における重要な課題の1つは、学習した関数の解釈可能な表現を見つけることである。
M\"obius 変換はこの目的のために必須であり、その係数は入力変数の集合に対するユニークな重要なスコアに対応する。
この変換は、ShapleyやBhanzafの値のような、広く使われているゲーム理論の重要さの概念と密接に関連しているが、同時に重要な高次相互作用も捉えている。
入力が$n$の関数のオビウス変換の計算には2^n$の係数が伴うが、関数がスパースであり、実世界の多くの関数が示すように、低次関数のときのトラクタブルになる。
これらの条件下では、変換計算の複雑さが大幅に減少する。
非ゼロ係数が$K$である場合、我々のアルゴリズムはM\"obius transform in $O(Kn)$ sample and $O(Kn^2)$ time asymptotically under certain assumptions, the first non-adaptive algorithm to be recovering $O(Kn)$ sample and $O(Kn^2)$ time asymptotically。
また、グループテストとM\"obius変換の驚くべき関係も明らかにした。
すべての相互作用が少なくとも$t$入力を含む関数に対しては、M\"obius変換を$O(Kt\log n)$サンプル複雑性と$O(K\mathrm{poly}(n))$タイムで計算するためにグループテスト結果を使用する。
このアルゴリズムの頑健なバージョンはノイズに耐え、この複雑さを維持する。
これはM\"obius変換のサブ線形クエリ複雑性、耐雑音性アルゴリズムの最初の$n$である。
いくつかの例では、スパースM\"ビウス変換によって生成される表現は、同じ数の項を使用しながら、シャプリー値やバンジャフ値に比べて元の関数に最大2倍忠実である。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [16.046186753149]
最近のLarge Language Models(LLM)におけるトランスフォーマーの成功の鍵は自己認識メカニズムである
我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。
トランスフォーマーモデルにおけるアテンション計算を加速するための新しいパラダイムが、より長いコンテキストへのアプリケーションを支援することを願っています。
論文 参考訳（メタデータ） (2024-05-08T17:11:38Z) - Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳（メタデータ） (2024-02-20T10:11:03Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions [12.522202946750157]
長さ$n$シーケンスの$q$-ary関数に特化してスパースフーリエ変換アルゴリズムを開発する。
固定$q$の場合、$q$-SFTのロバストバージョンはサンプル複雑性が$O(Sn2)$であり、計算複雑性が$O(Sn3)$と同じ保証を持つことを示す。
論文 参考訳（メタデータ） (2023-01-15T22:04:53Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Understanding and Compressing Music with Maximal Transformable Patterns [0.0]
点集合の最大パターンを探索するアルゴリズム、$DinmathbbRk$を提案する。
また、これらの最大パターンのそれぞれに対して発生の集合を探索する第2のアルゴリズムを提案する。
民謡旋律を調律語族に分類する作業において,3種類の異なる複雑性のクラスで新しい圧縮アルゴリズムを評価する。
論文 参考訳（メタデータ） (2022-01-26T17:47:26Z) - $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity [3.4984289152418753]
我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。
我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
論文 参考訳（メタデータ） (2020-08-16T21:26:46Z) - $O(n)$ Connections are Expressive Enough: Universal Approximability of
Sparse Transformers [71.31712741938837]
注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。
また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
論文 参考訳（メタデータ） (2020-06-08T18:30:12Z) - Quantum Legendre-Fenchel Transform [6.643082745560234]
離散ルジャンドル・フェンシェル変換を計算する量子アルゴリズムを提案する。
量子アルゴリズムは多対数因子に最適であることを示す。
論文 参考訳（メタデータ） (2020-06-08T18:00:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。