1深層NNによる関数近似

Hölder, Sobolev, Besov空間2

空間的非一様性

0

滑らかさの度合いSobolevクラスの近似理論

3

中間層の横幅が𝑁の
二層ニューラルネットワーク定理
𝜂がある開区間で無限回微分可能であり，その開区間のある点𝑏において
𝜕𝑘 𝜂𝑏 ≠ 0 (∀𝑘 ∈ ℤ, 𝑘 ≥ 0)
𝜕𝑥 𝑘とする．すると，∀𝑓 ∈ 𝑊𝑝𝑠 ( 0,1 𝑑 )に対してある𝑔 ∈ Π𝑁 が存在して，
𝑠−𝑑𝑓−𝑔 𝑝 ≲𝑁
𝑓 𝑊𝑝𝑠(ノード数𝑁の中間層を用いた近似誤差)[Mhaskar: Neural networks for optimal approximation of smooth and analytic
functions. Neural Computation, 8(1):164–177, 1996]• この近似誤差は𝑁個の基底を用いた近似法の中で最適なオーダーを達成．
• シグモイド関数は条件を満たす．ReLUは満たさない．
• 滑らかな関数はより近似しやすい．

ReLUの表現力• ReLU活性化関数• 現在広く使われている(LeakyReLUなどの亜種もあるがかなりスタンダード)• 統計的性質も解明されつつある➢万能近似能力あり➢(区分的) 滑らかな関数の推定
基本：局所多項式近似➢区分線形関数の表現➢有理関数の表現➢関数のテンソル積，合成関数の表現4

滑らかな関数の近似 (Yarotsky, 2016)5[Yarotsky: Error bounds for approximations with deep ReLU networks. 2016]• 二次関数の構成ℎ(𝑥)これが全ての基本ℎ ∘ ℎ(𝑥)ℎ ∘ ℎ ∘ ℎ(𝑥)２次関数の近似 (Telgarsky, 2015)

層を重ねることで指数的に誤差が減少
層の数，横幅，ユニット数：
中間層１層の場合：

改善（多項式オーダ→logオーダ）多項式の構成

6• 二次関数→掛け算（足し算はReLUで実現可能）• 掛け算→多項式（二次関数から構成した掛け算を繰り返し適用）（足し算と合わせて多項式を構成）→ 滑らかな関数の近似に利用

Holder classの近似
滑らかな関数のクラス（Holder class）• 滑らかな関数の局所的近似（テイラー展開）次多項式• 全体の近似1の分割(Yarotsky, 2016; Liang&Srikant, 2017)

7

推定理論

8

• パラメータ数

領域分割の数横幅：

分割ごとのパラメータ数
縦幅：のネットワークに埋め込める

縦幅 ，横幅 ，非ゼロパラメータ数：の深層NNモデルの集合
深層学習の汎化誤差（Schmidt-Hieber, 2017）
縦幅𝐿 = O(log(𝑛))，横幅𝑤 = O(𝑛𝑑−2𝛽+𝑑𝑑log(𝑛))，非ゼロ要素𝑠 = O(𝑛−2𝛽+𝑑log(𝑛))ミニマックス
最適レート
でバランス
バリアンス

バイアス

9

Besov空間の近似

空間の間の関係10

補間空間
補間空間（線形ノルム空間ℋと𝒢の間を”補完”，𝒢 ↪ ℋとする）：

補間空間は以下を満たす:

1112• 連続関数の領域：• 𝐿𝑟 -可積分な領域：• 例：

B-spline

Cardinal B-spline of order:→ Piece-wise polynomial of order m.

13

Cardinal B-spline interpolation (DeVore & Popov, 1988)

14• Atomic decomposition:𝑠 の必要十分条件:𝑓 ∈ 𝐵𝑝,𝑞

Wavelet/多重解像度展開
j=1

Scale

