Theoretical Limitations of Self-Attention in Neural Sequence Models

トランスフォーマーは、NLPの新たな主力製品として登場し、様々なタスクで大きな成功を収めています。 LSTMとは異なり、トランスフォーマーは自己注意によって入力配列を処理します。これまでの研究では、階層構造を処理するための自己注意の計算能力には限界があることが示唆されていました。本研究では、形式言語をモデル化するための自己注意の計算能力を数学的に調査した。ソフトアテンションとハードアテンションの両方において、自己注意の計算能力には強い理論的限界があることを示し、入力の長さに応じて層や頭の数が増えない限り、周期的な有限状態の言語や階層構造をモデル化することはできないことがわかった。自己注意が実用的に成功していることや、言語学において階層構造が重要な役割を果たしていることを考えると、これらの限界は驚くべきものであり、理論言語学で典型的に想定される形式言語に対しては弱すぎるモデルでも、自然言語をうまく近似できることを示唆している。

1 はじめに

トランスフォーマーは，言語モデリング，機械翻訳，事前学習された文脈に基づく単語埋込みの作成などのタスクで最先端の成果を上げており，NLP の新たな主力製品となっています。トランスフォーマーは、再帰的な計算を行わず、自己注意に基づいて、ほぼ並列に計算を行います。これにより、非常に長い配列にも対応できるようになっています（Vaswaniら、2017年、Daiら、2019年、Childら、2019年）。その一方で、入力を逐次処理できないため、表現力が制限されることも指摘されています（Tranら、2018年、Dehghaniら、2019年、Shenら、2018a、Chenら、2018年、Haoら、2019年）。シーケンスモデルにとって困難だと考えられている側面の1つは、階層構造と再帰性です。階層構造は、自然言語、特にそのシンタックスをモデル化するために不可欠であると広く考えられている（Everaert et al.、2015）。その結果、多くの研究者が、文脈自由言語（例えば、Kalinke and Lehmann, 1998; Gers and Schmidhuber, 2001; Gruning, 2006; Weiss et al., ¨ 2018; Sennhauser and Berwick, 2018; Korsky and Berwick, 2019）や、階層構造を伴う言語現象（例えば、Linzen et al., 2016; Gulordava et al., 2018）を捉えるリカレントニューラルネットワークモデルの能力を研究している。変圧器は階層構造のモデル化においてLSTMほど強くないのではないかと示唆する実験的証拠もあるが（Tran et al.、2018）、分析研究では、変圧器ベースのモデルが十分な量の構文知識をエンコードすることが示されている（例えば、Clark et al.、2019；Lin et al.、2019；Tenney et al.、2019）。

本研究では、これらの問題を理論的な観点から検討し、完全に自己注意に基づいたモデルが、無制限の再帰を伴う階層構造を理論的にモデル化することができるかどうかを問いかける。具体的には、階層構造に不可欠と考えられる2つの計算を実行する能力を調べます。これは、非正規文脈自由言語の基本的な問題であり、DYCK 言語 (Chomsky and Schutzenberger, 1963) によって形式化されています。これは、論理式を評価する際の基本的な要素であり、ビット列のPARITYを評価するようなものです。これらの問題は、入力の長さに応じてパラメータの数や大きさが増加しない限り、自己注意のみに頼る変換器や類似のモデルでは解決できないことを示します。 これらの言語は、階層構造の基本的な構成要素を表すだけでなく、正規言語や文脈自由言語の大きなクラスを表しており、我々の結果は他の形式言語のクラスにも引き継がれることになります。つまり、今回の結果は、他の形式言語のクラスにも適用できるということです。したがって、今回の結果は、自己言及が有限状態の言語や文脈自由言語をモデル化する能力について、より一般的な制限をもたらすものです。

理論的な研究では、リカレントニューラルネットワークの力を深く研究してきましたが（例えば、Siegelman and Sontag, 1995; Bengio et al., 1994; Weiss et al., 2018; Miller and Hardt, 2019, Merrill, 2019）、自己注意の理論的な研究は最近始まったばかりです（Perez et al., ´ 2019; Hsieh et al., 2019）。私たちの研究は、自己注意の力の限界に関する最初の理論的な結果を提供します。異なる証明方法を用いて、ハードな注意の設定とソフトな注意の設定の両方の結果を提供します。我々の結果は、ハードアテンション設定で最も強く、活性化関数やパラメータノルムに関する更なる仮定なしに保持されます。ソフトな注意の設定では、実用的に使われている活性化関数の滑らかさを仮定しても、結果を得ることができる。関連する研究（第2節）を議論した後、自己注意（第3節）と、正規言語と文脈自由言語を表す2つの基本的な形式言語（第4節）を紹介する。そして、ハードアテンション（セクション5）またはソフトアテンション（セクション6）を用いて、自己注意がこれらの言語をモデル化できないことを証明する。最後に、我々の結果について議論する（セクション7）。

3 Self-Attention

ここでは、Vaswaniら（2017）に倣って、Transformersで使用されるself-attentionを定義しますが、我々の証明における議論を単純化するために表記を若干変更しています。入力x = x1 ... xnがあり、すべてのxiはある有限のアルファベットVから来ており、xnは配列の終わりの記号です。この入力は、ある埋め込みマップを使って、一連の入力埋め込みv1, ... ..., vnにエンコードされます。 vn は，埋め込みマップ V → R k を用いて，一連の入力埋め込みにエンコードされる．さらに、p1, p2, ... の位置埋め込みpi∈R kを持つ。これらは、入力xとは独立しており、事前に定義されたスキームによって計算することもできるし、学習データに出現する各位置に対して学習することもできる（Vaswani et al. 入力エンベッディングと位置エンベッディングは、ベクトルy (0) i = f(vi , pi) (i = 1, ... , n)に結合され（例えば、加算や連結を介して）、これを層0と呼ぶことにする。変換器は固定数Lの層を持ち、k番目の層（k = 1, ... , L）の位置iにおける活性化y (k) iは、以下のように定義される。各層にはH個のアテンション・ヘッドがあり、まずh番目のヘッドのアテンション・スコアを計算します。

