On the Ability and Limitations of Transformers to Recognize Formal Languages

https://arxiv.org/abs/2009.11264
EMNLP 2020

トランスフォーマーは、多くのNLPタスクでリカレントモデルに取って代わりました。しかし、異なる構文特性をモデル化する能力の違いについては、まだほとんど知られていません。過去の研究では、LSTMは通常の言語で非常によく一般化し、対言語との密接な関係があることが示唆されている。本研究では、このような言語をモデル化するTransformerの能力と、その際の各構成要素の役割を体系的に研究する。まず、n-ary Boolean Expressions、Dyck-1、およびその一般化などのよく研究されている言語を含む、対抗言語のサブクラスに対するTransformerの構成を提供する。実験の結果、Transformerはこのサブクラスに適しており、その学習されたメカニズムは我々の構造と強く相関していることがわかりました。驚くべきことに、LSTMとは対照的に、Transformerは通常の言語のサブセットでのみ良好に動作し、よく知られている複雑さの尺度に基づいて言語を複雑にすると性能が低下する。また、自己注意メカニズムが特定の行動をモデル化する際に果たす役割や、位置符号化スキームがモデルの学習能力や汎化能力に与える影響についても分析した結果、洞察を得た。

https://github.com/satwik77/Transformer-Formal-Languages

1 はじめに

Transformer（Vaswaniら、2017）は自己注意に基づくアーキテクチャであり、さまざまなNLPタスクにおいて最先端の結果をもたらしてきました（Devlinら、2019；Liuら、2019；Radfordら、2018）。事前学習されたモデルの内部構造と中間表現を理解するために多くの努力が払われており、Rogersら（2020）は最近の調査である。しかし、シーケンスモデリングに関連するさまざまな動作をモデル化するための実用的な能力についての理解は、まだ浅いものです。一方で、LSTMのようなリカレントニューラルモデルの能力を理解しようとする研究が長く続いている（Hochreiter and Schmidhuber, 1997）。最近では、Weiss et al. (2018), Suzgun et al. (2019a) が、LSTMが計数のような動作を学習することで、Dyck-1やa n b nなどのカウンタ言語を認識できることを示しました。 Suzgunら（2019a）は、LSTMがShuffle-Dyckとも呼ばれる複数のDyck1言語のシャッフルを認識できることを示した。 Transformerベースのモデル（GPT-2やBERTなど）は、再帰性を備えておらず、ステップごとに計算を一から始めるため、カウンターを直接維持することができないのです。さらに、理論的にはRNNは任意の正規言語を有限の精度で認識できることが知られており、実用的な環境ではLSTMがこのタスクによく機能します。しかし、Transformerがこのような特性を実用的な環境でモデル化できるかどうかは未解決の問題です。

現在、NLPタスクでTransformerが主流になる前は、LSTMのようなRNNベースのリカレントモデルが主流であり、その計算能力は何十年も前から研究されてきた、例えば(Kolen and Kremer, 2001)。本研究では、Transformerが特定の対抗言語や正規言語上で表現、学習、一般化する能力を調査する。形式言語は、ネットワークが異なる構文特性を単独でモデル化する能力と、その際の個々のコンポーネントの役割を研究するための制御された設定を提供してくれる。最近の研究では、LSTMとカウンターオートマトンの間に密接な関係があることが示されています。そこで我々は、LSTMの能力がよく理解されている言語をモデル化するTransformerの能力を理解しようとする。 まず、TransformerがShuffle-Dyckやn-ary Boolean Expressionなどの特定のカウンタ言語を認識するのに十分な表現力を持っていることを示す。 そして、このようなカウンター言語に対するモデルの学習能力と一般化能力を広範囲に評価し、モデルがこのような言語に対してよく一般化することを見出した。これらのモデルの中間表現を可視化すると、我々の提案した構造と強い相関関係があることがわかる。 Transformersは、一般的に使用されているいくつかの対抗言語ではうまく一般化できるが、他の言語を認識する能力には限界があることが観察された。トランスフォーマーとLSTMの性能は、通常の言語（対抗言語のサブクラス）において明確なコントラストを示しています。その結果、LSTMとは対照的に、Transformerは、周期性のモデル化やモジュラーカウントを含む言語、さらにはDyck-1の単純なstar-free variantなどでは、限られた性能しか発揮できないことがわかったのです。本研究では、自己注意、位置符号化、層数という異なる構成要素の重要性についての洞察を得た。また、位置マスキングと位置エンコーディングは、どちらも一般化と訓練に役立つが、その方法は異なることも明らかになった。私たちは、慎重に選ばれた25以上の形式言語で広範囲な実験を行います。我々の結果は、正確な意味で非常に単純であり、特にリカレントモデルにとっては容易である実用的なサイズの問題に対するTransformerの限界を初めて示したものである。

