論文の概要: NoPE: The Counting Power of Transformers with No Positional Encodings

• arxiv url: http://arxiv.org/abs/2505.11199v1
• Date: Fri, 16 May 2025 12:56:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-19 14:36:14.983837
• Title: NoPE: The Counting Power of Transformers with No Positional Encodings
• Title（参考訳）: NoPE: 位置エンコーディングのないトランスフォーマーのカウントパワー
• Authors: Chris Köcher, Alexander Kozachinskiy, Anthony Widjaja Lin, Marco Sälzer, Georg Zetzsche,
• Abstract要約: 特異なハードアテンション機構を持つNOPE変換器は、最近、正規言語のみを表現できることが示されている。 本論文は, 平均的ハードアテンション機構において, NoPE変換器は驚くほど表現力が高いことを示す。
• 参考スコア（独自算出の注目度）: 41.364418162255184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Positional Encodings (PEs) seem to be indispensable for ensuring expressiveness of transformers; without them attention transformers reduce to a bag-of-word model. NoPE-transformers (i.e. with No PEs) with unique hard attention mechanisms were very recently shown to only be able to express regular languages, i.e., with limited counting ability. This paper shows that, with average hard attention mechanisms, NoPE-transformers are still surprisingly expressive: they can express counting languages corresponding to nonnegative integer solutions to multivariate polynomial equations (i.e. Diophantine equations), reasoning about which is well-known to be undecidable. In fact, we provide a precise characterization of languages expressible by Average Hard Attention NoPE-Transformers (NoPE-AHATs): they correspond precisely to what we call \emph{semi-algebraic sets}, i.e., finite unions of sets of nonnegative integer solutions to systems of multivariate polynomial inequations. We obtain several interesting consequences of our characterization. Firstly, NoPE-transformers can express counting properties that are far more complex than established models like simplified counter machines and Petri nets, but cannot express a very simple counting property of PARITY. Secondly, the problem of analyzing NoPE-transformers is undecidable, e.g., whether a given NoPE transformer classifies all input strings in one class. To complement our results, we exhibit a counting language that is not expressible by average hard attention transformers even with arbitrary PEs but is expressible in the circuit complexity class TC$^0$, answering an open problem.
• Abstract（参考訳）: ポジショナルエンコーディング(PE)はトランスフォーマーの表現性を確保するために欠かせないように思われるが、注意を払わないトランスフォーマーはバッグ・オブ・ワードモデルに還元される。 NoPE変換器 (No PEs) と固有のハードアテンション機構は、ごく最近になって正規言語、すなわち限定的なカウント能力でしか表現できないことが示されている。 この論文は、平均的なハードアテンション機構により、NoPE変換子は驚くほど表現力が高く、多変量多項式方程式(すなわち、ディオファント方程式)に対する非負の整数解に対応する数え上げ言語を表現でき、どれが決定不能であることがよく知られているのかを推論する。 実際、平均ハードアテンション NoPE-Transformers (NoPE-AHATs) で表現可能な言語の正確な特徴付けを提供する:それらは正確には、我々が 'emph{semi-algebraic set}' と呼ぶもの、すなわち、多変数多項式不等式系に対する非負の整数解の集合の有限和に対応する。 特徴付けの興味深い結果がいくつか得られます。 第一に、NoPE変換器は単純なカウンタマシンやペトリネットのような確立されたモデルよりもはるかに複雑なカウント特性を表現できるが、PARITYの非常に単純なカウント特性を表現できない。 第二に、与えられたNoPE変換器が1つのクラスで全ての入力文字列を分類するかどうかなど、NoPE変換器を解析する問題は決定不可能である。 その結果を補完するために、任意のPEであっても平均的なハードアテンション変換器では表現できないが、回路複雑性クラスTC$^0$で表現可能なカウント言語を示す。

関連論文リスト

• Extracting Finite State Machines from Transformers [0.3069335774032178]
  機械的解釈可能性の観点から正規言語で訓練された変圧器の訓練可能性について検討する。 有限個の記号が状態を決定するとき, 変圧器の訓練性に対して, より強い下界を経験的に見出す。 機械的な洞察により、1層トランスフォーマーが優れた長さの一般化で学習できる正規言語を特徴付けることができる。
  論文  参考訳（メタデータ） (2024-10-08T13:43:50Z)
• Length Generalization of Causal Transformers without Position Encoding [59.802708262402824]
  より長い文への一般化は、最近のTransformerベースの言語モデルにとって重要である。 位置符号化を伴わない変圧器長一般化特性について検討する。 NoPEは、一般的に使われる明示的な位置エンコーディングよりも長いシーケンスに拡張できるが、コンテキスト長が制限されている。
  論文  参考訳（メタデータ） (2024-04-18T14:38:32Z)
• The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
  実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。 答えはYESであるが、増加量は中間生成量に大きく依存する。 また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
  論文  参考訳（メタデータ） (2023-10-11T22:35:18Z)
• The Impact of Positional Encoding on Length Generalization in Transformers [50.48278691801413]
  復号器のみの変圧器長一般化性能と5つの異なる位置符号化手法との比較を行った。 その結果,ALiBi,Rotary,APEなどの位置符号化法は,下流タスクにおける長さ一般化には適していないことがわかった。
  論文  参考訳（メタデータ） (2023-05-31T00:29:55Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  連続列列列関数を近似できるかどうかに関して, RPE ベースの変換器のパワーを数学的に解析する。 RPEをベースとしたトランスフォーマーでは,ニューラルネットワークの深さや幅がどんなに深くても近似できない連続列列列列関数が存在することを示す。 我々は,その条件を満たす,Universal RPE-based (URPE) Attentionと呼ばれる新しいアテンションモジュールを開発する。
  論文  参考訳（メタデータ） (2022-05-26T14:51:30Z)
• CoPE: Conditional image generation using Polynomial Expansions [50.67390290190874]
  入力変数を2つ拡張し,それらの自己相関と相互相関をキャプチャする,copeと呼ばれる汎用フレームワークを導入する。 CoPEは8つのデータセットを含む5つのタスク(クラスジェネレーション、逆問題、エッジ・ツー・イメージ翻訳、イメージ・ツー・イメージ翻訳、属性誘導生成)で評価される。 徹底的な評価は、CoPEが多様な条件生成タスクに取り組むのに役立つことを示唆している。
  論文  参考訳（メタデータ） (2021-04-11T19:02:37Z)

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

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