深層学習の汎化誤差のための近似性能と複雑性解析
2019/11/22 IBIS企画セッション
今泉允聡（統計数理研究所 / 理化学研究所 / JSTさきがけ）

1

深層学習と問題設定

多層ニューラルネット（DNN）モデル• 多くの層を持つ（変換を繰り返す）ℓ層⽬の変換ℎℓ = 𝜎(Θ(ℓ ℎℓ)* )

⼊⼒𝒙出⼒
𝒚層ℓ

Θℓ : パラメタ (⾏列)𝜎: 活性化関数
sigmoid, ReLUなど

全𝑳層

データ上の経験誤差を最⼩化し、汎化誤差を評価
経験誤差(訓練誤差)
2ℒ Θ = 𝑛)*Σ01*ℓ 𝑦0 , 𝑓6 𝑥0
𝑓6: DNN, Θ = Θ* , … , Θ9;Θを学習

汎化誤差(精度の尺度)
;
𝐸ℒ Θ
2

汎化誤差の分解
誤差を三つの要素で説明;
Eℒ Θ
汎化誤差;
≤ infB ℒ ΘC + 𝐸 ℒ Θ6

近似誤差

DNNの表現⼒データ
近似誤差; + ℒ Θ; − inf ℒ ΘC−ℒ ΘB

複雑性誤差

DNNの集合の⼤きさ

𝑓6;
最適化
誤差
DNNの集合6

最適化誤差

学習がうまくいくか

本講演のトピック・近似誤差
・複雑性誤差3

汎化誤差の分解• 実際の学習の軌跡との対応
損失

テスト損失
訓練損失

複雑性誤差
（汎化ギャップ）
最適化誤差
近似誤差

0

Epoch4近似誤差

DNNと既存法の差を⽰す関数近似理論5近似誤差とは• DNN 𝑓6 が表現できるデータの構造で決まる
Θ: パラメタ回帰の例（損失ℓは⼆乗損失）
𝑓6 : DNN
データが 𝑌 = 𝑓 ∗ 𝑋 + 𝜀 から⽣成されている時︓
infB ℒ ΘC ≤ inf 𝑓 ∗ − 𝑓6 KJ + Noise Terms
6𝑌6

データ

𝑓6 𝑥0𝑋

データの構造を表現できている
表現できてない6普遍近似定理
よく知られている結果普遍近似定理 (Cybenko (1989)など)層が２つのニューラルネットワーク(NN)は、⼗分な数のパラメタがあれば、連続関数を任意の精度で近似できる。

• 層２つで成⽴→ 深層でなくて良い• 普遍近似は多くの他⼿法でも成⽴→ NNでなくて良い➡ なんでDNNを使うの︖

7

より詳細に近似を調べるには近似誤差の減衰レート• パラメタ(エッジ)が増えるときの誤差減少スピード

近似誤差の減衰レート𝒂𝑓 ∗: 近似対象の関数
𝑓6: 𝑊個のパラメタを持つDNN

近似
誤差遅い減衰（𝑎⼩）

inf ‖𝑓 ∗ − 𝑓6‖ = 𝑂(𝑊 )W )6

近似誤差

パラメタ増で減少速い減衰（𝑎⼤）0

パラメタ数 𝑾

• レートを出すには、𝑓 ∗ が滑らかである必要➡ 𝑓 ∗ が微分可能である状況を調べる
8

滑らかな関数に対する近似レート𝑓 ∗ ︓近似対象（⼊⼒𝑑次元、𝛽回微分可能）
𝑓6︓DNN（𝐿層, パラメタ𝑊個、活性化関数𝜎）𝝈がsigmoid等の場合 (Mhaskar (1996)など)
DNNは 𝐿 = 2 のもとで以下を達成︓
inf ‖𝑓 ∗ − 𝑓6‖ = 𝑂(𝑊 )`/b )6活性化関数がReLUの場合 (Yarotsky (2017)など)𝐿層のDNNは以下を達成︓
inf ‖𝑓 ∗ − 𝑓6‖ = 𝑂(𝑊 )`/b + 2)9 )6

