論文の概要: How to Capture Higher-order Correlations? Generalizing Matrix Softmax
Attention to Kronecker Computation
- arxiv url: http://arxiv.org/abs/2310.04064v1
- Date: Fri, 6 Oct 2023 07:42:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-09 23:19:20.049414
- Title: How to Capture Higher-order Correlations? Generalizing Matrix Softmax
Attention to Kronecker Computation
- Title(参考訳): 高次相関を捉えるには?
Kronecker計算に対する行列ソフトマックスの一般化
- Authors: Josh Alman, Zhao Song
- Abstract要約: 本稿では,三重相関を捉える注意の一般化について検討する。
この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。
構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
- 参考スコア(独自算出の注目度): 12.853829771559916
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In the classical transformer attention scheme, we are given three $n \times
d$ size matrices $Q, K, V$ (the query, key, and value tokens), and the goal is
to compute a new $n \times d$ size matrix $D^{-1} \exp(QK^\top) V$ where $D =
\mathrm{diag}( \exp(QK^\top) {\bf 1}_n )$. In this work, we study a
generalization of attention which captures triple-wise correlations. This
generalization is able to solve problems about detecting triple-wise
connections that were shown to be impossible for transformers. The potential
downside of this generalization is that it appears as though computations are
even more difficult, since the straightforward algorithm requires cubic time in
$n$. However, we show that in the bounded-entry setting (which arises in
practice, and which is well-studied in both theory and practice), there is
actually a near-linear time algorithm. More precisely, we show that bounded
entries are both necessary and sufficient for quickly performing generalized
computations:
$\bullet$ On the positive side, if all entries of the input matrices are
bounded above by $o(\sqrt[3]{\log n})$ then we show how to approximate the
``tensor-type'' attention matrix in $n^{1+o(1)}$ time.
$\bullet$ On the negative side, we show that if the entries of the input
matrices may be as large as $\Omega(\sqrt[3]{\log n})$, then there is no
algorithm that runs faster than $n^{3-o(1)}$ (assuming the Strong Exponential
Time Hypothesis from fine-grained complexity theory).
We also show that our construction, algorithms, and lower bounds naturally
generalize to higher-order tensors and correlations. Interestingly, the higher
the order of the tensors, the lower the bound on the entries needs to be for an
efficient algorithm. Our results thus yield a natural tradeoff between the
boundedness of the entries, and order of the tensor one may use for more
expressive, efficient attention computation.
- Abstract(参考訳): 古典的なトランスフォーマティブ・アテンション・スキームでは、3つの$n \times d$ size matrices $q, k, v$ (the query, key, value tokens) が与えられ、新しい$n \times d$ size matrix $d^{-1} \exp(qk^\top) v$ where $d = \mathrm{diag}( \exp(qk^\top) {\bf 1}_n )$ を計算することが目的である。
本研究では,三重相関を捉える注意の一般化について検討する。
この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。
この一般化の潜在的な欠点は、単純なアルゴリズムが$n$で3次時間を必要とするため、計算がさらに難しいように見えることである。
しかし、有界エントリー設定(実際には発生し、理論と実践の両方でよく研究されている)では、実際にはほぼ線形時間アルゴリズムが存在することを示す。
より正確には、有界なエントリは、すぐに一般化された計算を実行するのに必要かつ十分であることを示す: $\bullet$ 正の側で、入力行列のすべてのエントリが上述の$o(\sqrt[3]{\log n})$ で有界であるなら、$n^{1+o(1)}$時間で ``tensor-type'' の注意行列を近似する方法を示す。
$\bullet$ 負の面において、入力行列のエントリが$\Omega(\sqrt[3]{\log n})$ であるなら、$n^{3-o(1)}$ より速く走るアルゴリズムは存在しない(きめ細かな複雑性理論による強い指数時間仮説を仮定する)。
また、我々の構成、アルゴリズム、下界が自然に高次テンソルや相関に一般化されることも示している。
興味深いことに、テンソルの順序が高ければ高いほど、エントリ上の境界がより効率的なアルゴリズムでなければならない。
この結果から, 成分の有界性, テンソルの次数との自然なトレードオフが得られ, より表現的かつ効率的な注意計算に利用できる。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Solving Dense Linear Systems Faster than via Preconditioning [15.781447266000159]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳(メタデータ) (2023-12-14T12:53:34Z) - Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products [9.661328973620531]
自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。
我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。
我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
論文 参考訳(メタデータ) (2023-11-03T14:56:24Z) - 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) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳(メタデータ) (2023-02-26T02:42:39Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳(メタデータ) (2022-11-10T00:40:37Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳(メタデータ) (2022-09-30T04:15:44Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - Approximate Multiplication of Sparse Matrices with Limited Space [27.875251633343666]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。
理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文 参考訳(メタデータ) (2020-09-08T05:39:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。