論文の概要: Recurrent Neural Language Models as Probabilistic Finite-state Automata
- arxiv url: http://arxiv.org/abs/2310.05161v4
- Date: Tue, 19 Dec 2023 10:13:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 22:34:20.793815
- Title: Recurrent Neural Language Models as Probabilistic Finite-state Automata
- Title(参考訳): 確率的有限状態オートマトンとしてのリカレントニューラルネットワークモデル
- Authors: Anej Svete, Ryan Cotterell
- Abstract要約: RNN LMが表現できる確率分布のクラスについて検討する。
単純なRNNは確率的有限状態オートマトンの部分クラスと同値であることを示す。
これらの結果は、RNN LMが表現できる分布のクラスを特徴付けるための第一歩を示す。
- 参考スコア(独自算出の注目度): 66.23172872811594
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Studying language models (LMs) in terms of well-understood formalisms allows
us to precisely characterize their abilities and limitations. Previous work has
investigated the representational capacity of recurrent neural network (RNN)
LMs in terms of their capacity to recognize unweighted formal languages.
However, LMs do not describe unweighted formal languages -- rather, they define
\emph{probability distributions} over strings. In this work, we study what
classes of such probability distributions RNN LMs can represent, which allows
us to make more direct statements about their capabilities. We show that simple
RNNs are equivalent to a subclass of probabilistic finite-state automata, and
can thus model a strict subset of probability distributions expressible by
finite-state models. Furthermore, we study the space complexity of representing
finite-state LMs with RNNs. We show that, to represent an arbitrary
deterministic finite-state LM with $N$ states over an alphabet $\alphabet$, an
RNN requires $\Omega\left(N |\Sigma|\right)$ neurons. These results present a
first step towards characterizing the classes of distributions RNN LMs can
represent and thus help us understand their capabilities and limitations.
- Abstract(参考訳): 言語モデル(lms)を十分に理解された形式主義の観点から研究することで、その能力と限界を正確に特徴づけることができる。
前回の研究では、非重み付き形式言語を認識する能力の観点から、recurrent neural network (rnn) lmsの表現能力を調査した。
しかし、lms は非重み付き形式言語を記述せず、文字列上の \emph{probability distributions} を定義する。
本研究では,RNN LMが表現できる確率分布のクラスについて検討する。
単純RNNは確率的有限状態オートマトンの部分クラスと等価であり、したがって有限状態モデルで表現可能な確率分布の厳密な部分集合をモデル化できることを示す。
さらに, 有限状態LMをRNNで表現する空間複雑性について検討した。
任意の決定論的有限状態LMをアルファベット$\alphabet$上の$N$状態で表現するために、RNNは$\Omega\left(N |\Sigma|\right)$ニューロンを必要とする。
これらの結果は、RNN LMが表現できる分布のクラスを特徴付けるための第一歩を示し、その能力と限界を理解するのに役立ちます。
関連論文リスト
- A Theoretical Result on the Inductive Bias of RNN Language Models [56.06361029539347]
Hewittらによる最近の研究(2020年)は、リカレントニューラルネットワーク(RNN)の言語モデル(LM)としての実証的成功の解釈を提供する。
それらの構成を一般化し、RNNがより大規模なLMを効率的に表現できることを示す。
論文 参考訳(メタデータ) (2024-02-24T13:42:06Z) - On the Representational Capacity of Recurrent Neural Language Models [61.38536173209874]
計算時間を持つ有理重み付きRLMは、有理重み付き遷移を持つ決定論的確率的チューリングマシン(PTM)をシミュレートできることを示す。
また, 実時間計算の制約下では, 決定論的実時間有理PTMをシミュレートできることを示した。
論文 参考訳(メタデータ) (2023-10-19T17:39:47Z) - On the Computational Complexity and Formal Hierarchy of Second Order
Recurrent Neural Networks [59.85314067235965]
2次次リカレントネットワーク(RNN)の理論基盤を拡大する(2次RNN)
有界時間でチューリング完備な RNN のクラスが存在することを証明している。
また、記憶のない2ドルのRNNは、バニラRNNのような現代のモデルよりも優れており、正規文法の認識において繰り返し単位をゲートしていることを示す。
論文 参考訳(メタデータ) (2023-09-26T06:06:47Z) - Advancing Regular Language Reasoning in Linear Recurrent Neural Networks [61.305218287797025]
線形リカレントニューラルネットワークがトレーニングシーケンスに隠された規則を学習できるかを検討する。
ブロック対角および入力依存遷移行列を備えた新しいLRNNを提案する。
実験結果から,提案モデルが正規言語タスクで長さ外挿を行うことができる唯一のLRNNであることが示唆された。
論文 参考訳(メタデータ) (2023-09-14T03:36:01Z) - Probabilistic Modeling: Proving the Lottery Ticket Hypothesis in Spiking
Neural Network [30.924449325020767]
Lottery Ticket hypothesis (LTH) は、ランダムにdの大きいニューラルネットワークは小さなサブネットワークを含んでいると述べている。
LTHはプルーニングネットワークのための新しいパスを開く。
論文 参考訳(メタデータ) (2023-05-20T09:27:34Z) - Learning Low Dimensional State Spaces with Overparameterized Recurrent
Neural Nets [57.06026574261203]
我々は、長期記憶をモデル化できる低次元状態空間を学習するための理論的証拠を提供する。
実験は、線形RNNと非線形RNNの両方で低次元状態空間を学習することで、我々の理論を裏付けるものである。
論文 参考訳(メタデータ) (2022-10-25T14:45:15Z) - Learning Hierarchical Structures with Differentiable Nondeterministic
Stacks [25.064819128982556]
最近提案された非決定論的スタックRNN(NS-RNN)に基づくスタックRNNモデルを提案する。
NS-RNNは,5つの文脈自由言語モデリングタスクにおいて,従来のスタックRNNよりも低エントロピーを実現することを示す。
また,自然言語を用いた言語モデリングを実用化するNS-RNNの限定バージョンを提案する。
論文 参考訳(メタデータ) (2021-09-05T03:25:23Z) - Distance and Equivalence between Finite State Machines and Recurrent
Neural Networks: Computational results [0.348097307252416]
訓練されたRNN言語モデルから有限状態マシンベースモデルを抽出する問題に関するいくつかの結果を示す。
我々の3-SATによる削減技術は、後者の事実を他のRNNアーキテクチャに容易に一般化できるようにする。
論文 参考訳(メタデータ) (2020-04-01T14:48:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。