論文の概要: Self-Attention Networks Can Process Bounded Hierarchical Languages
- arxiv url: http://arxiv.org/abs/2105.11115v1
- Date: Mon, 24 May 2021 06:42:58 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-26 02:47:24.264187
- Title: Self-Attention Networks Can Process Bounded Hierarchical Languages
- Title（参考訳）: 自己組織化ネットワークは有界階層言語を処理できる
- Authors: Shunyu Yao, Binghui Peng, Christos Papadimitriou, Karthik Narasimhan
- Abstract要約: 自己アテンションネットワークが$mathsfDyck_k, D$, $mathsfDyck_k, D$を処理できることを証明する。
実験により、$mathsfDyck_kでトレーニングされた自己注意ネットワークは、ほぼ完全な精度で、より長い入力に一般化されることが示された。
- 参考スコア（独自算出の注目度）: 24.75432474021856
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Despite their impressive performance in NLP, self-attention networks were
recently proved to be limited for processing formal languages with hierarchical
structure, such as $\mathsf{Dyck}_k$, the language consisting of well-nested
parentheses of $k$ types. This suggested that natural language can be
approximated well with models that are too weak for formal languages, or that
the role of hierarchy and recursion in natural language might be limited. We
qualify this implication by proving that self-attention networks can process
$\mathsf{Dyck}_{k, D}$, the subset of $\mathsf{Dyck}_{k}$ with depth bounded by
$D$, which arguably better captures the bounded hierarchical structure of
natural language. Specifically, we construct a hard-attention network with
$D+1$ layers and $O(\log k)$ memory size (per token per layer) that recognizes
$\mathsf{Dyck}_{k, D}$, and a soft-attention network with two layers and
$O(\log k)$ memory size that generates $\mathsf{Dyck}_{k, D}$. Experiments show
that self-attention networks trained on $\mathsf{Dyck}_{k, D}$ generalize to
longer inputs with near-perfect accuracy, and also verify the theoretical
memory advantage of self-attention networks over recurrent networks.
- Abstract（参考訳）: NLPの性能は優れていたが、最近、$\mathsf{Dyck}_k$のような階層構造を持つ形式言語を処理するために、自己注意型ネットワークが制限されていることが証明された。
このことは、形式言語には弱すぎるモデルで自然言語をよく近似できる、あるいは自然言語における階層と再帰の役割が制限されるかもしれないことを示唆している。
自己アテンションネットワークが$\mathsf{Dyck}_{k, D}$, $\mathsf{Dyck}_{k}$のサブセットを$D$で束縛し、自然言語の有界階層構造をよりよく捉えることができることを証明することによって、この意味を証明できる。
具体的には、$d+1$のレイヤと$o(\log k)$のメモリサイズ(層当たりトークン)のハードアテンションネットワークを構築し、$\mathsf{dyck}_{k, d}$を認識し、2つのレイヤと$o(\log k)$のメモリサイズを持つソフトアテンションネットワークで$\mathsf{dyck}_{k, d}$を生成する。
実験により、$\mathsf{Dyck}_{k, D}$でトレーニングされた自己注意ネットワークは、ほぼ完全な精度でより長い入力を一般化し、また、繰り返しネットワークよりも自己注意ネットワークの理論的利点を検証する。
関連論文リスト
- Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
形式言語理論は、特に認識者に関するものである。
代わりに、非公式な意味でのみ類似したプロキシタスクを使用するのが一般的である。
ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価することで、このミスマッチを補正する。
論文 参考訳（メタデータ） (2024-11-11T16:33:25Z) - Neural Networks Generalize on Low Complexity Data [5.678271181959529]
本稿では、ReLUを活性化したフィードフォワードニューラルネットワークが、低複雑性データに基づいて一般化されていることを示す。
我々は、そのようなネットワークの記述長の概念とともに、この単純なプログラミング言語を定義する。
自然数の素性チェックなどの基本的な計算タスクの例を示す。
論文 参考訳（メタデータ） (2024-09-19T03:54:49Z) - Deep Neural Networks: Multi-Classification and Universal Approximation [0.0]
我々は,幅2ドル,深さ2N+4M-1$のReLUディープニューラルネットワークが,$N$要素からなる任意のデータセットに対して有限標本記憶を達成できることを実証した。
また、$W1,p$関数を近似するための深さ推定と$Lp(Omega;mathbbRm)$ for $mgeq1$を近似するための幅推定も提供する。
論文 参考訳（メタデータ） (2024-09-10T14:31:21Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19:32Z) - Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。
シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文 参考訳（メタデータ） (2023-05-25T22:27:42Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - An Exponential Improvement on the Memorization Capacity of Deep
Threshold Networks [40.489350374378645]
我々は$widetildemathcalO(e1/delta2+sqrtn)$ニューロンと$widetildemathcalO(fracddelta+n)$ウェイトが十分であることを証明した。
また、超平面を用いて球面上の$n$の点を分離する純粋に幾何学的な問題にニューラルネットワークを接続することで、新しい下界を証明した。
論文 参考訳（メタデータ） (2021-06-14T19:42:32Z) - 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) - Sharp Representation Theorems for ReLU Networks with Precise Dependence
on Depth [26.87238691716307]
D$ReLU層を持つニューラルネットワークに対して,2乗損失下でのシャープな表現結果を証明した。
その結果、より深いネットワークはよりスムーズな関数を表現するのに優れているという仮説が実証された。
論文 参考訳（メタデータ） (2020-06-07T05:25:06Z) - Backward Feature Correction: How Deep Learning Performs Deep
(Hierarchical) Learning [66.05472746340142]
本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。
我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
論文 参考訳（メタデータ） (2020-01-13T17:28:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。