論文の概要: RNNs can generate bounded hierarchical languages with optimal memory

• arxiv url: http://arxiv.org/abs/2010.07515v1
• Date: Thu, 15 Oct 2020 04:42:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-07 03:41:48.364611
• Title: RNNs can generate bounded hierarchical languages with optimal memory
• Title（参考訳）: RNNは最適なメモリで有界階層言語を生成することができる
• Authors: John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, Christopher D. Manning
• Abstract要約: RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。 明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
• 参考スコア（独自算出の注目度）: 113.73133308478612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recurrent neural networks empirically generate natural language with high syntactic fidelity. However, their success is not well-understood theoretically. We provide theoretical insight into this success, proving in a finite-precision setting that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth, reflecting the bounded memory needs and long-distance dependencies of natural language syntax. The best known results use $O(k^{\frac{m}{2}})$ memory (hidden units) to generate these languages. We prove that an RNN with $O(m \log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction. Finally, we show that no algorithm, even with unbounded computation, can suffice with $o(m \log k)$ hidden units.
• Abstract（参考訳）: リカレントニューラルネットワークは、構文的忠実度の高い自然言語を経験的に生成する。 しかし、その成功は理論的にはよく理解されていない。 我々はこの成功に関する理論的知見を提供し、RNNが自然言語構文の足場を反映した有界階層言語を効率的に生成できることを有限精度で証明した。 Dyck-($k$,$m$)は、($k$型の)よくネストされた括弧と$m$バウンドなネスト深さの言語で、バウンドメモリのニーズと自然言語構文の長距離依存性を反映している。 最もよく知られている結果は、これらの言語を生成するために$O(k^{\frac{m}{2}})$ memory (hidden unit)を使用する。 O(m \log k)$ の隠れ単位を持つ RNN は、明示的な構成によってメモリの指数的な減少が十分であることを示す。 最後に、非有界な計算であっても、$o(m \log k)$隠れ単位で十分であるアルゴリズムは存在しないことを示す。

関連論文リスト

• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  形式言語理論は、特に認識者に関するものである。 代わりに、非公式な意味でのみ類似したプロキシタスクを使用するのが一般的である。 ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価することで、このミスマッチを補正する。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• 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)
• Densely Connected $G$-invariant Deep Neural Networks with Signed Permutation Representations [6.200483285433661]
  有限群$G$,$G$-不変ディープニューラルネットワーク(G$-DNN)アーキテクチャをReLUアクティベーション付きで導入・検討する。 G$-DNNのプリアクティベーションは、Emphsigned permutation representations (signed perm-reps) of $G$で変換できる。 文献からReLUのアクティベーション関数にアクセスできるものよりも、より許容可能な$G$-DNNアーキテクチャが存在することを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:35:03Z)
• Residual Learning of Neural Text Generation with $n$-gram Language Model [41.26228768053928]
  我々は、$n$-gramのLMと実データ分布の間の残差に適合するニューラルネットワークLMを学習する。 当社のアプローチは、一般的なスタンドアロンニューラルネットワークモデルに対して、継続的にパフォーマンスの向上を実現しています。
  論文  参考訳（メタデータ） (2022-10-26T02:42:53Z)
• The Surprising Computational Power of Nondeterministic Stack RNNs [20.996069249108224]
  従来のリカレントニューラルネットワーク(RNN)は、固定された有限個のメモリセルを持つ。 本稿では,非決定論とニューラルコントローラが相互作用して,より予期せぬ2つの能力を生み出すことを示す。 まず、非決定論的スタック RNN は CFL だけでなく、多くの非文脈自由言語を認識できる。 第二に、スタックアルファベットのサイズを考えると、予想されるよりもはるかに大きなアルファベットサイズを持つ言語を認識できる。
  論文  参考訳（メタデータ） (2022-10-04T03:18:19Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。 このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
  論文  参考訳（メタデータ） (2021-10-07T05:25:23Z)
• Self-Attention Networks Can Process Bounded Hierarchical Languages [24.75432474021856]
  自己アテンションネットワークが$mathsfDyck_k, D$, $mathsfDyck_k, D$を処理できることを証明する。 実験により、$mathsfDyck_kでトレーニングされた自己注意ネットワークは、ほぼ完全な精度で、より長い入力に一般化されることが示された。
  論文  参考訳（メタデータ） (2021-05-24T06:42:58Z)
• Recursive Top-Down Production for Sentence Generation with Latent Trees [77.56794870399288]
  自然および合成言語に対する文脈自由文法の生成特性をモデル化する。 潜伏二分木構造にN$の葉を持つ動的プログラミングアルゴリズムを提案する。 また,Multi30kデータセットを用いたドイツ語と英語の翻訳実験を行った。
  論文  参考訳（メタデータ） (2020-10-09T17:47:16Z)

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

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