論文の概要: 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研究のための有望な道を提供する。
関連論文リスト
- A Theoretical Result on the Inductive Bias of RNN Language Models [56.06361029539347]
Hewittらによる最近の研究(2020年)は、リカレントニューラルネットワーク(RNN)の言語モデル(LM)としての実証的成功の解釈を提供する。
それらの構成を一般化し、RNNがより大規模なLMを効率的に表現できることを示す。
論文 参考訳(メタデータ) (2024-02-24T13:42:06Z) - Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
RNN LMが表現できる確率分布のクラスについて検討する。
単純なRNNは確率的有限状態オートマトンの部分クラスと同値であることを示す。
これらの結果は、RNN LMが表現できる分布のクラスを特徴付けるための第一歩を示す。
論文 参考訳(メタデータ) (2023-10-08T13:36:05Z) - Learning Transductions and Alignments with RNN Seq2seq Models [0.0]
本研究では,4つのトランスダクションタスクの学習において,Recurrent-Neural-Network sequence to sequence (RNN seq2seq)モデルの有効性について検討する。
RNN seq2seqモデルは、基礎となる関数を学習するのではなく、トレーニングデータや配信データに適合するマッピングを近似することができる。
論文 参考訳(メタデータ) (2023-03-13T04:15:33Z) - Quantum-Inspired Tensor Neural Networks for Option Pricing [4.3942901219301564]
近年の深層学習の進歩により,高次元の問題を解くことで,次元性の呪い(COD)に対処することが可能になった。
このようなCODに対処するアプローチのサブセットは、高次元PDEの解決に繋がった。
この結果、数学的な金融から産業用途の制御まで、様々な現実世界の問題を解決するための扉が開けた。
論文 参考訳(メタデータ) (2022-12-28T19:39:55Z) - Decomposing a Recurrent Neural Network into Modules for Enabling
Reusability and Replacement [11.591247347259317]
RNNをモジュールに分解する最初の手法を提案する。
我々は,Vanilla,LSTM,GRUなど,さまざまな種類のRNNを研究している。
本稿では,RNNモジュールを再利用し,様々なシナリオで置き換える方法について述べる。
論文 参考訳(メタデータ) (2022-12-09T03:29:38Z) - A Time Encoding approach to training Spiking Neural Networks [3.655021726150368]
スパイキングニューラルネットワーク(SNN)の人気が高まっている。
本稿では、時間符号化理論を用いて、SNNの理解と学習を支援する余分なツールを提供する。
論文 参考訳(メタデータ) (2021-10-13T14:07:11Z) - Learning Hierarchical Structures with Differentiable Nondeterministic
Stacks [25.064819128982556]
最近提案された非決定論的スタックRNN(NS-RNN)に基づくスタックRNNモデルを提案する。
NS-RNNは,5つの文脈自由言語モデリングタスクにおいて,従来のスタックRNNよりも低エントロピーを実現することを示す。
また,自然言語を用いた言語モデリングを実用化するNS-RNNの限定バージョンを提案する。
論文 参考訳(メタデータ) (2021-09-05T03:25:23Z) - FATNN: Fast and Accurate Ternary Neural Networks [89.07796377047619]
Ternary Neural Networks (TNN) は、完全な精度のニューラルネットワークよりもはるかに高速で、電力効率が高いため、多くの注目を集めている。
そこで本研究では、3次内積の計算複雑性を2。
性能ギャップを軽減するために,実装に依存した3次量子化アルゴリズムを精巧に設計する。
論文 参考訳(メタデータ) (2020-08-12T04:26:18Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。