論文の概要: Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly
the Star-Free Languages
- arxiv url: http://arxiv.org/abs/2310.13897v2
- Date: Thu, 18 Jan 2024 02:31:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-19 19:59:52.072727
- Title: Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly
the Star-Free Languages
- Title(参考訳): 仮面型ハードアテンション変換器とブールRASPがスターフリー言語を正確に認識する
- Authors: Dana Angluin, David Chiang, and Andy Yang
- Abstract要約: 我々は、注意力と厳密な将来のマスキングを備えたトランスフォーマーエンコーダについて検討する。
これらのネットワークによって認識される言語のクラスは、まさにスターフリー言語であることを示す。
- 参考スコア(独自算出の注目度): 7.938342455750221
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider transformer encoders with hard attention (in which all attention
is focused on exactly one position) and strict future masking (in which each
position only attends to positions strictly to its left), and prove that the
class of languages recognized by these networks is exactly the star-free
languages. Adding position embeddings increases the class of recognized
languages to other well-studied classes. A key technique in these proofs is
Boolean RASP, a variant of RASP that is restricted to Boolean values. Via the
star-free languages, we relate transformers to first-order logic, temporal
logic, and algebraic automata theory.
- Abstract(参考訳): コンバータエンコーダ(すべての注意が正確に1つの位置に集中している)と厳密な将来のマスキング(各位置が左の位置に厳密にしか入らない)について検討し、これらのネットワークで認識される言語のクラスがまさにスターフリー言語であることを証明した。
位置埋め込みの追加は、認識された言語のクラスを他のよく研究されたクラスに増加させる。
これらの証明の主要なテクニックは、Boolean値に制限されたRASPの亜種であるBoolean RASPである。
スターフリー言語を通じて、トランスフォーマーを一階述語論理、時相論理、代数的オートマトン理論に関連付ける。
関連論文リスト
- Theoretical Analysis of Hierarchical Language Recognition and Generation by Transformers without Positional Encoding [32.01426831450348]
因果マスキングと開始トークンによってトランスフォーマーは階層構造内の位置情報と深さを計算することができることを示す。
位置エンコーディングのないトランスフォーマーは階層型言語を生成することができることを示す。
論文 参考訳(メタデータ) (2024-10-16T09:56:01Z) - Extracting Finite State Machines from Transformers [0.3069335774032178]
機械的解釈可能性の観点から正規言語で訓練された変圧器の訓練可能性について検討する。
有限個の記号が状態を決定するとき, 変圧器の訓練性に対して, より強い下界を経験的に見出す。
機械的な洞察により、1層トランスフォーマーが優れた長さの一般化で学習できる正規言語を特徴付けることができる。
論文 参考訳(メタデータ) (2024-10-08T13:43:50Z) - A Transformer with Stack Attention [84.18399019794036]
本稿では,変圧器をベースとした言語モデルの拡張手法を提案する。
我々のスタックベースのアテンションメカニズムは、トランスフォーマーベースの言語モデルに組み込むことができ、モデルに解釈可能性のレベルを追加することができる。
スタックベースのアテンション機構の追加により、トランスフォーマーは、決定論的文脈自由言語をモデル化できるが、全てではない。
論文 参考訳(メタデータ) (2024-05-07T17:47:57Z) - Towards Lightweight Transformer via Group-wise Transformation for
Vision-and-Language Tasks [126.33843752332139]
本稿では,LW-Transformerと呼ばれる視覚・言語タスクのための,普遍的で軽量なトランスフォーマーに対するグループワイズ変換を提案する。
LW-Transformerを一組のTransformerベースのネットワークに適用し、3つの視覚・言語タスクと6つのベンチマークデータセットで定量的に測定する。
実験の結果,LW-Transformerは多数のパラメータや計算を節約しながら,視覚・言語タスクのためのトランスフォーマーネットワークと非常に競合する性能を発揮することがわかった。
論文 参考訳(メタデータ) (2022-04-16T11:30:26Z) - On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。
硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
論文 参考訳(メタデータ) (2021-06-30T17:09:47Z) - Thinking Like Transformers [64.96770952820691]
本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。
RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。
ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
論文 参考訳(メタデータ) (2021-06-13T13:04:46Z) - Scalable Transformers for Neural Machine Translation [86.4530299266897]
トランスフォーマーは、そのキャパシティとシーケンス生成の並列トレーニングのため、ニューラルネットワーク翻訳(NMT)で広く採用されている。
本稿では,異なるスケールのサブトランスフォーマーを自然に含み,パラメータを共有できる,スケーラブルなトランスフォーマーを提案する。
スケーラブルトランスフォーマーのトレーニングの難しさに対処する3段階のトレーニングスキームが提案されている。
論文 参考訳(メタデータ) (2021-06-04T04:04:10Z) - Transformer visualization via dictionary learning: contextualized
embedding as a linear superposition of transformer factors [15.348047288817478]
我々は,変圧器因子の線形重ね合わせとして,辞書学習を用いて「ブラックボックス」を開くことを提案する。
可視化により,変換因子によって得られた階層的意味構造を実演する。
この視覚化ツールによって、トランスフォーマーネットワークの動作に関するさらなる知識と理解が得られればと思っています。
論文 参考訳(メタデータ) (2021-03-29T20:51:33Z) - Position Information in Transformers: An Overview [6.284464997330884]
本稿では,トランスフォーマーモデルに位置情報を組み込む共通手法の概要について述べる。
本調査の目的は,Transformerにおける位置情報が活発で広範な研究領域であることを示すことである。
論文 参考訳(メタデータ) (2021-02-22T15:03:23Z) - On the Ability and Limitations of Transformers to Recognize Formal
Languages [9.12267978757844]
カウンター言語のサブクラスのためのトランスフォーマーの構築を提供する。
トランスフォーマーはこのサブクラスでうまく機能し、それらの学習メカニズムは我々の構成と強く相関している。
おそらく、LSTMとは対照的に、Transformerはパフォーマンスが低下する正規言語のサブセットでのみ動作する。
論文 参考訳(メタデータ) (2020-09-23T17:21:33Z) - Segatron: Segment-Aware Transformer for Language Modeling and
Understanding [79.84562707201323]
本稿では,セグメンテーション対応トランスフォーマー(Segatron)を提案する。
本稿ではまず,Transformerベースの言語モデルであるTransformer-XLにセグメント認識機構を導入する。
WikiText-103データセット上で17.1パープレキシティを実現することにより,Transformer-XLベースモデルと大規模モデルをさらに改善できることがわかった。
論文 参考訳(メタデータ) (2020-04-30T17:38:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。