論文の概要: On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks

• arxiv url: http://arxiv.org/abs/2309.14691v1
• Date: Tue, 26 Sep 2023 06:06:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-27 14:56:48.665277
• Title: On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks
• Title（参考訳）: 2次リカレントニューラルネットワークの計算複雑性と形式的階層性について
• Authors: Ankur Mali and Alexander Ororbia and Daniel Kifer and Lee Giles
• Abstract要約: 2次次リカレントネットワーク(RNN)の理論基盤を拡大する(2次RNN) 有界時間でチューリング完備な RNN のクラスが存在することを証明している。 また、記憶のない2ドルのRNNは、バニラRNNのような現代のモデルよりも優れており、正規文法の認識において繰り返し単位をゲートしていることを示す。
• 参考スコア（独自算出の注目度）: 59.85314067235965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Artificial neural networks (ANNs) with recurrence and self-attention have been shown to be Turing-complete (TC). However, existing work has shown that these ANNs require multiple turns or unbounded computation time, even with unbounded precision in weights, in order to recognize TC grammars. However, under constraints such as fixed or bounded precision neurons and time, ANNs without memory are shown to struggle to recognize even context-free languages. In this work, we extend the theoretical foundation for the $2^{nd}$-order recurrent network ($2^{nd}$ RNN) and prove there exists a class of a $2^{nd}$ RNN that is Turing-complete with bounded time. This model is capable of directly encoding a transition table into its recurrent weights, enabling bounded time computation and is interpretable by design. We also demonstrate that $2$nd order RNNs, without memory, under bounded weights and time constraints, outperform modern-day models such as vanilla RNNs and gated recurrent units in recognizing regular grammars. We provide an upper bound and a stability analysis on the maximum number of neurons required by $2$nd order RNNs to recognize any class of regular grammar. Extensive experiments on the Tomita grammars support our findings, demonstrating the importance of tensor connections in crafting computationally efficient RNNs. Finally, we show $2^{nd}$ order RNNs are also interpretable by extraction and can extract state machines with higher success rates as compared to first-order RNNs. Our results extend the theoretical foundations of RNNs and offer promising avenues for future explainable AI research.
• Abstract（参考訳）: 再発と自己注意を伴う人工ニューラルネットワーク(ANN)はチューリング完全(TC)であることが示されている。 しかし、既存の研究により、これらのアンはtc文法を認識するのに複数のターンまたはアンバウンドの計算時間を必要とすることが示されている。 しかし、固定または境界精度のニューロンや時間といった制約の下では、メモリを持たないANNは文脈自由言語を認識できない。 本研究では,2-次リカレントネットワーク(2-次リカレントネットワーク(2-d}$ RNN)の理論基盤を拡張し,有界時間でチューリング完全である2-次$ RNNのクラスが存在することを証明する。 このモデルは遷移テーブルを再帰的な重みに直接エンコードすることができ、有界時間計算を可能にし、設計によって解釈可能である。 また, 2 次 RNN がメモリなしで, 境界重みと時間制約の下で, バニラ RNN やゲートリカレントユニットなどの現代モデルより優れた正規文法認識性能を示した。 本稿では,2次RNNが正規文法の任意のクラスを認識するために必要なニューロンの最大数について,上限および安定性解析を行う。 トミタ文法に関する広範な実験は,計算効率の高いrnnの作成におけるテンソル接続の重要性を示すものである。 最後に、RNNが抽出によって解釈可能であることを示し、一階RNNと比較して高い成功率のステートマシンを抽出できることを示す。 我々の結果は、RNNの理論的基盤を拡張し、将来の説明可能なAI研究のための有望な道を提供する。

関連論文リスト

• Stuffed Mamba: State Collapse and State Capacity of RNN-Based Long-Context Modeling [69.36377985746878]
  本研究では,RNNの長期的文脈処理能力の低下の原因について検討し,重要な緩和策を提案する。 まず,訓練中に遭遇しないシーケンス長の大幅な性能劣化を引き起こす*状態崩壊*(SC)について検討する。 我々は,言語モデルとパスキー検索における逐次状態キャパシティを実証的に推定するために,長い文書上に一連のマンバ2モデルを訓練する。
  論文  参考訳（メタデータ） (2024-10-09T17:54:28Z)