2 Related Work

Suzgun et al. (2019b); Sennhauser and Berwick (2018); Skachkova et al. (2018) などの数多くの作品が、形式的な言語上で経験的に分析することで、リカレントモデルのcapabil itiesと内部動作を理解しようとしています。 Weissら（2018）は、LSTMがカウンターオペレーションをシミュレートできることを示し、a n b nやa n b n c nなどの言語を認識する実用的な能力を探りました。 Suzgunら（2019a）はさらに、LSTMがDyck-1とShuffle-Dyckを認識することを学習でき、k-カウンターマシンの動作をシミュレートできることを示しました。リカレントモデルの理論的な接続はカウンター言語で確立されている(Merrill, 2019; Merrill et al., 2020; Merrill, 2020)。また、RNNベースのモデルが規則的な言語を認識できることが示されており（Kolen and Kremer, 2001; Korsky and Berwick, 2019）、規則的な言語を認識するように訓練されたRNNからDFAを抽出する取り組みも行われている（Weiss et al., 2019; Wang et al., 2018b; Michalenko et al. トランスフォーマーについては、そのような研究は知られていません。最近、研究者たちは、中間層に含まれる情報など、実用的なNLPタスクで訓練されたTransformerのさまざまな側面を経験的に分析しようとしています(Rogers et al., 2020; Reif et al., 2019; Warstadt et al., 2019)。 Voitaら（2019）は、異なるタイプの注意ヘッドの役割を研究しました。 Yangら（2019）；Tsaiら（2019）は、異なる位置符号化スキームを介して順序情報を学習するモデルの能力を検討しました。これらを補完するために、私たちの研究は、言語構造のモデリングに関連する可能性のある特定の行動をモデル化するTransformerの能力を分析することに焦点を当てています。最近では、TransformerがTuring-completeであること(Perez et al. ´ , 2019; Bhattamishra et al., 2020)や、任意の精度が与えられたsequence-to-sequence関数の普遍的な近似器であること(Yun et al., 2020)が示されている。 Hahn (2020) は、Transformer が言語 Parity と Dyck-2 を認識できないことを示している。しかし、これらの結果は非常に長い単語にしか適用されず、実用的なサイズの入力への適用性は明らかではない（実際、実用的なサイズの入力では異なる挙動が見られるだろう）。また、これらの結果はTransformerの表現力に関するものであり、学習能力や一般化能力には当てはまらない。このように、Transformerが形式言語をモデル化する能力については、さらなる調査が必要である。

3 定義

