Transformerは優れたモデルか？

# はじめに
この記事は、鈴木大慈先生の論文[1]の付録部分についての備忘録です。

Transformerをベースとした生成AIに多額のお金が投資されてます。また、Transformerをベースとした日本語に対応したLLMがリリースされるたびにニュースで取り上げられるなど注目されています。なぜTransformerがすごいのか？という根拠を、数理工学的に解説した論文[1]は、社会的に価値があると思い、備忘録を公開します。

# Transformerは優れたモデルか？
論文[1]では、「Transformerは、はたして優れたモデルなのか？」を解析しています。

結論から言うと、

- 無限次元入力のsequence-to-sequence関数に対し、Transformerは近似・推論能力をもつ
- Attentionは、入力列に応じて重要なトークンを選択することができる


# C. Auxiliary Lemmas

## Lemma C.1.

下の式変形に注意すればよい。

```math
\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は、下記の記事を参照ください。

https://mathlog.info/articles/lqrISJVIvbZ4ugOiQCHv

## Lemma C.4.

### FNNのクラス
FNN layerについて紹介する。深さ$L$、幅$W$のFNNは、
```math
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のノルム

```math
\lVert X \rVert_{\infty} = \sup_{i\in [d],\ j\in \mathbb{Z}}|X_{ij}|
```

行列のL0ノルム
```math
\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$で定まる

```math
\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]$とすれば、

```math
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$とおいて、
```math
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$で定まる。

```math
\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 
```

### 式変形

```math
\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$とすると、

```math
\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)$は定義される。

```math
\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から

```math
\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


```math
|\|x-y\|^2-\|z-y\|^2| = \langle x-z, x+z-2y\rangle
```

```math
\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}
```

```math
\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$について、以下が成り立つ。
> ```math
> \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)
> ```

浪人さんのブログ、わかりやすくてすごいです！

https://seetheworld1992.hatenablog.com/entry/2017/06/12/211954


```math
\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.

https://arxiv.org/abs/2305.18699