Big Bird: Transformers for Longer Sequences
- 発表先
- NeurIPS 2020国際会議
- arXiv への初回投稿
- arXiv:2007.14062
この論文を引用 · BibTeX
引用情報はリンク先の論文の版に対応し、原論文の著者を記載しています。
@misc{transformersbigbird2020,
title = {{Big Bird: Transformers for Longer Sequences}},
author = {Manzil Zaheer and Guru Guruganesh and Avinava Dubey and Joshua Ainslie and Chris Alberti and Santiago Ontanon and Philip Pham and Anirudh Ravula and Qifan Wang and Li Yang and Amr Ahmed},
year = {2020},
eprint = {2007.14062},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2007.14062}
}
Transformer の自己注意機構の計算複雑度は です。
アルゴリズムの計算複雑度がこの形になると、最適化の余地がずいぶん大きそうに見えます。
ん?どうしてまたこの始まり?
問題の定義
Transformer モデル(例えば BERT)は、並列計算能力と現代のハードウェアのサポートのおかげで、さまざまな自然言語処理タスクで優れたパフォーマンスを発揮しています。しかし、自己注意機構によって引き起こされる計算およびメモリの要求は、シーケンス長の二乗に比例し、長いコンテキストを必要とするタスクへの直接的な応用を制限しています。
Longformer の登場後、Google Brain チームは BigBird を提案しました。これは、長いシーケンスの処理に特化した Transformer の変種です。
基本理論の不足
それに加えて著者らは、従来の疎注意に関する研究は主に経験則に基づき、理論的な保証が十分ではなかったと考えています。完全な注意を使う Transformer の表現能力については先行研究がありますが、計算量を減らしてもその能力を保てるかは明らかではありません。本論文では、そのために十分な疎接続の構造を調べます。
このような動機を基に、著者は BigBird モデルを提案しました。このモデルは、長いシーケンスタスクで優れたパフォーマンスを実現しながら、理論的な表現能力を維持するために、スパース注意機構を使用しています。
解決問題
モデルアーキテクチャ
この論文の概念は非常にシンプルで、この図を見るだけでほぼ理解できます。
BigBird のアーキテクチャでは、著者は 3 種類のコンポーネントを設計し、最終的にスパースなアーキテクチャを形成しました:
- 上図 (a) はランダム注意機構で、モデルの各層のトークン間でランダムに接続を構築します。
- 上図 (b) はスライディングウィンドウ注意機構で、各トークンは前後の固定範囲内のトークンにのみ注意を払います。
- 上図 (c) はグローバル注意機構で、特定のトークンは他のすべてのトークンに注意を払い、同時に他のトークンもそのトークンに注意を払います。
- 上図 (d) は、これら 3 つの機構を組み合わせて、BigBird の注意機構を形成します。
アーキテクチャ設計
ランダム接続数 、窓幅 、グローバルトークン数 を系列長 に対して固定すれば、1 層の接続数は になります。
著者は 2 種類の異なるグローバルトークン選択方法を設計し、後の実験で比較を行いました:
-
BIGBIRD-ITC(内部 Transformer 構造)
- グローバルトークンの選択:この設計では、いくつかの既存のトークンが「グローバル」トークンとして指定されます。これにより、これらのトークンはシーケンス内のすべての他のトークンに注意を払うことができます。
- 行列表示:グローバルトークンとして選ばれたインデックス集合 に対して、対応する隣接行列 は調整され、すべてのグローバルトークン に対して、 の行と列のすべての要素を 1 に設定します(すなわち、 および )。これにより、これらのトークンはシーケンス内のすべての他のトークンと相互作用することができます。
-
BIGBIRD-ETC(拡張 Transformer 構造)
- 追加のグローバルトークン:ITC とは異なり、ETC 設計は追加のグローバルトークン(例えば CLS トークン)を導入します。これらのトークンは、すべての既存のトークンに注意を払うように設計されています。
- 行列の拡張:行と列をそれぞれ 個追加して、 の にします。新しいグローバルノードに対応する行・列はともに 1 とし、元の接続は残りのブロックに保存します。
証明前に
ここからは本論文で最も難解な部分が始まります。著者は BigBird の理論的な性質を証明し、「ランダム注意機構」を採用する理由を説明します。
結論を先に使っても問題ありませんが、せっかくなので少しだけ見てみましょう。
証明の前に、著者が自己注意機構についてどのように理論的に説明しているかを見てみましょう:
-
一般化された注意機構
- BigBird モデルは、各層の Transformer でシーケンス を処理するために、一般化された注意機構を使用します。
- 注意機構は有向グラフ で表現され、グラフのノードセットは であり、有向エッジは考慮される内積の集合を示します。
-
注意出力ベクトル
- グラフの各ノード に対して、出力ベクトル はノード と、その出辺が向かう近傍 に基づいて計算されます。
- 具体的な計算方法は次の通りです:
- ここで はクエリとキー、 はバリューの関数です。 には全入力ではなく、近傍のトークンだけを積みます。
- はスコア関数で、softmax や hardmax が使用されます。
- はヘッドの数です。
-
完全グラフとスパース化:
- もしが完全な有向グラフであれば、それは Vaswani らが記述した完全な二次注意機構に戻ります。
- グラフのスパース化は、ノード間で一定数のランダムエッジを選択することによって実現され、計算複雑度を削減します。
-
ランダムスパースグラフ:
- ランダムグラフには短い経路やスペクトル特性で完全グラフに近づくものがあり、著者らはこれを設計の手がかりにします。
- Erdős–Rényi グラフの議論はその直感を示すものです。BigBird の注意では、各クエリが 個のキーをランダムに参照します。
-
局所性とスライディングウィンドウ:
- 多くの NLP タスクや計算生物学の背景では、大量の参照情報が局所性を示し、隣接するトークンから情報を抽出することが多いです。
- BigBird モデルでは、この局所性に対応するためにスライディングウィンドウ注意機構を使用します。
-
グローバルトークンの使用:
- グローバルトークンを導入して、シーケンス内のすべてのトークンを扱う状況を模倣します。これらのトークンは注意計算で重要な役割を果たし、シーケンス全体の処理に関与します。
上記の説明では、新しい内容は特にありませんが、これを通じて、元々の注意機構は「一般化された注意機構」の一部であり、「特例」に過ぎないことが示されています。
この「特例」とは完全な有向グラフであり、注意機構を「特製」の有向グラフに調整することがスパース注意機構への道を開くことを意味しています。
また、なぜランダム注意機構が採用されたのかも説明されています:
- ランダム接続はノード間の経路を短くし、離れた位置へ情報を伝える助けになるからです。
ただし、Erdős–Rényi グラフは発想の説明であり、BigBird の実際の注意では各クエリが 個のキーをランダムに参照し、局所窓とグローバルトークンも残します。後者は万能近似の証明でも鍵になります。
証明開始
Transformer のエンコーダースタックは、本質的に一連の繰り返しの単層エンコーダーであり、各エンコーダーにはそれぞれのパラメータセットがあります。
この構造は、複数の段階を通じて入力データを処理することを可能にし、各層は前の層の出力を基にデータをさらに変換します。
-
パラメータ化:
- H:各エンコーダー層の注意ヘッドの数。
- m:各注意ヘッドのサイズ。
- q:出力ネットワークの隠れ層のサイズ。
-
注意機構:
- 有向グラフ によって定義されます。従来の注意機構(例えば Vaswani らが提案したもの)とは異なり、この構成では、各シーケンスの開始時に特別なマーカー を追加します。このマーカーは、シーケンスの集約情報を表すためや、特定のコンテキスト要求に対応するために使用されます。グラフ の頂点集合にはこの特別なマーカーが含まれており、すなわち です。
-
入力および出力処理:
- 初めに追加された余分なノード があっても、Transformer はシーケンスを から にマッピングするように概念化されています。
- 最終出力層では、余分なノードとそのベクトルを破棄すると仮定し、出力の次元が入力と一致することを確認します。
- 位置情報は token 軸に対応させます。ここでは に統一し、位置行列も と書いて、原論文の転置記法の混在による次元の混乱を避けます。
-
一般的な近似:
- 関数クラス は、 という連続関数の集合です。ここでの連続性は ノルムによる位相で考えます。
- 関数近似の品質を測る距離尺度は、-ノルム距離 です。
-
定義: を中心にした星型グラフ
- ここで、星型グラフ は特別なグラフ構造で、1 つの中心ノード(0 番ノード)が、グラフ内の他のすべてのノード(1 番から n 番まで)と直接接続されています。
- この構造は非常に重要で、中心ノードが他のすべてのノードに直接影響を与えることを可能にするため、後の証明で使用される重要な特性です。
-
定理:疎注意機構の一般的な近似能力
- 論文で定義したモデル族では、星型 (各通常ノードが自身とグローバルノードを参照し、後者は全通常ノードを参照)を含むグラフに対し、任意の 、 と連続関数について を満たす Transformer が存在します。
- これは、このような Transformer モデルが関数クラス 内の任意の連続関数を近似できることを意味します。
-
証明ステップ 1:分割定数関数でを近似
最初に扱う関数 は、有界領域 上の連続関数です。各次元を粒度 の格子に分け、各小区画では値が一定の関数 を作ります。こうして、まず元の関数 を区分的定数関数で近似します。
-
証明ステップ 2:修正された Transformer で分割定数関数を近似
ここが証明の要点です。自己注意機構を使って、入力行列 とその各行 の組に固有のコードを作り、そのコードから対応する出力を得ます。疎注意では各クエリが少数のキーしか参照できないため、行列全体の情報をどう集めるかが課題です。著者らは、入力値の範囲に応じて値を動かす疎なシフト演算子と追加のグローバルトークンを使って、この文脈写像を構成します。
-
証明ステップ 3:元の Transformer で修正された Transformer を近似
最後のステップは、修正された Transformer モデルを元の Transformer モデル(ReLU と softmax 関数を使用)で近似することです。これは近似の存在を示す段階です。
チューリング完全性
実際、Pérez らの研究によると、完全な注意機構に基づいた Transformer モデルはチューリング完全であることが示されています。つまり、あらゆるチューリング機械の計算プロセスをシミュレートできるということです。
ただし、この結果は理論的な仮定に基づいています。それは、モデルが「任意の精度でデータを処理できる」という前提です。
実際の応用では、この仮定は成立しません。なぜなら、Transformer は実際には有限状態機械であり、真のチューリング完全性には達していないからです。
-
疎注意機構でもチューリング機械をシミュレートするのに十分か?
本文では、適切な調整を行うことで、疎エンコーダとデコーダを使用する Transformer もチューリング完全を実現できることが述べられています。
チューリング機械の模擬では、因果的な疎接続を持つ decoder を構成します。この証明用 encoder–decoder と、実験の双方向 BigBird encoder は構成を区別します。
さらに、Pérez らの方法では、各トークンがテープ履歴の表現としても機能し、完全な注意機構はテープ上の正しいシンボルを移動および検索するために使用されます。
疎注意機構の実装において、履歴記録を指すアドレススキームの変更が必要ですが、その他のアーキテクチャはほとんどそのまま適用可能です。
これにより、疎構成であっても、Transformer は任意の計算プロセスをシミュレートできる潜在能力を持っていることが示され、これがさまざまな複雑な計算タスクにおける Transformer の応用の理解と拡張に対する理論的な基盤を提供します。
疎注意機構の制限
この課題は、 個の単位ベクトル が与えられたとき、各ベクトル に対して対応する最遠ベクトル を見つけることです。
ここでの「最遠」とは、ベクトル空間で 2 つのベクトル間のユークリッド距離が最大であることを意味します。実際には、これが内積を最小化することに相当します。
完全な注意機構では、この課題は比較的簡単に解決できます。なぜなら、この機構はすべてのベクトル対に対して内積計算を許すからです。
言い換えれば、完全な自己注意機構は、すべてのベクトル対間の関係を同時に評価できるため、 層で各ベクトルの最遠ベクトルを見つけることができます。
疎注意機構の場合、状況は大きく異なります。
OVC と論文のモデル条件の下では、1 層あたり 辺の注意でこの課題を解くには 層が必要です。波形記号は多重対数因子を省きます。完全な注意の定数層でも、各層の組合せ演算は二次です。これは条件付きの下界であり、任意の幅や外部演算を許したモデル全般への主張ではありません。
これは、疎注意機構では計算資源の消費を削減できるものの、特定のタイプの問題を解決する際に、実際にはより多くの層が必要であり、実用上の制限になる可能性があることを示しています。
討論
本節では、自然言語処理(NLP)タスクでより長い入力シーケンスを扱う利点を見ていきます。まず質問応答(QA)、次に長文書の要約を取り上げ、長い文脈がそれぞれの結果を改善できるかを確認します。
QA-dev
- データセット:HotpotQA、Natural Questions、TriviaQA、WikiHop を含む。
- 評価指標:基本的なサイズのモデルを使用し、WikiHop の精度、および HotpotQA、Natural Questions、TriviaQA の F1 スコアを報告。
BigBird は良好な結果です。Table 2 の ITC/ETC は HotpotQA Answer が 75.7/75.5、TriviaQA が 79.5/78.7、WikiHop はともに 75.9 です。ETC はほかの複数指標で上回ります。
QA Test finttune
- タスクとデータセット:HotpotQA、Natural Questions、TriviaQA、WikiHop を含む。
- ベンチマーク:BIGBIRD-ETC モデルと BIGBIRD を除いたランキング上位 3 つのモデルを比較。
この実験では、BIGBIRD-ETC は Natural Questions の長い答え、TriviaQA、WikiHop のテストで新しい SOTA を達成しました。一方、Natural Questions の短い答えと HotpotQA の Answer・Joint では首位ではありません。BIGBIRD は単一モデルで、Natural Questions の上位エントリーにはアンサンブルが多く、著者らは短い答えの結果にその違いが影響した可能性を挙げています。
長文書要約能力
ここでは arXiv、PubMed、BigPatent の 3 データセットを使い、エンコーダーに BigBird の疎注意、デコーダーに完全な自己注意を使っています。基礎モデルは RoBERTa、Large モデルは Pegasus の重みから初期化しています。Table 4 では Large の BigBird-Pegasus が 3 データセットすべての ROUGE-1/2/L で表中の Pegasus 比較行を上回ります。
著者らは、長い入力を扱えることで文書中に散らばる情報を拾いやすくなると考えています。長文書を扱う方法として興味深い結果です。
結論
これまでの Sparse Transformer や Longformer などのモデルと比べて、本文の主要な貢献は、疎注意機構に対する詳細な数学的理論の証明を提供した点にあります。
完全な注意に近い能力を、ランダム接続・スライディングウィンドウ・一部のグローバルトークンを組み合わせて狙う設計です。ただし、万能近似の定理で十分条件とされたのは星型構造を含むことです。
Transformer の理論的性質を掘り下げ、疎注意でも万能近似やチューリング完全性が成り立つ条件を示した点が、この論文の大きな貢献です。実験では長い系列を扱う利点も示しています。
証明方法の詳細については、論文の付録に約 20 ページ分の内容があり、興味のある読者は元の論文を参照することをお勧めします。