論文の概要: Logical Languages Accepted by Transformer Encoders with Hard Attention
- arxiv url: http://arxiv.org/abs/2310.03817v1
- Date: Thu, 5 Oct 2023 18:13:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 19:22:56.972542
- Title: Logical Languages Accepted by Transformer Encoders with Hard Attention
- Title(参考訳): ハードアテンションのあるトランスフォーマーエンコーダが受け入れる論理言語
- Authors: Pablo Barcelo, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir
Podolskii
- Abstract要約: 我々は,(1)UHAT(Unique Hard Attention Transformers)と(2)AHAT(Average Hard Attention Transformers)の2つの自己注意機構に注目した。
UHATエンコーダは、回路複雑性クラス$sf AC0$内の言語のみを認識することが知られている。
AHATエンコーダは$sf AC0$以外の言語を認識できるが、その表現力はより大きな回路複雑性クラス$sf TC0$、すなわち$sf AC0$にある。
- 参考スコア(独自算出の注目度): 45.14832807541816
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We contribute to the study of formal languages that can be recognized by
transformer encoders. We focus on two self-attention mechanisms: (1) UHAT
(Unique Hard Attention Transformers) and (2) AHAT (Average Hard Attention
Transformers). UHAT encoders are known to recognize only languages inside the
circuit complexity class ${\sf AC}^0$, i.e., accepted by a family of poly-sized
and depth-bounded boolean circuits with unbounded fan-ins. On the other hand,
AHAT encoders can recognize languages outside ${\sf AC}^0$), but their
expressive power still lies within the bigger circuit complexity class ${\sf
TC}^0$, i.e., ${\sf AC}^0$-circuits extended by majority gates. We first show a
negative result that there is an ${\sf AC}^0$-language that cannot be
recognized by an UHAT encoder. On the positive side, we show that UHAT encoders
can recognize a rich fragment of ${\sf AC}^0$-languages, namely, all languages
definable in first-order logic with arbitrary unary numerical predicates. This
logic, includes, for example, all regular languages from ${\sf AC}^0$. We then
show that AHAT encoders can recognize all languages of our logic even when we
enrich it with counting terms. We apply these results to derive new results on
the expressive power of UHAT and AHAT up to permutation of letters (a.k.a.
Parikh images).
- Abstract(参考訳): 我々はトランスフォーマーエンコーダで認識できる形式言語の研究に貢献する。
本研究では,(1)UHAT(Unique Hard Attention Transformers)と(2)AHAT(Average Hard Attention Transformers)の2つの自己注意機構に着目した。
UHATエンコーダは回路複雑性クラス${\sf AC}^0$内の言語のみを認識することが知られている。
一方、ahatエンコーダは${\sf ac}^0$)以外の言語を認識できるが、その表現力は依然として、多数派ゲートによって拡張された${\sf ac}^0$-circuits というより大きな回路複雑性クラスである${\sf tc}^0$ にある。
まず、UHATエンコーダでは認識できない${\sf AC}^0$-言語が存在するという負の結果を示す。
正の面では、UHATエンコーダは${\sf AC}^0$-Languageの豊富な断片、すなわち任意の単項数値述語を持つ一階述語論理で定義可能な全ての言語を認識できることを示す。
この論理には、例えば${\sf ac}^0$の全ての正規言語が含まれる。
次に、AHATエンコーダは、数項で拡張しても、論理の全ての言語を認識できることを示す。
これらの結果を用いて,UHAT と AHAT の表現力の新たな成果を文字の置換(パリカー画像)に導出する。
関連論文リスト
- Chain of Code: Reasoning with a Language Model-Augmented Code Emulator [119.0018170558366]
言語モデル(LM)はコード記述を活用して思考の連鎖推論を改善する。
我々は、LMコード駆動推論を改善するシンプルな、そして驚くほど効果的な拡張であるChain of Code (CoC)を提案する。
CoCは、大小のモデルと同様の規模でスケールし、LMが「コードを考える」ことで正しく答えられるような推論の問題の範囲を広げる。
論文 参考訳(メタデータ) (2023-12-07T17:51:43Z) - Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly
the Star-Free Languages [7.938342455750221]
我々は、注意力と厳密な将来のマスキングを備えたトランスフォーマーエンコーダについて検討する。
これらのネットワークによって認識される言語のクラスは、まさにスターフリー言語であることを示す。
論文 参考訳(メタデータ) (2023-10-21T03:26:39Z) - The Expressive Power of Transformers with Chain of Thought [35.25166532364007]
実際には、トランスフォーマーの推論は、答える前に中間トークン列を生成および条件にすることで改善することができる。
答えはYESであるが、増加量は中間生成量に大きく依存する。
また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置し, 解解時間問題のクラスを正確に認識させる。
論文 参考訳(メタデータ) (2023-10-11T22:35:18Z) - Guess & Sketch: Language Model Guided Transpilation [61.24102712913847]
学習されたトランスパイレーションは、手作業による書き直しやエンジニアリングの取り組みに代わるものだ。
確率的ニューラルネットワークモデル(LM)は、入力毎に可塑性出力を生成するが、正確性を保証するコストがかかる。
Guess & Sketch は LM の特徴からアライメントと信頼性情報を抽出し、意味的等価性を解決するためにシンボリック・ソルバに渡す。
論文 参考訳(メタデータ) (2023-09-25T15:42:18Z) - Physics of Language Models: Part 1, Context-Free Grammar [61.05762942335984]
我々は、GPTのようなHOW生成言語モデルを研究するための制御実験を設計し、文脈自由文法(CFG)を学ぶ。
難しい(長くあいまいな)CFGであっても、事前学習したトランスフォーマーは、ほぼ完璧な精度と印象的な多様性で文を生成することができる。
論文 参考訳(メタデータ) (2023-05-23T04:28:16Z) - Verified Reversible Programming for Verified Lossless Compression [11.020543186794459]
ロスレス圧縮の実装は通常、エンコーダとデコーダの2つのプログラムを含む。
我々は、非対称数値システム(ANS)に基づく圧縮手法のかなりのクラスが、エンコーダとデコーダの間で共有構造を持つことを観察する。
私たちはAgdaに埋め込まれた小さな可逆言語「Flipper」を実装しました。
論文 参考訳(メタデータ) (2022-11-02T16:39:41Z) - LAE: Language-Aware Encoder for Monolingual and Multilingual ASR [87.74794847245536]
言語固有の情報を混在させることにより,両状況に対処する新しい言語対応エンコーダ (LAE) アーキテクチャを提案する。
マンダリン・イングリッシュ・コードスウィッチ音声を用いた実験により,LAEはフレームレベルで異なる言語を識別できることが示唆された。
論文 参考訳(メタデータ) (2022-06-05T04:03:12Z) - Formal Language Recognition by Hard Attention Transformers: Perspectives
from Circuit Complexity [1.0159205678719043]
文字列アクセプタと見なされるUHATとGUHAT変換器は、複雑性クラスAC$0$の形式言語しか認識できないことを示す。
対照的に、非AC$0$言語 MAJORITY と DYCK-1 は AHAT ネットワークによって認識可能であり、AHAT が UHAT と GUHAT が認識できない言語を認識できることを意味する。
論文 参考訳(メタデータ) (2022-04-13T19:25:42Z) - Safety Synthesis Sans Specification [5.874782446136914]
ハードウェアおよびソフトウェア検証の多くの状況において、これは自然な問題である、と私たちは主張する。
この問題に対する学習アルゴリズムを考案し、その時間とクエリの複雑さが、対象言語のランク、不適合性尺度、与えられた反例の最大長に関するものであることを示す。
論文 参考訳(メタデータ) (2020-11-15T21:13:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。