論文の概要: 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) が偽でない限り、自己着の時間複雑性は入力長において必ずしも二次的であることを証明する。 この議論は、注意の計算がほとんど、そして様々な注意のメカニズムのために行われる場合でも成り立つ。 下限を補うものとして, 多項式次数に指数依存するコストで, 有限テイラー級数を線形時間に使用すれば, ドット生成自己アテンションを近似することが可能であることを示した。

関連論文リスト

• Tensor Attention Training: Provably Efficient Learning of Higher-order Transformers [18.331374727331077]
  テンソルアテンションの時間的複雑さは、変圧器におけるその利用にとって重要な障害である。 注意訓練の後方勾配をほぼ線形時間で計算できることを実証する。
  論文  参考訳（メタデータ） (2024-05-26T02:59:13Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。 我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
  論文  参考訳（メタデータ） (2023-08-27T11:51:27Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• 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)
• Capturing Multi-Resolution Context by Dilated Self-Attention [58.69803243323346]
  限定的自己意識と拡張メカニズムの組み合わせを提案し,これを拡張的自己意識と呼ぶ。 制限された自己注意は、高分解能でクエリの隣接するフレームに注意を払い、拡張メカニズムは、より低い解像度でそれに出席できるように遠方の情報を要約します。 ASRの結果は、制限された自己アテンションのみと比較して大幅に改善され、計算コストのごく一部をフルシーケンスベースの自己アテンションと比較すると、同様の結果が得られる。
  論文  参考訳（メタデータ） (2021-04-07T02:04:18Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。