論文の概要: Rational Transductors

• arxiv url: http://arxiv.org/abs/2602.07599v1
• Date: Sat, 07 Feb 2026 16:01:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.716089
• Title: Rational Transductors
• Title（参考訳）: 合理的トランスダクタ
• Authors: Mehryar Mohri,
• Abstract要約: EmphRational Transductorsは,行列値の繰り返しでトランスフォーマーを増強するデュアルストリームアーキテクチャである。 EmphDeep Rational Injection スキームにより,有理状態情報をアテンション機構に注入することにより,トランスフォーマーの表現力を厳密に一般化する。
• 参考スコア（独自算出の注目度）: 30.916600771560933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Standard Transformers excel at semantic modeling but struggle with rigid sequential logic and state tracking. Theoretical work establishes that self-attention is limited to $\AC^0$ (under hard attention) or $\TC^0$ (under soft attention), complexity classes that often fail to support robust length generalization on sequential problems without intermediate chain-of-thought. In this work, we introduce \emph{Rational Transductors}, a dual-stream architecture that augments the Transformer with a matrix-valued recurrence derived from Weighted Finite Automata (WFA). By injecting rational state information into the attention mechanism via a \emph{Deep Rational Injection} scheme, our framework strictly generalizes the expressive power of Transformers to capture all Regular Languages, $\NC^1$-complete problems (such as Boolean Formula Evaluation), and fundamental separations like Parity and Modular Counting, while preserving $O(L + \log T)$ parallel time complexity. We ground the architecture in a rigorous learning theory: we prove that \emph{Random Rational Features} act as a universal basis for sequential dependencies, justifying our initialization strategy, while establishing that the \emph{Differentiable Rational Feature} regime is necessary to close the representational compactness gap. Theoretical analysis and empirical results demonstrate that Rational Transductors solve the "Regular Gap," enabling robust length generalization on algorithmic tasks where standard Transformers fail, without the sequential computational bottlenecks of traditional RNNs.
• Abstract（参考訳）: 標準的なトランスフォーマーはセマンティックモデリングに優れていますが、厳格なシーケンシャルロジックと状態トラッキングに苦労しています。 理論的な研究は、自己注意は(ハードアテンションの下で)$\AC^0$または$\TC^0$(ソフトアテンション下で)制限され、しばしば中間連鎖を持たないシーケンシャルな問題に対する堅牢な長さの一般化をサポートしない複雑性クラスである。 本稿では,重み付き有限オートマタ (WFA) から導かれる行列値の再現性でトランスフォーマーを増強するデュアルストリームアーキテクチャである \emph{Rational Transductors} を紹介する。 我々のフレームワークは,有理状態情報を \emph{Deep Rational Injection} スキームを介してアテンション機構に注入することにより,すべての正規言語を捕捉するトランスフォーマーの表現力,$\NC^1$-完全問題(ブール式評価など),Parity や Modular Counting などの基本的な分離,および$O(L + \log T)$並列時間複雑性を厳密に一般化する。 我々は, アーキテクチャを厳密な学習理論で基礎づける: \emph{Random Rational Features} が連続的依存関係の普遍的基盤として機能し, 初期化戦略を正当化し, 表現コンパクト性ギャップを埋めるためには \emph{Differentiable Rational Feature} 体制が必要であることを証明する。 理論的解析と実証的な結果から、Rational Transductors が "Regular Gap" を解き、従来の RNN の逐次計算ボトルネックを伴わずに、標準変換器が失敗するアルゴリズム的タスクにおいて、堅牢な長さの一般化を可能にすることを示した。

関連論文リスト

• Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version) [49.462399222747024]
  本研究では,大規模状態空間を持つ決定過程(MDP)における非マルコフ報酬の論理的仕様に関する新しい枠組みを提案する。 我々のアプローチは有限トレース(LTLfMT)上での線形時間論理モデュロ理論を利用する 本稿では,報酬マシンとHER(Hindsight Experience Replay)をベースとした一階述語論理仕様の翻訳手法を提案する。
  論文  参考訳（メタデータ） (2026-02-05T22:11:28Z)
• Plain Transformers are Surprisingly Powerful Link Predictors [57.01966734467712]
  リンク予測はグラフ機械学習における中核的な課題であり、リッチで複雑なトポロジ的依存関係をキャプチャするモデルを必要とする。 グラフニューラルネットワーク(GNN)が標準的なソリューションであるのに対して、最先端のパイプラインは明示的な構造やメモリ集約的なノードの埋め込みに依存していることが多い。 本報告では,手作りのプリミティブに置き換えるエンコーダのみのプレーントランスであるPENCILについて,サンプリングしたローカルサブグラフに注目する。
  論文  参考訳（メタデータ） (2026-02-02T02:45:52Z)
• Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval [0.0]
  現代の情報検索は、単純な文書フィルタリングから複雑でニューロシンボリックな推論へと移行しつつある。 我々は、DAG(Directed Acyclic Graphs)に基づく形式的検索言語(mathcalL_R$)を提示し、複雑性クラスを$mathbfP$で取得することを証明する。 この研究は、インデックスを汎用計算エンジンに変換する理論的基礎を確立する。
  論文  参考訳（メタデータ） (2026-01-26T18:07:40Z)
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization [53.89723291716722]
  AI推論に関する重要な問題は、モデルが学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。 状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。 定数深度変換器はCoTで$mathsfNC1$-complete問題を確実に学習することを保証する。
  論文  参考訳（メタデータ） (2025-11-10T18:40:24Z)
• On the Existence of Universal Simulators of Attention [17.01811978811789]
  注意出力と基礎となる基本行列を同一に再現し、RASPを介してアクティベーション操作を行う方法を提案する。 我々の証明は、これまで学習によってのみ近似することが知られていたアルゴリズムによって達成可能なデータ非依存の解の存在を初めて示すものである。
  論文  参考訳（メタデータ） (2025-06-23T15:15:25Z)
• Transformers Are Universally Consistent [14.904264782690639]
  ソフトマックスに基づく非線形アテンションを備えたトランスフォーマーは,最小二乗の回帰処理を行う場合,一様に整合性を示す。 我々は経験的誤差の上限を導出し、この条件下では$mathcalO(t-1/2d)$の証明可能な速度で減衰し、$t$は入力トークンの数を表し、$d$は埋め込み次元を表す。
  論文  参考訳（メタデータ） (2025-05-30T12:39:26Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。 思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。 SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
  論文  参考訳（メタデータ） (2025-04-13T13:35:41Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)

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

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