ReLUの尖りから来る影響

9誤差レート𝛽/𝑑は、 𝑓 ∗ の滑らかさで増加、⼊⼒次元で減少。

活性化関数𝜎による違い• 𝜎が滑らかな場合（sigmoid, softplus）
2層NN⾜し上げ

ノード毎に多項式近似テイラー多項式を表現• 𝜎が滑らかでない場合（ReLU, LeakyReLU）
⾜し上げ

𝐿層DNN
層を重ねて細かい⻭を表現

区分線形関数でテイラー多項式を近似10良いレートなの︖• 誤差レート𝛽/𝑑は理論的に最適

すごいぞ︕
やはりDNNは最適なんだ︕

近似誤差の最適性 (DeVore+ (1989)など)
近似誤差レート𝑂(𝑊 )`/b )は理論上の最適値。

• しかし、他⼿法も同じように最適他のも最適だから結局同じ︖

他⼿法の近似レート (Newman+ (1964)など)
フーリエ基底、多項式基底などによる近似はレート𝑂(𝑊 )`/b )を達成する。
𝑓 ∗ が滑らかなら、DNNと他⼿法の理論的性能は同等。11

DNNが重要になる状況1汎化性能も優越するが、ここでは近似性能のみ記述• 𝑓 ∗ が滑らかでない場合、DNNが他に優越𝑓 ∗ 𝑥* , 𝑥K

近似レートの差別化(Imaizumi & Fukumizu (2019))

𝑥*𝑥K

区分上でのみ滑らかな関数

𝑓 ∗ = Σc 𝑓c ⊗ 1fg

𝑓c : 滑らかな関数, 1fg : 区分上の指⽰関数

DNNのレート︓𝑂(max{𝑊 )`/b , 𝑊 )k/K(b)*) })他⼿法(カーネル等)のレート︓𝑂(max{𝑊 )`/b , 𝑊 )k/m(b)*) })（𝛼は区分の境界線の滑らかさ）

区分の境界が複雑な形➡ DNNが速いレートを達成
12

DNNが重要になる状況2汎化性能も優越するが、ここでは近似性能のみ記述• 𝑓 ∗ が不均⼀な滑らかさを持つ場合、DNNが優越
領域A領域B近似レートの差別化(Suzuki (2019))

DNNのレート︓
𝑂(𝑊 )`/b )他⼿法(カーネル等)のレート︓
𝑂(𝑊 )(`)(*/o)*/K)p )/b )（𝑝は不均⼀さの程度）∗

Besov空間の関数

