How Can Self-Attention Networks Recognize Dyck-n Languages?

[e4exp]

• https://arxiv.org/abs/2010.04303
• 2020 EMNLP

本研究では、Dyck-n (n) 個の言語の認識を、自己注意（SA）ネットワークで行うことに注目する。 本研究では、開始記号を持つSA（SA+）と持たないSA（SA-）という2種類のSAの性能を比較した。 その結果、SA+は、より長い配列やより深い依存関係に一般化できることがわかった。 また、SA+の精度は58.82%であるのに対し、SA-は長い配列では完全に壊れてしまうことがわかった。 SA+が学習したアテンションマップは、解釈が容易であり、スタックベースの言語認識器との互換性があることがわかった。 驚くべきことに、SAネットワークの性能はLSTMと同等であり、これはSAが再帰なしに階層を学習できることを示す証拠である。

[e4exp]

1 はじめに

形式言語を用いて神経アーキテクチャの基本的な特性を研究することへの関心が高まっており，解釈可能なモデルの抽出につながっている（Weissら，2018；Merrillら，2020）。 最近の研究（Hao et al., 2018; Suzgun et al., 2019; Skachkova et al., 2018）では、文脈自由言語のサブセットである一般化されたDyck-n（Dn）言語が探求されている。 Dnはn種類の異なるブラケットペアを持つ「バランスのとれた」括弧の文字列で構成されており、入れ子構造を研究するための正統的な形式言語です（Chomsky and Schutzenberger ¨ , 1959）。 Weissら（2018）は、LSTM（Hochreiter and Schmidhuber, 1997）がk-counter machineの変形であり、D1言語を認識できることを示している。 しかし、動的計数機構は、プッシュダウンオートマトンをエミュレートする必要があるため、Dn>1では十分ではない。 Hahn (2020) は、十分に大きな長さの場合、Transformers (Vaswani et al., 2017) はD2言語のトランスダクションに失敗することを示しています。 我々は、語彙に開始記号を追加することで、2層の多頭SAネットワーク（すなわちTransformerのエンコーダ）がDn言語を学習し、完全ではないものの、より長い配列に一般化できることを経験的に示している。 図1に示すように、このネットワークは、スタックベースのオートマトンのように、開き括弧に対応する閉じ括弧を識別することができます。 例えば、文字列「([])」の中の記号「]」は、まずスタックから「[]」を取り出し、次に最後にマッチしなかった記号「()」に注目し、次の有効な閉じ括弧を決定します。 開始記号(T)は、節の終わりやシーケンスの終わりの発生をモデルに学習させる。 本研究は、形式言語上のSAを実証的に調査した初めての研究である。 開始記号を組み込んだSA（SA+）とそうでないSA（SA-）を詳細に比較し、シーケンスの長さや依存関係の深さに応じて、両者の一般化に大きな違いがあることを示している。

最近の研究では、階層構造をモデル化する自己注意メカニズムの能力には限界があることが示唆されています。 Shenら（2019）は、論理的推論（Bowmanら、2015）やListOps（Nangia and Bowman、2018）などのタスクにおけるTransformの性能は、LSTMよりも劣るか悪いことを示しています。 Tranら（2018）もSAについて同様の結果を報告しており、階層構造のモデル化には再帰性が必要であると結論づけています。 これと比較して、我々の結果は、SA+がDn言語において、より長い配列のD2を除いてLSTMよりも優れていることを示している。 Papadimitriou and Jurafsky (2020)は、ニューラルモデルが階層構造を学習する能力は、階層を直接符号化するのではなく、「振り返り」の能力に起因するとしている。 私たちの分析は、正しい先行するシンボルにエレガントに注意を向けることで、階層構造を学習するSAの能力に光を当てています。

[e4exp]

2 関連研究

