論文の概要: The Surprising Computational Power of Nondeterministic Stack RNNs

• arxiv url: http://arxiv.org/abs/2210.01343v1
• Date: Tue, 4 Oct 2022 03:18:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 14:16:33.016341
• Title: The Surprising Computational Power of Nondeterministic Stack RNNs
• Title（参考訳）: 非決定論的スタックrnnの驚くべき計算能力
• Authors: Brian DuSell, David Chiang
• Abstract要約: 従来のリカレントニューラルネットワーク(RNN)は、固定された有限個のメモリセルを持つ。 本稿では,非決定論とニューラルコントローラが相互作用して,より予期せぬ2つの能力を生み出すことを示す。 まず、非決定論的スタック RNN は CFL だけでなく、多くの非文脈自由言語を認識できる。 第二に、スタックアルファベットのサイズを考えると、予想されるよりもはるかに大きなアルファベットサイズを持つ言語を認識できる。
• 参考スコア（独自算出の注目度）: 20.996069249108224
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Traditional recurrent neural networks (RNNs) have a fixed, finite number of memory cells. In theory (assuming bounded range and precision), this limits their formal language recognition power to regular languages, and in practice, RNNs have been shown to be unable to learn many context-free languages (CFLs). In order to expand the class of languages RNNs recognize, prior work has augmented RNNs with a nondeterministic stack data structure, putting them on par with pushdown automata and increasing their language recognition power to CFLs. Nondeterminism is needed for recognizing all CFLs (not just deterministic CFLs), but in this paper, we show that nondeterminism and the neural controller interact to produce two more unexpected abilities. First, the nondeterministic stack RNN can recognize not only CFLs, but also many non-context-free languages. Second, it can recognize languages with much larger alphabet sizes than one might expect given the size of its stack alphabet. Finally, to increase the information capacity in the stack and allow it to solve more complicated tasks with large alphabet sizes, we propose a new version of the nondeterministic stack that simulates stacks of vectors rather than discrete symbols. We demonstrate perplexity improvements with this new model on the Penn Treebank language modeling benchmark.
• Abstract（参考訳）: 従来のリカレントニューラルネットワーク(RNN)は、固定された有限個のメモリセルを持つ。 理論上(境界範囲と精度を仮定すると)、これは形式言語認識能力を正規言語に制限するものであり、実際、RNNは多くの文脈自由言語(CFL)を習得できないことが示されている。 RNNが認識する言語のクラスを拡張するために、以前の作業では、RNNを非決定論的スタックデータ構造で拡張し、プッシュダウンオートマトンと同等にし、言語認識能力をCFLに拡張した。 非決定論は、すべてのCFLを認識するために必要であるが、本稿では、非決定論とニューラルコントローラが相互作用して、より予期しない2つの能力を生み出すことを示す。 まず、非決定論的スタック RNN は CFL だけでなく、多くの非文脈自由言語を認識できる。 第二に、スタックアルファベットのサイズを考えると、予想されるよりもはるかに大きなアルファベットサイズを持つ言語を認識できる。 最後に,スタック内の情報容量を増加させ,大きなアルファベットサイズでより複雑なタスクを解決できるようにするため,離散記号ではなくベクトルのスタックをシミュレートする非決定性スタックの新バージョンを提案する。 我々はpenn treebank language modeling benchmark(リンク)で、この新しいモデルによるパープレキシティの改善を実証する。

関連論文リスト

• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  形式言語理論は、特に認識者に関するものである。 代わりに、非公式な意味でのみ類似したプロキシタスクを使用するのが一般的である。 ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価することで、このミスマッチを補正する。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages [78.1866280652834]
  大規模言語モデル (LM) は文字列上の分布である。 RNNとTransformer LMによる規則的LM(RLM)の学習性について検討する。 RNNとトランスフォーマーの双方において,RLMランクの複雑さは強く,学習可能性の有意な予測因子であることが判明した。
  論文  参考訳（メタデータ） (2024-06-06T17:34:24Z)
• 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 [56.11830645258106]
  本稿では,リニアリカレントニューラルネットワーク(LRNN)がトレーニングシーケンスに隠された規則を学習できるかを検討する。 ブロック対角および入力依存遷移行列を備えた新しいLRNNを提案する。 実験結果から,提案モデルが正規言語タスクに対して長さ外挿を行うことができる唯一のLRNNであることが示唆された。
  論文  参考訳（メタデータ） (2023-09-14T03:36:01Z)
• Nondeterministic Stacks in Neural Networks [0.456877715768796]
  我々は、非決定論的プッシュダウンオートマトンを効率的にシミュレートする微分可能なデータ構造を開発する。 これにより、任意の文脈自由言語に対する形式的認識能力が向上することを示す。 また,非決定論的スタックを付加したRNNでは,驚くほど強力な動作が可能であることを示す。
  論文  参考訳（メタデータ） (2023-04-25T16:00:40Z)
• Learning Hierarchical Structures with Differentiable Nondeterministic Stacks [25.064819128982556]
  最近提案された非決定論的スタックRNN(NS-RNN)に基づくスタックRNNモデルを提案する。 NS-RNNは,5つの文脈自由言語モデリングタスクにおいて,従来のスタックRNNよりも低エントロピーを実現することを示す。 また,自然言語を用いた言語モデリングを実用化するNS-RNNの限定バージョンを提案する。
  論文  参考訳（メタデータ） (2021-09-05T03:25:23Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。 明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
  論文  参考訳（メタデータ） (2020-10-15T04:42:29Z)
• Learning Context-Free Languages with Nondeterministic Stack RNNs [20.996069249108224]
  本稿では,指数的なスタック構成を同時にかつトラクタブルに符号化する,微分可能なスタックデータ構造を提案する。 我々は、このデータ構造とリカレントニューラルネットワーク(RNN)コントローラの組み合わせを非決定論的スタックRNNと呼んでいる。
  論文  参考訳（メタデータ） (2020-10-09T16:48:41Z)
• Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack [73.48927855855219]
  リカレントニューラルネットワーク(RNN)は、シーケンスモデリング、生成、予測に広く使われているディープアーキテクチャである。 RNNは、非常に長いシーケンスに対してあまり一般化せず、多くの重要な時間的処理や時系列予測問題に適用性を制限する。 これらの欠点に対処する方法の1つは、スタックのような外部の異なるメモリ構造とRNNを結合することである。 本稿では,重要なアーキテクチャと状態更新機構を備えたメモリ拡張RNNを改良する。
  論文  参考訳（メタデータ） (2020-04-04T14:19:15Z)

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

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