論文の概要: 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 が認識できない言語を認識できることを意味する。
関連論文リスト
- Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
形式言語理論は、特に認識者に関するものである。
代わりに、非公式な意味でのみ類似したプロキシタスクを使用するのが一般的である。
ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価することで、このミスマッチを補正する。
論文 参考訳（メタデータ） (2024-11-11T16:33:25Z) - A Transformer with Stack Attention [84.18399019794036]
本稿では,変圧器をベースとした言語モデルの拡張手法を提案する。
我々のスタックベースのアテンションメカニズムは、トランスフォーマーベースの言語モデルに組み込むことができ、モデルに解釈可能性のレベルを追加することができる。
スタックベースのアテンション機構の追加により、トランスフォーマーは、決定論的文脈自由言語をモデル化できるが、全てではない。
論文 参考訳（メタデータ） (2024-05-07T17:47:57Z) - Masked Hard-Attention Transformers 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) - Shapley Head Pruning: Identifying and Removing Interference in
Multilingual Transformers [54.4919139401528]
言語固有のパラメータを識別・解析することで干渉を減らすことができることを示す。
固定モデルから同定された注目ヘッドを除去することで、文分類と構造予測の両方において、ターゲット言語の性能が向上することを示す。
論文 参考訳（メタデータ） (2022-10-11T18:11:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。