ここで、f att k,h は、前のレベルの活性化を組み合わせて、注目度のスコアにします。これは、例えば、ドット積や加法的注意を用いて実装することができる。具体的には、Vaswaniら（2017、p.5）に記載されている実装では、位置ごとの活性化y（k-1）iを別々に「クエリ」ベクトルQy（k-1）iと「キー」ベクトルKy（k-1）iに線形変換し（いくつかのパラメータ行列K、Qについて）、注意スコアa（k,h）i,jは、クエリQy（k-1）iとキーKy（k-1）jのスケーリングされたドットプロダクトとして実装されます。頭部の活性化は、注目度の重みaˆ (k,h) i,jによって重み付けされて計算されます。

Vaswani et al. (2017)の実装では、まず活性化y (k-1) jを「値ベクトル」に線形変換してからaˆ (k,h) i,jを乗算していますが、これは数学的には、後述するマップf actの一部としてbi,k,hにこの線形変換を適用することと等価です。ソフトアテンションバージョンでは、これらの重みaˆ (k,h) i,jはソフトマックス演算によって得られる：aˆ (k,h) i,- = softmax(a (k,h) i,- ) 。ハードアテンションバリアント(Perez et al., 2019)では、実際の最大´アテンション値を取る： aˆ (k,h) i,j = δ j,arg maxj ′ a (k,h) i,j′ そして、ポジションごとのアクティベーションは次のように計算されます。

ここで、f actは、y (k-1) iからy (k) iへのスキップ接続（Vaswani et al, 2017）を持つ完全接続のフィードフォワードネットワークとして実装されます。

ハードアテンションとソフトアテンション

ソフトアテンションとハードアテンションの選択がある(Shen et al., 2018b; Perez et al., 2019)。変圧器の1つ前の´理論的研究（Perez et al., ´ 2019）では、ハードアテンションを想定しています。実際には、ソフトな注意は勾配降下法で訓練するのが簡単です。しかし、分析研究では、訓練されたトランスフォーマーモデルでは、注意が1つまたは少数の位置に集中することが多く（Voita et al., 2019; Clark et al., 2019）、最も重要なヘッドは少数の位置に明確に集中するものであることが示唆されており（Voita et al. ここでは、ハードアテンション（セクション5）とソフトアテンション（セクション6）の両方を検討する。

言語認識の形式化

入力文字列を形式的な言語に属するか属さないかに分類するタスクである言語認識の問題を考える。 Weissら（2018）に倣い、これを、単語をラベル1（「言語に含まれる」）と0（「言語に含まれない」）にマッピングする配列対配列のタスクとして形式化する。 sequence-to-sequenceタスクにおける変換器の構築（Vaswani et al., 2017）に従い、配列終了記号を読んだ後に得られる最後の活性化y（L）nから、このラベルのソフトマックス確率ベクトルを計算する。

4 正規言語と文脈自由言語

ここでは，代表的な2つの言語を用いて，正規言語と文脈自由言語を認識する変換器の能力を分析する．

PARITY

は、1の数が偶数であるようなビット列の集合です。これは非常に単純な正規言語で、2つの状態を持つ有限状態オートマトンで認識されます。正規言語は、チョムスキー階層の最下層に位置し、単純なRNNでもすべての正規言語を計算することができます。正規言語の中でも、特に基本的なクラスを形成しているのが、counter-freeまたはstar-free言語(McNaughton and Papert, 1971)であり、これらの言語は、ユニオン、コンプリメンテーション、コンカチネーションのみを用いた正規表現で表現することができます。ある意味では、PARITYは最も単純な非カウンタフリー、つまり周期的な正規言語です。つまり、変換器がPARITYを計算できなければ、カウンタフリーではない任意の正規言語を（ほぼ）2認識できません。自然言語の文脈では、PARITYは論理式の評価の文脈で自然に発生します。反復された否定を評価することは、入れ子になった否定の数が偶数か奇数かを数えることに等しい。変換器がパリティを計算できなければ、論理式を正確に評価することもできません。

2DYCK

は、2種類の括弧（'('、')'と'['、']'）で構成される、正しく括られた言葉の言語です。この言語は、階層構造の非常に単純なモデルである。 Chomsky-Schutzenberger ¨定理（Chomsky and Schutzenberger, 1963）¨とは、任意の文脈自由言語は、正規言語との交わりと同型化により、複数種類の括弧を持つ2DYCKの変形から生じるというものです。その結果、LSTMが2DYCKのような言語をモデル化する能力は、実験的研究の対象となっています（Sennhauser and Berwick, 2018; Skachkova et al., 2018; Bernardy, 2018）。我々の理論的な結果は、変換器は、括弧の種類が少ないまたは多い変種を含む2DYCKをモデル化する能力が強く制限されていることを示すだろう。

5 ハードアテンションの結果

