論文の概要: 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パープレクティビティは、ソフトマックスで訓練されたモデルと同等であることを示す。
そして、大きなコンテキストでは、トレーニング時間がフラッシュアテンションよりも大幅に速いことを示します。
関連論文リスト
- Learning Linear Attention in Polynomial Time [115.68795790532289]
線形注意を持つ単層変圧器の学習性に関する最初の結果を提供する。
線形アテンションは RKHS で適切に定義された線形予測器とみなすことができる。
我々は,すべての経験的リスクが線形変換器と同等のトレーニングデータセットを効率的に識別する方法を示す。
論文 参考訳（メタデータ） (2024-10-14T02:41:01Z) - Power-Softmax: Towards Secure LLM Inference over Encrypted Data [2.4576879793338913]
ホモモルフィック暗号化(HE)は暗号化形式を持つために暗号手法を必要とする。
以前のアプローチでは、10倍を超える大きな度合いを持つ事前訓練されたモデルを直接近似していた。
トレーニングのための安定なフォームを提供し、トレーニングと近似し易い、新しいタイプの自己意図(self-attention)を提案する。
論文 参考訳（メタデータ） (2024-10-12T09:32:42Z) - Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time [17.086679273053853]
本研究では,新しい高速近似法により,ほぼ線形時間で勾配を計算することができることを示す。
勾配の効率を改善することで、この作業がより効果的なトレーニングと長期コンテキスト言語モデルのデプロイを促進することを期待する。
論文 参考訳（メタデータ） (2024-08-23T17:16:43Z) - Lean Attention: Hardware-Aware Scalable Attention Mechanism for the Decode-Phase of Transformers [4.674454841332859]
トランスフォーマーベースのモデルは、自然言語処理の最も広く使われているアーキテクチャの1つとして登場した。
これらの巨大なモデルはメモリが空腹で、最先端のAIアクセラレータでも大きな推論レイテンシが生じる。
本稿ではトークン生成フェーズの自己認識をスケーラブルに計算する手法であるLeanAttentionを提案する。
論文 参考訳（メタデータ） (2024-05-17T00:52:39Z) - Decreasing the Computing Time of Bayesian Optimization using
Generalizable Memory Pruning [56.334116591082896]
本稿では,任意のサロゲートモデルと取得関数で使用可能なメモリプルーニングとバウンダリ最適化のラッパーを示す。
BOを高次元または大規模データセット上で実行することは、この時間の複雑さのために難解になる。
すべてのモデル実装はMIT Supercloudの最先端コンピューティングハードウェア上で実行される。
論文 参考訳（メタデータ） (2023-09-08T14:05:56Z) - 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) - A Reinforcement Learning Environment for Polyhedral Optimizations [68.8204255655161]
マルコフ決定過程(MDP)として多面体モデルにおける法的変換空間の形状に依存しない定式化を提案する。
変換を使う代わりに、定式化は可能なスケジュールの抽象空間に基づいている。
我々の総合的MDP定式化は、強化学習を用いて幅広いループで最適化ポリシーを学習することを可能にする。
論文 参考訳（メタデータ） (2021-04-28T12:41:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。