論文の概要: PolySketchFormer: Fast Transformers via Sketches for Polynomial Kernels
- arxiv url: http://arxiv.org/abs/2310.01655v1
- Date: Mon, 2 Oct 2023 21:39:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-04 18:37:14.300902
- Title: PolySketchFormer: Fast Transformers via Sketches for Polynomial Kernels
- Title(参考訳): polysketchformer:多項式核のスケッチによる高速トランスフォーマー
- Authors: Praneeth Kacham, Vahab Mirrokni, Peilin Zhong
- Abstract要約: 準4次時間におけるソフトマックスアテンション機構の出力を近似する障壁を破る方法を示す。
本稿では,注目行列に因果マスクを適用し,コンテキスト長で時間線形にアテンション機構の出力を計算する,効率的なブロックベースアルゴリズムを提案する。
これらの観測は、証明可能な保証を持つ言語モデリングのための実用的な線形時間変換アーキテクチャであるemphPolyFormerの設計に役立ちます。
- 参考スコア(独自算出の注目度): 26.963201282082796
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quadratic complexity of attention in transformer architectures remains a
big bottleneck in scaling up large foundation models for long context. In fact,
recent theoretical results show the hardness of approximating the output of
softmax attention mechanism in sub-quadratic time assuming Strong Exponential
Time Hypothesis. In this paper, we show how to break this theoretical barrier
by replacing softmax with a polynomial function and polynomial sketching. In
particular we show that sketches for Polynomial Kernel from the randomized
numerical linear algebra literature can be used to approximate the polynomial
attention which leads to a significantly faster attention mechanism without
assuming any sparse structure for the attention matrix that has been done in
many previous works.
In addition, we propose an efficient block-based algorithm that lets us apply
the causal mask to the attention matrix without explicitly realizing the $n
\times n$ attention matrix and compute the output of the polynomial attention
mechanism in time linear in the context length. The block-based algorithm gives
significant speedups over the \emph{cumulative sum} algorithm used by Performer
to apply the causal mask to the attention matrix. These observations help us
design \emph{PolySketchFormer}, a practical linear-time transformer
architecture for language modeling with provable guarantees.
We validate our design empirically by training language models with long
context lengths. We first show that the eval perplexities of our models are
comparable to that of models trained with softmax attention. We then show that
for large context lengths our training times are significantly faster than
FlashAttention.
- Abstract(参考訳): トランスフォーマーアーキテクチャにおける注意の二次的複雑さは、長いコンテキストで大規模基礎モデルをスケールアップする上で、依然として大きなボトルネックとなっている。
実際、最近の理論結果は、強い指数時間仮説を仮定した亜四次時間におけるソフトマックス注意機構の出力を近似する難しさを示している。
本稿では,softmaxを多項式関数と多項式スケッチに置き換えることで,この理論上の障壁を破る方法について述べる。
特に、ランダム化された数値線形代数の文献からポリノミアル・カーネルのスケッチを用いて多項式の注意を近似し、それまで多くの研究で行われてきた注意行列のスパース構造を仮定することなく、より高速な注意機構を実現できることを示す。
さらに,n \times n$ attention matrixを明示的に認識することなく,注意行列に因果マスクを適用し,文脈長に線形な時間に多項式注意機構の出力を計算する効率的なブロックベースアルゴリズムを提案する。
ブロックベースのアルゴリズムは、Performer が注意行列に因果マスクを適用するために用いた \emph{cumulative sum} アルゴリズムを大幅に高速化する。
これらの観測は、証明可能な保証付き言語モデリングのための実用的な線形時間変換アーキテクチャである \emph{PolySketchFormer} の設計に役立つ。
長い文脈長を持つ言語モデルを訓練することで、経験的に設計を検証する。
まず、私たちのモデルのevalパープレクティビティは、ソフトマックスで訓練されたモデルと同等であることを示す。
そして、大きなコンテキストでは、トレーニング時間がフラッシュアテンションよりも大幅に速いことを示します。
関連論文リスト
- LOOPer: A Learned Automatic Code Optimizer For Polyhedral Compilers [1.7529897611426233]
ディープラーニングに基づくコストモデルを用いた,最初の多面体自動スケジューリングシステムである LOOPer を紹介する。
大規模なアフィン変換の探索をサポートし、多面体変換の複雑な配列を適用できる。
また、複数のループネストと長方形および非矩形反復領域を持つプログラムの最適化もサポートする。
論文 参考訳(メタデータ) (2024-03-18T07:22:31Z) - The Expressibility of Polynomial based Attention Scheme [8.517077915534932]
大規模言語モデル(LLM)は、私たちの日常生活の様々な側面を著しく改善しました。
変換器における注意の二次的複雑さは、長いテキストを処理するためにこれらのモデルをスケールアップする際の課題である。
本稿では,表現的注意力に関する理論的分析を行う。
論文 参考訳(メタデータ) (2023-10-30T22:16:18Z) - Decreasing the Computing Time of Bayesian Optimization using
Generalizable Memory Pruning [56.334116591082896]
本稿では,任意のサロゲートモデルと取得関数で使用可能なメモリプルーニングとバウンダリ最適化のラッパーを示す。
BOを高次元または大規模データセット上で実行することは、この時間の複雑さのために難解になる。
すべてのモデル実装はMIT Supercloudの最先端コンピューティングハードウェア上で実行される。
論文 参考訳(メタデータ) (2023-09-08T14:05:56Z) - KDEformer: Accelerating Transformers via Kernel Density Estimation [30.860357184928407]
本稿では,Dot-product attention mechanismの正確な計算方法を提案する。
提案手法は, 精度, メモリ, 実行時間において, 他の注目度よりも優れていることを示す。
T2T-ViTを用いた画像分類では,精度低下が0.5%以下であるのに対して,18時間以上のスピードアップを示す。
論文 参考訳(メタデータ) (2023-02-05T18:23:49Z) - Softmax-free Linear Transformers [90.83157268265654]
視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。
既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。
我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
論文 参考訳(メタデータ) (2022-07-05T03:08:27Z) - Sketching as a Tool for Understanding and Accelerating Self-attention
for Long Sequences [52.6022911513076]
トランスフォーマーベースのモデルは、自己アテンションモジュールの二次空間と時間的複雑さのために、長いシーケンスを処理するのに効率的ではない。
我々はLinformerとInformerを提案し、低次元投影と行選択により2次複雑性を線形(モジュラー対数因子)に還元する。
理論的解析に基づいて,Skeinformerを提案することにより,自己注意の促進と,自己注意への行列近似の精度の向上を図ることができる。
論文 参考訳(メタデータ) (2021-12-10T06:58:05Z) - SOFT: Softmax-free Transformer with Linear Complexity [112.9754491864247]
視覚変換器(ViT)は、パッチワイド画像トークン化と自己認識によって、様々な視覚認識タスクの最先端を推し進めている。
線形複雑度で自己注意を近似する様々な試みが自然言語処理で行われている。
これらの制限は、近似中にソフトマックスの自己注意を維持することに根ざしている。
ソフトマックスフリー変圧器(SOFT)を初めて提案する。
論文 参考訳(メタデータ) (2021-10-22T17:57:29Z) - Predicting Attention Sparsity in Transformers [0.9786690381850356]
本稿では, 遠心注意の空間パターンを計算前に同定するモデルであるスペーサーファインダーを提案する。
我々の研究は、予測された注目グラフの間隔とリコールの間のトレードオフを広範囲に分析することで、モデル効率を研究するための新しい角度を提供する。
論文 参考訳(メタデータ) (2021-09-24T20:51:21Z) - Stable, Fast and Accurate: Kernelized Attention with Relative Positional
Encoding [63.539333383965726]
相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。
相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
論文 参考訳(メタデータ) (2021-06-23T17:51:26Z) - A Reinforcement Learning Environment for Polyhedral Optimizations [68.8204255655161]
マルコフ決定過程(MDP)として多面体モデルにおける法的変換空間の形状に依存しない定式化を提案する。
変換を使う代わりに、定式化は可能なスケジュールの抽象空間に基づいている。
我々の総合的MDP定式化は、強化学習を用いて幅広いループで最適化ポリシーを学習することを可能にする。
論文 参考訳(メタデータ) (2021-04-28T12:41:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。