論文の概要: Simulating Weighted Automata over Sequences and Trees with Transformers

• arxiv url: http://arxiv.org/abs/2403.09728v1
• Date: Tue, 12 Mar 2024 21:54:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 21:44:54.577393
• Title: Simulating Weighted Automata over Sequences and Trees with Transformers
• Title（参考訳）: 変圧器を用いた重み付きオートマタの列と木上でのシミュレーション
• Authors: Michael Rizvi, Maude Lizaire, Clara Lacroce, Guillaume Rabusseau,
• Abstract要約: DFAを仮定するモデルのクラスである重み付き有限オートマトン (WFAs) と重み付き木オートマトン (WTA) をシミュレートできることを示す。 我々はこれらの主張を正式に証明し、ターゲットオートマタの状態数の関数として必要とされる変換器モデルのサイズについて上限を与える。
• 参考スコア（独自算出の注目度）: 5.078561931628571
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformers are ubiquitous models in the natural language processing (NLP) community and have shown impressive empirical successes in the past few years. However, little is understood about how they reason and the limits of their computational capabilities. These models do not process data sequentially, and yet outperform sequential neural models such as RNNs. Recent work has shown that these models can compactly simulate the sequential reasoning abilities of deterministic finite automata (DFAs). This leads to the following question: can transformers simulate the reasoning of more complex finite state machines? In this work, we show that transformers can simulate weighted finite automata (WFAs), a class of models which subsumes DFAs, as well as weighted tree automata (WTA), a generalization of weighted automata to tree structured inputs. We prove these claims formally and provide upper bounds on the sizes of the transformer models needed as a function of the number of states the target automata. Empirically, we perform synthetic experiments showing that transformers are able to learn these compact solutions via standard gradient-based training.
• Abstract（参考訳）: トランスフォーマーは自然言語処理(NLP)コミュニティにおいてユビキタスモデルであり、過去数年間で印象的な経験的成功を収めてきた。 しかし、それらの理由と計算能力の限界についてはほとんど理解されていない。 これらのモデルはシーケンシャルなデータを処理せず、RNNのようなシーケンシャルなニューラルモデルよりも優れている。 近年の研究では、これらのモデルが決定論的有限オートマトン(DFAs)の逐次推論能力をコンパクトにシミュレートできることが示されている。 トランスフォーマーはより複雑な有限状態マシンの推論をシミュレートできるだろうか? 本研究では、重み付き有限オートマトン (WFAs) と、重み付きオートマトン (WTA) を木構造入力に一般化した重み付きツリーオートマトン (WTA) のクラスをシミュレートできることを示す。 我々はこれらの主張を正式に証明し、ターゲットオートマタの状態数の関数として必要とされる変換器モデルのサイズについて上限を与える。 実験により,変圧器は標準勾配に基づく学習により,これらのコンパクトな解を学習可能であることを示す。

関連論文リスト

• Algorithmic Capabilities of Random Transformers [49.73113518329544]
  埋め込み層のみを最適化したランダムトランスフォーマーによって、どのような関数が学習できるかを検討する。 これらのランダムなトランスフォーマーは、幅広い意味のあるアルゴリズムタスクを実行することができる。 以上の結果から,これらのモデルが訓練される前にも,アルゴリズム能力がトランスフォーマに存在することが示唆された。
  論文  参考訳（メタデータ） (2024-10-06T06:04:23Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Boolformer: Symbolic Regression of Logic Functions with Transformers [26.946376237404994]
  本稿では,ブール関数の終端から終端までのシンボリックレグレッションを実行するためにトレーニングされた最初のトランスフォーマーアーキテクチャであるBoolformerを紹介する。 クリーンな真理表を提供すると、トレーニング中に見られなかった複素関数のコンパクトな公式を予測できることが示される。 我々は、Boolformerを現実世界のバイナリ分類データセットの広いセットで評価し、古典的な機械学習手法に代わる解釈可能な代替手段としての可能性を示した。
  論文  参考訳（メタデータ） (2023-09-21T16:11:38Z)
• How Powerful are Decoder-Only Transformer Neural Models? [0.0]
  GPT-xで採用されている基礎技術のチューリング完全性に対処する最初の研究である。 単語埋め込みの空間性/圧縮性はチューリング完全性を維持する上で重要な考慮事項であることを示す。
  論文  参考訳（メタデータ） (2023-05-26T15:35:43Z)
• Characterizing Intrinsic Compositionality in Transformers with Tree Projections [72.45375959893218]
  トランスのようなニューラルモデルは、入力の異なる部分間で情報を任意にルーティングすることができる。 3つの異なるタスクに対するトランスフォーマーは、トレーニングの過程でより木のようなものになることを示す。 これらの木はモデル挙動を予測し、より木のようなモデルは構成的一般化のテストにおいてより良く一般化する。
  論文  参考訳（メタデータ） (2022-11-02T17:10:07Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
  入力トークン数における算術精度が対数的である変換器は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。 これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
  論文  参考訳（メタデータ） (2022-07-02T03:49:34Z)
• Automatic Rule Induction for Efficient Semi-Supervised Learning [56.91428251227253]
  半教師付き学習は、少量のラベル付きデータからNLPモデルを一般化できることを約束している。 事前訓練されたトランスモデルはブラックボックス相関エンジンとして機能し、説明が困難であり、時には信頼性に欠ける振る舞いをする。 本稿では,これらの課題に,簡易かつ汎用的なフレームワークであるAutomatic Rule Injection (ARI) を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2022-05-18T16:50:20Z)
• Addressing Some Limitations of Transformers with Feedback Memory [51.94640029417114]
  トランスフォーマーは、フィードフォワードネットワークであるにもかかわらず、シーケンシャルな自動回帰タスクにうまく適用されている。 本稿では、過去のすべての表現を将来のすべての表現に公開する、フィードバックトランスフォーマーアーキテクチャを提案する。 言語モデリング、機械翻訳、強化学習の様々なベンチマークにおいて、表現能力の増大は、同等のトランスフォーマーよりもはるかに強力なパフォーマンスを持つ、小さくて浅いモデルを生成することができることを実証する。
  論文  参考訳（メタデータ） (2020-02-21T16:37:57Z)

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

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