search

e4exp / paper_manager_abstract

0 stars 0 forks source link

On the Computational Power of Transformers and its Implications in Sequence Modeling #573

Open e4exp opened 2 years ago

e4exp commented 2 years ago

トランスフォーマーは、様々なシーケンスモデリングのタスクで幅広く使用されています。 トランスフォーマーの内部構造を実験的に解明するために、多大な研究努力が払われてきました。 しかし、Transformerの能力と固有の限界についての概念的・理論的理解はまだ浅い。 特に、位置エンコーディング、アテンションヘッド、残差接続、フィードフォワードネットワークなど、Transformerの様々な構成要素の役割は明らかになっていない。 本論文では、これらの疑問に答えるための一歩を踏み出した。 我々は、チューリング完全性によって把握される計算能力を分析する。 まず、バニラトランスフォーマーがTuring-completeであることを示すために、代替となるより単純な証明を提供し、次に、位置マスキングのみのトランスフォーマーと位置エンコーディングのないトランスフォーマーもTuring-completeであることを証明する。 さらに、ネットワークのチューリング完全性に対する各構成要素の必要性を分析したところ、興味深いことに、特定のタイプの残余接続が必要であることがわかりました。 この結果の実用的な意味を、機械翻訳と合成タスクの実験によって示す。

https://github.com/satwik77/Transformer-Computation-Analysis

e4exp commented 2 years ago

1 はじめに

Transformer（Vaswaniら、2017年）は、機械翻訳（Ottら、2018年）、言語モデリング（Radfordら、2018年）、質問応答（Devlinら、2019年）など、さまざまなNLPタスクにおいて最先端の結果をもたらした、最近の自己注意に基づくsequence-to-sequenceアーキテクチャです。 Transformersの亜種が多数提案されているが、これらの亜種の根底にはやはりオリジナルのアーキテクチャがある。 Transformersのような機械学習モデルの学習と一般化がその分析における中心的な目標であるが、この目的のための不可欠な前提条件は、モデルの計算能力の特徴付けである： あるタスクのためのモデルの学習は、モデルがそのタスクを実行することが計算上できない場合には成功しない。

リカレントネットワーク（RNN）の計算能力は何十年も前から研究されていますが（Kolen and Kremer, 2001; Siegelmann, 2012）、トランスフォーマーに関してはまだ初期段階にあります。 有名なSiegelmannとSontag（1992）の研究では、任意の精度を仮定して、RNNがTuring-completeであることが示されました。 最近では、Perez et al. ´ (2019)が、ハードアテンションを持つバニラトランスフォーマーも、任意の精度を与えればチューリングマシンをシミュレートできることを示した。 しかし、RNNとは対照的に、Transformerは複数のコンポーネントで構成されており、どのコンポーネントがそのチューリング完全性に必要であり、それによってその計算表現力に決定的な影響を与えるのかは不明である。 Transformerの様々な構成要素がその有効性に果たす役割は、さらなる改良のための重要な問題です。 Transformerは入力を逐次処理しないため、何らかの位置情報が必要となります。順序情報を捉えるために、様々な位置符号化方式が提案されています（Shaw et al.2018; Dai et al.2019; Huang et al.2018）。 同時に、機械翻訳について、Yangら（2019）は、Transformerの位置マスキングのみの場合（Shenら、2018）、位置エンコーディングを用いた場合と同等の性能を発揮することを示した。 位置マスキング（図1）の場合、明示的な符号化とは対照的に、モデルは先行する入力の上にアテンダンスすることだけが許され、追加の位置符号化ベクトルは入力ベクトルに結合されません。 Tsaiら（2019）は、位置マスキングを用いた場合、明示的な符号化が必要かどうかという問題を提起した。 さらに、Perez et al. ´ (2019)のTuringcompleteness証明は残差接続に大きく依存していたため、これらの接続がTuring-completenessに必須であるかどうかを問うた。 本論文では、そのような疑問に答えるための一歩を踏み出す。 以下に、本論文の主な貢献を列挙します。

image

image

e4exp commented 2 years ago

