論文の概要: The Counting Power of Transformers

• arxiv url: http://arxiv.org/abs/2505.11199v2
• Date: Fri, 26 Sep 2025 22:10:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 20:10:04.310487
• Title: The Counting Power of Transformers
• Title（参考訳）: 変圧器の計数力
• Authors: Marco Sälzer, Chris Köcher, Alexander Kozachinskiy, Georg Zetzsche, Anthony Widjaja Lin,
• Abstract要約: 我々は変圧器の計数力を調べるための公式な枠組みを提供する。 我々の主な成果は、変換器が非常に非線形なカウント特性を表現できることである。 より正確には、変換器が全ての半代数的カウント特性をキャプチャできることを証明できる。
• 参考スコア（独自算出の注目度）: 45.96383652484399
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Counting properties (e.g. determining whether certain tokens occur more than other tokens in a given input text) have played a significant role in the study of expressiveness of transformers. In this paper, we provide a formal framework for investigating the counting power of transformers. We argue that all existing results demonstrate transformers' expressivity only for (semi-)linear counting properties, i.e., which are expressible as a boolean combination of linear inequalities. Our main result is that transformers can express counting properties that are highly nonlinear. More precisely, we prove that transformers can capture all semialgebraic counting properties, i.e., expressible as a boolean combination of arbitrary multivariate polynomials (of any degree). Among others, these generalize the counting properties that can be captured by C-RASP softmax transformers, which capture only linear counting properties. To complement this result, we exhibit a natural subclass of (softmax) transformers that completely characterizes semialgebraic counting properties. Through connections with the Hilbert's tenth problem, this expressivity of transformers also yields a new undecidability result for analyzing an extremely simple transformer model -- surprisingly with neither positional encodings (i.e. NoPE-transformers) nor masking. We also experimentally validate trainability of such counting properties.
• Abstract（参考訳）: カウント特性(例えば、ある入力テキストで他のトークンよりも多くのトークンが発生するかどうかを決定する)は、トランスフォーマーの表現性の研究において重要な役割を担っている。 本稿では,変圧器の計数力に関する公式な枠組みを提供する。 既存のすべての結果は、線型不等式のブール結合として表現可能な(半)線形数え上げ特性に対してのみ、変圧器の表現性を示すと論じる。 我々の主な成果は、変換器が非常に非線形なカウント特性を表現できることである。 より正確には、変換器はすべての半代数的数え上げ特性、すなわち任意の多変数多項式(任意の次数)のブール結合として表現できることを証明できる。 これらのうち、C-RASPソフトマックス変換器で捕捉できるカウント特性を一般化し、線形カウント特性のみをキャプチャする。 この結果を補完するために、半代数的カウント特性を完全に特徴付ける(ソフトマックス)変換器の自然なサブクラスを示す。 ヒルベルトの10番目の問題と接続することで、トランスフォーマーの表現性は、非常に単純なトランスフォーマーモデルを解析するための新しい決定不可能な結果をもたらす。 また、そのようなカウント特性のトレーニング性についても実験的に検証する。

関連論文リスト

• PaTH Attention: Position Encoding via Accumulating Householder Transformations [56.32365080761523]
  PaTHは、ハウステリア変換の累積積に基づいて、フレキシブルなデータ依存位置符号化方式である。 家庭用行列の積をコンパクトに表現することで,効率的な並列学習アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2025-05-22T08:36:09Z)
• 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)
• 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)

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

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