はじめに
この記事は、鈴木大慈先生の論文[1]の付録部分についての備忘録です。
Transformerをベースとした生成AIに多額のお金が投資されてます。また、Transformerをベースとした日本語に対応したLLMがリリースされるたびにニュースで取り上げられるなど注目されています。なぜTransformerがすごいのか？という根拠を、数理工学的に解説した論文[1]は、社会的に価値があると思い、備忘録を公開します。
Transformerは優れたモデルか？
論文[1]では、「Transformerは、はたして優れたモデルなのか？」を解析しています。
結論から言うと、
- 無限次元入力のsequence-to-sequence関数に対し、Transformerは近似・推論能力をもつ
- Attentionは、入力列に応じて重要なトークンを選択することができる
C. Auxiliary Lemmas
Lemma C.1.
下の式変形に注意すればよい。
\sum_{j=1}^{d}e^{\theta_j} \geq e^{\theta_{i^\ast}} \ \ (\because e^x\geq 0)
Lemma C.2.
工事中
Lemma C.3.
内積が許容誤差$\varepsilon$以下であれば、正規直交基底みたいな身分を付与することにする。そうすると、正規直交基底みたいな身分に要する必要な次元が、対数オーダーだけで実現できることを主張している。Chernoff Boundsを用いて証明しており、かっこいい。Chernoff Boundsは、下記の記事を参照ください。
Lemma C.4.
FNNのクラス
FNN layerについて紹介する。深さ$L$、幅$W$のFNNは、
f(x) := (A_L\eta(\cdot)+b_L)\circ\cdots\circ (A_1 x+b_1)
ここで、ReLU活性化関数は、$\eta(x) = \max\lbrace x, 0\rbrace$である。
無限次元sequenceのノルム
\lVert X \rVert_{\infty} = \sup_{i\in [d],\ j\in \mathbb{Z}}|X_{ij}|
行列のL0ノルム
\lVert A \rVert_{0} = |\lbrace (i,j) | A_{ij}\neq 0\rbrace|
FNNのクラス$\Psi(L,W,B,S)$は、深さ$L$、幅$W$、norm bound$B$、sparsity $S$で定まる
\Psi(L,W,B,S):=\lbrace f \ \ | \max_{i} \lbrace
\lVert A_{i}\rVert_{\infty}, \lVert b_{i}\rVert _{\infty} \rbrace \leq B, \ \
\sum_{i=1}^{L} \lVert A_{i} \rVert_{0} + \lVert b_{i} \rVert_{0} \leq S \rbrace
Attentionのクラス
埋め込み次元$D$、Head数$H$、窓幅$U$、$K_h\in \mathbb{R}^{D^\prime\times D}$、$Q_h\in \mathbb{R}^{D^\prime\times D}$、$V_h\in \mathbb{R}^{D\times D}$とする。self-attention layer $g$は、Value行列$V_h X[i-U:i+U]$とすれば、
g(X)_i = x_i + \sum_{h=1}^{H}V_h X[i-U:i+U] A_h
ただし、キー行列$K^{(h)}X[i-U:i+U]$、クエリベクトル$Q^{(h)}x_i$とおいて、
A_h:= \text{Softmax}((K^{(h)}X[i-U:i+U])^T(Q^{(h)}x_i))
Attentionのクラス$\mathcal{A}(U,D,H,B)$は、窓幅$U$、埋め込み次元$D$、Head数$H$、norm bound$B$で定まる。
\mathcal{A}(U,D,H,B) = \lbrace g \ \ |
\max_{h}\lbrace
\lVert K_{h}\rVert _{\infty}, \ \
\lVert Q_{h}\rVert _{\infty}, \
\lVert V_{h}\rVert _{\infty} \rbrace\leq B
\rbrace
式変形
\begin{align}
\lVert (K_{h}\bar{X})^TQ_{h}x_i - (K_{h}\bar{X})^TQ_{h}x_{i}^{\prime})\rVert _{\infty}
&\leq \lVert K_{h}\rVert _{\infty} \lVert \bar{X}\rVert _{\infty} \lVert Q_{h}\rVert _{\infty}\lVert x_i -x_{i}^{\prime} \rVert _{\infty} \\
&\leq (BD)(rD)(BD) \lVert X_i - X_{i}^{\prime} \rVert _{\infty}\\
&= rB^2 D^3 \lVert X_i -X_{i}^{\prime} \rVert _{\infty}
\end{align}
うーん、なぜ$D$がいるのでしょうねぇ...
Lemma C.5.
結構、簡単に計算できます。
Lemma C.6.
結構、簡単に計算できます。
Lemma C.7.
結構、簡単に計算できます。
D. Approximation ability of FNN
Lemma D.1.
結構、簡単に計算できます。
Lemma D.1.
結構、簡単に計算できます。
Lemma D.2.
結構、簡単に計算できます。
Theorem D.3.
結構、簡単に計算できます。
E. Proof of Theorem 4.2
Embedding layer
埋め込み次元$D$とすると、Embedding layerは、Positional encoding $P$とすると、
\text{E}_{\text{ncp}} = EX + P
ただし、$E\in \mathbb{R}^{D\times d}$、$P=[p_i]_{i=-\infty}^{\infty}\in \mathbb{R}^{D\times d}$である。
Transformerのクラス
Transformerのクラス$F\in\mathcal{T}(M,U,D,H,L,W,S,B)$は定義される。
\mathcal{T}(M,U,D,H,L,W,S,B)
= \lbrace f_M\circ g_M\circ\cdots \circ f_1\circ g_1\circ \text{E}_{\text{ncp}} \ \ |\ \ \lVert E\rVert _{\infty}\leq B, \ f_i \in \Psi(L,W,S,B), \ g_i \in \mathcal{A}(U_i,D,H,B)\rbrace
式変形
$s_{j_h}^{(h)}\geq s_{j}^{(h)}+\chi/U^2$であり、$j\leq U$であるので、Lemma C.1から
\lVert e_{j_h}-\text{softmax}(s^{(h)})\rVert _{1}
\leq 2Ue^{-\chi/U^2}
が成り立つ。
F. Proof of Theorem 4.5
結構、簡単に計算できます。
G. Proof of Theorem 5.2
式変形1
|\|x-y\|^2-\|z-y\|^2| = \langle x-z, x+z-2y\rangle
\begin{align}
\|x-y\|^2-\|z-y\|^2
&= \langle x-y,x-y \rangle - \langle z-y,z-y \rangle\\
&= \langle x,x \rangle -2 \langle x,y \rangle + \langle y,y \rangle
- \langle z,z \rangle +2 \langle z,y \rangle - \langle y,y \rangle\\
&= \langle x,x \rangle -2 \langle x,y \rangle - \langle z,z \rangle +2 \langle z,y \rangle\\
\end{align}
\begin{align}
\langle x-z, x+z-2y\rangle
&= \langle x,x\rangle + \langle x,z\rangle -2 \langle x,y\rangle
- \langle z,x\rangle - \langle z,z\rangle +2 \langle z,y\rangle\\
&= \langle x,x \rangle -2 \langle x,y \rangle - \langle z,z \rangle +2 \langle z,y \rangle
\end{align}
式変形2
Hoeffding's Inequalityに対して、Bernstein 's Inequalityは確率分布についての情報を用いて、よりきつくバウンドする。
Bernstein 's Inequality
$X_1,\cdots,X_n$を$\text{E}[X_i]=0$となる独立な確率変数で、確率1で$|X_i|\leq M$を満たすとする。
$\sigma^2=\dfrac{1}{n}\sum_{i=1}^{n}\text{Var}[X_i]$とする。
すべての$\varepsilon >0$について、以下が成り立つ。\text{Pr}\left(\left|\dfrac{1}{n}\sum_{i=1}^{n}X_i\right|>\varepsilon\right) \leq 2\exp\left(-\dfrac{n\varepsilon^2}{2\sigma^2+\dfrac{2M}{3}\varepsilon}\right)
浪人さんのブログ、わかりやすくてすごいです！
\begin{align}
\text{Pr}(T\geq \sqrt{t})
&= \text{Pr}\left(\max_j \sum_{i=1}^{n} \tilde{X}_i(j)\geq \sqrt{t}\right)\\
&= \text{Pr}\left(\bigcup_{j=1}^{N} \sum_{i=1}^{n} \tilde{X}_i(j)\geq \sqrt{t}\right)\\
&\leq \sum_{j=1}^{N}\text{Pr}\left(\sum_{i=1}^{n} \tilde{X}_i(j)\geq \sqrt{t}\right)\\
&= 2N\exp\left(-\dfrac{t}{2\left(8nR^2+\dfrac{4R^2}{3r}\sqrt{t}\right)}\right)
\end{align}
H. Proof of Theorem 5.3
結構、簡単に計算できます。
I. Proof of Theorem 5.4
結構、簡単に計算できます。
J. Proof of Theorem 5.5
結構、簡単に計算できます。
参考文献
[1] Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input, Shokichi Takakura and Taiji Suzuki, ICML2023.