BERTやGPTなどの一般的な事前学習済みのLMモデルで使用されているTransformerを、オリジナルのseq-to-seqアーキテクチャのエンコーダのみのモデルとみなします（Vaswani et al, 2017）。エンコーダは、それぞれ2つのブロックを持つ複数の層で構成されています。 (1)自己注意ブロック、(2)フィードフォワードネットワーク(FFN)です。 1 ≤ i ≤ nにおいて，i番目のステップでは，モデルはシーケンスs1, s2, ... ... , siを入力とする。 si (s∈Σ) を入力とし，出力ベクトル yi を生成します．各入力siは，関数fe : Σ → R dmodelを用いて，まず埋め込みベクトルに変換され，通常は何らかの位置符号化が加えられて，最終的な入力ベクトルxiが生成される．エンベッディング次元 dmodelは、ネットワークの中間ベクトルの次元でもある。 i ≥ 1でXi := (x1, ... , xi)とします。自己保持ブロックでは、入力ベクトルは線形変換Q(-)、K(-)、V(-)を受け、それぞれ対応するクエリ、キー、値のベクトルが得られます。セルフアテンション・メカニズムは、入力として、クエリ・ベクトルQ（xi）、キー・ベクトルK（Xi）、バリュー・ベクトルV（Xi）を受け取ります。 Att(Q(xi), K(Xi), V (Xi))で示されるアテンションヘッドは、ベクトルai = Pi j=1 αjvj , ここで、(α1, . . . , αi) = softmax(<Q(xi), K(x1)>, . . ... ,<Q(xi), K(x1)>, . ,<Q(xi), K(xi)>)である。 ziで示される層の出力は、zi = O(ai)で計算されます。ここで、1 ≤ i ≤ n、O(-)は通常、ReLU活性化を持つFFNを示します。完全なL層モデルは，上述の単層モデルを繰り返し適用したもので，その最終層でベクトルz L iを生成する（Lは最終層を示す）．最終的な出力は，ベクトルz L iに何らかの正規化またはFFNを施した投影層を適用することで得られ，yi = F(z L i )で表される．ネットワークの学習プロセスを支援するために、残差接続と層の正規化も適用されます。 LMの設定では、Transformerが入力を順次処理する際に、各入力シンボルは自分自身と前の入力の上にのみ出席でき、それに続く入力にはマスキングが適用されます。なお、マスクされた自己注視を介してこのような形で位置情報を提供することは、位置マスキングとも呼ばれます（Vaswani et al. 位置エンコーディングと位置マスキングのないTransformerモデルは、orderinsensitiveです。

3.1 形式言語

形式言語とは、プログラミング言語や自然言語の構文を抽象化したモデルで、認知言語学にも関連しています。例えば、Jager and ¨ Rogers (2012); Hahn (2020) およびその参考文献があります。

カウンター言語。

