論文の概要: Formal Language Recognition by Hard Attention Transformers: Perspectives
from Circuit Complexity
- arxiv url: http://arxiv.org/abs/2204.06618v1
- Date: Wed, 13 Apr 2022 19:25:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-15 12:22:32.258895
- Title: Formal Language Recognition by Hard Attention Transformers: Perspectives
from Circuit Complexity
- Title(参考訳): ハードアテンショントランスフォーマーによる形式言語認識:回路複雑性からの視点
- Authors: Yiding Hao, Dana Angluin, and Robert Frank
- Abstract要約: 文字列アクセプタと見なされるUHATとGUHAT変換器は、複雑性クラスAC$0$の形式言語しか認識できないことを示す。
対照的に、非AC$0$言語 MAJORITY と DYCK-1 は AHAT ネットワークによって認識可能であり、AHAT が UHAT と GUHAT が認識できない言語を認識できることを意味する。
- 参考スコア(独自算出の注目度): 1.0159205678719043
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper analyzes three formal models of Transformer encoders that differ
in the form of their self-attention mechanism: unique hard attention (UHAT);
generalized unique hard attention (GUHAT), which generalizes UHAT; and
averaging hard attention (AHAT). We show that UHAT and GUHAT Transformers,
viewed as string acceptors, can only recognize formal languages in the
complexity class AC$^0$, the class of languages recognizable by families of
Boolean circuits of constant depth and polynomial size. This upper bound
subsumes Hahn's (2020) results that GUHAT cannot recognize the DYCK languages
or the PARITY language, since those languages are outside AC$^0$ (Furst et al.,
1984). In contrast, the non-AC$^0$ languages MAJORITY and DYCK-1 are
recognizable by AHAT networks, implying that AHAT can recognize languages that
UHAT and GUHAT cannot.
- Abstract(参考訳): 本稿では, トランスフォーマーエンコーダの3つの形式モデルについて分析し, 自己注意機構の形式が異なる: ユニークなハードアテンション (UHAT) , 一般化されたユニークなハードアテンション (GUHAT) , 平均的なハードアテンション (AHAT) 。
文字列アクセプタとみなすUHATおよびGUHATトランスフォーマーは,一定の深さと多項式サイズを持つブール回路の族で認識可能な言語であるAC$^0$の形式言語しか認識できないことを示す。
これらの言語はac$^0$ (furst et al., 1984) の外にあるため、この上界がハーンの (2020) を仮定すると、guhat はディック言語やパリティ言語を認識できない。
対照的に、非AC$^0$言語 MAJORITY と DYCK-1 は AHAT ネットワークによって認識可能であり、AHAT が UHAT と GUHAT が認識できない言語を認識できることを意味する。
関連論文リスト
- Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly
the Star-Free Languages [7.938342455750221]
我々は、注意力と厳密な将来のマスキングを備えたトランスフォーマーエンコーダについて検討する。
これらのネットワークによって認識される言語のクラスは、まさにスターフリー言語であることを示す。
論文 参考訳(メタデータ) (2023-10-21T03:26:39Z) - Logical Languages Accepted by Transformer Encoders with Hard Attention [45.14832807541816]
我々は,(1)UHAT(Unique Hard Attention Transformers)と(2)AHAT(Average Hard Attention Transformers)の2つの自己注意機構に注目した。
UHATエンコーダは、回路複雑性クラス$sf AC0$内の言語のみを認識することが知られている。
AHATエンコーダは$sf AC0$以外の言語を認識できるが、その表現力はより大きな回路複雑性クラス$sf TC0$、すなわち$sf AC0$にある。
論文 参考訳(メタデータ) (2023-10-05T18:13:40Z) - Linearity of Relation Decoding in Transformer Language Models [82.47019600662874]
トランスフォーマー言語モデル(LM)で符号化された知識の多くは、関係性の観点から表現することができる。
関係のサブセットに対して、この計算は対象表現上の1つの線形変換によってよく近似されることを示す。
論文 参考訳(メタデータ) (2023-08-17T17:59:19Z) - Average-Hard Attention Transformers are Constant-Depth Uniform Threshold
Circuits [0.0]
平均的注意力変換器はクラスTC0に該当する言語を認識する。
本稿は、第1結果を拡張して均一回路を生成可能であることを示す。
論文 参考訳(メタデータ) (2023-08-06T21:23:22Z) - Physics of Language Models: Part 1, Context-Free Grammar [61.05762942335984]
我々は、GPTのようなHOW生成言語モデルを研究するための制御実験を設計し、文脈自由文法(CFG)を学ぶ。
難しい(長くあいまいな)CFGであっても、事前学習したトランスフォーマーは、ほぼ完璧な精度と印象的な多様性で文を生成することができる。
論文 参考訳(メタデータ) (2023-05-23T04:28:16Z) - Shapley Head Pruning: Identifying and Removing Interference in
Multilingual Transformers [54.4919139401528]
言語固有のパラメータを識別・解析することで干渉を減らすことができることを示す。
固定モデルから同定された注目ヘッドを除去することで、文分類と構造予測の両方において、ターゲット言語の性能が向上することを示す。
論文 参考訳(メタデータ) (2022-10-11T18:11:37Z) - Word Embedding Transformation for Robust Unsupervised Bilingual Lexicon
Induction [21.782189001319935]
2つの言語の埋め込みの同型性を高めるための変換に基づく手法を提案する。
我々の手法は最先端の手法と比較して、競争力や優れた性能を達成することができる。
論文 参考訳(メタデータ) (2021-05-26T02:09:58Z) - On the Ability and Limitations of Transformers to Recognize Formal
Languages [9.12267978757844]
カウンター言語のサブクラスのためのトランスフォーマーの構築を提供する。
トランスフォーマーはこのサブクラスでうまく機能し、それらの学習メカニズムは我々の構成と強く相関している。
おそらく、LSTMとは対照的に、Transformerはパフォーマンスが低下する正規言語のサブセットでのみ動作する。
論文 参考訳(メタデータ) (2020-09-23T17:21:33Z) - Inducing Language-Agnostic Multilingual Representations [61.97381112847459]
言語間の表現は、世界中のほとんどの言語でNLP技術が利用可能になる可能性がある。
i) 対象言語のベクトル空間をピボットソース言語に再配置すること、(ii) 言語固有の手段と分散を取り除くこと、(ii) 副産物としての埋め込みの識別性を向上すること、(iii) 形態的制約や文の並べ替えを除去することによって言語間の入力類似性を高めること、の3つのアプローチを検討する。
論文 参考訳(メタデータ) (2020-08-20T17:58:56Z) - Phonological Features for 0-shot Multilingual Speech Synthesis [50.591267188664666]
単言語モデルにおいても,トレーニング中に見つからない言語に対して,コードスイッチングが可能であることを示す。
テスト時には、訓練で見たことのない音の近似を含む、新しい言語で、理解不能で、コードスイッチトされた音声を生成する。
論文 参考訳(メタデータ) (2020-08-06T18:25:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。