ハードアテンションの研究から分析を始めます（Perez et al.2019）。我々は、ハード´アテンション変換はPARITYや2DYCKを表現できないことを示す。結果を最大限に一般的なものにするために、我々の分析は組み合わせ論的な議論を用い、例えば活性化関数やパラメータ行列のノルムなどについては仮定しない。実際、各層の内部の位置情報表現y (k) jが、離散的な構造ではなく、ベクトル値であることも仮定しません。我々の目的は、ハードアテンション変換器がPARITYや2DYCKを表現することができないことを証明することである。この証明の基本的な考え方（図1参照）は、入力記号のごく一部を特定の方法で固定することで、残りのほとんどすべての入力記号を無視してしまうような形で、変換器の「注意を引く」ことができるというものです。このことから、入力ビットの一つ一つが重要なPARITYのような問題は、変換器では解決できないことがわかります。いくつかの入力ビットを「固定」するという考えを公式化するために、入力制限という概念を導入します。入力制限（略して制限）ρは、写像ρn : {1, ... ... , n} → {∗, 0.01} のファミリーです。入力制限ρは、入力長がnのとき、入力記号xiをρn(i)∈{0, 1}のときにρn(i)という値に固定することで、変換器に適用されます。結果として得られる変換器の出力値は、ρn(i) = ∗ となるような入力 xi にのみ依存します。このような入力制限を利用するアイデアは、ブール回路の理論で成功している（Furstら、1984；Hastadら、1994）。特に、Furstら(1984)は、∧、∨、¬ゲートを持つ多項式サイズの有界深さのブール回路がPARITYを計算できないことを証明するためにこの方法を使ったことで有名です。本論文では、変換器に適した適切な制限の存在を証明する新しい方法を説明します。これは、ブール回路の文献から得られた証明方法が、実値の活性化を持つネットワークに一般化されていないようだからです。次の結果は、いくつかの入力を特定の方法で固定することにより、任意の変換器が入力ビットを無視するように強制できるという主張を公式化したものです。

定理1です。

任意のハードアテンショントランスフォーマーが与えられ、C∈（0，1）とする。すると、次のような制限ρと整数c＞0が存在する。

(for all sufficiently large n) また，制限された入力に対して変換器が計算する関数は，入力長nによらず≦c個の入力にのみ依存するようなものである．まず、このことが、変換器が2つの形式言語を認識しないことを意味することを示します。

補論2. ハードアテンションを持つトランスフォーマーはPARITYや2DYCKをモデル化できない。