決定論的カウンターオートマトン（DCA）が認識する言語であり、有限個のカウンタを持つDFAです（Fischer et al. カウンタは一定の値で増加／減少させることができ，0にリセットすることもできる（詳細はApp.B.1）．シーケンスモデルの研究によく使われるカウンタ言語は，Dyck-1，a n b n，a n b n c n である．リカレントモデルがこれらの言語を認識できるかどうか、またそのメカニズムを調べた作品がいくつかあります。我々は、Shuffle-Dyck（Suzgun et al. (2019a)で使用されている）やn-ary Boolean Expressionsなどのカウンター言語のいくつかの一般的な形式と同様に、これらの言語を分析に含める。アルファベットΣ = {[, ]}上の言語Dyck-1は、導出規則S → [ S ] | SS | で定義されるバランスのとれた括弧で構成される。 Shuffle-DyckはDyck-1言語のシャッフルを含む言語のファミリーである。 Shuffle-kはk個のDyck-1言語をシャッフルしたもので、k個の異なるタイプの括弧を含み、各タイプの括弧はバランスがとれていることが要求されるが、その相対的な順序には制約がない。例えば，アルファベットΣ = {[, ],(,)}上のShuffle-2言語は，単語([)] and [(]))を含みますが， ])[()は含みません．また，n-ary Boolean Expressions (ここではBoolExp-n)を考えます．これは，演算子の数とそれらの個々のアリティによってパラメータ化された有効なBoolean式(前置記法)の言語のファミリーです．例えば、単項演算子∼と二項演算子∧を持つ式は、'∧ ∼ 01'という単語を含みますが、'∼ 10'という単語は含みません（正式な定義はApp.Bにあります）。なお、Dyck-1 や a n b n のような言語は文脈自由ですが、Dyck-1 や a n b n を認識するには、カウンタが1つの DCA で十分です。同様に、2つのシングルターンカウンターを持つDCAは、a n b n c nを認識することができます。一方、Shuffle-Dyckを認識するには、複数のマルチターンカウンタが必要で、あるタイプのブラケットに対して、対応するカウンタが1だけインクリメントまたはデクリメントされます。同様に、BoolExpの認識には、演算子に応じてカウンタが更新される1カウンタDCAが必要です。 3項演算子はカウンタを2（＝アリティ-1）だけ増加させ、1項演算子はカウンタを0だけ増加させます。

正規言語。

正規言語は、形式言語の中でも最も研究されているクラスであり、対の言語のサブクラスを形成しています1 。正規言語は、星のない言語と星のない言語の2つのサブクラスに分かれています。

スターフリー言語は、union、intersection、complementation、concatenationの各演算子で形成される正規表現で記述できますが、Kleene star（＊）は記述できません。星なし言語は、正規言語と同様に、代数的、論理的、その他の複数の特徴付けが驚くほど豊富で、現在も活発に研究されています（McNaughton and Papert, 1971; Jager and Rogers ¨ , 2012）。富田文法は、正規言語の中でも特に単純な部類に属し、一階論理で定義可能であることや、モジュラーカウントを必要とする言語を表現できないことなど、単純さの概念を様々な方法で精密化することができます。我々はまず、リカレントモデルの評価や訓練されたリカレントモデルからDFAを抽出するための一般的なベンチマークである、小さなサイズのDFAで表現可能な7つの正規言語を含むTomita文法を検討する（例えば、Wang et al (2018a)参照）。富田文法には、星なし言語と非星なし言語が含まれています。さらに、(aa) ∗ , Parity, (abab) ∗ などのいくつかの非スターフリー言語を調査する。

Parityは{0, 1}上の単語で、1の数が偶数のものを含みます。同様に、(aa) ∗ や (abab) ∗ では、モデリングの周期性が必要です。一方、一見似ている言語の(ab) ∗ はスターフリーです。 (ab) ∗ = (b∅^c + ∅^ca + ∅^caa∅^c + ∅^c bb∅^c )^c 、ここで、- cは集合の補完を表すので、∅^c = Σ∗ となります。

スター・フリー言語のドット・デプスは，スター・フリー正規表現で必要とされる入れ子式の連結性または順序性の尺度である（正式な定義はApp.B.2にある）。星のない言語のファミリーD0, D1, ...を定義する。 n ≥ 0の場合、Σ = {a, b}上の言語Dnは帰納的に以下のように定義される。 Dn = (aDn-1b) ∗ ここで、D0 = eps, 空の言葉である。したがって、D1 = (ab) ∗ 、D2 = (a(ab) ∗ b) ∗ となります。言語Dnはdot-depth nを持つことが知られています。考慮されたすべての言語のリストとその定義はApp.B.にあります。

4 表現力の結果

命題 4.1.

Shuffle-Dyck言語群を認識できる第3節で定義されたTransformerが存在する。

証明します。

s1, s2, ... ..., snをアルファベット上の列w∈Shuffle-kとする。 s1, ... , snはアルファベットΣ = {[0, ... ... , [k-1, ]0, ] k-1}以上の配列w∈Shuffle-kを表す Shuffle1という言語はDyck-1と等価である。任意のShuffle-k言語について、dmodel = 2kのモデルを考える。ここで、埋め込み関数feは以下のように定義される。開き括弧[j where, 0 ≤ j < kの各タイプに対して，ベクトルfe([j ) は，添字2jと2j + 1でそれぞれ+1と-1の値を持つ。残りの添字では値0となる．同様に、閉じたブラケットごとに、ベクトルfe(]j )は、添字2jと2j + 1で値-1と+1を持ち、それ以外の添字では値0を持ちます。 Dyck-1の場合は、fe([) = [+1, -1]T、fe(]) = [-1, +1]Tとなります（dmodel = 2の場合）。ここでは、単層のTransformerを使用しており、キーベクトルの線形変換に対応する行列をnull行列、つまりすべてのxに対してK(x)=0に設定しています。 Q(-)とV(-)に対応する行列はIdentityに設定されています。したがって、Att(Q(xi), K(Xi), V (Xi)) = 1 / i Sum^i{j=1} vj for 1 ≤ i ≤ n. したがって、i番目のステップで、自己注目ブロックは、添字2jに値σ([j )-σ(]j) / i、添字2j + 1に値σ( ]j -σ([j ) / iを持つベクトルaiを生成し、ここでσ(s)は記号sの出現回数を示す。

例えば、Dyck-1では、最初のi個の入力に、σ([)の開カッコとσ(])の閉カッコがある場合、ai = [ σ([)-σ(]) / i , σ(])-σ([) / i ]^T となります。ここでi = σ([) + σ(])です。 aiにおいて、σ([)-σ(])は、インデックスiにおけるDyck-1単語の深さ（開き括弧と閉じ括弧の数の差）を表しています。したがって、1つ目の座標は、Dyck-1ワードの深さとそのインデックスでの長さの比であり、もう1つの座標はそのマイナスである。

次に、ベクトルaiに対してReLU活性化による単純なFFNを適用します。ベクトルzi = ReLU(I a_i). ベクトルziの偶数添字は，対応する型の開括弧の数が閉括弧の数よりも大きければ，非零になる。奇数の添字についても同様のことが言えます。したがって、ある単語がShufflekであるためには、ベクトルziの奇数添字の値は決してゼロであってはならず、最後のステップではすべての座標の値をゼロにして、開きカッコと閉じカッコの数が同じになるようにしなければならないのである。

入力シーケンスs1, s2, ... ..., snに対して、モデルはziを生成します。 snに対して，モデルは指定された構造に基づいてz1, ... ... , znを生成する．単語wは，zi,2j+1 = 0 for all 1 ≤ i ≤ n, 0 ≤ j < k and zn = 0 であれば，言語Shuffle-kに属し，そうでなければ，言語に属さない。これは、与えられたシーケンスを分類するために、自己注意とフィードフォワードネットワークの層を追加することで簡単に実装できる。//

上記の構成で精度のボトルネックとなるのは、ベクトルaiにσ([)-σ(]) / iという形式の値を計算することである。 rビットの有限精度の設定では、これはrの指数関数的な値まで計算できるので、我々の証明は、TransformerがShuffle-Dyckの言語をビット数の指数関数的な長さで認識できることを伴う。同様の論理で、TransformerはBoolExp-nという言語群を認識できることも示すことができる（Lemma C.2参照）。このモデルでは、演算子のアリティに応じて値ベクトルを設定することで、各ステップにおける基礎となるオートマトンのカウンタ値と入力の長さの比を、自己注意によって得ることができます。上記の構成は、これらの言語ファミリーに特有のものですが、付録では、より一般的だが制限されたカウンター言語のサブクラスに対する証明を提供しています（Lemma C.1を参照）。上記の構成は、トランスフォーマーが関連する計算を間接的に行うことで、どのようにこのような言語を認識できるかを説明するためのものである。後で説明するように、これは訓練されたモデルがどのようにそのような言語を認識するかを解釈するのにも役立ちます。

5 実験設定

本実験では，カウンタ言語と通常言語の階層に属する27の形式言語を対象とした．各言語について，固定長の窓からサンプルを生成して学習セットとし，異なる長さの窓から複数の検証セットを生成してモデルの汎化能力を評価した．ほとんどの言語では，長さ1から50までの10k個のサンプルをトレーニングセットとして生成し，長さが異なるが連続した窓を持つサンプルを含む複数の検証セットを作成した．各検証セットのサンプル数は2kで，各ウィンドウの幅は約50である． (ab)∗やa n b n c nのように，与えられた長さの窓の中に正の例がほとんどない言語では，学習窓の中のすべての正の例で学習を行います。同様に，各検証セットには，特定の範囲で可能なすべての言語の文字列が含まれている。付録の表6は，我々が検討した27の形式言語のデータセットの統計を示している2．ソースコードは，https://github.com/satwik77/Transformer-Formal-Languages で公開しています．

5.1 トレーニングの詳細

Gers and Schmidhuber (2001)で紹介され、Suzgun et al. (2019b,a)で使用されている文字予測タスクでモデルをトレーニングします。 LMの設定と同様に、モデルには与えられた言語からの正のサンプルのみが提示される。入力シーケンスs1, s2, . . ... , snに対して，モデルはシーケンスを受け取る． sn を受け取ると，モデルは配列 s1, . . . . . , si を 1 ≤ i ≤ n の各ステップ i で受け取り，(i + 1)番目のステップで次の合法/有効な文字セットを予測することがモデルの目的である．これ以降、文字予測タスクを完璧に実行できるモデルを言語認識できると言います。

このモデルでは，言語の語彙に含まれる各文字に，次のタイムステップでの有効性に対応する確率を割り当てている．出力は，各座標が言語の語彙の中の文字に対応するk-hotベクトルで表すことができます．出力は，モデルが各文字に割り当てたスコアにシグモイド活性化を適用して計算される． Suzgunら（2019b,a）に従い，モデルの学習目的は，予測された確率とk-hotラベルとの間の平均二乗誤差を最小化することである3。推論の際には，0.5の閾値を用いてモデルの予測値を得る。テストサンプルに対して、モデルの予測値が正しいとみなされるのは、各ステップでの出力が正しい場合のみです。すべてのステップで出力が正しい場合にのみ正しい予測が得られるため、これは比較的厳しい指標であることに注意してください。テストサンプルに対するモデルの精度は、正しく予測された全サンプルの割合です4。 Suzgunら（2019a）と同様に、我々はトレーニングセットを記憶することを防ぎ、モデルを視覚化することが可能なように、小さなサイズのモデルを考慮します。我々の実験では、最大4層、4ヘッド、中間ベクトルの次元が2～32以内のTransformを考慮します。また、様々なハイパーパラメータを用いて、モデルのチューニングを行いました。また、絶対的なエンコーディング、相対的なエンコーディング（Dai et al.、2019）、明示的なエンコーディングを行わずに位置マスキングのみを使用するなど、さまざまな方法で位置情報を提供することの影響を調べます。

6 対抗言語での結果

9つの対抗言語でモデルの性能を評価した．表1は，いくつかの代表的な言語に対する上述の異なるモデルの性能を示したものである．また、ベースラインとしてLSTMの性能も記載している。その結果、Shuffle-DyckやBoolExp-nなどの一般的な形式のカウンタ言語に対して、サイズの小さい（シングルヘッド、シングルレイヤー）Transformがうまく一般化できることがわかりました。驚くべきことに、この挙動は、ネットワークに明示的な位置エンコーディングの形が与えられておらず、位置情報がマスキングの形でしか得られない場合に観察された。位置エンコーディングを持つモデルの場合、より高い長さへの汎化能力がないのは、テスト時に受け取る位置エンコーディングの一部についてモデルが一度も学習されていないことが原因と考えられる。一方、位置エンコーディングの明示的な形式を持たないモデルは、タスクを実行する能力があれば、そのような問題の影響を受けにくく、様々なハイパーパラメータ設定の間でうまく一般化することがわかりました

6.1 自己注意の役割

4項の仮説を確認するために、Shuffle-2とBoolExp-3によく汎化する学習済みモデルの特定の属性を可視化する。 Shuffle-Dyckでは、自己注意のメカニズムにより、各ステップにおける入力の深さと長さの比率を計算することでシーケンスを認識します。 BoolExp-nでは、対応するカウンタの値を長さで割った値を計算することで、同様にタスクを達成することができます（Lemma C.2を参照）。興味深いことに、Shuffle-2で学習したモデルの自己注意ブロックの出力を可視化したところ、その要素が深さと長さの比と強い相関があることがわかりました。図2aに示すように、自己注意ブロックの出力ベクトルの異なる座標には、Shuffle-2言語の異なるカウンターに対応する計算が含まれています。 Shuffle-4言語で学習したモデルでも同様の動作が見られます（付録の図5を参照）。同様に、3つの演算子を持つブール式で学習したモデルを可視化してみると、その要素とカウンタ値と入力の長さの比に強い相関関係6があることがわかりました（図2b参照）。これは、このモデルが、我々の構築方法のように、必要な計算を間接的に実行することで、入力を認識することを学習していることを示している。また、どちらのモデルでも、自己注意ブロックの注意の重みは一様に分布していることがわかりました（付録の図4を参照）。さらに、開き括弧と閉じ括弧の埋め込みと値のベクトルを調べたところ、それぞれの座標は符号が逆で大きさが似ていることがわかりました。

Shuffle-Dyckとは対照的に、BoolExp-nでは、値ベクトルの要素の大きさは、対応するアリティに応じています。例えば、3項演算子の大きさは、1項演算子の大きさの（ほぼ）3倍でした（付録の図3を参照）。これらの観察結果は、私たちの構造と一致しています。このモデルは、カウンタの更新を決定するためにその値のベクトルを使用し、各ステップで、間接的な方法で最終的なカウンタの値の形を得るためにすべての値を集約していることを示しています。これは、各入力を受信する際にそのセル状態にそれぞれの更新を行うことで、より直接的にkカウンターの動作をシミュレートできるLSTMと補完的な関係にある（Suzgun et al.2019a）。

6.2 単層トランスフォーマーの限界

単層トランスフォーマーは、一般的に研究されているいくつかのカウンタ言語を容易に認識できることが確認されましたが、一方で、リセット操作を必要とするカウンタ言語については、必ずしもそうではありません。ここでは、Dyck-1言語の変形を定義します。 Reset-Dyck-1をアルファベットΣ={[, ], #}上で定義される言語とし、#はカウンタをリセットする記号を表す。 Reset-Dyck-1の単語はΣ ∗#vの形をしており、文字列vはDyck1に属している。機械はリセット記号#に出会うと、それまでの入力をすべて無視し、カウンタを0にリセットしてスタート状態にならなければならない。これは、位置マスキングのある単層自己注意ネットワークでは直接実装できないことを簡単に示すことができます（付録のLemma C.3）。符号化の有無にかかわらず、重要な制限は、単層ネットワークの場合、得点関数hQ(xn)、K(x#)iと、リセット記号に対応する値ベクトルが、それが否定（リセット）されることになっている先行入力に依存しないという事実です。多層ネットワークでは、リセットシンボルのスコアリング関数と同様に、値ベクトルが先行する入力に依存するため、同様の制限はありません。このような言語から生成されたデータを用いてモデルを評価したところ、単層ネットワークは2層のネットワークとは対照的に、うまく機能しないことがわかりました（表2）7 。一方，LSTMでは，リセット操作をforget gateでエミュレートすることができる．

7 一般的な言語での結果

まず、一般的なベンチマークである富田文法を調べます。 LSTMは7つの言語全てを完全に一般化するのに対し、Transformerは3つの言語（全て非星型言語）を一般化することができませんでした。なお、Tomita文法では、星のない言語はすべてdot-depthが1である。星のない言語を認識するには、周期性やモジュラーカウントなどのモデリング特性が必要である。そこで、(aa)∗やParityなどの最も単純な非星型言語を用いてモデルを評価した。このような言語では、LSTMは学習や汎化に一貫して失敗するのに対し、非常に小さなサイズのLSTMは完璧に動作することがわかりました。表4は、いくつかの非星のない言語での性能を示しています。 LSTMは、内部メモリと再帰8を利用することで、ここで検討したような単純な無星言語を容易に認識できることに注意してほしい。 しかし、内部メモリを使用せずに自己注意メカニズムによって同じタスクを行うことは、非常に自明ではなく、潜在的に不可能である。 (aa)∗やParityのような言語は、最も単純な非星型言語の一つであり、このような言語を認識する際の限界は、より多くの言語のクラスに引き継がれます。上記の結果は、星のない言語こそがTransformerで認識できる正規の言語であることを示唆しているかもしれません。次のセクションで説明するように、これはそうではありません。

7.1 位置エンコーディングの必要性

Transformerのアーキテクチャでは、ある種の言語を認識するのに限界があります。 Transformerは、位置のマスキングのみでタスクを実行できる場合はうまく一般化しているように見えますが、位置の明示的なエンコーディングがないと、ある種の言語を認識することができません。ここでは、項3.1で定義した星なし言語Dnのファミリーを考える。ここで、Dnの記号aとbは、Dyck-1の開括弧と閉括弧に相当する。 DnとDyck-1の認識の主な違いは、Dnの場合、入力が最大深度nに達したとき、モデルは次の文字がa（開括弧）は無効であると予測しなければならないのに対し、Dyck-1では開括弧は常に許可されていることである。我々は、位置マスキングのみのTransformerがDyck-1上でうまく一般化できるものの、n > 1の言語Dnを認識することができないことを示す。この限界は、モデルがaのみのシーケンスを受け取った場合、ソフトマックスベースの集約により、自己注意ブロックaiの出力は一定のベクトルとなり、フィードフォワードの出力も一定のベクトル、すなわちz1 = z2 = ... = znとなることを意味するという事実から生じる。 Dnのような言語の場合、入力がn個の連続したasで始まると、モデルはn番目のaとそれ以前のaを区別することができないため、モデルはDnという言語を認識することができません。この制限は、モデルに明示的な位置エンコーディングが与えられている場合には存在しない。言語Dnのインスタンスに位置情報を付与したTransformerを評価したところ、学習時と同じ長さの文字列であればある程度汎化できるが、それ以上の長さになると汎化できないことがわかった（表4）。

小さくて単純な自己注意ネットワークが、Dyck-1のような言語では非常によく汎化できるのに、star-freeのようなもっと単純なクラスに属する言語では限られた性能しか得られないというのは、驚くべきことかもしれません。同様に、(aa)∗ , は単項言語（アルファベットサイズは1）であるため、モデルは各ステップで常に同じ文字を受け取ることになります。したがって、位置マスキングのみのモデルでは、どのステップでも出力ベクトルが同じになり、(aa)∗ という言語を認識することができません。 Parityという言語では、入力単語に1しか含まれていない場合、タスクは(11)∗を認識することになるため、位置エンコーディングを持たないモデルでは、ネットワークの大きさに関わらず、非常に小さい長さであってもParityを認識することができません（Lemma C.4を参照）。順列不変のParityでは、非常に小さい長さであっても変換器が認識するためには位置の符号化が必要であることは驚きです。

7.2 カスタム位置エンコーディングの影響

ネットワークの能力と複雑さは、位置エンコーディングスキームに大きく依存する可能性がある。例えば、言語 (aa) ∗ の場合、自己注意ネットワークがそれを認識できるかどうかは、位置のエンコーディングにのみ依存します。標準的な絶対値と相対値の符号化方式で評価すると、このモデルは学習や一般化がうまくできないことがわかります。一方で、2の周期を持つcos(nπ)を位置の符号化に用いれば、自己注意メカニズムは容易に課題を達成できることが容易に示されますが、このような符号化を用いて経験的に評価した場合も同様に観察されます。しかし、(aaaa) ∗ のように周期性が4の言語では、同じ符号化は機能しません。表5は、エンコーディングの種類を変えた場合のモデルの性能を示しています。

固定長の学習可能な位置の埋め込みを用いた場合、得られた学習済みの埋め込みはcos(nπ)形式と非常によく似ているが、このような埋め込みは、より長い配列には使用できない。このことは、(Liu et al., 2020)のような学習データ中に見られない可変長の入力に外挿できる、より優れた学習可能な符号化スキームの必要性を提起している。 15種類以上の常用言語に関する実験によると、Transformerはドット深度1以内の星なし言語を一般化することができるが、それ以上のドット深度や非星なし言語のような複雑なクラスでは困難であることを示しているようだ。付録の表9に、検討したすべての正規言語の結果を示します。

8 考察

我々は、TransformerがShuffle-DyckやBoolean Expressionsのようなある種のカウンタ言語を、我々の提案した構造と同様の方法で容易に一般化できることを示した。我々の視覚化は、Transformerがいくつかの統計的な規則性に過度に適合するのではなく、一般化可能なメカニズムでこれを行うことを示唆しています。自然言語と同様に、ブール式は再帰的にネストされた階層的な構成要素で構成されている。 最近、Papadimitriou and Jurafsky (2020)は、Shuffle-Dyckのような形式言語でLSTMを事前学習すると、自然言語でのLM性能に移行することを示した。 同時に、我々の結果は、大規模な正規言語のクラスでLSTMと比較してTransformerの明らかな限界を示している。 明らかに、Transformerの性能と能力は、位置エンコーディングスキームや層の数などのアーキテクチャ構成要素に大きく依存している。 リカレントモデルは、カウンター言語や正規言語に適したオートマトンのような構造を持っていますが、自己注意ネットワークの構造は非常に異なっており、このことが今回の課題に対する能力を制限しているようです。私たちの研究は、いくつかの未解決の問題を提起しています。我々の結果は、Transformerはドット深度1のstar-free言語にはうまく一般化するが、それ以上の深度には対応できないという仮説と一致しています。この仮説を理論的にも経験的にも明らかにすることは魅力的な課題です。自然言語と形式言語におけるTransformerの性能の違いは、自然言語の複雑さと言語解析との関係について何を示しているのだろうか。 Hahn(2020)も参照）。もう一つの興味深い方向性は、Transformerのある修正や最近提案された変種が、形式言語での性能を向上させるかどうかを理解することです。正則言語や反則言語は自然言語のある側面をモデル化しますが、文脈自由言語は階層的な依存関係のような他の側面をモデル化します。我々の結果は、これらの言語にいくつかの示唆を与えますが、文脈自由言語に関する詳細な研究は今後の課題とします。

e4exp / paper_manager_abstract