𝑓 = Σr 𝑐r 𝜙r + Σr,u 𝑐r,u 𝜓r,u𝑐⋅ o + Σu 2xu `y*/K)*/ox */x𝑐⋅,u o<∞

不均⼀さがより強い➡ DNNが速いレートを達成
13

DNNは局所構造を表現できる• これまで︓均⼀な滑らかさ・構造を表現
𝑓 𝑥𝑥

カーネル法
スプライン法
フーリエ法 など

• DNN︓局所的に滑らかさを変えられる前半の層で関数の台を分割

分断

後半の層で関数を表現

関数14

更なるDNNの役割︓特徴量抽出
特徴量変換＋関数表現を考える
前半の層で特徴量を抽出

後半の層で関数を表現

抽出

関数

Cat

DNNは複数回の四則演算をする➡ 既存の変換（フーリエ変換など）が近似的に可能

15

DNNが重要になる状況3• 特徴空間への写像がある場合、DNNのレート改善𝑓 ∗ (𝛽回微分可能)

近似レート
𝜙 (𝛾回微分可能)

𝑔 (𝛽回微分可能)

𝑋

𝜔

𝑌

⼊⼒空間(𝑑次元)

特徴空間(𝑠 < 𝑑次元)

出⼒(Peterson et al. (2019))(Schmidt-Hieber (2019a))

DNNのレート︓𝑂(max{𝑊 )|/b , 𝑊 )`/} })⼀般的なレート︓
𝑂(𝑊 )`/b )特徴量が低次元・ 𝜙がシンプル
特徴写像𝜙(未知)と関数𝑔の合成➡ DNNのレート改善𝑓∗ = 𝑔 ∘ 𝜙

16

DNNが重要になる状況3+• 特徴空間の具体例︓低次元集合𝑓 ∗ (𝛽回微分可能)

低次元特徴量がある時の近似レート(Nakada & Imaizumi (2019))

𝑌𝑋
⼊⼒空間(𝑑次元)

低次元集合
例︓フラクタル(𝑠 < 𝑑次元)

出⼒

低次元集合Ω上の関数∗𝑓 𝑋 , Supp 𝑋 = Ω

DNNのレート︓)`/} )‡𝑂(𝑊
⼀般的なレート︓
𝑂(𝑊 )`/b )（𝑠: 低次元集合の次元）➡ DNNのレート改善
17

DNNが重要になる状況3+• 特徴空間の具体例︓低次元多様体𝑓 ∗ (𝛽回微分可能)
多様体特徴量がある時の近似レート(Schmidt-Hieber (2019b))

𝑌𝑋
⼊⼒空間(𝑑次元)

低次元多様体(𝑠 < 𝑑次元)

出⼒多様体上への変換を持つ関数∗𝑓 =𝑔∘𝜙

DNNのレート︓)`/} )‡𝑂(𝑊
⼀般的なレート︓
𝑂(𝑊 )`/b )➡ DNNのレート改善
18近似誤差のまとめ• DNNが優位・改善する状況の発⾒特徴量変換を含む関数構造(⼀様に)滑らかな関数追加

局所構造を持つ関数 (区分滑・Besov)拡張• 知⾒1︓局所構造を持つ関数ではDNNが優位• 既存法(カーネル法など)に対する優位性も⽰される• 知⾒2︓特徴量抽出が有効ならDNNは改善• 狭い関数クラスだが、特徴量の構造がDNNに合う
19近似誤差の未解決点• まだ未解決な点も多い
結局、層はすごく多いのがいいの︖

超深層(100層など)の意義は不明
・上記の結果は3~5層で成⽴・ReLUの場合も𝑂(log 𝑛)層くらい議論︓Yarotsky(2018)などどんな特徴量が必要なの︖

使える特徴量概念は抽象的・解析できる特徴は次元などに限定
・具体的な特徴付けは今後の課題
議論︓Alemi+(2016)など

ラフな差別化は出来つつあるが、現象を説明するにはまだ壁
20

複雑性誤差なぜ巨⼤モデルでも汎化する︖

21

そもそも複雑性誤差とは︖• 汎化誤差(期待値)と訓練誤差(経験平均)との差;
𝐸ℒ Θ;
−ℒ Θ

評価⽅法︓⼀様収束誤差• 可能な全ての𝚯上でのE[ℒ Θ ]とℒ(Θ)の差;
𝐸ℒ Θ;
−ℒ Θ

≤ sup 𝐸 ℒ ΘC

E[ℒ Θ ]

6Bℒ(Θ)
×;学習したΘ− ℒ ΘC

複雑性誤差の評価

Θの集合

22

なぜ全てのΘを考える︖アルゴリズムのランダムを考慮することもある; ](期待値)を考えるとは︖• 汎化誤差E[ℒ Θ• 可能な𝐷2 すべての場合の平均値を考えること
汎化誤差(期待値)を考える

データ𝐷2
学習された𝑓Ž;
取りうる𝑓Ž;可能な𝐷2DNNの集合(⼤)

取りうる𝐷2 をすべて考慮
可能な𝐷2 から定まる𝑓Ž; をすべて考慮
23

既存理論の考え⽅
既存理論• 複雑性誤差＝可能な𝑓Ž の集合

可能な𝐷2 から定まる𝑓Ž; をすべて考慮

データ𝐷2

可能な𝐷2の⼤きさ

DNNの集合(⼤)

可能な𝑓Ž; の候補集合が⼤きいほど複雑性誤差が増加
24

複雑性評価の数学的⽅法レートは改善可だが⼤きさへの依存は不可
𝑛: データ数
𝑊: パラメタ数

複雑性評価（e.g. Anthony & Bartlett (1999)）
1 J
sup E ℒ Θ − ℒ Θ = 𝑂• log 𝑁’ 𝑑𝛿𝑛 •6

可能な𝑓6の集合の⼤きさ
導出の流れ
⼀様誤差
sup |E ℒ Θ − ℒ Θ

Dudley積分

Rademacher複雑性𝑛6)*/K

EJ

2
sup Σ01*
𝜎0 ℓ 𝑦0 , 𝑓6 𝑥06𝑛)*/K ••→集合の⼤きさを評価
ΘΘ

𝜎0 : Rademacher変数

log 𝑁’ 𝑑𝛿××××Θ

𝑁’ : {𝑓6 }の最⼩𝛿被覆数25×: 離散点（被覆球の中⼼）複雑性はパラメタ数が主DNNの複雑性評価（e.g. Anthony & Bartlett (1999)）
𝑊 log 𝐿1 J
• log 𝑁’ 𝑑𝛿 = 𝑂𝑂𝑛 •𝑛➡ パラメタ数 𝑊 が主な要素• この理論はDNNの実性能を説明できない
⼤量のパラメタは複雑性誤差を上げる
統計・学習理論の(⼤)原則

⽭盾

⾼精度DNNは膨⼤なパラメタ数
Alex Net →６千万
VGG Net →１億26

新しい複雑性評価の着想
着想︓可能な 𝑓6 すべてを考える必要は無いのでは︖• データ依存で実現しうる𝑓6の部分集合がありそう
これまでの複雑性誤差

データ𝐷2

可能な全DNN

データ依存部分集合の⼤きさ→巨⼤な複雑性
新しい着想

可能な𝐷2

DNNの集合データ依存集合の⼤きさ→⼩さい複雑性27

新しい着想を⽀持する実験• データ依存集合の重要性を⽰す実験(Zhang+ (2017))• 全然違うデータ𝐷2 , 𝐷2C でも、DNNの近似誤差・複雑性誤差は両⽅とも⼩さい

既存理論︓複雑性誤差＝
𝐷2の⼤きさ
𝐷2

𝑓6

𝐷2C
𝑓6Bor

𝑓6 𝑓6B

𝐷2C

⼤きな近似誤差

⼤きな複雑性

近似誤差︓どちらも⼩複雑性誤差︓⼤近似誤差︓どちらかは⼤28
複雑性誤差︓⼩データ依存集合は実験を説明• データ依存集合の重要性を⽰す実験(Zhang+ (2017))• 全然違うデータ𝐷2 , 𝐷2C でも、DNNの近似・複雑性誤差は両⽅とも⼩さい

新しい着想︓複雑性誤差＝データ依存集合
𝐷2

𝑓6𝑓6B

DNNの集合𝐷2Cの⼤きさ近似誤差︓どちらも⼩複雑性誤差︓常に⼩実験・実現象と⼀致︕
29

データ依存集合を考える• データ依存集合の重要性を⽰す実験(Zhang+ (2017))• 全然違うデータ𝐷2 , 𝐷2C でも、DNNの近似・複雑性誤差は両⽅とも⼩さい

新しい着想︓複雑性誤差＝データ依存集合

何によって決まっているの︖

はの⼤きさ

試みの⼀部
1. ノルム制約(暗黙的正則化)
2. 学習アルゴリズム
3. 各種正則化⼿法
他多数
30

試み1. ノルム制約下の複雑性• パラメタΘが⼗分に⼩さい場合• 各層ℓ = 1, … , 𝐿の Θℓ が𝑀ℓ で抑えられると仮定

DNNの集合制約された集合{𝑓6: Θℓ ≤ 𝑀ℓ , ∀ ℓ}

ノルム制約下での複雑性誤差(Neyshabur+ (2015a))(Golowich+ (2019))
𝐵 𝐿 ∏9ℓ1* 𝑀ℓ𝑂

Πℓ 𝑀ℓ0𝑛

𝐵 = max 𝑥0 : データの⼤きさ
0
他、Bertlett+ (2017)など• パラメタ数𝑊には（陽には）依存しない。
• 𝑀ℓ が⼩さいほど、複雑性誤差は⼩さくなる。

31

試み1. ノルム制約下の複雑性• 他ノルムや、各層の勾配を抑えることもDNNの集合
ノルムと勾配が制約された集合

0

ノルム・ヤコビアン制約下の誤差(Wei & Ma (2019))

𝑂‡9Σℓ1*𝑀ℓC 𝐾ℓ K/œ +CC C K/œ œ/K𝑀ℓ 𝐾ℓ𝑛𝑀ℓC , 𝑀ℓCC : Θℓ の別ノルムでの上限
𝐾ℓ , 𝐾ℓC : ℓ層のヤコビアンの上限
32

試み1. ノルム制約下の複雑性• ノルム制約の実現性に課題
パラメタのノルムが常に⼩さければ複雑性誤差も⼩さい︕
じゃあどういう時にノルムが⼩さいの︖
それはDNN特有なの︖➡ まだ明確な特徴づけは明らかでない
数学的発⾒による仮説はある(線形モデルの収束など: Neyshabur+ (2014), Arora+(2019))

33

試み2. 学習アルゴリズムの影響• 学習アルゴリズム（勾配法）の性能を評価• 探索される範囲＝実現する𝑓6 の集合
DNNの集合勾配法で探索初期値𝑓6(£)

勾配法による最適化初期値を設定 Θ(•)

探索される範囲
確率的勾配法(SGD)にも拡張可能

パラメタ更新 𝑡 = 1, … , 𝑇
Θ(Ÿy*) ← Θ(Ÿ) − 𝜂Ÿ ∇6ℒ Θ Ÿ𝜂Ÿ : ステップサイズ
34

試み2. 学習アルゴリズムの影響• 探索性能を下げる → 実現する𝑓6 も減る
DNNの集合ステップサイズ・更新回数を減

早く学習をやめれば誤差減(Hardt+ (2016))(Kuzborskij+ (2017))𝜂Ÿ = O(1/𝑡)とする(𝑊/𝐿)9 𝑇 x
𝑂𝑛

探索範囲は縮⼩𝑇 ≥ 1: パラメタの更新回数
𝑞 ∈ (0,1): 減衰率• 探索範囲を狭めれば、複雑性誤差は⼩さくなる。
• パラメタ数𝑊の影響は受ける。

35

試み2. 学習アルゴリズムの影響• 実際の探索の低次元性を考慮
DNNの集合初期値𝑓6(£)

勾配法で探索探索される範囲(低次元集合)

低次元集合上の探索で誤差減(Imaizumi & Sriperumbudur (2019))𝜂Ÿ = O(1/𝑡)とする

𝑂‡

𝑑¨Bx
𝐿𝑑 log 𝑇𝑛𝑑¨ < 𝑊: 探索される空間の次元

𝑞C ∈ (0,1): 減衰率• 低次元構造で、パラメタ数𝑊の影響を緩和。
• ただし活性化関数に制約が⼊る。

36

試み2. 学習アルゴリズムの影響• ノルム制約の実現性に課題学習を控えめにすれば複雑性誤差は⼩さい︕

それは良いパラメタが学習できないんじゃないの︖➡ 近似・最適化誤差との関係は明らかでない。
損失関数の形状の研究が必要。
実験的反論もある: Hoﬀer+ (2018)37

複雑性誤差の理論まとめ
問題︓DNNは膨⼤なパラメタを持つが、複雑性誤差が⼩さい理論化の⽅向︓複雑性誤差＝データ依存のモデル部分集合• その部分集合の正体は明らかでない

正体の候補
・ノルム制約集合
・学習アルゴリズムの影響
・各種正則化⼿法（バッチ正規化など）, 他多数
多くの仮説・実験・数学的発⾒・暗黙的正則化 / バイアス / 損失関数の形状, etc…
38

まとめと展望39

まとめ・展望
近似誤差• 進捗しているが更なる発展の余地

複雑性誤差

実運⽤

• 実現象との⼤きな⽭盾• モデル部分集合のスキーム 数学的発⾒• 未解明な点は多い• 他のスキームも提案

実験・数学的発⾒から理論の拡張へ

Lo$ery Ticket,
Implicit bias,
Double Descent,Flat minima, etc.

DNNの理論40

ご静聴ありがとうございました。

41

Reference• Cybenko, G. (1989). Approximations by superpositions of a sigmoidal function.
Mathematics of Control, Signals and Systems, 2, 183-192.
• Mhaskar, H. N. (1996). Neural networks for optimal approximation of smoothand analytic functions. Neural computation, 8(1), 164-177.
• Yarotsky, D. (2017). Error bounds for approximations with deep ReLU networks.
Neural Networks, 94, 103-114.
• DeVore, R. A., Howard, R., & Micchelli, C. (1989). Optimal nonlinearapproximation. Manuscripta mathematica, 63(4), 469-478.
• Newman, D. J. and Shapiro, H. S., (1964) Jacksonʼs theorem in higher
dimensions, On Approximation Theory (Proceedings of Conference inOberwolfach, 1963), pp. 208–219.
• Imaizumi, M., & Fukumizu, K. (2018). Deep neural networks learn non-smoothfunctions eﬀectively. AI & Statistics.
• Suzuki, T. (2018). Adaptivity of deep ReLU network for learning in Besov andmixed smooth Besov spaces: optimal rate and curse of dimensionality.
• Petersen, P., & Voigtlaender, F. (2018). Optimal approximation of piecewisesmooth functions using deep ReLU neural networks. Neural Networks, 108,296-330.
• Schmidt-Hieber, J. (2019a). Nonparametric regression using deep neuralnetworks with ReLU activation function. Annals of Statistics, to appear.
42

• Nakada, R., & Imaizumi, M. (2019). Adaptive approximation and estimation ofdeep neural network to intrinsic dimensionality. arXiv preprint
arXiv:1907.02177.
• Schmidt-Hieber, J. (2019b). Deep ReLU network approximation of functions ona manifold. arXiv preprint arXiv:1908.00695.
• Yarotsky, D. (2018). Optimal approximation of continuous functions by very
deep relu networks. Conference on Learning Theory.
• Alemi, A. A., Fischer, I., Dillon, J. V., & Murphy, K. (2016). Deep variational
information bottleneck. International Conference on Learning Representations.
• Anthony, M., & Bartlett, P. L. (1999). Neural network learning: Theoreticalfoundations. cambridge university press.
• Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2016). Understanding
deep learning requires rethinking generalization. International Conference onLearning Representations.
• Neyshabur, B., Tomioka, R., & Srebro, N. (2014). In search of the real inductive
bias: On the role of implicit regularization in deep learning. arXiv preprint
arXiv:1412.6614.
• Arora, S., Cohen, N., Hu, W., & Luo, Y. (2019). Implicit Regularization in Deep
Matrix Factorization. Neural Information Processing Systems.
• Hardt, M., Recht, B., & Singer, Y. (2016). Train faster, generalize better: Stabilityof stochastic gradient descent. In International Conference on Machine
Learning.
• Kuzborskij, I., & Lampert, C. H. (2017). Data-dependent stability of stochastic
gradient descent. arXiv preprint arXiv:1703.01678.

43