修士論文 要旨

Approximation and Estimation Ability of Transformers forSequence-to-sequence Function with Inﬁnite Dimensional Input（無限次元入力トランスフォーマーの近似及び推定能力について）
高倉 将吉

数理情報学専攻 48226214

鈴木 大慈 准教授

指導教員

る．ある無限次元入出力の真の関数 F ◦ : [0, 1]∞ → R∞

1 はじめにが存在して，出力が Y (i) := F ◦ (X (i) ) + ξ (i) と生成さトランスフォーマーは自己注意機構を用いた深層学習アーキテクチャであり，自然言語処理や画像処理など(i)れるとする．ここで，ξj (j ∈ N) は正規分布 N (0, σ 2 )にしたがう独立な確率変数である．の特に入力の次元が高いタスクにおいて高い性能を示している．本研究では，無限次元入出力のノンパラメト推定量 F̂ の評価には，以下のような平均二乗誤差を用いる．

リック回帰問題において，トランスフォーマーの近似能X
1ERl,r (F̂ , F ) =r−l+1r◦

力および推定能力を解析した．特に，真の関数の滑らかF̂i − Fi◦i=l

さが入力の方向ごとに異なる場合について入出力の次元に依存しない収束レートを示し，トランスフォーマー

2


,2,PX

本 研 究 で は 特 に ，観 測 さ れ た n 個 の 入 出 力 デ ー タn

かな方向が入力ごとに異なるような関数クラスを提案(X (i) , Y (i) ) i=1 に対してトランスフォーマーのクラ2
Pn Pr (i)(i)
スの中で経験損失
F(X)−Yをjj
i=1j=l

し，同様の収束レートを示した．

最小化する推定量 F̂ の性能を解析する．

が次元の呪いを回避できることを示した．さらに，滑ら3.2

2 既存研究トランスフォーマーモデル

トランスフォーマーは (1) 全結合層，(2) 自己注意機

有限次元入出力の場合については学習可能な位置符

構，(3) 位置符号化の 3 つの要素から構成される．ま号化を用いたトランスフォーマーが任意の連続関数をず，横幅 W の L 層の全結合層 f (x) := (AL η(·) +近似できることを示している [4]．しかしながら，必要なパラメータ数は入力次元に対して指数関数的に増大

bL ) ◦ · · · ◦ (A1 x + b1 ) で あ っ て ，∥Al ∥∞ , ∥bl ∥∞ ≤PLB, i=1 ∥Ai ∥0 + ∥bi ∥0 ≤ S を満たすものからなるクしてしまい，これは回避できない [4]．よって，意味のラスを Ψ(L, W, S, B) とする．次に埋め込み次元 D, 窓ある収束レートを得るためには，関数クラスを適切に幅 U の自己注意機構 g(X)i := xi +制限する必要がある．この観点から，入力の一部にのみ