証明する。 PARITYでは、制限をかけた後、トランスフォーマーの出力はc個の入力に依存する。十分に大きなサイズnの入力は、したがって、出力に影響を与えない無制限の入力がある。 2DYCKについては、ハードアテンショントランスフォーマは、単一のブラケットタイプ('(', ')')を持つより単純な変種1DYCKさえも解くことができないことを示します。まず、最初の0.2n個の入力位置を「('」に、最後の0.2n個の入力位置を「)」に制限します。その後、C = 0.9の定理による制限を適用すると、結果的に制限された入力は、良好なブラケット型の入力と非良好なブラケット型の入力の両方と互換性がありますが、予測は制限された数の位置にのみ依存します。予測は限定された数の位置にのみ依存するので、これは変換器が1DYCKを認識できず、したがって2DYCKも認識できないことを示しています。

考察

ハードアテンション変換器でモデル化できる類似の言語と比較するのは有益かもしれません。まず、1 ∗（アルファベット{0, 1}上）は、1のみで0がない単語の正規言語で、その最小オートマトンはPARITYのように2つの状態を持ちます。変換器は、0の入力がある位置があればそれに注目し、そのような位置を見つけたら拒否する注目ヘッドを持つことで、これを認識することができます。

次に、a n b nは非常に基本的な文脈自由言語です。この言語は、適切な位置埋め込みを用いて、

(1)1つのヘッドに最大の位置nに注目させ、 (2)この情報を用いて、位置<n/2の任意のb、または位置≧n/2の任意のaに注目させることで認識できる。

そのようなシンボルが見つかった場合、モデルは拒否し、そうでなければ受け入れます。これらの言語とPARITY / 2DYCKとの決定的な違いは、入力文字列の任意の部分にいくつかの入力を固定することで、簡単に非メンバーを強制することができる点である。例えば、1 ∗ の場合は0を1つ、a n b n の場合は後半にaを1つ、といった具合である。したがって、このような単純な言語は、深さ削減法の影響を受けず、実際に自己言及で完璧にモデル化することができます。

一般に、深さ削減法は、十分に敏感な言語に適用される。あるC∈(0, 1)について、Cn個の入力シンボルを固定しても、ある単語がその言語の内部にあるか外部にあるかを強制できない場合、ハードアテンション変換器はこの言語を認識できない。関数の感度は、計算複雑性において研究されており（Boppana, 1997; Gopalan et al., 2016）、最近ではフィードフォワードネットワークにおける一般化との関連性が指摘されている（De Palma et al., 2018）。今後の研究では、これらの関連性を調査するつもりです。

定理の証明方法

定理1を証明するためのアプローチは、入力制限をレイヤー1から順に構築していくことです。この構成を成立させるためには、ある層で適切な制限を構築することが主な課題となります。図2に示すように、この制限は数個の入力ビット（約（1 - C 1/L）n個の多くの入力ビット）にしか影響を与えず、第1層の各アテンションヘッドにはc個の入力ビット以外を無視させる必要があります。意外かもしれませんが、これは可能です。アイデアは、いくつかのヘッドに対して高い注意スコアを達成する入力ビットを固定し、そのような高い注意スコアを達成できない入力ビットは無視するようにすることです。このような制限が常に存在することを示したら、この手法を使って、図1に示すように、層を反復的に取り除くことができます。

このような最初の制限を適用した後は，第1層の各頭部は有界数cの入力位置にのみ依存することになる．第2段階では、同じ議論を第2層のヘッドに適用し、第2層の各ヘッドが第1層のヘッドの有界数c′にのみ依存するようにします。このステップの後、第1層を、入力位置の有界数≦cc′を最下層の活性化y(0)iに変換するフィードフォワードネットワークの集まりに分解することができます。このステップの後、第1層は完全に取り除かれました。この議論を繰り返し、予測出力が入力長とは無関係に有界数の入力位置にのみ依存するようになるまで、すべての層を除去します。

ここで、これらのアイデアを正式なものにします。変換器の第1層を除去すると、最下層の各ヘッドが入力位置の組み合わせに依存するようになるため、結果として得られる構造は、もはや変換器ではありません。この概念を正確にするために、技術的な定義を導入します。

定義 3. (c-Transformer)。

cを正の整数とする。L層のc変換器とは、層-0の活性化y (0) jが、1つの位置jだけでなく、≦c個の入力位置の埋め込みの関数となるものである

for some indices i j,n s ∈ {1, . . . , n} (s = 1, . . . , c).

この技術的な概念により、私たちは、自己主張をする層がなくなるまで、最下位の層を繰り返し取り除き、層を減らすことができることを示します。

Lemma 4. (Depth Reduction Lemma).

L層のc変換器と、次のような制限ρが与えられる。

(C∈(0,1]) for all sufficiently large n. 任意のC′<Cを選ぶ。すると、次のような制限ρ′がある。

であり，結果として得られる関数が，ある整数k（C′に依存する）について，L-1層の（c - (2ckH + 1) ）-変換器によって計算されるようなものであり，H≧1は各層と位置における注目ヘッドの数である。レムマは定理1を暗示しています。

定理1の証明

変換器の出力は，最後の活性化 y (L) n によって決定される．深さ削減の定理を反復的に適用し，定理中の定数C′を適切に選択して，0番目の層だけが残るようにする．そして，結果として得られる制限を適用した後，最終的な活性化 y (L) n は，y (0) n によって計算され，これは，有界数の入力ビットによって決定される

5.1 Depth Reduction Lemmaの証明

本節では、Depth Reduction Lemmaを証明します。与えられた制約ρnに基づいて、各nに対して別々に制約ρ′nを構築します。この過程では、追加のビットを制限するだけです。つまり、ρ ′ n (i)がρn(i)と異なる場合は、ρn(i)が∗であったところにρ ′ n (i)が0または1になる場合だけです。 ρ（1）n , ρ（2）n , ρ（3）n = ρ ′ n の3段階で構成されており、いずれも追加のビットを制限することができます。最後に、Depth Reduction Lemmaの結論が、結果として得られる制限ρ ′ nに対して満たされることを検証します。

この証明では、nに依存しないいくつかのパラメータが必要になります。まず、整数kが必要ですが、これは証明を成功させるためには十分に大きくなければならず、証明の後半で固定されます。第二に、パラメータη∈(0, 1 2)、q∈(0, 1)、δ>0が必要であり、具体的な値は証明の後で固定する。

第1段階

ρnから始めて、まず、ρ（1）nを適用する際に、各入力ビットが最大で≦ 1 / η c/C 多数の異なるレイヤ0ヘッドへの入力となるような制限ρ（1）nに修正します。 1 /η c/C以上の異なるlayer-0の活性化に入力される入力ビットの数が≧ η Cnであると仮定する。そうすると、入力ビットとそれに応じたレイヤー0の活性化のペアの数は > ηCn - 1 /η c/C = nc となる。しかし、このようなペアはせいぜいnc個しかありません。なぜなら、n個のlayer-0活性化があり、それぞれの活性化は≦c個の入力に依存するからです。そこで、層-0の頭に依存する＞1/ η c/Cの入力ビットの数は、≦ηCnとなります。これらの入力ビットを{0, 1}の中のある固定値に制限することで、ρnからρ(1)nを得ることができます(どの値でも構いません)。そして、集合{i ≤ n : ρ(1)n (i) = ∗}は、十分に大きなnに対して、少なくとも(1 - η)Cn個の要素を持ったままです。

第2ステージ

ここで第2ステージについて説明する。位置i（i = 1, ... ... , n）にあるレイヤー1のアテンションヘッドh（h = 1, ... ... , H）を（h, i）と呼ぶことにする。このようなヘッド(h, i)を固定する。 y (0) i は ≤ c 個の入力ビットに依存するので，最大で ≤ 2 c 個の可能性のある値をとることができる．各可能値zと各位置j∈{1, ... ... , n}に対して，我々は以下のようにこのペアで達成可能な最大の注目値を計算する。

は、ステージ1で構築された制限ρ（1）nに適合する入力x1 ... xnのみを考慮します。各値zに対して、位置{1, . . .. . n}をこの値で下に向かって並べ、各層のj（z）1 , .. . j (z) 1 , ... ... , j(z) n という順序が得られる．これは，ある位置iにある各レイヤー1のアテンションヘッドhと，y (0) iの各可能な値zについてのものである（同値の場合は，脚注1により位置順に並べる）．各レイヤー1のアテンションヘッドと各zに対して，1≦i (z) 1 < i(z) 2 < - - < i(z) k ≦ n のシーケンスを選び， (1) 各i (z) s に対して，位置j (z) i (z) sの活性化にのみ入力xqが少なくとも1つ存在し，j (z) i (z) s′ (s neq s′ ) が存在しないこと， (2) i (z) k が最小であること．すなわち，i (z) k が小さく，(1) も満たす部分列は存在しない．この構造は，図3の例で視覚化されている．

このようなサブシーケンスは、n ≤ ckでない限り存在し、その場合には、この入力長nに対して既にDepth Reduction Lemmaが満たされている。 z が活性化 y (0) i の可能値であるとすると、位置 i の頭部 h と y (0) i の可能値 z のペア((i, h), z)は、層-0 の活性化 y (0) i (z) s (s∈{1, ... k})の一つが、ρ(1)n で最大注目値(7)を達成する値に固定されていれば、満たされているということになる。また、各((h, i), z)が満たされていれば、(h, i)が満たされていると言います。この定義の背景にある考え方は、((h, i), z)が満たされている場合、y (0) iが値zを取ると仮定して、ρ ′ nを適用するときにこの頭が注意を払うことができる異なる層-0の頭は、最大でk個あります。私たちの目的は、各層-1の頭が満足するようにρ ′ nを構築することです。 ρn(i)=∗で、xiがr ≤ i (z) k , for some zのj (z) rへの入力として現れるとき、層-1頭部はある入力xiにk依存する。

i (z) kは最小なので、ある入力があるj i (z) s (s ≤ k)への入力として現れるときのみ、層-1頭部はある入力にk依存する。特に，1つの層-1頭部は，≦2 c ckの入力変数にのみk依存する． 2つのレイヤ-1ヘッドは，一方のj i (z) sと他方のj i (z′) s′がともにある入力ビットxlにk依存する場合，k-neighborsとなる．私たちは、ランダムに選ばれた制約に対する確率論的な議論を用いて、ρ′nを構築します。この方法を成功させるためには、第1層の異なるヘッドの活性化の間に十分な独立性が必要です。そのため、各ヘッドのk-neighborsの数が制限されていることを確認する必要があります。 η∈(0, 1 2 )を思い出し、Hを第1層の各位置にある注目ヘッドの数とする。

ρ（1）nをρ（2）nに修正し、各層-0の頭が最大で≦2 ckH個のk-dependingの不満足な層-1の頭を持つようにする。あるレイヤー0のヘッドが、2 ckH以上のk個の不満足なレイヤー1のヘッドを持っていると仮定します。 ≦c個の入力ビットを固定し、ピジョンホールの原理に訴えることで、このヘッドを、これらのk個のdepending layer1ヘッドのうち少なくとも＞kH個のヘッドに対して最大の注目値を達成する値に固定することができる。これをρ（1）nに追加した結果の制限をρ（2）nとします。このようにすると、{i ≤ n : ρ (2) n (i) = ∗}はまだ少なくとも(1-η)Cn -c個の要素を持ち、さらにkH個以上のペア((h, i), z)が満たされるようになります。続いて、配列j (z) 1 , ... ... , j(z) nの選択を繰り返す。 j (z) 1 , ... ... , j(z) nという配列の選択を繰り返し（定義のρ (1) nをρ (2) nに置き換えて）、ρ (2) nの追加入力ビットを制限するために、ここで説明した構成を繰り返します。この手順を、レイヤー0のヘッドが > 2 ckH many k-dependent unsatisfiited layer1 head (h, i) を持つことがなくなるまで繰り返します。この手順は、最大で各レイヤー1ヘッドが満足するまで、つまり最大で2 cHn kH = 2 cn k回繰り返します。この手順を繰り返し行う回数をUとする（U≦2 cn k ）。最後に、{i ≤ n : ρ (2) n (i) = ∗}は少なくとも(1 - η)Cn - cU ≥ (1 - η)C - 2 c c k nの要素を持つ。 2 c c k ≤ ηとなるようにkを大きく選ぶことで、{i ≤ n : ρ (2) n (i) = ∗}はやはり少なくとも(1 - 2η)Cn個の要素を持つことがわかります。これが完了すると、各層-0の頭は、k依存の不満足な層-1の頭を最大で≦2 ckH個持つことになります。したがって、各入力ビットは、最大でも≦2^c / η kc H/C 多くの k-dending の不満足な layer-1 ヘッドを持つことになります。その結果、すべての不満足なlayer-1ヘッドは、最大でf≦2^2c /η c^2 k^2 H/C個の不満足なk-neighborsを持つことになります。

第3段階

最後の3つ目の制限「ρ（3）n」を構築するために、「確率論的手法」を適用します。制約ρ (3) nの確率分布を定義し、必要なタイプの制約に割り当てられる確率が0よりも厳密に大きいことを示し、そのような制約が存在することを示します。各入力長nに対して、各入力位置i∈{1, ... ... , n}に独立に記号1または0を割り当てる制限ρ（3）nに対する分布を定義する。 ρ (2) n (i) neq ∗となる入力ビットでは、このランダムな制限がρ (2) n (i)と一致するように制限します。レイヤー1のアテンションヘッド（h, i）と各値z（最大でも2c個）について、X（z）i,hを、このヘッドについてy（0）j i（z）1 , ... ... , y（0）j i（z）1 , ... ... のいずれでもない事象と定義する。

X0は、ρ（2）nが＊にマッピングする入力ビットのうち、（1＋δ）q以上がρ（3）nによってt 0/1に設定されるイベントと定義します（ここで、δ∈（0、1）は後で固定します）。我々の目標は、すべてのイベント{X0}∪{X (z) i,h : i, z}を回避する制限ρ ′ nに、ゼロではない量の確率質量が割り当てられていることを示すことです。まず、Chernoff boundが与えます（Mitzenmacher and Upfal, 2017, Theorem 4.4）。

ステージ2の後にρ（2）nが≧（1 - 2η）Cnの無制限の入力ビットを持っていたからです。

次に、X (z) i,h (i = 1, 2, ... , n, h = 1, ... , H)の確率がkで指数関数的に減衰することを示します。まず、ステージ2の後に((h, i), z)が既に満たされている場合、P(X (z) i,h )=0となります。また、表記を容易にするためにzを固定して、Y t i,h (t = 1, ... , k)を、層-0の活性化y (0) j i (z) tが、与えられた注意ヘッド(h, i)に対して、最高の注意重みを生成する値に固定されない事象とする。 X (z) i,h = T t Y t i,h であることに注意してください。 P(Y s i,h)≦1-(q/2)c∈(0, 1)となる。任意のY s i,hは、各入力ビットが最大で1/ η c/Cに依存するレイヤー0ヘッドを持つため、最大でc * 1 /η c/C = 1 /η c^ 2 /Cの他のイベントY s ′ i,hに統計的に依存することができる。したがって、これらの中に≧k /(1 /η c^2 /C)の独立したイベントのセットがあります。これらをY t1 i,h, ... ...と呼ぶ。, Y ^{k /(1 /η c^2 /C)} i,h とする。そして、X (z) i,h ⊆ T ^{k/ (1 /η c^2 /C)}_{s=1} Y ts i,h, ゆえに

各 i = 1, 2, ... ..., n および h = 1, ... ... に対して , n と h = 1, ... ... , H である。全てのイベント{X0}∪{X (z) i,h : i, h, z}を避ける制限ρ (3) nが存在すると結論づけるために、Lovasz Local Lemma (Mitzenmacher ´ and Upfal, 2017, Theorem 6.17)を適用します。各イベントX (z) i,hは、集合{X (z ′ ) (j,h′ ) : head (j, h′ ) and (i, h) are not k-neighbors}から統計的に独立しています。この集合の補集合は、ステージ2の終わりに結論付けられたように、カーディナリティ≦f＝2 ^2c/ η *c^2 k^2H /Cとなります。セットA := 1 /k^2 , B := 1/2 . Lovasz Local´ Lemmaにより、次のように示せば十分である。

Lovasz Local Lemmaは、すべてのイベント{X0}∪{X (z) i,h : i, h, z}を回避する何らかの入力制限ρ (3) nが存在することを保証します。 (10)では、次のようになります。

右辺の最初の項について

また，は次と等しい

の場合について．

したがって、kを（nとは無関係に）十分に大きく選べば、(12)のRHSを任意に1に近づけることができ、特にDよりも大きくすることができる。また、(11)を満たすために

Hであり、これは十分に大きなn、kに対して成立する（ここでも、nに依存しないkを選ぶ）。結論として、十分に大きなnに対して、nに依存しないkに対して、すべての事象{X0}∪{X (z) i,h : i, z}を回避する制限ρ (3) nが存在します。このようなρ（3）に対して、十分に大きいnについて次が成り立つ

次に、(1 - 2η) - (1 - (1 + δ)q) = C ′/Cとなるように、η∈(0, 1 /2 )を小さく、q∈(0, 1)を大きく、(1 + δ)q∈(0, 1)となるように δ>0 選ぶ。

ρ (3) nを適用した後、すべての層-1ヘッドbj,1,hは、 (1) y (0) jに入力されるc個の入力ビットと、 (2)ヘッドがk個依存する≦c 2^c k個の入力ビットのみに依存します。

したがって，各層-1活性化y (1) jは，≦c - (2^c kH + 1) 個の入力ビットにのみ依存する． H個の異なる注意ヘッドがk個依存する≦H - c - 2^c - k個の入力ビットがあり、さらにy (0) jからのスキップコネクションがあり、それ自体は≦c個の入力ビットに依存する。このようにして、第0層を取り除き、第1層の活性化 y (1) j を第0層の活性化 y (0) j に変換すると、ρ (3) を適用したときに以前と同じ計算を行う (c * (2^c kH + 1))-変換器が得られます。以上でDepth Reduction Leの証明は終了です。

6 ソフトアテンションの結果

前節では、ハードアテンションを用いた変換器では、さまざまなコア形式言語を認識できないことを示した。本節では、ソフトアテンションについて検討します。ハードアテンションの設定で見つけたのと同じくらい強い制限を証明することは、計算複雑性の大きな未解決問題を解決することになり、したがって、現在利用可能な数学的手法で達成することは極めて困難であることがわかった3。変換器で使われる操作の滑らかさを利用して、入力が長くなると、どんな変換器でもそのような分布をロバストにモデル化できなくなることを示します。この証明の背景にある考え方は、入力が長ければ、一つの入力記号が変換器の出力に与える影響は小さいということです。

Lemma 5.

ソフトアテンション変換器が与えられ、入力の長さをnとする。 1つの入力シンボルxi (i < n)を交換した場合、デコーダ層での結果としての活性化y (L) nの変化は、パラメータ行列に依存する定数でO( 1 / n )に制限される。これはリカレントネットワークとは対照的です。 (RNNは)非常に長い入力であっても、1つの入力を変更することで最終的な状態に無視できない影響を与えることができます。例えば、現在のプレフィックスのパリティを符号化した隠れた状態を通してパリティを認識するRNNは、1つの入力ビットが反転した場合、その隠れた状態を反転させます。

Lemma 5は、入力が長くなると、個々の入力シンボルに非常に敏感な予測問題において、ソフトアテンション変換器は良好なクロスエントロピーを達成できないことを意味する。ソフトマックス出力を持つReLU MLPのようなリプシッツ連続の予測関数では、類似した活性化y (L) nにエンコードされた入力に対して、大きく異なる予測を行うことができない。すべての仮定を明確にするために、以下の設定を仮定するが、結果は具体的な詳細には依存しない。 PARITYでは、それまでに放出された1の数が偶数である場合、確率pで終了し、それ以外の場合はそれぞれ等しい確率で1または0を放出する2状態オートマトンが生成するビット列の分布を考えます。この分布から引き出された文字列の前置詞が与えられた場合，Σ = {0, 1, ENDOFSEQUENCE}から次のシンボルを予測するように変換器に依頼します．なお，次のシンボルがENDOFSEQUENCEになるのは，接頭辞が偶数の1を持つ場合に限られる． 2DYCKについては，Skachkovaら(2018)の実験的研究に従い，S → (S)SまたはS → [S]Sをそれぞれ確率p/2で展開し，S → ǫを確率1 - pで展開するPCFGが生成する分布をとり，Σ = {(,), [, ], ENDOFSEQUENCE}の中から次の文字を予測するようにモデルに依頼する。

定理6。

PARITYまたは2DYCKのソフトアテンション変換器が与えられるとする。 n → ∞とすると、次の記号を予測する際のクロスエントロピーはunigram chance levelに収束する(PARITY)か、少なくともある定数ǫ＞0で最適なクロスエントロピーから離す(2DYCK)。

証明します。

まず、「PARITY」について考えてみましょう。 1つのビットを交換することで、PARITYのメンバーシップが反転する。したがって、任意のx∈PARITYに対して、1ビットだけ異なる文字列x ′ not ∈PARITYが存在することになる。 xとx ′は1ビットしか違わないので、変換器の出力活性化はO( 1 n )だけ異なることになる。したがって、リプシッツ連続予測関数では、偶数回の1の後と奇数回の1の後に異なる次のシンボルの確率をロバストに割り当てることができず、クロスエントロピーはunigram chanceレベルに収束してしまう。

2DYCKでは、PCFG(Probabilistic Context-free Grammar: PCFG)で生成された単語の前置詞であることが知られている長さnの文字列xを考えます。このとき，xが両方とも閉じ括弧で終わり，かつアンバランスであるような定数P0∈（0，1）（pに依存するがnには依存しない）が，確率≧P0で存在することを示すことができます。4 そのようなxの後、次の記号は、一定の非ゼロ確率（1 - p）で閉じ括弧である。 xの後に例えば「)'」が続くことはあっても「]'が続くことはないとすると、入力位置が1つだけ異なり、次の記号が「]'になることはあっても「)'になることはない文字列x′が存在することになる。 x は閉じ括弧で終わると仮定されていたので，交換された記号は x の最後の記号ではなく，したがって，変換器の x と x ′ の予測は，O( 1 / n ) だけ異なります．予測タスクは， (1) 開き括弧と閉じ括弧，あるいは ENDOFSEQUENCE が続くかどうか， (2) 括弧が続く場合に丸括弧と角括弧が続くかどうかを予測することに分解できます．クロスエントロピーの損失は、この2つの連続した予測タスクで発生するクロスエントロピーの合計となる。したがって、このような接頭辞xの後に正しい閉じ括弧、例えば「）」が続く場合、モデルはn→∞として、2つ目のタスクで少なくともlog2のクロスエントロピー損失を被ることになりますが、これは2つの可能な閉じ括弧の間での選択における偶然のパフォーマンスを反映しています。対照的に、(2)の最適なクロスエントロピー損失は、ブラケットのタイプ（丸か四角か）が実際にはxによって完全に決定されるため、0となる。したがって、長さnのすべての接頭辞xに関する全体のクロスエントロピーは、n → ∞として漸近的に、最適なクロスエントロピーよりも少なくともP0 (1 - p) log 2 > 0となる。//