2 関連研究

ニューラルネットワークの計算力は、McCulloch and Pitts (1943) の基礎論文以来、研究されてきました。 特に、sequence-to-sequenceモデルのうち、RNNのこの側面は古くから研究されてきました(Kolen and Kremer, 2001)。 Siegelmann and Sontag (1992)による代表的な研究では、RNNがunbounded precisionを用いてTuring machineをシミュレートできることが示された。 Chenら（2018）は、ReLU活性化を持つRNNもTuring-completeであることを示した。 最近の多くの作品は、実用的な設定でRNNの計算能力を探っている。 いくつかの作品(Merrill et al., 2020)、(Weiss et al., 2018)では、最近、RNNがカウンター的な言語を認識する能力を研究した。 また、バランスの取れた括弧の文字列を認識するRNNの能力も研究されている（Sennhauser and Berwick, 2018; Skachkova et al., 2018）。 しかし、Transformerに関するこのような分析は少ない。 トランスフォーマーに関する理論的な研究は、トランスフォーマーの概念を公式化し、任意の精度を与えられたチューリングマシンをシミュレートできることを示したPerez et al. ´（2019）によって開始されました。 我々の研究と並行して、自己注意に基づくモデルを理解するためのいくつかの取り組みが行われている（Levine et al.2020; Kim et al. 2020 Hronら(2020)は、ヘッドの数が無限大になる傾向にあるとき、Transformerはガウス過程として振る舞うことを示している。 Hahn (2020)は、Transformerエンコーダーが正規言語と文脈自由言語をモデル化する際の限界を示した。 最近、Transformerは、任意の精度が与えられた配列-配列関数の普遍的な近似器であることが示された(Yun et al., 2020)。 しかし、これらはTransformerの完全なアーキテクチャには適用できない2。 我々と同様の目的で、Tsaiら（2019）はカーネル定式化による注意メカニズムの研究を試みた。 しかし、Transformerの様々なコンポーネントの体系的な研究は行われていない。

e4exp commented 2 years ago

3 定義と前置詞

計算に使用する数字は，Qと呼ばれる有理数の集合である． 数列X = (x1, ... , xn)に対して，1 ≤ j ≤ nのとき，Xj := (x1, ... , xj )とする． ここでは，大きさmのアルファベットΣを用い，#と$はそれぞれ入力数列の始まりと終わりを表す特別な記号である． 記号は，与えられた「基本」埋め込み fb : Σ → Q^db を介してベクトルにマッピングされる． 例えば、このエンベッディングは、RNNがシンボルを処理する際に用いられるものである。 ここでは，fb(#) = 0db，fb($) = 0db とした． 位置のエンコーディングは、関数pos : N → Q^db とする． これらを組み合わせることで，位置iにあるシンボルsの埋め込みをf(fb(s), pos(i))で与え，単にfb(s)+pos(i)とすることが多い． ベクトル[s]∈Qmは，シンボルs∈Σのワンhot符号化を表す。

3.1 RNNs

RNNの定義はSiegelmann and Sontag (1992)に従っています。 配列s1s2 ... sn ∈ Σ ∗）をRNNに与えるために、これらをベクトルx1, x2, ... ... , xnに変換します。 xi = fb(si)とします。 RNNは再帰式ht = g(Whht-1 + Wxxt + b)で与えられ、t ≥ 1、関数g(-)は活性化σ、バイアスベクトルb∈Qdh、行列Wh∈Qdh×dh、Wx∈Qdh×db、ht∈Qdhは与えられた初期隠れ状態h0を持つ隠れ状態、dhは隠れ状態の次元である。 最後のシンボルsnが入力された後、RNNが停止するまで、終端シンボルfb($)を入力し続ける。 これにより、RNNは入力を読み込んだ後、計算を実行することができます。 seq-to-seqニューラルネットワークのクラスは、そのネットワークが認識する言語のクラスが、まさにチューリングマシンが認識する言語のクラスである場合、チューリング完全である。

定理3.1. (Siegelmann and Sontag, 1992)

