Fugu-MT 論文翻訳(概要): Transformers in Uniform TC$^0$

論文の概要: Transformers in Uniform TC$^0$

arxiv url: http://arxiv.org/abs/2409.13629v1
Date: Fri, 20 Sep 2024 16:38:05 GMT
ステータス: 処理完了
システム内更新日: 2024-11-07 06:08:43.920413
Title: Transformers in Uniform TC$^0$
Title（参考訳）: 一様TC$^0$の変換器
Authors: David Chiang,
Abstract要約: AHAT と SMAT によって認識される言語は、回路複雑性クラス TC$0$ に含まれることを示す。近似のないAHAT,O(poly(n))ビットの浮動小数点精度を持つSMAT,および少なくとも2-O(poly(n))$の絶対誤差を持つSMATは、すべてDLOGTIME-uniform TC$0$であることを示す。
参考スコア（独自算出の注目度）: 10.524504523959767
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Previous work has shown that the languages recognized by average-hard attention transformers (AHATs) and softmax-attention transformers (SMATs) are within the circuit complexity class TC$^0$. However, these results assume limited-precision arithmetic: using floating-point numbers with O(log n) bits (where n is the length of the input string), Strobl showed that AHATs can be approximated in L-uniform TC$^0$, and Merrill and Sabharwal showed that SMATs can be approximated in DLOGTIME-uniform TC$^0$. Here, we improve these results, showing that AHATs with no approximation, SMATs with O(poly(n)) bits of floating-point precision, and SMATs with at most $2^{-O(poly(n))}$ absolute error are all in DLOGTIME-uniform TC$^0$.
Abstract（参考訳）: これまで、平均的注意変換器(AHAT)とSMAT(Softmax-attention transformer)によって認識された言語は、回路複雑性クラスTC$^0$に含まれていた。 Strobl は AHAT が L-ユニフォーム TC$0$ で近似できることを示し、Merrill と Sabharwal は SMAT が DLOGTIME-ユニフォーム TC$0$ で近似できることを示した。ここでは、近似のないAHAT、浮動小数点精度のO(poly(n))ビットのSMAT、最大2$^{-O(poly(n))のSMAT、絶対誤差がすべてDLOGTIME-uniform TC$^0$であることを示す。

関連論文リスト

MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文参考訳（メタデータ） (2024-05-29T18:36:59Z)
Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文参考訳（メタデータ） (2024-02-20T10:11:03Z)
Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
論文参考訳（メタデータ） (2024-02-06T18:59:30Z)
TCNCA: Temporal Convolution Network with Chunked Attention for Scalable Sequence Processing [52.64837396100988]
MEGAは最近のトランスフォーマーベースのアーキテクチャで、線形リカレント演算子を使用し、並列計算はFFTに基づいて、$O(LlogL)$で、$L$はシーケンス長である。線形再帰を特別な時間的畳み込みネットワークに置き換えることで、より浅いネットワークでより大きい受容場を許容し、計算複雑性を$O(L)$に減らし、それらのアプローチを構築する。我々は,EnWik8言語モデリングにおけるTCNCA,LRA(Long-range-arena)シーケンス分類,および合成推論ベンチマーク連想リコールの評価を行った。
論文参考訳（メタデータ） (2023-12-09T16:12:25Z)
Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits [0.0]
平均的注意力変換器はクラスTC0に該当する言語を認識する。本稿は、第1結果を拡張して均一回路を生成可能であることを示す。
論文参考訳（メタデータ） (2023-08-06T21:23:22Z)
Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文参考訳（メタデータ） (2022-12-01T15:57:58Z)
Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
論文参考訳（メタデータ） (2022-05-16T02:24:52Z)
Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文参考訳（メタデータ） (2020-06-21T06:57:59Z)
$O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
論文参考訳（メタデータ） (2020-06-08T18:30:12Z)

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