論文の概要: Learning to Understand: Identifying Interactions via the Mobius
Transform
- arxiv url: http://arxiv.org/abs/2402.02631v1
- Date: Sun, 4 Feb 2024 22:47:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-06 18:22:36.131199
- Title: Learning to Understand: Identifying Interactions via the Mobius
Transform
- Title（参考訳）: 理解への学習:Mobius変換によるインタラクションの特定
- Authors: Justin S. Kang, Yigit E. Erginbas, Landon Butler, Ramtin Pedarsani,
Kannan Ramchandran
- Abstract要約: 機械学習における最も基本的な問題の1つは、我々が学習した関数の解釈可能な表現を見つけることである。
Mobius変換は、その係数が入力変数の集合上のユニークな重要なスコアに対応するため、このために有用なツールである。
この研究は、非ゼロモダス係数の分数(したがって入力間の相互作用)が小さい(典型的)レジームに焦点をあてる。
- 参考スコア（独自算出の注目度）: 19.939343881656594
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the most fundamental problems in machine learning is finding
interpretable representations of the functions we learn. The Mobius transform
is a useful tool for this because its coefficients correspond to unique
importance scores on sets of input variables. The Mobius Transform is strongly
related (and in some cases equivalent) to the concept of Shapley value, which
is a widely used game-theoretic notion of importance. This work focuses on the
(typical) regime where the fraction of non-zero Mobius coefficients (and thus
interactions between inputs) is small compared to the set of all $2^n$ possible
interactions between $n$ inputs. When there are $K = O(2^{n \delta})$ with
$\delta \leq \frac{1}{3}$ non-zero coefficients chosen uniformly at random, our
algorithm exactly recovers the Mobius transform in $O(Kn)$ samples and
$O(Kn^2)$ time with vanishing error as $K \rightarrow \infty$, the first
non-adaptive algorithm to do so. We also uncover a surprising connection
between group testing and the Mobius transform. In the case where all
interactions are between at most $t = \Theta(n^{\alpha})$ inputs, for $\alpha <
0.409$, we are able to leverage results from group testing to provide the first
algorithm that computes the Mobius transform in $O(Kt\log n)$ sample complexity
and $O(K\mathrm{poly}(n))$ time with vanishing error as $K \rightarrow \infty$.
Finally, we present a robust version of this algorithm that achieves the same
sample and time complexity under some assumptions, but with a factor depending
on noise variance. Our work is deeply interdisciplinary, drawing from tools
spanning across signal processing, algebra, information theory, learning theory
and group testing to address this important problem at the forefront of machine
learning.
- Abstract（参考訳）: 機械学習における最も根本的な問題の1つは、我々が学習する関数の解釈可能な表現を見つけることである。
Mobius変換は、その係数が入力変数の集合上のユニークな重要なスコアに対応するため、このために有用なツールである。
Mobius Transform は、ゲーム理論における重要概念であるShapley value の概念と強く関連している(場合によっては同等である)。
この研究は、非零モビウス係数の分数(したがって入力間の相互作用)が、$n$入力間の2^n$ 可能なすべての相互作用の集合に比べて小さい(典型的な)レジームに焦点を当てている。
k = o(2^{n \delta})$ with $\delta \leq \frac{1}{3}$ non-zero 係数がランダムに選択されたとき、このアルゴリズムは、o(kn)$ のサンプルでモビウス変換を正確に回復し、o(kn^2)$ のエラーが消えると、k \rightarrow \infty$ となる。
また、グループテストとMobius変換の驚くべき関係も明らかにしました。
すべての相互作用が少なくとも$t = \Theta(n^{\alpha})$入力の間にある場合、$\alpha < 0.409$に対して、グループテストの結果を活用して、$O(Kt\log n)$サンプル複雑性と$O(K\mathrm{poly}(n))$エラーを消滅した時間を$K \rightarrow \infty$で計算する最初のアルゴリズムを提供する。
最後に、このアルゴリズムの頑健なバージョンを示し、いくつかの仮定の下で同じサンプルと時間複雑性を達成するが、ノイズ分散に依存する要因を持つ。
私たちの研究は、信号処理、代数、情報理論、学習理論、グループテストにまたがるツールから、機械学習の最前線でこの重要な問題に対処するために、深く学際的です。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。