• Obtaining Optimal Spiking Neural Network in Sequence Learning via CRNN-SNN Conversion [12.893883491781697]
  スパイキングニューラルネットワーク(SNN)は、従来の人工ニューラルネットワーク(ANN)に代わる有望な選択肢である 我々は、ニューラルネットワークにおける異なる構造のエンドツーエンド変換をサポートするために、2つのサブパイプを設計する。 本手法の有効性を,最先端の学習法や変換法と比較し,短時間・長期の時間スケールで示す。
  論文  参考訳（メタデータ） (2024-08-18T08:23:51Z)
• A Tensor Decomposition Perspective on Second-order RNNs [5.922280687190788]
  CPRNNと呼ばれるCP分解を用いた2RNNのパラメータ化モデルについて検討する。 ランクと隠れサイズがモデルキャパシティに与える影響を分析し、これらのパラメータに基づいてRNN, 2RNN, MIRNN, CPRNN間の関係を示す。 これらの結果はPenn Treebankデータセットの実験によって実証的に支援され、固定パラメータ予算により、CPRNNは、RNN、2RNN、MIRNNよりも、適切なランクと隠されたサイズで優れていることを示す。
  論文  参考訳（メタデータ） (2024-06-07T16:18:32Z)
• Learning Useful Representations of Recurrent Neural Network Weight Matrices [30.583752432727326]
  リカレントニューラルネットワーク(Recurrent Neural Networks、RNN)は、汎用並列シーケンスコンピュータである。 下流タスクと同様に、RNN分析を容易にするRNN重みの有用な表現をどうやって学習するか? 我々は、RNN重みに対するいくつかの力学的アプローチを検討し、RNNに対して置換同変のDeep Weight Space層を適用する。 我々の2つの新しい機能主義者は、入力を探索することでRNNの重みから情報を'インターロゲート'することで抽出する。
  論文  参考訳（メタデータ） (2024-03-18T17:32:23Z)
• 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 [56.11830645258106]
  本稿では,リニアリカレントニューラルネットワーク(LRNN)がトレーニングシーケンスに隠された規則を学習できるかを検討する。 ブロック対角および入力依存遷移行列を備えた新しいLRNNを提案する。 実験結果から,提案モデルが正規言語タスクに対して長さ外挿を行うことができる唯一のLRNNであることが示唆された。
  論文  参考訳（メタデータ） (2023-09-14T03:36:01Z)
• Learning Transductions and Alignments with RNN Seq2seq Models [0.8158530638728501]
  本研究では,4つのトランスダクションタスクの学習において,Recurrent-Neural-Network sequence to sequence (RNN seq2seq)モデルの有効性について検討する。 RNN seq2seqモデルは、基礎となる関数を学習するのではなく、トレーニングデータや配信データに適合するマッピングを近似することができる。
  論文  参考訳（メタデータ） (2023-03-13T04:15:33Z)
• Learning Hierarchical Structures with Differentiable Nondeterministic Stacks [25.064819128982556]
  最近提案された非決定論的スタックRNN(NS-RNN)に基づくスタックRNNモデルを提案する。 NS-RNNは,5つの文脈自由言語モデリングタスクにおいて,従来のスタックRNNよりも低エントロピーを実現することを示す。 また,自然言語を用いた言語モデリングを実用化するNS-RNNの限定バージョンを提案する。
  論文  参考訳（メタデータ） (2021-09-05T03:25:23Z)
• A Formal Hierarchy of RNN Architectures [88.38859874233944]
  階層構造は、RNNのメモリを測定する空間と、リカレント更新が重み付けされた有限状態マシンで記述できるかどうかという有理再帰という2つの形式的特性に基づいている。 これらのモデルの表現能力は、複数の層を積み重ねたり、異なるプール機能で構成することでどのように拡張されるかを示す。 我々は、不飽和RNNの実用的な学習能力は、同様の階層に従うと仮定する。
  論文  参考訳（メタデータ） (2020-04-18T00:57:54Z)
• 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)

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

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