論文の概要: On The Computational Complexity of Self-Attention
- arxiv url: http://arxiv.org/abs/2209.04881v1
- Date: Sun, 11 Sep 2022 14:38:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-13 14:08:03.184204
- Title: On The Computational Complexity of Self-Attention
- Title(参考訳): 自己着脱の計算複雑性について
- Authors: Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, Chinmay Hegde
- Abstract要約: 現代の変圧器は、時間と空間の複雑さが入力の長さの2乗である自己認識機構に依存している。
我々は、強い指数時間仮説(SETH)が偽でない限り、自己注意の時間複雑性は入力長において必然的に二次的であることを証明した。
下界を補うものとして、有限テイラー級数を用いて線型時間でドット積自己アテンションを近似することは実際に可能であることを示す。
- 参考スコア(独自算出の注目度): 22.3395465641384
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Transformer architectures have led to remarkable progress in many
state-of-art applications. However, despite their successes, modern
transformers rely on the self-attention mechanism, whose time- and
space-complexity is quadratic in the length of the input. Several approaches
have been proposed to speed up self-attention mechanisms to achieve
sub-quadratic running time; however, the large majority of these works are not
accompanied by rigorous error guarantees. In this work, we establish lower
bounds on the computational complexity of self-attention in a number of
scenarios. We prove that the time complexity of self-attention is necessarily
quadratic in the input length, unless the Strong Exponential Time Hypothesis
(SETH) is false. This argument holds even if the attention computation is
performed only approximately, and for a variety of attention mechanisms. As a
complement to our lower bounds, we show that it is indeed possible to
approximate dot-product self-attention using finite Taylor series in
linear-time, at the cost of having an exponential dependence on the polynomial
order.
- Abstract(参考訳): トランスフォーマーアーキテクチャは多くの最先端のアプリケーションで著しく進歩した。
しかし、現代の変圧器は成功にもかかわらず、時間と空間の複雑さが入力の長さの2乗である自己認識機構に依存している。
サブクワッドラティックランニングタイムを実現するための自己注意機構を高速化するいくつかの手法が提案されているが、これらの研究の大部分は厳密なエラー保証を伴わない。
本研究では,複数のシナリオにおいて自己注意の計算複雑性の低い境界を確立する。
我々は、強指数時間仮説 (seth) が偽でない限り、自己着の時間複雑性は入力長において必ずしも二次的であることを証明する。
この議論は、注意の計算がほとんど、そして様々な注意のメカニズムのために行われる場合でも成り立つ。
下限を補うものとして, 多項式次数に指数依存するコストで, 有限テイラー級数を線形時間に使用すれば, ドット生成自己アテンションを近似することが可能であることを示した。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。
我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
論文 参考訳(メタデータ) (2023-08-27T11:51:27Z) - Time-dependent Hamiltonian Simulation Using Discrete Clock Constructions [63.18141027763459]
正規作用素指数を用いて順序演算子指数を近似する新しい手法を提案する。
クロックに使用される量子ビットの数が増加するにつれて、順序演算子の指数関数誤差は消えることを示す。
応用として、時間依存ハミルトニアンに対する新しい多積式(MPF)を提供する。
論文 参考訳(メタデータ) (2022-03-21T21:29:22Z) - Fragmented imaginary-time evolution for early-stage quantum signal
processors [0.0]
QITE(Quantum imaginary-time Evolution)のシミュレーションは、量子計算の大きな可能性である。
我々の主な貢献は、新しい世代の決定論的高精度QITEアルゴリズムである。
複雑化に優れたQITE回路サブルーチンを2つ提案する。
論文 参考訳(メタデータ) (2021-10-25T18:02:24Z) - SOFT: Softmax-free Transformer with Linear Complexity [112.9754491864247]
視覚変換器(ViT)は、パッチワイド画像トークン化と自己認識によって、様々な視覚認識タスクの最先端を推し進めている。
線形複雑度で自己注意を近似する様々な試みが自然言語処理で行われている。
これらの制限は、近似中にソフトマックスの自己注意を維持することに根ざしている。
ソフトマックスフリー変圧器(SOFT)を初めて提案する。
論文 参考訳(メタデータ) (2021-10-22T17:57:29Z) - Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
計算の複雑さを低く保ちつつ、各注目ヘッドにフルアテンション機能を提供するコンバインダを提案する。
既存のスパース変圧器で使用されるスパースアテンションパターンのほとんどは、そのような分解設計をフルアテンションに刺激することができることを示す。
自己回帰的タスクと双方向シーケンスタスクの両方に関する実験的評価は、このアプローチの有効性を示す。
論文 参考訳(メタデータ) (2021-07-12T22:43:11Z) - Autoformer: Decomposition Transformers with Auto-Correlation for
Long-Term Series Forecasting [68.86835407617778]
Autoformerは、Auto-Correlation機構を備えた、新しい分解アーキテクチャである。
長期的な予測では、Autoformerは6つのベンチマークで相対的に改善され、最先端の精度が得られる。
論文 参考訳(メタデータ) (2021-06-24T13:43:43Z) - Model Checking Quantum Continuous-Time Markov Chains [11.182363315152399]
我々は量子連続時間マルコフ連鎖(QCTMC)のモデルチェックを初期化した。
リアルタイムシステムとして、信号時間論理(STL)によりQCTMC上の時間特性を規定する。
論文 参考訳(メタデータ) (2021-05-02T02:46:19Z) - Revisiting Linformer with a modified self-attention with linear
complexity [0.0]
時間・空間の線形複雑性を考慮した自己保持の代替法を提案する。
この方法は長いシーケンスで機能するので、音声だけでなく画像にも使用できる。
論文 参考訳(メタデータ) (2020-12-16T13:23:29Z) - Open quantum systems beyond Fermi's golden rule: Diagrammatic expansion
of the steady-state time-convolutionless master equation [0.0]
我々は,スーパー演算子ではなく演算子に基づく定常TCL生成器を評価するための図式的手法を開発した。
我々は,Fermi貯水池に結合した1つの非相互作用レベルにおいて本手法をベンチマークし,次から次への正確な拡張を復元する。
論文 参考訳(メタデータ) (2020-10-19T20:27:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。