続いて、定理5の証明を行います。

Lemma 5の証明。

i番目の位置の入力だけが異なる2つの入力について、デコーダ層の活性化を比較する。 D = ||vi-v ′ i ||_2 を、この位置での入力エンベッディングの差のノルムとする。 k = 1, ... ... , Lに対する帰納法によって，あるC > 1, ... ,Lについて帰納法により，あるC > 0（以下で選択）に対して，結果として得られる活性化の差y^(k)_j , y^(k)_j ′が次のように束縛されることを示す．

これを示すと、個々の入力が最終的な予測に与える影響は、パラメータ行列のノルムと層の数に応じた定数で、O( 1 / n )となることがわかります。ここで、この証明における変換器の重要な特性は、層の数Lが入力長とは無関係に拘束されることであることを指摘しておきます。同様の証明方法は、平均プーリングを用いた1次元の時間的畳み込みのように、拘束力のない多数の入力を滑らかに結合する他の固定深度アーキテクチャにも適用できます。

k = 0の場合，|| y (0) i - y (0) i ′ || ≤ D，j neq iの場合，||y (0) j - y (0) j ′ || = 0となる． k＞0の場合、まず、||y（k）j ||_2 ≦ 2C^L_f^{act}（||pj||＋||vj||）、ここで、C_f^{act} ＜∞は、ReLU MLPとして実装されているf actのパラメータ行列のノルムに依存することに注意する（Vaswani et al, 2017). この上界を||y (k) j ||2に対してFと書きます。アテンションロジットは、ドットプロダクトアテンションの場合にはA := F^2C_f^{att}、アディティブアテンションの場合にはA := 2F C_f^{att}で拘束される。そして、任意のアテンションウェイトaˆj,i = exp(ai)/ Sum_j exp(a_j)は次式で上界される。