i + U ] Softmax((Kh X[i − U :依存するブール値入力の関数クラス [1] や階層的な構造あって，∥Kh ∥∞ , ∥Qh ∥∞ , ∥Vh ∥∞ ≤ B を満たすものを持った関数クラス [2] についてトランスフォーマーのか ら な る ク ラ ス を A(U, D, H, B) と す る ．た だ し ，近似能力および推定能力が解析されている．しかし，こX[i − U, i + U ] = [xi−U , . . . , Xi+U ] と定めた．最後

れらの研究では収束レートが入力次元に依存しており，に，位置符号化を EncP (X) = EX + P と定める．ここ無限次元入力を含む非常に入力の次元が高い設定ではで，P は固定された位置符号化である．以上により，ト意味のある結果を得ることができない．一方，畳み込みランスフォーマーのクラスは以下のように定義される．

ニューラルネットワークについては，無限次元入力の設:= {fM ◦ gM ◦ · · · ◦ f1 ◦ g1 ◦ EncP | ∥E∥∞ ≤ B,する収束レートが示されている [3].

fi ∈ Ψ(L, W, S, B), gi ∈ A(Ui , D, H, B)} ,3 問題設定

以

入力トークンの次元 d に対して，[0, 1]
度 PX にしたがう確率変数 X

n=

下では解

析の都合，推定TR oF̃i (X) = min {R, max {−R, Fi (X)}} | F ∈ T:=

量 の 有 界 性 を 保 証 し た

ノンパラメトリック回帰問題(i)h=1 Vh X[i − U :i + U ])⊤ (Qh xi )) でT (M, U, D, H, L, W, S, B)

定において非等方的な滑らかさを持つ関数クラスに対

3.1

PHd×∞(i)xjo∞ 上の確率測を考えj=−∞nというクラスを考えることにする．

上Approximation and Estimation Ability of Transformers for Sequence-to-sequence Function with Inﬁnite Dimensional Input ( 高倉 将吉)

3.3のノルムである．また，領域の分割 {Ωλ }λ∈Λ への正則

γ 平滑空間条件として，ある定数 c > 0 に対して以下の条件を満た√ 2 cos(2π|rij |x)ψrij (x) := 1√
2 sin(2π|rij |x)YYψr (X) :=ψrij (Xij )i=1 j=1

δs (f ) =す重要度関数 µ : Ω → R∞ が存在することを仮定する．

(rij < 0),(rij = 0),(rij > 0),X

Ωλ = {X ∈ Ω | µ(X)πλ (1) > · · · > µ(X)πλ (2V +1) },µ(X)πλ (i) ≥ µ(X)πλ (i+1) + ci−β

4 主結果

⟨f, ψr ⟩ ψr .

本稿では推定誤差に関する結果のみを紹介する．

r∈Zd×∞,⌊2sij −1 ⌋≤rij <2sij0とする．このとき，p ≥ 2, θ ≥ 1 に対して γ 平滑空間は以下のように定義される．

noγFp,θ
:= f ∈ L2 ([0, 1]d×∞ ) | ∥f ∥F γ < ∞ .
ここで，∥f ∥F γ :=p,θγ

θ2θγ(s) ∥δs (f )∥p,PXs∈Nd×∞01/θは Fp,θ のノルムである．γ は各方向の滑らかさを表す関数であり，本研究では特にある数列 a ∈ Rd×∞を>0用いて (1) 異方平滑 γ(s) = ⟨a, s⟩，(2) 混合平滑 γ =max {aij sij | i ∈ [d], j ∈ Z} と表される場合を扱う．ここで，a は各方向の滑らかさを表すパラメータであり，aij が大きいほどその方向の滑らかであると言える．一方で，aij が小さいほど関数はその方向に大きく変化するため，重要な方向であると言える．滑らかさパラメー
タ a に関して ā を aij を昇順に並び替えた数列として，∥a∥wlα := supj j α ā−1j , ã :=P∞
−1 −1と定める．

i=1 āi

また，簡単のため混合平滑の場合には a† = ã，異方平滑の場合には a† = ā1 と定める．

3.4

推定誤差解析

真の関数 F ◦ がシフト同変であり 0 番目のトークンに対応する出力 F0◦ が（区分）γ 平滑空間の単位球に含まp,θP4.1れており，ある定数 R に対して ∥F0 ∥∞ ≤ R を満たすとする．また，ある 0 < α < ∞ について滑らかさパラ
メータ a が ∥a∥wlα ≤ 1 と aij = Ω(log(|j| + 1)) (γ 平滑空間の場合), aij = Ω(j α ) (区分 γ 平滑空間の場合)を満たすとする．特に F ◦ が区分 γ 平滑関数の場合，重要度関数 µ が γ 平滑関数に関する仮定を満たすとする．
さらに，混合平滑の場合には ā1 < ā2 を仮定する．
以上の仮定のもとで，ハイパーパラメータを適切に設定した経験損失最小化推定量 F̂ の推定誤差は以下のように評価できる．

• γ 平滑空間の場合
Rl,r (F̂ , F ) ≲ n

γ 平滑空間では滑らかさは入力によらず一定であり，重要な方向は変化しない．しかし，実際の応用では入力ごとに重要な方向が異なると考えられる．そこで各2a†2a† +1(log n)2/α+2+max {4/α,4} .

• 区分 γ 平滑空間の場合
Rl,r (F̂ , F ) ≲ n

区分 γ 平滑関数−−2a†2a† +1

どちらの場合も主要項は n−(log n)5/α+2+max {4/α,4} .
2a†2a† +1であり，a† は滑らかさのみに依存するため，推定誤差は入力や出力の次元に依存しないことがわかる．

領域ごとに滑らかな方向が異なる区分 γ 平滑関数を次

参考文献のように定義する．まず，分布のサポート Ω の分割[1] Benjamin L. Edelman, Surbhi Goel, Sham Kakade,and Cyril Zhang. Inductive Biases and Variable Creation in Self-Attention Mechanisms. In Proceedings ofthe 39th International Conference on Machine Learning, pp. 5793–5831. PMLR, 2022.
[2] Iryna Gurevych, Michael Kohler, and Gözde GülŞahin. On the rate of convergence of a classiﬁer basedon a Transformer encoder. IEEE Transactions on Information Theory, 2022.
[3] Sho Okumoto and Taiji Suzuki. Learnability of convolutional neural networks for inﬁnite dimensional input
via mixed and anisotropic smoothness. In International Conference on Learning Representations, 2022.
[4] Chulhee Yun, Srinadh Bhojanapalli, Ankit SinghRawat, Sashank Reddi, and Sanjiv Kumar. Are
Transformers universal approximators of sequence-tosequence functions? In International Conference on
Learning Representations, 2020.

{Ωλ }λ∈Λ が与えられているとする．V ∈ N に対して，{1, . . . , 2V + 1} から {−V, . . . , V } への全単射 πλ に対してトークンを並び替える写像 Πλ と Π を次のように定める．

Πλ ([x−V , . . . , xV ]) := [xπλ (1) , . . . , xπλ (2V +1) ],Π(X) := Πλ ([x−V , . . . , xV ]) (X ∈ Ωλ ).
以上を用いて区分 γ 平滑関数はnoγγPp,θ(Ω) := g = f ◦ Π | f ∈ Fp,θ, ∥g∥P γ < ∞ ,p,θと 定 義 さ れ る ．こ こ で ，∥g∥P γ

Pθ

d×[−V :V ]s∈N02θγ(s) ∥δs (f ) ◦ Π∥p,PX

1/θ

:=p,θ

はγ
Pp,θ