論文の概要: Stronger Separation of Analog Neuron Hierarchy by Deterministic Context-Free Languages

• arxiv url: http://arxiv.org/abs/2102.01633v1
• Date: Tue, 2 Feb 2021 17:44:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-13 00:29:04.960579
• Title: Stronger Separation of Analog Neuron Hierarchy by Deterministic Context-Free Languages
• Title（参考訳）: 決定論的文脈自由言語によるアナログニューロン階層のより強い分離
• Authors: Ji\v{r}\'i \v{S}\'ima
• Abstract要約: チョムスキー階層内の飽和線形活性化関数を用いて離散時間リカレントニューラルネットワーク(NN)の計算能力を分析する。 このモデルは、正規言語(REG)を認識する有限オートマトン(チョムスキーレベル3)と同値のヘビサイド活性化関数を持つ二進状態NNと一致する。 つまり、DCFLs $setminus$ REG) $subset$ (2ANNs $setminus$ 1ANNs)は、1ANNs $cap$を意味する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the computational power of discrete-time recurrent neural networks (NNs) with the saturated-linear activation function within the Chomsky hierarchy. This model restricted to integer weights coincides with binary-state NNs with the Heaviside activation function, which are equivalent to finite automata (Chomsky level 3) recognizing regular languages (REG), while rational weights make this model Turing-complete even for three analog-state units (Chomsky level 0). For the intermediate model $\alpha$ANN of a binary-state NN that is extended with $\alpha\geq 0$ extra analog-state neurons with rational weights, we have established the analog neuron hierarchy 0ANNs $\subset$ 1ANNs $\subset$ 2ANNs $\subseteq$ 3ANNs. The separation 1ANNs $\subsetneqq$ 2ANNs has been witnessed by the non-regular deterministic context-free language (DCFL) $L_\#=\{0^n1^n\mid n\geq 1\}$ which cannot be recognized by any 1ANN even with real weights, while any DCFL (Chomsky level 2) is accepted by a 2ANN with rational weights. In this paper, we strengthen this separation by showing that any non-regular DCFL cannot be recognized by 1ANNs with real weights, which means (DCFLs $\setminus$ REG) $\subset$ (2ANNs $\setminus$ 1ANNs), implying 1ANNs $\cap$ DCFLs = 0ANNs. For this purpose, we have shown that $L_\#$ is the simplest non-regular DCFL by reducing $L_\#$ to any language in this class, which is by itself an interesting achievement in computability theory.
• Abstract（参考訳）: 離散時間リカレントニューラルネットワーク(nns)の計算能力をチョムスキー階層内の飽和線形活性化関数を用いて解析する。 整数重みに制限されたこのモデルは、有限オートマトン(チョムスキーレベル3)と同値の2進状態 NN と一致し、正則言語(REG)を認識する一方、有理重みはこのモデルを3つのアナログ状態単位(チョムスキーレベル0)に対してもチューリング完全とする。 中間モデル $\alpha$ANN を、有理重み付き$\alpha\geq 0$余剰アナログ状態ニューロンで拡張し、アナログニューロン階層 0ANNs $\subset$ 1ANNs $\subset$ 2ANNs $\subseteq$ 3ANNs を確立した。 分離 1ANNs $\subsetneq$ 2ANNs は非正規決定論的文脈自由言語 (DCFL) $L_\#=\{0^n1^n\mid n\geq 1\}$ によって目撃され、実際の重みでも任意の 1ANN では認識できないが、DCFL (Chomsky level 2) は有理重みを持つ 2ANN では受け入れられる。 本稿では,非正規DCFLが実重量の1ANNでは認識できないことを示すことにより,この分離を強化する。つまり (DCFLs $\setminus$ REG) $\subset$ (2ANNs $\setminus$ 1ANNs) であり,これは 1ANNs $\cap$ DCFLs = 0ANNs を意味する。 この目的のために、$L_\#$は、このクラスの任意の言語に$L_\#$を還元することで、最も単純な非正規DCFLであることを示した。

関連論文リスト

• Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
  3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。 次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。 この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
  論文  参考訳（メタデータ） (2023-11-23T02:19:32Z)
• 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)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。 しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。 我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。 N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
  論文  参考訳（メタデータ） (2023-06-05T21:35:32Z)
• Generalization Ability of Wide Neural Networks on $\mathbb{R}$ [8.508360765158326]
  広い2層ReLUニューラルネットワークのmathbbR$上での一般化能力について検討した。 $i)$幅$mrightarrowinfty$のとき、ニューラルネットワークカーネル(NNK)がNTKに均一に収束すると、$ii)$$$$K_1$のRKHSに対する回帰の最小値が$n-2/3$;$iii)$ 広義のニューラルネットワークをトレーニングする際に早期停止戦略を採用する場合、$ivとなる。
  論文  参考訳（メタデータ） (2023-02-12T15:07:27Z)
• Neural Networks Efficiently Learn Low-Dimensional Representations with SGD [22.703825902761405]
  SGDで訓練されたReLU NNは、主方向を回復することで、$y=f(langleboldsymbolu,boldsymbolxrangle) + epsilon$という形の単一インデックスターゲットを学習できることを示す。 また、SGDによる近似低ランク構造を用いて、NNに対して圧縮保証を提供する。
  論文  参考訳（メタデータ） (2022-09-29T15:29:10Z)
• Training Overparametrized Neural Networks in Sublinear Time [14.918404733024332]
  ディープラーニングには膨大な計算とエネルギーのコストが伴う。 探索木の小さな部分集合として、二分ニューラルネットワークの新しいサブセットを示し、それぞれが探索木のサブセット(Ds)に対応する。 我々はこの見解が深層ネットワーク(Ds)の分析解析にさらに応用できると考えている。
  論文  参考訳（メタデータ） (2022-08-09T02:29:42Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。 また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
  論文  参考訳（メタデータ） (2022-06-26T06:51:31Z)
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
  2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。 過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
  論文  参考訳（メタデータ） (2020-07-09T07:09:28Z)
• $\Pi-$nets: Deep Polynomial Neural Networks [86.36557534288535]
  $Pi$-Netsは、出力が入力の高次であるニューラルネットワークである。 我々は、$Pi$-Netsが標準のDCNNよりも優れた表現能力を持っていることを実証的に実証した。 近年のStyleGANのような生成モデルが,先行モデルに改良を加えた理由を解明する。
  論文  参考訳（メタデータ） (2020-03-08T18:48:43Z)

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

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