論文の概要: A Fast Optimization View: Reformulating Single Layer Attention in LLM
Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time
- arxiv url: http://arxiv.org/abs/2309.07418v1
- Date: Thu, 14 Sep 2023 04:23:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-15 16:21:45.508192
- Title: A Fast Optimization View: Reformulating Single Layer Attention in LLM
Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time
- Title(参考訳): 高速最適化視点:テンソルとSVMトリップに基づくLLMにおける単一層アテンションの修正と行列乗算時間での解法
- Authors: Yeqi Gao, Zhao Song, Weixin Wang, Junze Yin
- Abstract要約: 我々は、一層注意ネットワーク目的関数 $L(X,Y) の証明可能な保証を提供することに注力する。
多層LCMネットワークでは、mathbbRn×d2$の行列$Bを層の出力と見なすことができる。
損失関数をトレーニングする反復アルゴリズムを$L(X,Y)$ up $epsilon$で、$widetildeO( (cal T_mathrmmat(n,d) + dで実行される。
- 参考スコア(独自算出の注目度): 7.613259578185218
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Large language models (LLMs) have played a pivotal role in revolutionizing
various facets of our daily existence. Solving attention regression is a
fundamental task in optimizing LLMs. In this work, we focus on giving a
provable guarantee for the one-layer attention network objective function
$L(X,Y) = \sum_{j_0 = 1}^n \sum_{i_0 = 1}^d ( \langle \langle \exp(
\mathsf{A}_{j_0} x ) , {\bf 1}_n \rangle^{-1} \exp( \mathsf{A}_{j_0} x ), A_{3}
Y_{*,i_0} \rangle - b_{j_0,i_0} )^2$. Here $\mathsf{A} \in \mathbb{R}^{n^2
\times d^2}$ is Kronecker product between $A_1 \in \mathbb{R}^{n \times d}$ and
$A_2 \in \mathbb{R}^{n \times d}$. $A_3$ is a matrix in $\mathbb{R}^{n \times
d}$, $\mathsf{A}_{j_0} \in \mathbb{R}^{n \times d^2}$ is the $j_0$-th block of
$\mathsf{A}$. The $X, Y \in \mathbb{R}^{d \times d}$ are variables we want to
learn. $B \in \mathbb{R}^{n \times d}$ and $b_{j_0,i_0} \in \mathbb{R}$ is one
entry at $j_0$-th row and $i_0$-th column of $B$, $Y_{*,i_0} \in \mathbb{R}^d$
is the $i_0$-column vector of $Y$, and $x \in \mathbb{R}^{d^2}$ is the
vectorization of $X$.
In a multi-layer LLM network, the matrix $B \in \mathbb{R}^{n \times d}$ can
be viewed as the output of a layer, and $A_1= A_2 = A_3 \in \mathbb{R}^{n
\times d}$ can be viewed as the input of a layer. The matrix version of $x$ can
be viewed as $QK^\top$ and $Y$ can be viewed as $V$. We provide an iterative
greedy algorithm to train loss function $L(X,Y)$ up $\epsilon$ that runs in
$\widetilde{O}( ({\cal T}_{\mathrm{mat}}(n,n,d) + {\cal
T}_{\mathrm{mat}}(n,d,d) + d^{2\omega}) \log(1/\epsilon) )$ time. Here ${\cal
T}_{\mathrm{mat}}(a,b,c)$ denotes the time of multiplying $a \times b$ matrix
another $b \times c$ matrix, and $\omega\approx 2.37$ denotes the exponent of
matrix multiplication.
- Abstract(参考訳): 大規模言語モデル(LLM)は、我々の日常生活における様々な側面に革命をもたらす重要な役割を担っている。
注意の回帰を解くことはLLMを最適化する基本的な課題である。
本研究では、一層アテンションネットワーク対象関数 $L(X,Y) = \sum_{j_0 = 1}^n \sum_{i_0 = 1}^d ( \langle \langle \exp( \mathsf{A}_{j_0} x ) , {\bf 1}_n \rangle^{-1} \exp( \mathsf{A}_{j_0} x ), A_{3} Y_{*,i_0} \rangle - b_{j_0,i_0} )^2$ に対して証明可能な保証を与えることに焦点を当てる。
ここで、$\mathsf{A} \in \mathbb{R}^{n^2 \times d^2}$は、$A_1 \in \mathbb{R}^{n \times d}$と$A_2 \in \mathbb{R}^{n \times d}$の間のクロネッカー積である。
A_3$ は $\mathbb{R}^{n \times d}$, $\mathsf{A}_{j_0} \in \mathbb{R}^{n \times d^2}$ の行列は $\mathsf{A}$ の$j_0$-番目のブロックである。
X, Y \in \mathbb{R}^{d \times d}$は私たちが学びたい変数である。
$B \in \mathbb{R}^{n \times d}$と$b_{j_0,i_0} \in \mathbb{R}$は$j_0$-th rowと$i_0$-th column of $B$, $Y_{*,i_0} \in \mathbb{R}^d$は$Y$の$i_0$-column vectorであり、$x \in \mathbb{R}^{d^2}$は$X$のベクトル化である。
多層llmネットワークでは、行列 $b \in \mathbb{r}^{n \times d}$ は層の出力と見なすことができ、$a_1= a_2 = a_3 \in \mathbb{r}^{n \times d}$ は層の入力と見なすことができる。
x$の行列版は$QK^\top$と見ることができ、$Y$は$V$と見ることができる。
損失関数 $l(x,y)$ up $\epsilon$ を訓練するための反復的グリーディアルゴリズムを提供し、$\widetilde{o}( ({\cal t}_{\mathrm{mat}}(n,n,d) + {\cal t}_{\mathrm{mat}}(n,d,d) + d^{2\omega}) \log(1/\epsilon)$ time で実行する。
ここで、${\cal T}_{\mathrm{mat}}(a,b,c)$ は $a \times b$ matrix と $b \times c$ matrix を乗算する時間を表し、$\omega\approx 2.37$ は行列乗算の指数を表す。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳(メタデータ) (2023-10-02T16:44:47Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳(メタデータ) (2023-04-10T05:52:38Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳(メタデータ) (2023-02-26T02:42:39Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳(メタデータ) (2023-02-01T05:22:40Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳(メタデータ) (2021-09-06T14:21: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) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。
これは高速多重極法について証明された最初の公式な制限である。
論文 参考訳(メタデータ) (2020-11-04T18:35:02Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳(メタデータ) (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。