a n b n , an b n c md m (文脈フリー)や a n b n c n , an+mb n c m (文脈依存)などの形式言語は、RNNを用いて広範囲に研究され、認識されてきました(Elman, 1990; Das et al., 1992; Steijvers and Grunwald ¨ , 1996)。 しかし、Dn言語に対する同じリカレントアーキテクチャの性能は低く、一般化されていないことが問題となっています。 Sennhauser and Berwick (2018)とBernardy (2018)は、Dn文字列の各位置で次に可能な閉じ括弧を予測するRNNの能力を研究し、より高い再帰深度での一般化が乏しいことを発見しました。 Haoら（2018）は、スタック・アグメンテッドLSTMがDn言語でより良い一般化を達成することを報告したが、ネットワーク計算はスタックをエミュレートしていない。 さらに最近では、Suzgunら（2019）がメモリ・アグメンテッド・リカレント・ニューラル・ネットワークを提案し、Dn言語の認識のためのシーケンス分類タスクを定義した。 Yuら（2019）は、D2言語に対する注意ベースのseq2seqフレームワークの利用を検討し、より深さのある配列への一般化がまだ不足していることを明らかにした。 経験的な調査以外にも、形式言語はニューラルネットワークの複雑さを理解するために理論的に研究されてきた(Siegelmann and Sontag, 1992; Perez et al. ´ , 2019)が、その多くは実験では満たすことができない仮定-無限の精度や拘束されない計算時間-の下で行われている。

[e4exp]

3 実験

