論文の概要: 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 の表現力の新たな成果を文字の置換(パリカー画像)に導出する。
関連論文リスト
- Can Transformers Reason Logically? A Study in SAT Solving [17.15701291424892]
本研究では, LLMの論理的推論能力について, ブール満足度問題(SAT)の文脈で検討する。
まず,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いてSATを解くデコーダのみの変換器を構築する。
我々は、よく知られたDPLL SAT-solvingアルゴリズムにトレース等価性を示すことによって、その正当性を証明した。
論文 参考訳（メタデータ） (2024-10-09T21:01:52Z) - Extracting Finite State Machines from Transformers [0.3069335774032178]
機械的解釈可能性の観点から正規言語で訓練された変圧器の訓練可能性について検討する。
有限個の記号が状態を決定するとき, 変圧器の訓練性に対して, より強い下界を経験的に見出す。
機械的な洞察により、1層トランスフォーマーが優れた長さの一般化で学習できる正規言語を特徴付けることができる。
論文 参考訳（メタデータ） (2024-10-08T13:43:50Z) - Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
2種類のランダムな$n$-gram LMを学習するトランスフォーマーの能力について検討する。
例えば、$n$-gram LMに対する古典的な推定手法として、add-$lambda$ smoothing outperform transformerがある。
論文 参考訳（メタデータ） (2024-10-03T21:21:02Z) - CRUXEval-X: A Benchmark for Multilingual Code Reasoning, Understanding and Execution [50.7413285637879]
CRUXEVAL-Xコード推論ベンチマークには19のプログラミング言語が含まれている。
各言語に対して少なくとも600人の被験者で構成され、合計19Kのコンテンツ一貫性テストがある。
Pythonでのみトレーニングされたモデルでさえ、他の言語で34.4%のPass@1を達成することができる。
論文 参考訳（メタデータ） (2024-08-23T11:43:00Z) - Chain of Code: Reasoning with a Language Model-Augmented Code Emulator [115.16975276693267]
我々は、LMコード駆動推論を改善するシンプルながら驚くほど効果的な拡張であるChain of Codeを提案する。
キーとなるアイデアは、プログラム内のセマンティックなサブタスクを、インタープリタが明示的にキャッチできるフレキシブルな擬似コードとしてフォーマットすることを、LMに促すことである。
論文 参考訳（メタデータ） (2023-12-07T17:51:43Z) - Guess & Sketch: Language Model Guided Transpilation [59.02147255276078]
学習されたトランスパイレーションは、手作業による書き直しやエンジニアリングの取り組みに代わるものだ。
確率的ニューラルネットワークモデル(LM)は、入力毎に可塑性出力を生成するが、正確性を保証するコストがかかる。
Guess & Sketch は LM の特徴からアライメントと信頼性情報を抽出し、意味的等価性を解決するためにシンボリック・ソルバに渡す。
論文 参考訳（メタデータ） (2023-09-25T15:42:18Z) - Verified Reversible Programming for Verified Lossless Compression [11.020543186794459]
ロスレス圧縮の実装は通常、エンコーダとデコーダの2つのプログラムを含む。
我々は、非対称数値システム(ANS)に基づく圧縮手法のかなりのクラスが、エンコーダとデコーダの間で共有構造を持つことを観察する。
私たちはAgdaに埋め込まれた小さな可逆言語「Flipper」を実装しました。
論文 参考訳（メタデータ） (2022-11-02T16:39:41Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。