論文の概要: 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$で表現可能なカウント言語を示す。

関連論文リスト

• On the Expressive Power of Floating-Point Transformers [12.42591017155152]
  浮動小数点パラメータと浮動小数点演算を用いた浮動小数点変換器の表現可能性について検討する。 浮動小数点変換器は位置符号化なしでも非置換同変関数のクラスを表現することができることを示す。
  論文  参考訳（メタデータ） (2026-01-23T05:03:00Z)
• Probability Distributions Computed by Hard-Attention Transformers [53.17368795629463]
  変換言語認識器の自己回帰化は,時として表現性を高める可能性があることを示す。 私たちの全体的な貢献は、トランスフォーマーが表現できる関数を、言語モデルとして最も一般的なユースケースで分解することにあります。
  論文  参考訳（メタデータ） (2025-10-31T02:41:05Z)
• Transformers are Inherently Succinct [46.836122954309566]
  変換器は形式言語の標準表現よりもかなり簡潔に形式言語を表現できることを証明している。 この表現性の副産物として, 変圧器のバリデーション特性が確実に抽出可能であることを示す。
  論文  参考訳（メタデータ） (2025-10-22T07:25:54Z)
• PaTH Attention: Position Encoding via Accumulating Householder Transformations [56.32365080761523]
  PaTHは、ハウステリア変換の累積積に基づいて、フレキシブルなデータ依存位置符号化方式である。 家庭用行列の積をコンパクトに表現することで,効率的な並列学習アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2025-05-22T08:36:09Z)
• Concise One-Layer Transformers Can Do Function Evaluation (Sometimes) [1.157192696857674]
  本稿では,変圧器の表現能力に関する研究に寄与する。 任意の関数を与えられた引数で$[n]$から$[n]$に評価する基本的な計算タスクを実行する能力に焦点を当てる。
  論文  参考訳（メタデータ） (2025-03-28T01:40:23Z)
• Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size [6.9060054915724]
  トランスフォーマー(Transformer)は、様々な領域で顕著なパフォーマンスを示すニューラルネットワークの一種である。 本研究では,変圧器の柱対称近似能力について検討した。
  論文  参考訳（メタデータ） (2025-02-17T05:56:11Z)
• Extracting Finite State Machines from Transformers [0.3069335774032178]
  機械的解釈可能性の観点から正規言語で訓練された変圧器の訓練可能性について検討する。 有限個の記号が状態を決定するとき, 変圧器の訓練性に対して, より強い下界を経験的に見出す。 機械的な洞察により、1層トランスフォーマーが優れた長さの一般化で学習できる正規言語を特徴付けることができる。
  論文  参考訳（メタデータ） (2024-10-08T13:43:50Z)
• Transformers are Efficient Compilers, Provably [11.459397066286822]
  トランスフォーマーベースの大規模言語モデル(LLM)は、幅広い言語関連タスクにおいて驚くほど堅牢なパフォーマンスを示している。 本稿では,表現力の観点から,トランスフォーマーをコンパイラとして用いることの正式な調査に向けて第一歩を踏み出す。 代表言語であるMini-Huskyを導入し、現代のC言語の特徴をカプセル化する。
  論文  参考訳（メタデータ） (2024-10-07T20:31:13Z)
• 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)
• Attention Is Not All You Need Anymore [3.9693969407364427]
  本稿では,トランスフォーマーの自己保持機構に対するドロップイン置換のファミリを提案する。 実験結果から,自己保持機構をSHEに置き換えることによってトランスフォーマーの性能が向上することが示唆された。 提案されたエクストラクターは、自己保持機構よりも速く走ることができる。
  論文  参考訳（メタデータ） (2023-08-15T09:24:38Z)
• The Impact of Positional Encoding on Length Generalization in Transformers [50.48278691801413]
  復号器のみの変圧器長一般化性能と5つの異なる位置符号化手法との比較を行った。 その結果,ALiBi,Rotary,APEなどの位置符号化法は,下流タスクにおける長さ一般化には適していないことがわかった。
  論文  参考訳（メタデータ） (2023-05-31T00:29:55Z)
• Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input [50.83356836818667]
  無限次元入力を持つシーケンス・ツー・シーケンス関数として変換器の近似と推定能力について検討する。 我々の理論的結果は、高次元データに対する変換器の実用的成功を支持する。
  論文  参考訳（メタデータ） (2023-05-30T02:44:49Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  連続列列列関数を近似できるかどうかに関して, RPE ベースの変換器のパワーを数学的に解析する。 RPEをベースとしたトランスフォーマーでは,ニューラルネットワークの深さや幅がどんなに深くても近似できない連続列列列列関数が存在することを示す。 我々は,その条件を満たす,Universal RPE-based (URPE) Attentionと呼ばれる新しいアテンションモジュールを開発する。
  論文  参考訳（メタデータ） (2022-05-26T14:51:30Z)
• On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
  飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。 硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
  論文  参考訳（メタデータ） (2021-06-30T17:09:47Z)
• Scalable Transformers for Neural Machine Translation [86.4530299266897]
  トランスフォーマーは、そのキャパシティとシーケンス生成の並列トレーニングのため、ニューラルネットワーク翻訳(NMT)で広く採用されている。 本稿では,異なるスケールのサブトランスフォーマーを自然に含み,パラメータを共有できる,スケーラブルなトランスフォーマーを提案する。 スケーラブルトランスフォーマーのトレーニングの難しさに対処する3段階のトレーニングスキームが提案されている。
  論文  参考訳（メタデータ） (2021-06-04T04:04:10Z)
• CoPE: Conditional image generation using Polynomial Expansions [50.67390290190874]
  入力変数を2つ拡張し,それらの自己相関と相互相関をキャプチャする,copeと呼ばれる汎用フレームワークを導入する。 CoPEは8つのデータセットを含む5つのタスク(クラスジェネレーション、逆問題、エッジ・ツー・イメージ翻訳、イメージ・ツー・イメージ翻訳、属性誘導生成)で評価される。 徹底的な評価は、CoPEが多様な条件生成タスクに取り組むのに役立つことを示唆している。
  論文  参考訳（メタデータ） (2021-04-11T19:02:37Z)

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

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