カーネル法と深層学習の数理

カーネル法と深層学習の数理

鈴木大慈

東京大学大学院情報理工学系研究科数理情報学専攻 理研

2020

年

月

日

日

@

広島市立大学集中講義

1 / 37

Outline

1

カーネル法と

における確率的最適化 再生核ヒルベルト空間の定義

再生核ヒルベルト空間における最適化

2

深層ニューラルネットワークとカーネル

Outline

1

カーネル法と

における確率的最適化 再生核ヒルベルト空間の定義

再生核ヒルベルト空間における最適化

2

深層ニューラルネットワークとカーネル

3 / 37

線形回帰

デザイン行列

真のベクトル

モデル

リッジ回帰（Tsykonov 正則化）

βˆ←arg min

β∈R^p

1

n∥Xβ−Y∥²2+λ_n∥β∥²2.

変数変換

正則化項のため，

．つまり，

ある

が存在して，

と書ける．

(

等価な問題

α∈Rⁿ

1

n∥XX^⊤α−Y∥²2+λnα^⊤(XX^⊤)α.

※

より，観測値

と

の内積さえ計算できればよい．

線形回帰

デザイン行列

真のベクトル

モデル

リッジ回帰（Tsykonov 正則化）

βˆ←arg min

β∈R^p

1

n∥Xβ−Y∥²2+λ_n∥β∥²2.

変数変換

正則化項のため，

．つまり，

ある

が存在して，

と書ける．

(

等価な問題

α∈Rⁿ

1

n∥XX^⊤α−Y∥²2+λnα^⊤(XX^⊤)α.

※

より，観測値

と

の内積さえ計算できればよい．

4 / 37

リッジ回帰のカーネル化

リッジ回帰（変数変換版）

ˆ

α←arg min

α∈Rⁿ

1

n∥(XX^⊤)α−Y∥²2+λ_nα^⊤(XX^⊤)α.

※

はサンプル

と

の内積．

•

カーネル法のアイディア

x

の間の内積を他の非線形な関数で置き換える:

この

をカーネル関数と呼ぶ

カーネル関数の満たすべき条件 対称性:

正値性

i=1

∑m

j=1αiαjk(xi,xj)≥0, (∀{xi}^mi=1, {αi}^mi=1, m).

逆にこの性質を満たす関数なら何でもカーネル法で用いて良い．

リッジ回帰のカーネル化

リッジ回帰（変数変換版）

ˆ

α←arg min

α∈Rⁿ

1

n∥(XX^⊤)α−Y∥²2+λ_nα^⊤(XX^⊤)α.

※

はサンプル

と

の内積．

•

カーネル法のアイディア

x

の間の内積を他の非線形な関数で置き換える:

x_i^⊤x_j → k(x_i,x_j).

この

をカーネル関数と呼ぶ

カーネル関数の満たすべき条件 対称性:

正値性

∑m

j=1αiαjk(xi,xj)≥0, (∀{xi}^mi=1, {αi}^mi=1, m).

逆にこの性質を満たす関数なら何でもカーネル法で用いて良い．

5 / 37

カーネルリッジ回帰

カーネルリッジ回帰

として，

ˆ

α←arg min

β∈Rⁿ

1

n∥Kα−Y∥²2+λnα^⊤Kα.

新しい入力

に対しては，

y=

∑n

i=1

k(x,xi) ˆαi

で予測．

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-1 -0.5 0 0.5 1 1.5

カーネル関数

再生核ヒルベルト空間

ある

が存在して，

． カーネルトリック

i=1αiϕ(xi), ϕ(x)⟩Hk =∑n

i=1αik(xi,x).

→カーネル関数の値さえ計算できれば良い．

カーネルリッジ回帰

カーネルリッジ回帰

として，

ˆ

α←arg min

β∈Rⁿ

1

n∥Kα−Y∥²2+λnα^⊤Kα.

新しい入力

に対しては，

y=

∑n

i=1

k(x,xi) ˆαi

で予測．

カーネル関数

再生核ヒルベルト空間

ある

が存在して，

k(x,x^′) =⟨ϕ(x), ϕ(x^′)⟩_Hk

． カーネルトリック:

i=1αiϕ(xi), ϕ(x)⟩_Hk =∑n

i=1αik(xi,x).

→カーネル関数の値さえ計算できれば良い．

6 / 37

再生核ヒルベルト空間

(Reproducing Kernel Hilbert Space, RKHS)

入力データの分布：P

，対応する

空間：L

カーネル関数は以下のように分解できる

k(x,x^′) =

∑∞ j=1

µjej(x)ej(x^′).

(e_j)^∞_j=1

は

内の正規直交基底:

µ_j ≥0.

Definition ( 再生核ヒルベルト空間 ( H

))

⟨f,g⟩_Hk :=∑_∞

j=1 1

µ_jαjβj forf =∑_∞

j=1αjej, g =∑_∞

j=1βjej ∈L2(PX).

∥f∥_Hk :=√

⟨f,f⟩_Hk.

Hk :={f ∈L₂(P_X)| ∥f∥Hk <∞}equipped with⟨·,·⟩Hk.

再生性:

に対して

は内積の形で「再生」される:

f(x) =⟨f,k(x,·)⟩Hk.

再生核ヒルベルト空間の性質

ϕk(x) =k(x,·)∈ Hk

と書けば，k(x,

と書ける．この

を特徴写像とも言う．

カーネル関数に対応する積分作用素

Tkf :=

∫

f(x)k(x,·)dPX(x).

先のカーネル関数の分解は

のスペクトル分解に対応．

再生核ヒルベルト空間

は以下のようにも書ける

∥f∥_Hk = inf{∥h∥L2(PX)|f =T_k^1/2h, h∈L2(PX)}. f ∈ Hk

は

j=1ajõjej(x)

と書けて，

j=1a²_j

．

は

内の正規直交基底，

は

内の完全正規直交基底．

特徴写像

を完全正規直交基底に関する係数で表現すると

µ1e1(x),√

µ2e2(x), . . .)^⊤

8 / 37

再生核ヒルベルト空間のイメージ

非線形な推論を再生核ヒルベルト空間への非線形写像

を用いて行う．

再生核ヒルベルト空間では線形な処理をする．

Reproducing Kernel Hilbert Space

カーネル法は第一層を固定し第二層目 のパラメータを学習する横幅無限大の

層ニューラルネットワークともみな せる．

(

浅い 学習手法の代表例)

カーネルリッジ回帰の再定式化

再生性:

に対し

f(x) =⟨f, ϕ(x)⟩_Hk.

カーネルリッジ回帰の再定式化

fˆ← min

f∈Hk

1 n

∑n i=1

(y_i−f(x_i))²+C∥f∥²_Hk

表現定理

∃α_i ∈R s.t. ˆf(x) =

∑n i=1

α_ik(x_i,x),

⇒ ∥ˆf∥_Hk =√∑n

i,j=1α_iα_jk(x_i,x_j) =√ α^⊤Kα.

さきほどのカーネルリッジ回帰の定式化と一致．

10 / 37

カーネルの例

ガウシアンカーネル

k(x,x^′) = exp (

−∥x−x^′∥² 2σ²

)

多項式カーネル

k(x,x^′) =(

1 +x^⊤x^′)p

χ²-カーネル

k(x,x^′) = exp (

−γ²∑d j=1

(x_j−x_j^′)² (xj+x_j^′)

)

Mat´ern-kernel

k(x,x^′) =

∫

R^d

e^{iλ⊤(x−x′)} 1

(1 +∥λ∥²)^α+d/2dλ

グラフカーネル，時系列カーネル，...

Outline

1

カーネル法と

における確率的最適化 再生核ヒルベルト空間の定義

再生核ヒルベルト空間における最適化

2

深層ニューラルネットワークとカーネル

12 / 37

再生核ヒルベルト空間内の確率的最適化 (1)

問題設定:

yi =f^o(xi) +ξi.

(x_i,y_i)ⁿ_i=1

から

を推定したい．(f

は

にほぼ入っている) 期待損失の変形:

E[(f(X)−Y)²] =E[(f(X)−f^o(X)−ξ)²] =E[(f(X)−f^o(X))²] +σ²

→

を解けば

が求まる．

期待損失の

微分:

K_x =k(x,·)∈ Hk

とする．f

に気を付けると

L(f) =E[(f(X)−Y)²] =E[(⟨K_X,f⟩_Hk −Y)²]

の

内での

微分は以 下の通り:

∇L(f) = 2E[K_X(⟨K_X,f⟩_Hk −Y)]

= 2(E[KXK_X^∗]

| {z }

=:Σ

f −E[KXY])

= 2(Σf −E[KXY]).

再生核ヒルベルト空間内の確率的最適化 (2)

L(f) =E[(f(X)−Y)²]

の

内での

微分:

∇L(f) = 2E[KX(⟨KX,f⟩_Hk−Y)] = 2(E[KXK_X^∗]

| {z }

=:Σ

f −E[KXY]) = 2(Σf−E[KXY]).

期待損失の勾配法:

f_t^∗=f_t^∗₋₁−η2(Σf_t^∗₋₁−E[KXY]).

経験損失の勾配法

^{は標本平均}

ˆft = ˆft−1−η2(Σˆbft−1−Eb[KXY]).

確率的勾配による更新

g_t=g_t−1−η2(K_xitK_x^∗

itg_t−1−K_xity_it).

※

は

から

一様に取得．

14 / 37

勾配のスムージングとしての見方

関数値の更新式:

f_t^∗(x) =f_t^∗₋₁(x)−η2(Σf_t^∗₋₁−E[K_XY])(x)

=f_t^∗₋₁(x)−2η

∫

k(x,X) (f_t^∗₋₁(X)−Y)

| {z }

→f_t−1^∗ (X)−f^o(X)

dP(X,Y)

=f_t^∗₋₁(x)−2ηTk(f_t^∗₋₁−f^o)(x).

積分作用素

は高周波成分を抑制する作用がある．

RKHS

内の勾配は

内の関数勾配をT

によって平滑化したものになってい る．(実際は

のサンプルからの推定値を使う)

高周波成分が出てくる前に止めれば過学習を防げる．

→

迂闊に

法などを使うと危険．

Early stopping による正則化

Early stopping による正則化

初期値

訓練誤差最小化元

（過学習）

Early stopping

バイアス

バリアンス分解

∥f^o−ˆf∥L₂(P_X)

| {z }

Estimation error

≤ ∥f^o−fˇ∥L₂(P_X)

| {z }

Approximation error (bias)

+∥ˇf −ˆf∥L₂(P_X)

| {z }

Sample deviation (variance)

訓練誤差最小化元に達する前に止める

ことで正則化が働く．

無限次元モデル

は過学習しやすいので気を付ける必要がある．

16 / 37

解析に用いる条件

通常，以下の条件を考える． （統計理論でも同様の仮定を課す定番の仮定）

(Caponnetto and de Vito, 2007, Dieuleveut et al., 2016, Pillaud-Vivien et al., 2018)

µ_i =O(i^−α) forα >1.

α

は

の複雑さを特徴づける．

小さい

複雑，大きい

単純

f^o

が

からどれだけ

を特徴づけ．

r = 1/2

は

に対応．(r

はみ出てる,

含まれる)

∥f∥L_∞(P_X) ≲∥f∥¹_L⁻_2(P^µ_X)∥f∥^µ_Hk (∀f ∈ Hk) forµ∈(0,1].

Hk

に含まれている関数の滑らかさを特徴づけ． （小さい

滑らか）

※ 最後の条件について:

空間) かつ

の台が

で密度関数を持ち，その密度が下からある定数

で抑えられていれば，

µ=d/(2m)

でなりたつ．

収束レート

バイアス

バリアンスの分解

∥f^o−gt∥²L₂(P_X) ≲∥f^o−f_t^∗∥²L₂(P_X)

| {z }

(a):Bias

+∥f_t^∗−fˆt∥²L₂(P_X)

| {z }

(b):Variance

+∥ˆft−gt∥²L₂(P_X)

| {z }

(c):SGD deviation

(a) (ηt)^−2r, (b) ^{(ηt)1/α+(ηt)}_n ^µ−2r, (c)η(ηt)^1/α−1

(a)

勾配法の解のデータに関する期待値と真の関数とのズレ

．

勾配法の解の分散

．

(c)

確率的勾配を用いることによる変動

更新数

を大きくすると

は減るが

が増える．これらをバランスす る必要がある

Theorem (Multi-pass SGD の収束レート (Pillaud-Vivien et al., 2018))

η= 1/(4 sup_xk(x,x)²)

とする．

µα <2rα+ 1< α

の時，

とすれば，

E[L(gt)]−L(f^o) =O(n⁻2rα/(2rα+1)

).

µα≥2rα+ 1

の時，

とすれば，

18 / 37

Natural gradient の収束

Natural gradient (自然勾配法):

ˆf_t = ˆf_t−1−η(Σ +λI)⁻¹(bΣˆf_t−1−Eb[K_XY]).

(unlabeled data

が沢山あり

は良く推定できる設定

の解析

Theorem (Natural gradient の収束 (Amari et al., 2020))

E[∥fˆt−f^o∥²L2(P_X)]≲B(t) +V(t),

ただし，B(t

V(t) =(1 +ηt)λ⁻¹B(t) +λ^−α1

n +(1 +tη)⁴(1∨λ^2r−µ)λ^−α1

n .

特に，λ

で

※ バイアスは急速に収束するが，バリアンスも速く増大する．

→

のため高周波成分が早めに出現する．より早めに止め

ないと過学習する．

収束の様子

Natural gradient

Gradient descent Predictive error

Variance

Bias

Step

20 / 37

作用素 Bernstein の不等式

Σ =Ex[KxK_x^∗]: Σf =∫

k(·,x)f(x)dPx(x) Σ =b _n¹∑n

i=1Kx_iK_x^∗_i: Σfb = ¹_n∑n

i=1k(·,xi)f(xi)

Σλ:= Σ +λI

，

とする．以下のような評価が必要

∥Σ⁻_λ¹(Σ−Σ)Σb ⁻_λ¹∥≲

√F_∞(λ)β

n +(1 +F_∞(λ))β n with prob. 1−δ

．ただし，

．

→ 経験分布と真の分布のずれをバウンド．

Theorem ( 自己共役作用素の Bernstein の不等式 (Minsker, 2017))

(X_i)ⁿ_i=1

は独立な自己共役作用素の確率変数で

かつ，

σ²≥ ∥∑n

i=1E[X_i²]∥, U ≥ ∥X_i∥

とする．r

として，

P (

∑n i=1

X_i ≥t

)

≤14r(∑n

i=1E[X_i²]) exp (

− t² 2(σ²+tU/3)

) .

X_i= Σ⁻_λ¹K_xiK_x^∗

iΣ⁻_λ¹

とする．

も参照)

正則化ありの確率的最適化

二乗損失を拡張して，一般の滑らかな凸損失関数

を考える． （判別問題など）

正則化ありの期待損失最小化:

min

f∈Hk

E[ℓ(Y,f(X))] +λ∥f∥²_Hk =:Lλ(f).

これを

で解く．目的関数が

gt+1=gt−ηt(ℓ^′(yt,gt(xt)) +λgt).

¯ gT+1=

T+1∑

t=1

2(c0+t−1)

(2c₀+T)(T+1)gt (

多項式平均

仮定：(i)

は

kL_λ(g).

Theorem (Nitanda and Suzuki (2019))

適切な

に対して

とすれば，

E[L_λ(¯g_T+1)−L_λ(g_λ)]≲ M²

λ(c0+T)+ γ+λ

T+ 1∥g₁−g_λ∥²_Hk.

さらにマルチンゲール確率集中不等式より

も得られる．

判別問題なら

のもと判別誤差の指数収束も示せる．

マルチンゲール Hoeffding の不等式

Theorem (マルチンゲール Hoeffding 型集中不等式 (Pinelis, 1994))

確率変数列: D

．

とする．

∀ϵ >0

に対し

P [

max

1≤t≤T∥

∑t

s=1

Ds∥_Hk ≥ϵ ]

≤2 exp (

− ϵ² 2∑T

t=1R_t² )

.

Dt=E[¯gT+1|Z1, . . . ,Zt]−E[¯gT+1|Z1, . . . ,Zt−1],

ただし

とすれば，

t=1Dt= ¯gT+1−E[¯gT+1]

となり，期待値と実 現値のずれを抑えられる．

(補足) Lλ

は

ノルムに関して

∥g¯T+1−gλ∥_Hk ≤O( 1 λ²T)

が高い確率で成り立つ．実は

でもあるので，

|P(Y = 1|X)−P(Y =−1|X)| ≥δ

なるマージン条件

condition)

のもと，完全な判別が高い確率でできるようになる．

マルチンゲール Hoeffding の不等式

Theorem (マルチンゲール Hoeffding 型集中不等式 (Pinelis, 1994))

確率変数列: D

．

とする．

∀ϵ >0

に対し

P [

max

1≤t≤T∥

∑t

s=1

Ds∥_Hk ≥ϵ ]

≤2 exp (

− ϵ² 2∑T

t=1R_t² )

.

Dt=E[¯gT+1|Z1, . . . ,Zt]−E[¯gT+1|Z1, . . . ,Zt−1],

ただし

とすれば，

t=1Dt= ¯gT+1−E[¯gT+1]

となり，期待値と実 現値のずれを抑えられる．

(

補足

は

ノルムに関して

強凸であることより，

∥g¯T+1−gλ∥_Hk ≤O( 1 λ²T)

が高い確率で成り立つ．実は

でもあるので，

|P(Y = 1|X)−P(Y =−1|X)| ≥δ

なるマージン条件

condition)

のもと，完全な判別が高い確率でできるようになる．

23 / 37

( 参考 ) Strong low noise condition

Outline

1

カーネル法と

における確率的最適化 再生核ヒルベルト空間の定義

再生核ヒルベルト空間における最適化

2

深層ニューラルネットワークとカーネル

25 / 37

Integral representation

Definition: η andψareadmissible if

∫ bψ(ζ)bη(ζ)

|ζ|^d dζ <∞. (whereψ,b ηbare the Fourie traonsform ofψ,η).

Theorem (Sonoda and Murata (2015))

If f :R^d →Rand its Fourie transorm are in L1(R^d), andη, ψ are admissible (e.g., η is ReLU), then

T(w,b) =

∫

f(x)ψ(w^⊤x−b)∥x∥dx, f(x) =

∫

T(w,b)∥w∥⁻¹η(w^⊤x−b)dwdb (integral form).

Integral representation of deep neural network

Finite sum form

fˆ(x) =∑m

j=1v_jη(w_j^⊤x+b_j)

Integral form

f^o(x) =∫

h(w,b)η(w^⊤x+b)dwdb

ˆf(x) =WLη(WL−1η(WL−2. . . η(W1x+b1) +b2. . .)))

f^o(x) =f_L^o◦f_L^o₋₁◦ · · · ◦f₁^o(x) f_ℓ^o[F](τ,x) =

∫h^o_ℓ(τ, τ^′)η(F(τ^′,x))dQℓ(τ^′) +b_ℓ^o(τ).

Still universal approximator.

27 / 37

Detail of the integral form of DNN

Output to theℓ-th layer:

F_ℓ(τ,x) =

∫

Yℓ

h_ℓ^o(τ, τ^′)

| {z }

Weight

η(F_ℓ−1(τ^′,x))dQ_ℓ(τ^′) +b^o_ℓ(τ)

| {z }

Bias

.

This measures how much the inputx contains the featureτ at theℓ-th layer.

Yℓ: the feature index space at theℓ-th layer (Generally continuous space).

Qℓ: prob. measure onYℓ

Examples of activation functions:

ReLU:η(u) = max{u,0} Sigmoid: η(u) = _1+exp(¹_−u)

Illustration of continuous feature space

F_ℓ(τ,x) =

∫

Yℓ

h_ℓ^o(τ, τ^′)

| {z }

Weight

η(F_ℓ−1(τ^′,x))dQ_ℓ(τ^′) +b^o_ℓ(τ)

| {z }

Bias

.

The shape of the spaceYℓ could be arbitrary.

(could be discrete and could be continuous)

29 / 37

Continuous feature in real

Distributed representation in a real DNN

Reproducing kernel Hilbert space on the ℓ-th layer

Construct an RKHS on each layer.

→We can employ the theory of the kernel method.

Fℓ(τ,x): an output from theℓ-th layer to the feature τ in the next layer.

(Fℓ(τ,x) =∫

Yℓh^o_ℓ(τ, τ^′)η(Fℓ−1(τ^′,x))dQℓ(τ^′) +b^o_ℓ(τ).)

kℓ(x,x^′) =

∫

η(Fℓ−1(τ,x))η(Fℓ−1(τ,x^′))dQℓ(τ)

kℓ defines an RKHSHℓ.

For allf ∈ Hℓ, there exitsh∈L2(Qℓ) andg ∈L2(P(X)) such that f(x) =

∫

Yℓ

h(τ^′)η(Fℓ−1(τ^′,x))dQℓ(τ^′) =

∫

kℓ(x,x^′)g(x^′)dP(x^′)

∥f∥Hℓ =∥h∥L₂(Q_ℓ)=∥g∥L₂(P(X))

(c.f., Bach (2015)).

31 / 37

Complexity of RKHS

Let

T_ℓ:f 7→

∫

k_ℓ(·,x^′)f(x^′)dP(x^′).

Let the spectrum decomposition of k_ℓbe kℓ(x,x^′) =

∑∞ j=1

µ^(ℓ)_j ϕ^(ℓ)_j (x)ϕ^(ℓ)_j (x^′) inL2(P(X)×P(X)).

Definition

Thedegree of freedom ofFℓ is defined as

Nℓ(λ) :=Tr[(Tℓ+λ)⁻¹Tℓ] =

∑∞ j=1

µ^(ℓ)_j µ^(ℓ)_j +λ

.

Nℓ(λ) measurescomplexityof the RKHS.

This is very much related to the notion ofcovering numberof the RKHS.

Degree of freedom in kernel method

The degree of freedom appears to characterize the generalization error of kernel ridge regression.

ˆfλ=argmin

H

1 n

∑n

i=1

(yi−f(xi))²+λ∥f∥²_H whereHis an RKHS with a bounded kernelk.

Proposition (Caponnetto and de Vito (2007))

If f^o∈ H, then it holds that

∥ˆfλ−f^o∥²L₂(P_X)≤C (

|{z}λ

bias

+ N(λ)

| {z }n

variance

) ,

with high probability. (N(λ) :=∑_∞

j=1 µ_j

µ_j+λ where(µj)^∞_j=1 are the eigenvalues of the kernel)

Basically,λsatisfying

N(λ) n =λ gives the optimal rate.

33 / 37

Rough sketch ofN_ℓ(λ).

Estimation error inNℓ(λ) dimensional space: ^Nℓ_n^(λ) Bias (residual): λ

Finite approximation via kernel quadrature

Theorem (Approximation error in RKHS H

)

Forλ >0, suppose that

mℓ≥5Nℓ(λ) log(64Nℓ(λ)),

then there exist positive reals{τi}^mi=1^ℓ ⊂ Yℓ and(qj)^m_j=1^ℓ with∑m_ℓ j=1

1

qj ≤2mℓsuch that

sup

f:∥f∥Hℓ≤1

∥β∥inf²2≤m⁴ℓ

f −

m_ℓ

∑

j=1

β_jq_j^−1/2η(Fℓ−1(τj,·))

2

L₂(P(X))

≤4λ.

Proof is given by a modification of Bach (2015).

The true function g can be approximated with precision λby a finite sum (mℓ=O(Nℓ(λ) log(Nℓ(λ)))).

Fℓ(τ,x) =

∫

Yℓh^o_ℓ(τ, τ^′)η(Fℓ−1(τ^′,x))dQℓ(τ^′) +b_ℓ^o(τ).

N_ℓ(λ) =∑_∞

j=1 µ^(ℓ)_j µ^(ℓ)_j +λ

35 / 37

Finite approximation via kernel quadrature

Theorem (Approximation error in RKHS H

)

Forλ >0, suppose that

mℓ≥5Nℓ(λ) log(64Nℓ(λ)),

then there exist positive reals{τi}^m_i=1^ℓ ⊂ Yℓ and(qj)^m_j=1^ℓ with∑mℓ

j=1 1

q_j ≤2mℓsuch that ifη is scale invariant (η(au) =aη(u) (∀a>0)),then

sup

f:∥f∥Hℓ≤1

∥β∥inf²2≤m⁴ℓ

f −

m_ℓ

∑

j=1

β_jη(q⁻_j ^1/2Fℓ−1(τj,·))

2

L2(P(X))

≤4λ.

Proof is given by a modification of Bach (2015).

The true function g can be approximated with precision λby a finite sum (mℓ=O(Nℓ(λ) log(Nℓ(λ)))).

This reduces the complexity very much!

Assumption on norms

Now, we move to the deep neural network, and assume the following norm bound.

Fℓ(τ,x) =

∫

Yℓ

h_ℓ^o(τ, τ^′)

| {z }

Weight

η(Fℓ−1(τ^′,x))dQℓ(τ^′) +b^o_ℓ(τ)

| {z }

Bias

.

sup_τ∈Yℓ+1∥h^o_ℓ(τ,·)∥L2(Qℓ) ≤R (∀ℓ) (⇒ ∥Fℓ(τ,·)∥_Hℓ ≤R)

∥b^o_ℓ∥∞≤R_b (∀ℓ)

36 / 37

Approximation error of deep NN

(degree of freedom) Nℓ(λ) =∑_∞

j=1 µ^(ℓ)_j µ^(ℓ)_j +λ. Integral form:

f_ℓ^o(g) =

∫

h^o_ℓ(τ, τ^′)η(g(τ^′))dQ_ℓ(τ^′) +b^o_ℓ(τ), f^o(x) =f_L^o◦f_L^o₋₁◦ · · · ◦f₁^o(x),

Finite dimensional model:

f_ℓ^∗(g) =W^(ℓ)η(g) +b^(ℓ), f^∗(x) =f_L^∗◦f_L^∗₋₁◦ · · · ◦f₁^∗(x).

Theorem (Approximation error of deep NN)

For anyλℓ>0, δ >0,

mℓ≥5Nℓ(λℓ) log(32Nℓ(λℓ)/δ) (width ofℓ-th layer)

⇒ ∃{W^(ℓ),b^(ℓ)}^Lℓ=1 s.t. ∥f^o−f^∗∥L₂(P(X))≤

∑L

ℓ=2

2

√ ˆ

c_δ^L−ℓ−1R^L−ℓ√ λ_ℓ

whereˆcδ= 4 1−δ,

moreover ∥W^(ℓ)∥F ≤ˆcδR,∥b^(ℓ)∥ ≤Rb.

37 / 37