論文の概要: On the Representational Capacity of Recurrent Neural Language Models
- arxiv url: http://arxiv.org/abs/2310.12942v3
- Date: Wed, 22 Nov 2023 01:39:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 18:15:17.844191
- Title: On the Representational Capacity of Recurrent Neural Language Models
- Title(参考訳): リカレントニューラルネットワークモデルの表現能力について
- Authors: Franz Nowak, Anej Svete, Li Du, Ryan Cotterell
- Abstract要約: 計算時間を持つ有理重み付きRLMは、有理重み付き遷移を持つ決定論的確率的チューリングマシン(PTM)をシミュレートできることを示す。
また, 実時間計算の制約下では, 決定論的実時間有理PTMをシミュレートできることを示した。
- 参考スコア(独自算出の注目度): 61.38536173209874
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work investigates the computational expressivity of language models
(LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992)
famously showed that RNNs with rational weights and hidden states and unbounded
computation time are Turing complete. However, LMs define weightings over
strings in addition to just (unweighted) language membership and the analysis
of the computational power of RNN LMs (RLMs) should reflect this. We extend the
Turing completeness result to the probabilistic case, showing how a rationally
weighted RLM with unbounded computation time can simulate any deterministic
probabilistic Turing machine (PTM) with rationally weighted transitions. Since,
in practice, RLMs work in real-time, processing a symbol at every time step, we
treat the above result as an upper bound on the expressivity of RLMs. We also
provide a lower bound by showing that under the restriction to real-time
computation, such models can simulate deterministic real-time rational PTMs.
- Abstract(参考訳): 本稿では,recurrent neural networks(rnns)に基づく言語モデル(lms)の計算表現性について検討する。
Siegelmann and Sontag (1992) は、合理的な重みと隠れた状態と非有界な計算時間を持つ RNN がチューリング完全であることを示した。
しかし、文字列の重み付けは、単に(重み付けされていない)言語のメンバーシップに加えて定義されており、RNN LM(RLM)の計算能力の分析もこれを反映すべきである。
チューリング完全性の結果を確率ケースに拡張し、有理重み付き計算時間を持つ有理重み付きrlmが、有理重み付き遷移を伴う任意の決定論的確率的チューリングマシン(ptm)をいかにシミュレートできるかを示す。
実のところ、RLMはリアルタイムに動作し、各ステップでシンボルを処理するので、上記の結果をRLMの表現性上の上限として扱う。
また、実時間計算の制限下では、決定論的実時間有理PTMをシミュレートできることを示す。
関連論文リスト
- A Theoretical Result on the Inductive Bias of RNN Language Models [56.06361029539347]
Hewittらによる最近の研究(2020年)は、リカレントニューラルネットワーク(RNN)の言語モデル(LM)としての実証的成功の解釈を提供する。
それらの構成を一般化し、RNNがより大規模なLMを効率的に表現できることを示す。
論文 参考訳(メタデータ) (2024-02-24T13:42:06Z) - LLMs learn governing principles of dynamical systems, revealing an
in-context neural scaling law [0.0]
動的システムの振る舞いを外挿する大規模言語モデルの能力について検討する。
この結果から,LLaMAはテキストをベースとした言語モデルであり,動的システム時系列の正確な予測が可能であることがわかった。
LLMから直接多桁数の確率密度関数を抽出するフレキシブルで効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-01T17:28:10Z) - Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
RNN LMが表現できる確率分布のクラスについて検討する。
単純なRNNは確率的有限状態オートマトンの部分クラスと同値であることを示す。
これらの結果は、RNN LMが表現できる分布のクラスを特徴付けるための第一歩を示す。
論文 参考訳(メタデータ) (2023-10-08T13:36:05Z) - Advancing Regular Language Reasoning in Linear Recurrent Neural Networks [61.305218287797025]
線形リカレントニューラルネットワークがトレーニングシーケンスに隠された規則を学習できるかを検討する。
ブロック対角および入力依存遷移行列を備えた新しいLRNNを提案する。
実験結果から,提案モデルが正規言語タスクで長さ外挿を行うことができる唯一のLRNNであることが示唆された。
論文 参考訳(メタデータ) (2023-09-14T03:36:01Z) - Large Language Models as General Pattern Machines [64.75501424160748]
我々は,事前訓練された大規模言語モデル (LLM) が,複雑なトークンシーケンスを自動回帰的に完了することを示す。
驚いたことに、語彙からランダムにサンプリングされたトークンを用いてシーケンスが表現された場合でも、パターン完了の習熟度を部分的に保持することができる。
本研究では,ロボット工学における問題に対して,これらのゼロショット機能がどのように適用されるかを検討する。
論文 参考訳(メタデータ) (2023-07-10T17:32:13Z) - Extracting Finite Automata from RNNs Using State Merging [1.8072051868187933]
文法的推論から状態マージパラダイムに着想を得たRNNから有限オートマトンを抽出する手法を提案する。
提案手法の有効性をTomita言語ベンチマークで検証したところ,ベンチマーク中のすべての言語でトレーニングされたRNNから忠実なオートマトンを抽出できることが確認された。
論文 参考訳(メタデータ) (2022-01-28T23:03:25Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳(メタデータ) (2021-07-28T04:28:55Z) - PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。
我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。
回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
論文 参考訳(メタデータ) (2021-03-23T17:03:10Z) - Distance and Equivalence between Finite State Machines and Recurrent
Neural Networks: Computational results [0.348097307252416]
訓練されたRNN言語モデルから有限状態マシンベースモデルを抽出する問題に関するいくつかの結果を示す。
我々の3-SATによる削減技術は、後者の事実を他のRNNアーキテクチャに容易に一般化できるようにする。
論文 参考訳(メタデータ) (2020-04-01T14:48:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。