k=0と分解できて
(ただし）

k=1

j=1𝛼2,1k=2(ノルムの同値性)

j=1𝛼0,1𝛼1,1𝛼2,2

j=2

j=2
𝛼2,3
j=3

𝛼1,2
𝛼2,4

j=4

k=3
We show that DNN canapproximate each B-spline.

𝑁 terms (𝑓に応じて適切に選択)(see also Bolcskei, Grohs, Kutyniok, Petersen: Optimal Approximation with Sparsely Connected Deep Neural Networks. 201

Besov空間とスパース性との関係
Wavelet基底

解像度

𝛼0,1

𝑘=0
𝑘=1

低周波

𝑘=2

𝑗=1
𝛼1,1𝑗=1
𝛼2,1 𝛼2,2
𝑗=1

𝑗=2

𝛼1,2
𝑗=2
𝛼2,3 𝛼2,4𝑗=3

𝑗=4

𝑘=3
高周波

場所によって滑らかさが違うのでウェーブレット基底のスパースな線形結合が有効

Wavelet基底による展開

小さな𝑝 = スパースな係数

基本的にℓ𝑝 -ノルム

(0 < 𝑝)

空間的な滑らかさの非一様性

15Besov空間とスパース性との関係
Wavelet基底

解像度

𝛼0,1

𝑘=0
𝑘=1

𝑘=2

𝑗=1
𝛼1,1
𝑗=1
𝛼2,1 𝛼2,2𝑗=1

𝑗=2

𝛼1,2𝑗=2
𝛼2,3 𝛼2,4𝑗=3

𝑗=4

𝑘=3

基本的にℓ𝑝 -ノルムWavelet基底による展開

小さな𝑝 = スパースな係数(0 < 𝑝)

空間的な滑らかさの非一様性

1617• 詳細は手書きノートで説明非適応的な手法との比較
DNN:

18なる仮定のもとで• 適応的な非線形近似が必要 (Dung, 2011)
線形近似 (Linear width)：(𝐿𝑁 はランク𝑁の線形作用素)

𝑝 ≠ 𝑟が重要

非適応的近似（N-term approx., Kolmogorov width）：
𝑠(𝑆𝑁 は𝐵𝑝,𝑞内の𝑁次元線形部分空間)

小さな𝑝推定誤差の導出：ノーテーション

••
•
•

縦幅：
横幅：
枝の数：
各パラメータの上限：• 活性化関数はReLUを仮定

19の深層NNモデルの集合

推定誤差の導出

20• 最小二乗解 (訓練誤差最小化)

ただし，(clipping)．

定理 (推定精度),かつのとき，とすることで，3𝑝 = 𝑞 = ∞のとき，Schmidt-Hieber (2017) に帰着．

証明: (1) 近似誤差の評価

21• 0 < 𝑝, 𝑞, 𝑟 ≤ ∞と0 < 𝑠 < ∞が以下を満たすとする:(𝐿𝑟 -可積分性)•を𝑠 < min{𝑚, 𝑚 − 1 + 1/𝑝}を満たす整数とする．

深層ニューラルネットワークの近似誤差ある自然数 と用いて深さ , 横幅 , 枝の数 , ノルム上界 を以下のように定める：

すると，深層NNは以下の誤差でBesov空間の元を近似できる：

大体パラメータ数

Pinkus (1999), Mhaskar (1996): 𝑝 = 𝑟かつ1 ≤ 𝑝, ReLU活性化関数ではない．
Petrushev (1998): 𝑝 = 𝑟 = 2, ReLU活性化関数ではない (𝑠 ≤ 𝑘 + 1 + (𝑑 − 1)/2)．

証明: (1) 近似誤差の評価の導出

22• Step 1: Besov空間の基底展開∵ B-Splineによる適応的近似[DeVore & Popov, 1988; Dung, 2011]⋅ 𝐿𝑟 ≤ 𝑁 −𝑠/𝑑

• Step 2: 各基底をDNNで近似.
: DNNによる近似.
: 線形結合• Step 3: 二つの評価を統合≤ O(𝑒 −𝐿 )≤ 𝑁 −𝑠/𝑑証明: (2) バイアス-バリアンス分解

23（局所Rademacher complexityを用いて証明）
古典的なノンパラ回帰の方法でOK．DNNに関する評価は[Schmidt-Hieber, 2019; Hayakawa&Suzuki,2020]

深さ

横幅

スパース性
(非零パラメータ数)

各パラメータの絶対値の上界なら⇒ バイアスとバリアンスのトレードオフをバランスすればよい．

線形推定量“浅い” 学習法
Kernel ridge regression:

24
学習可能

正則化付き最小二乗推定量
固定(特徴マップ)固定

グラム行列 (カーネル関数)(see also [Imaizumi&Fukumizu, 2019])

線形推定量: 観測値𝑌 = 𝑦𝑖 𝑛𝑖=1 に対して線形な推定量.

例線形•
•
•
•

Kernel ridge estimator
Sieve estimator
Nadaraya-Watson estimator
k-NN estimator

Minimax-optimal rate of linear estimators• Ω = 0,1 𝑑• 𝑃𝑋 = Unif(Ω)• 𝒜: decomposition of Ω s.t. Ω = 2𝐾
• ℱ: function classCondition A• ∃𝑟1 , 𝑟2 > 0 s.t. 𝑛−𝑟1 ≤ 2−𝐾 ≤ 2−𝑟2 (polynomial order)• Event ℰ:
1.
2.

𝑥𝑖 𝑥𝑖 ∈ 𝐴 𝑖 = 1,2, … , 𝑛
𝑃 ℰ ≥ 1 − 𝑜(1)≤ 𝐶 ′ 𝑛/2𝐾 for all 𝐴 ∈ 𝒜Condition B

There exists Δ > 0 that satisfies the following two conditions:
Δ𝐹• ∃𝐹 > 0 s.t. ∀𝐴 ∈ 𝒜, ∃𝑔𝐴 ∈ ℱ, it holds that 𝑔𝐴 𝑥 ≥ (∀𝑥 ∈ 𝐴)
1• 𝐶 ′′ > 0 s.t. σ𝑛𝑖=1 𝑔 𝑥𝑖 2 ≤ 𝐶 ′′ Δ2 2−𝐾 (∀𝑔 ∈ ℱ)
𝑛225

Minimax-optimal rate of linear
estimatorsA• ∃𝑟1 , 𝑟2 > 0 s.t. 𝑛−𝑟1 ≤ 2−𝐾 ≤ 2−𝑟2 (polynomial order)• Event ℰ:
1.
2.

B𝑥𝑖 𝑥𝑖 ∈ 𝐴 𝑖 = 1,2, … , 𝑛
𝑃 ℰ ≥ 1 − 𝑜(1)≤ 𝐶 ′ 𝑛/2𝐾 for all 𝐴 ∈ 𝒜

There exists Δ > 0 that satisfies the following two conditions:
Δ𝐹• ∃𝐹 > 0 s.t. ∀𝐴 ∈ 𝒜, ∃𝑔𝐴 ∈ ℱ, it holds that 𝑔𝐴 𝑥 ≥ (∀𝑥 ∈ 𝐴)
1
• 𝐶 ′′ > 0 s.t. σ𝑛𝑖=1 𝑔 𝑥𝑖 2 ≤ 𝐶 ′′ Δ2 2−𝐾 (∀𝑔 ∈ ℱ)
𝑛2Theorem

ΔUnder Conditions A and B, it holds:

𝐹 2 2𝐾 𝐹 3 2 −𝐾min, Δ 2′′4𝐶𝐶 𝑛 32

≤ 𝑅∗

ℎ2𝐾 = ℎ−𝑑

• There is a trade-off between 𝐾 and Δ.
• Equating first and second terms gives the minimax-rate.

26

Typical example𝛽• Besov space: 𝐵𝑝,𝑞 ( 0,1 𝑑 )27

「浅い」学習との比較

28• 深層学習は場所によって解像度を変える適応力がある→学習効率が良い• 浅い学習は様々な関数を表現できる基底をあらかじめ十分用意して“待ち構える”必要がある．
→学習効率が悪い
𝑠仮定 𝑓 ∘ ∈ 𝐵𝑝,𝑞( 0,1 𝑑 ): 真が“Besov空間”に入っている．

線形推定量 (非適応的手法)[Suzuki, ICLR2019]

深層学習

カーネルリッジ回帰等：≫
最適ではない最適(𝑛: sample size，𝑝: uniformity of smoothness，𝑠: smoothness)
一様な解像度
平均二乗誤差 E 𝑓መ − 𝑓 ∗2

適応的解像度がサンプルサイズが増えるにつれ減少するレート

ミニマックス最適性の意味で理論上これ以上改善 • Wavelet shrinkageより弱い条件• 基底を用意せず最適化するだけでOKできない精度を達成できている．

次元の呪いと線形推定量

29(s.t. 𝑊𝑥 + 𝑏 ∈ 0,1 𝐷 for any 𝑥 ∈ 0,1 𝑑 )𝑓 ∘ は𝐷-次元部分空間にのみ依存(非適応的)

線形推定量

深層≪(𝑛−2𝑠2𝑠+1 when 𝐷 = 1)

深層にすることで次元の呪いを回避できている．

𝑐 = 1 if 𝐷 < 𝑑/2, 𝑐 = 0 if 𝐷 ≥ 𝑑/2.

(𝑛2𝑠+𝑑−2𝑠+2𝑑when 𝐷 = 1 and 𝑝 = 1)

導出：凸法の理論
定理 (凸法の議論) [Hayakawa&Suzuki, 2019] [Donoho & Johnstone, 1994]

さらに条件を仮定すれば「Q-hull」まで拡張できる．

30

Approach• We show that conv(ℱ𝛾 ) contains a Gaussian
kernel with small width.
• The set of neural networks can approximate
a ridge shape function.

31

Irie-Miyake integral representation

32

Theorem (Irie-Miyake integral representation) [Th.3.1 of Hornik et al. (1990)]

forwhere 𝑤 ≠ 0 is any non-zero real value.

Integrable