チューリングマシンで計算可能な任意のseq-to-seq関数Σ ∗ → Σ ∗ は、RNNでも計算可能である。 詳細は、付録のB.1節を参照してください。

3.2 Transformerアーキテクチャ

バニラ・トランスフォーマー

ここでは、Perez et al. ´ (2019)によって形式化された位置符号化を伴うオリジナルのTransformerアーキテクチャ(Vaswani et al., 2017)を、いくつかの修正を加えて説明します。 このサブセクションのすべてのベクトルは、Q^dからのものです。 Transと示されるトランスフォーマーは、seq-to-seqアーキテクチャである。 その入力は、 (i)ベクトルのシーケンスX = (x1, ... , xn)、 (ii)シードベクトルy0からなる。

出力は，ベクトルのシーケンスY = (y1, ... , yr)である． 配列Xは，記号列（s1, ... , sn）∈Σnから，前述のエンベッディングを用いて，xi = f(fb(si), pos(i))として得られる。 変換器は、変換器エンコーダと変換器デコーダの組み合わせで構成されています。 トランスフォーマー層のフィードフォワードネットワークには、Siegelmann and Sontag (1992)の活性化、すなわち、x < 0で値0、0 < x < 1で値x、x > 1で値1をとる飽和線形活性化関数σ(x)を使用します。 この活性化は、σ(x)=ReLU(x) - ReLU(x - 1)により、標準的なReLU活性化に簡単に置き換えることができます。

自己注意。

セルフアテンションメカニズムは、入力として (i)クエリベクトルq、 (ii)一連のキーベクトルK = (k1, ... , kn)、 (iii)一連のバリューベクトルV = (v1, ... , vn)を受け取ります。 KとVに対するq-attention（Att(q, K,V )と表記）は、ベクトルa = α1v1+α2v2+- -+αnvnであり、 (i) (α1, ... , αn) = ρ(f att(q, k1), ... ... , f att(q, kn)) となります。, (ii) 正規化関数ρ : x = (x1, ... , xn)∈Qnにおいて、x1, ... , xnの中で最大値がr回発生する場合、hardmax(x1, ... , xn)とする。 xnの中で最大値がr回発生した場合、xiが最大値であればhardmax(x)i := 1/r、そうでなければhardmax(x)i := 0となります。 実際にはsoftmaxがよく使われますが、その出力値は一般に合理的ではありません。 (iii) バニラ変換の場合、使用されるスコアリング関数f attは、乗算的注意（Vaswani et al., 2017）と非線形関数の組み合わせである：f att(q, ki) = - hq, kii . これはPerezら´（2019）でも使われていた。

トランスフォーマーエンコーダ。

単層のエンコーダは，関数Enc(X; θ)であり，入力X = (x1, ... , xn)はQdのベクトルのシーケンス，パラメータθであり，出力はQdのベクトルの別のシーケンスZ = (z1, ... , zn)である． パラメータθは，Qd → Qd型の関数Q(-)，K(-)，V(-)，O(-)を指定しています． 関数Q(-)、K(-)、V(-)は線形変換、O(-)はFFNである。 1≦i≦nの場合、自己吸着ブロックの出力は次のように生成されます。

image

この演算はエンコーダエンコーダーのアテンションブロックとも呼ばれる。 出力Zは、1≦i≦nの場合、zi＝O（ai）＋aiで計算され、加算演算＋xiと＋aiが残差接続となる。 完全なL層トランスエンコーダTEnc(L) (X; θ) = (Ke ,V e ) は、単層エンコーダと同じ入力X = (x1, ... , xn) を持つ。 一方，その出力であるKe = (k e 1 , . . . , k e n ) とV e = (v e 1 , . . . v e n ) には，2つのシーケンスが含まれている． TEnc(L)は，L個の単層エンコーダーの合成によって得られる． X(0) := Xとし，0 ≤ l ≤ L - 1に対して，X(l+1) = Enc(X(l) ; θ`)とし，最終的に，Ke = K(L) (X(L) ), V e = V(L) (X(L) ) となる．