C := 2 * (1 + exp(2A) + L_f^{act} ) を選びます。ここで、Lf^{act} は ReLU MLP f act の Lipschitz 定数です。ここで、Lf actはReLU MLP f actのリプシッツ定数である。ここで、bi,k,hはSum^n{j=1} aˆ k,h i,j y (k-1) jに等しい。まず、次のように計算します。

これは、帰納法の仮説を用いると、最大でも

第二に、j neq iの場合、それは上で次のように制限されます。

これはでバウンドされる．これでk > 0についてのinductive stepが証明された

7 考察

我々は、無限の精度を持ってしても、変換器が非カウンタフリーの正規言語や基本的な階層構造をロバストにモデル化できないことを示した。ハードアテンションの設定では、活性化関数やパラメータの大きさに関わらず、我々の結果は有効であり、どの変換器も文字列をそのような言語に属するものとして正確に分類できないことを示しています。ソフトアテンションでは、我々の結果はやや一般的ではないが、形式言語上の分布をモデル化する際に、変換器は完全なクロスエントロピーを達成できないことを示している。我々の結果は漸近的なものであり、入力が十分に長い場合、どんな変換器でもPARITYと2DYCKのモデル化を間違えることを示している。実際、入力長に任意の境界Nが与えられれば、長さn≦Nのすべての例で完全な精度またはクロスエントロピーを達成する変換器を構築することができる。 我々の結果は、ヘッドとレイヤーの数、またはパラメータノルムがNとともに増加しなければならないことを示している。 したがって、より厳しい非漸近的な境界を考慮すると、ここで報告された結果は、実世界のNLPシステムの実用的な限界の決定的な証拠となる必要はありません。我々の結果の最も重要な意味は、本質的には理論的なものであると考えています。今回の結果は、最近のNLPの進歩の中心となっているアーキテクチャである自己注意の能力を分析するための数学的手法を示しています。これらのツールは、自己注意と、理論的によく研究されているリカレント・アーキテクチャとの違いを理論的に理解するのに役立ちます。 LSTMのようなリカレントネットワークは、有限状態オートマトンを完全にエミュレートすることができるため、状態遷移とシンボル放出の分布がマルコフ型であれば、最適なクロスエントロピーを持つ任意の有限状態の言語をモデル化することができます。特に、i.i.d.ビット列のPARITYは、入力の長さによらず、完全な精度とクロスエントロピーで予測することができます。さらに、無限精度のRNNやLSTMはスタックをモデル化することができるため(Tabor, 2000; Gruning, ¨ 2006; Kirov and Frank, 2012)、理論的には2DYCKやその他の決定論的文脈自由言語を完全にモデル化することができます。このように、今回発表された結果は、自己注意に完全に依存して構築されたモデルは、リカレントアーキテクチャと比較して表現力が制限される可能性があるという直感を理論的に裏付けるものである(Tran et al., 2018; Dehghani et al., 2019; Shen et al., 2018a; Chen et al., 2018; Hao et al., 2019)。ここで開発された漸近法を経験的な研究や非漸近法的な拡張で補完することは、今後の研究のための興味深い手段です。