先行研究（Gers and Schmidhuber, 2001; Suzgun et al., 2019）に倣い、Dn言語の認識をトランスダクションタスクとして定式化する。 有効な文字列が与えられたら、モデルに次の可能な記号を自動回帰的に予測するように求める。 例として、D2言語の入力文字列「[ ( ) ] ( [ ]」を考えると、文字列中の次の有効な括弧のセット-(, [, or ])を予測することを求めます。 我々は、モデルが入力列の各位置にあるすべての可能な括弧のセットを正しく予測する場合にのみ、入力が正確に認識されると考える。 本論文では，句を部分文字列と呼び，その中では，それぞれの種類の括弧の閉じた部分と開いた部分の数が等しいとする． 2つの多頭型自己注意ネットワーク（すなわち、Transformerのエンコーダ部分のみ）を学習し、一方は語彙に追加の開始記号を組み込み（SA+）、もう一方は組み込まない（SA-）。 各モデルの層数は2、アテンションヘッドの数h＝4、モデル次元d＝256とした。 学習可能な埋め込みを用いて、各入力記号を256次元のベクトルに変換します。 また、標準的なTransformer（Vaswani et al., 2017）と同様に、各層の周りに残差接続を追加し、続いて層の正規化を行います。 2つの一方向性LSTMを学習します。 1つは開始記号を使用し（LSTM+）、もう1つは使用しません（LSTM-）。 LSTMは、320次元の隠れた状態と、学習した入力の埋め込みのための320次元のベクトルを使用します。SAとLSTMのバリエーションは，いずれも約1.6Mのパラメータを持っています1． 最適化にはAdam (Kingma and Ba, 2015) を使用しています。 SA+とSA-では，学習率ηを次のように変化させています．

ここでitrは反復回数を意味し、warmupは10kに設定されています。 ハイパーパラメータconstは，[0.01, 0.1, 1.0, 10]の値を用いて調整し，0.1を使用した． LSTMについては，初期学習率を0.001とするが，学習率のスケジューリングは行わない．

すでに既存の文献に記載されている確率的文脈自由文法（PCFG）によって、実験用の合成データセットを再生成します（Suzgun et al.、2019）。 例えば、Dyck-2言語のPCFGは次のように定義できる。 (1) S -→ [S], (2) S -→ {S}, (3) S -→ SS, (4) S -→ ε, それぞれの確率はp = 0.25です。 各Dn言語について，長さ2〜50の32k個の配列で学習し，長さ52〜74の32k個の配列で検証し，長さ76〜100と102〜126の区間に均等に分けた10k個の配列で評価した． 図2は，学習と評価におけるD2配列の長さと深さの分布を示している。

Dyckの高い言語（Dn>2）では，PCFGが異なる括弧のペアに等しい確率を与え，S -→ (S), S -→ [S], ...の形式のルールの合計確率が0.5であるため，学習データセットと評価データセットは，同じような深さと長さの分布になります。 D1, D2, D3, D4言語で実験を行った。 なお，括弧のペアの数は，実験の設定を変更しない限り，任意に増やすことはできない． 学習時の配列の長さを2から50まで変化させたところ，最大で25の異なるペアを含むことができた． 配列予測タスクでは，Dn 言語の入力語彙（V i n ）は，n 組の括弧と追加の開始記号 T の 2n+1 個の記号で構成されるが，出力語彙（V o n ）には開始記号 T は含まれない． 配列の次の括弧には複数の可能性があるかもしれないので，出力を k-hot ベクトルとして符号化し，ネットワークを次式で与えられる 2 つの cross-entropy 損失関数を用いて最適化するマルチラベル分類アプローチを採用した．

ここで、｜V^o_n｜は出力語彙サイズ（D1は2、D2は4、D3は6、D4は8）、yˆi∈{0, 1}、yiはそれぞれラベルiに対する目標値と予測値である。

3.1 評価

表1は，D1，D2，D3，D4言語におけるSA+とSA-の精度を比較したものである。 両モデルとも，D1での性能はほぼ完璧（98%以上）であり，配列の長さが増えても劣化は見られない． D2に対するSA-の精度は、長さ76-100の配列で14.52%であり、それを超えると完全に失敗する。 これに対し、D2におけるSA+の性能は、長さ76-100および102-126の配列に対して、それぞれ93.34%および58.82%と大幅に向上しています。 D3とD4では、SA-の性能がD2に比べて向上しており、長さ76-100の配列に対して、それぞれ32.62%と42.94%の精度となった。 SA+の性能は、長さ76-10の配列ではDn≧2でほぼ一定(約93%)ですが、長さ102-126の配列では、D2(58.82%)からD3(66.88%)、D4(72.38%)へと大幅に改善しています。 SAとは異なり、LSTMの性能は開始記号の追加後に低下し、シーケンス長102-106のD4で最大の低下（4.3%）が見られました。 開始記号によって、SAは正しい先行トークンに注目することができましたが、LSTMには効果がありませんでした。 長さ102-126のD2シーケンスにおいて、LSTM-は73.20%の精度を達成し、SA+に比べて約14%改善しました。 他の全ての比較において、SA+はLSTM-を上回っている。

この2つのアーキテクチャには，もう1つ興味深い違いがあります． 括弧のペアの数が増えるとLSTMの精度が悪化するのに対し，SA+とSA-の精度は向上するのである． この現象を理解するために、各言語の学習セット、検証セット、テストセットを見てみると、Dn言語の検証セットとテストセットには、ほぼ必ず（99％以上）n種類の括弧の配列が含まれているのに対し、学習セットには1≦m＜n種類の括弧の配列が含まれている可能性があることがわかった。 これは、SAは他の言語の配列でデータを補強することで利益を得られ、LSTMはそうではないことを意味しています。 別の言い方をすれば、これらの結果は、LSTMが、おそらく数え方に強い帰納的バイアスを持っていることを示唆しており(Kharitonov and Chaabouni, 2020)、その結果、Dyckの高い言語では性能が低下する可能性がある。

3.2 エラー分析

我々は，失敗位置（fp）を，モデルが次の可能な括弧のセットを正しく予測できなかったシーケンスの最初のシンボルの位置と定義する． (i)深さ(dp)は，その記号を含む，それまでにマッチしなかった括弧の数であり， (ii)頭への距離(dh)は，誤って分類された閉じ括弧とその開き括弧の間の記号の数である． 図3aは，SA+とSA-の誤差分布を，失敗位置(fp)と頭への距離(dh)の観点からプロットしたものである． どのような種類のエラーが発生するかという点で、2つのモデルには明確な違いがある。 SA-はシーケンスのかなり早い段階で破損し、エラーの大半はfp=25-75で発生しているのに対し、SA+のエラーはfp>80に集中している。 図3bcは、D2とD4の言語について、SA+とSA-の性能が深度（dp）によってどのように変化するかを示している。 SA-はD2において、dp=10での約38%からdp=20を超えると完全に失敗するまで、急激に精度が低下するため、深度に対して非常に敏感である。 それに比べ、SA+はdp=10で94%からdp=20で72%と、精度の低下はそれほど大きくない。

[e4exp]

4 Stack-Based Recognizer との互換性

Dn>1 個の言語を認識する（メモリレス）SA ネットワークの能力は興味深いものである。 本節では、SA+とSA-が生成する第2層のアテンションマップを対比し、SA+の成功を導く根本的なメカニズムについての洞察を提供する。 ここでは、互換性を、スタックベースの言語認識器（M）の状態とアテンションマップの整合性の定量的な尺度として定義する。 M は仮想的なスタックの先頭にアクセスでき、開 きカッコと閉じカッコに応じてプッシュとポップが可能である。 このアナロジーに基づいて、すべての開始ブラケットは自分自身に注意を払い、すべての終了ブラケットはまずポップを行い、最後のマッチしていないブラケットに注意を払うべきである。 例えば、文字列 "([])" の中のシンボル "]" は、まずスタックから "[" をポップし、次に最後にマッチしなかったシンボルである "(" をアタッチして、次の有効な閉じ括弧を決定します。 シーケンス内のすべての閉じた記号について、少なくとも1つのヘッドの最も高いアテンションスコアが正しいブラケットを指していれば、そのSAは互換性があると考える。 さらに、SA+とSA-を公平に比較するために、開始シンボルをスタックにプッシュせず、文節の最後ではない閉じ括弧のみを考慮する。 図5は、SA+とSA-の互換性を配列長に対してプロットしたものである。 D2上のSA-は、学習時に見られた配列長（40-50）においても、互換性はほぼゼロであり、ほぼ完璧な精度を達成していることがわかる。 それに比べてSA+は、トレーニング中に見られた配列の長さでは完全な互換性を持ち、より長い配列でも高い互換性を維持しています。 さらに，驚くべきことではないが，長さ 50-100 における精度と互換性の分布のピアソン相関は，すべての SA+ モデルで 90%を超えている。 図4は、D2系列「([([]]])」に対するSA+とSA-の4つのヘッドのアテンションマップである。 SA+の3番目のヘッドは、我々が期待するスタックベースの認識器と一致していることがわかる。 3番目のヘッドの重要な特徴は、最後のシンボルが開始シンボルTに注目していることである。 開始シンボルにより、モデルは節の終わりとシーケンス全体の終わりの発生を学習することができた。

[e4exp]

5 結論と今後の課題

我々は、自己注意（SA）ネットワークが一般化されたDn言語を学習する能力についての実証的な証拠を提供する。 2つのSAネットワーク、SA+とSA-の性能を比較した。 SA+とSA-の違いは、語彙に開始記号を含めるかどうかだけである。 開始記号を追加するだけで、SA+はより長く、より深さのある配列に一般化できることを実証した。 Dn言語の認識が本質的に階層的なタスクであることを考えると、SA（無再帰）がLSTMに対して競争的な性能を持つことは意外に思えるかもしれない。 実験の結果、Dyck言語の認識は再帰とは関係なく、頭のトークンを調べるための正しい表現を学習することが重要であると結論づけた。 さらに、SA+によって学習された表現は非常に解釈しやすく、ネットワークはスタックオートマトンに似た計算を行うことがわかった。 この結果は、形式言語が、SAの性能と解釈可能性の間の相互作用を探るための興味深い手段になり得ることを示唆している。 SAとLSTMの比較では、2つのアーキテクチャの間に興味深いコントラストが見られ、さらなる調査が必要である。 最近の研究(Katharopoulos et al., 2020)では、注目メカニズムを線形化することでTransformerをRNNとして表現する方法が示されており、これらの神経アーキテクチャのより理論的な分析の基礎となる可能性があります(例：帰納的バイアスと複雑性)。