しかし、自然言語の構文や意味の一般化を適切に捉えるためには、文脈自由文法やそれ以上のレベルの漸近的に強力な形式が必要であると一般的に主張されてきた（例えば、Chomsky, 1957; Shieber, 1985）。我々の結果は、自己注意が文脈自由言語や評価項目式をモデル化する能力に限界があることを示している。特に、自己言及はスタックや任意の有限状態オートマトンを模倣することはできません。経験的な研究によると、リカレントモデルと変換モデルの両方で、強力な定量的性能を持つモデルは、引き続き構文の一般化に苦労しており、perplexityなどの定量的性能指標は、より挑戦的なベンチマークで表示される構文知識から部分的に分離されることが示唆されている（例えば、Kuncoroら、2018年、Marvin and Linzen、2018年、Tranら、2018年、McCoyら、2019年）。

しかし、NLPタスクにおけるトランスフォーマーの成功は、理論言語学で一般的に想定されている形式言語に対して形式的に弱すぎる手法でも、自然言語の多くの側面をうまくモデル化できることを示唆している。漸近解析の一般的な限界を超えて、このような現象が起こる理由として考えられるのは、言語が認知的な要因により、再帰的構造を限定的にしか使用しないことです。例えば、中心埋め込みと呼ばれる反復括弧を持つ構文構造は、人間が処理するには非常に困難であることが以前から指摘されている(Miller and Chomsky, 1963; Gibson and Thomas, 1999)。興味深いことに、自己注意は、人間が単語を処理する際に、いくつかの前の単語を処理した際に記憶に保存されたチャンクに注意を払うと仮定した、人間の文処理における記憶の心理言語学的モデルと似ているところがあります（Lewis and Vasishth, 2005; Parker et al. このような処理モデルでは，自己注意に基づくニューラルネットワークモデルについて理論的に示したことと同様に，括弧を数えることができないため，センター埋め込みが困難であると予測される（Lewis and Vasishth, 2005）。

8 おわりに

規則的な言語や階層構造をモデル化する際の自己注意の能力を正式に調べました。その結果、ハードアテンションでもソフトアテンションでも、また、無限の精度が許される場合でも、トランスフォーマは周期的な正規言語や基本的な再帰をモデル化できないことを示しました。これは、自己注意では、一般的にスタックや一般的な有限状態オートマトンをエミュレートできないことを意味します。我々の結果は、自己注意が再帰を避けることによって、非常に限られた計算能力しか持たないという考えを理論的に裏付けるものである。

e4exp / paper_manager_abstract