1

広島市立大学集中講義

カーネル法と深層学習の数理
鈴木大慈
東京大学大学院情報理工学系研究科数理情報学専攻
理研AIP
2020年8月28日/29日

機械学習と人工知能の歴史
１９４６： ＥＮＩＡＣ，高い計算能力
フォン・ノイマン「俺の次に頭の良い奴ができた」
１９５２： Ａ．Ｓａｍｕｅｌによるチェッカーズプログラム
ルールベース
１９５７：Ｐｅｒｃｅｐｔｒｏｎ，ニューラルネットワークの先駆け
１９６０年代前半：

ＥＬＩＺＡ（イライザ），
擬似心理療法士
１９８０年代：
エキスパートシステム

人手による学習ルールの作りこみの限界「膨大な数の例外」
Siriなどにつながる

2

統計的学習

第一次ニューラルネットワークブーム
１９６３：線形サポートベクトルマシン

線形モデルの限界

１９８０年代：多層パーセプトロン，誤差逆伝搬，畳み込みネット
第二次ニューラルネットワークブーム

非凸性の問題

１９９２： 非線形サポートベクトルマシン（カーネル法）１９９６： スパース学習 （Lasso）
２００３： トピックモデル （LDA）
２０１２： Supervision （Alex-net）
第三次ニューラルネットワークブーム

データの増加＋計算機の強化ネオコグニトロン

3[福島,79]・人間の脳を模倣
・畳み込みネットの初期型
・自己組織型学習→素子を足してゆくLeNet[LeCun+etal,89]

4

LeNet-5[LeCun etal,98]• 畳み込み＋プーリング：現在も使われている構造• 誤差逆伝搬法でパラメータを更新• 手書き文字認識データセット（MNIST）で９９％の精度を達成

5

Deep Learning
深層学習

ImageNet

ImageNet: 1,000カテゴリ，約120万枚の訓練画像データ

ILSVRC (ImageNet Large Scale Visual Recognition Competition)[J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.
ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.]

6

ImageNetデータにおける識別精度の変遷
Classification error (%)
30

深層学習

25
20
15
10
5
0

ILSVRC2010ILSVRC
2011

8層

8層

19層

22層

ILSVRCILSVRCILSVRCILSVRC

VGG

GoogleNet

2012

AlexNet

2013

2014

2014

152層
Human

ImageNet: 21841クラス，14,197,122枚の訓練画像データ
そのうち1000クラスでコンペティション

ILSVRC2015

ResNet7

深層学習の広がり

8

様々なタスクで高い精度
画像の生成

AlphaGo/Zero

画像認識[Silver et al. (Google Deep Mind): Mastering the game of Go withdeep neural networks and tree search, Nature, 529, 484—489, 2016][Glow: Generative Flow with Invertible 1x1 Convolutions. Kingma
and Dhariwal, 2018]

自動翻訳[He, Gkioxari, Dollár, Girshick: Mask R-CNN, ICCV2017]

画像の変換[Zhu, Park, Isola, and Efros: Unpaired image-to-image translation using
cycle-consistent adversarial networks. ICCV2017.][Wu et al.: Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation. arXiv:1609.08144]

諸分野への波及
ロボット

医療

9

医療分野における「深層学習」
を用いた論文数[タオル畳み、サラダ盛り付け 「指動く」ロボット初公開,
ITMedia:http://www.itmedia.co.jp/news/articles/1711/30/news089.html]

量子化学計算，分子の物性予測[Litjens, et al. (2017)]- 人を超える精度（FROC73.3% -> 87.3%）- 悪性腫瘍の場所も特定[Niepert, Ahmed&Kutzkov: Learning Convolutional Neural Networks
for Graphs, 2016][Gilmer et al.: Neural Message Passing for Quantum Chemistry, 2017][Faber et al.:Machine learning prediction errors better than DFT
accuracy, 2017.][Detecting Cancer Metastases on
Gigapixel Pathology Images: Liu etal., arXiv:1703.02442, 2017]

解決すべき問題点
なぜ深層学習はうまくいくのか？

• 「○○法が良い」という様々な仮説の氾濫．
• 世界的課題• 原理解明• どうすれば“良い”学習が実現できるか？→新手法の開発
学会の問題意識民間の問題意識• 中で何が行われているか分からないものは用いたくない．
• 企業の説明責任．深層学習のホワイトボックス化．

Ali Rahimi’s talk at NIPS2017 (test of time award).
“Random features for large-scale kernel methods.”“錬金術”という批判

数学の必要性10深層学習の理論概観
応用

解釈可能性：

説明可能性，データの可視化，メンテナン
スの容易化

各種テクニックの解析：

アーキテクチャの解析，損失関数の設計，最適化技法の解析

11

理論を通して深層学習の不可思議な挙動を理解したい．
 説明責任 可能性と限界の把握 学習手法設計の指針

応用から基礎まで
深層学習の原理解明：
広い範囲に“理論”
表現理論，汎化誤差理論，最適化の収束理は遍在する．
論
学習の本質解明：“良い”学習手法の特徴付け，統一理論，
深層学習を優越する方法論の提唱
基礎

今日の範囲

教師あり学習12

画像-猫 (y=1)-犬 (y=2)-人間 (y=3)

学習：「関数」をデータに当てはめる
モデル：関数の集合（例：深層NNの表せる関数の集合）

深層ニューラルネットの構造

13

𝑥𝑥 𝑊𝑊1 ℎ1 𝑊𝑊2 ℎ2 𝑊𝑊3 ℎ3
基本的に「線形変換」と「非線形活性化関数」の繰り返し．
𝑥𝑥

入力

𝑊𝑊1 𝑥𝑥ℎ1 (𝑊𝑊1 𝑥𝑥)

線形変換 非線形変換ℎ1 𝑢𝑢 = ℎ11 𝑢𝑢1 , ℎ12 𝑢𝑢2 , … , ℎ1𝑑𝑑 𝑢𝑢𝑑𝑑

𝑊𝑊2 ℎ1 (𝑊𝑊1 𝑥𝑥)
線形変換

𝑇𝑇

• ☆ReLU (Rectified Linear Unit)：• シグモイド関数：ℎ2 (𝑊𝑊2 ℎ1 𝑊𝑊1 𝑥𝑥 )非線形変換

活性化関数は通常要素ごとにかかる．Poolingのよ
うに要素ごとでない非線形変換もある．

• 第ℓ層

全結合モデル

14

活性化関数の例☆ReLU (Rectified Linear Unit)

シグモイド関数15

訓練誤差と汎化誤差
パラメータ
損失関数

16

：ネットワークの構造を表す変数：パラメータ がデータをどれだけ説明しているか

予測誤差：損失の期待値

本当に最小化したいもの．

訓練誤差：有限個のデータで代用

代わりに最小化するもの．

(訓練データはテストデータと同じ分布に従っていると仮定)

この二つには大きなギャップがある．
[過学習]※クラスタリング等，教師なし学習も尤度を使ってこのように書ける．

学習理論の設定• 汎化ギャップ(汎化誤差)と余剰誤差
Generalization gap

Excess risk

汎化誤差:
余剰誤差:
もしくは

17

学習機の複雑さと学習能力

18• No free lunch theorem「あらゆる問題で性能の良い汎用的学習機は実現不可能であり，ある問題に特殊化された手法に勝てない」
ある問題に特化した方法

予測誤差

平均

汎用的な方法問題

機械学習への教訓「必要以上に複雑なモデルを当てはめると失敗する」
学習手法は「どこかを“贔屓”する必要がある」→ モデリングの重要性 (オッカムの剃刀)
William of Ockham：1285-1347．スコラ学の神学者，哲学者．
No free lunch theorem: [D.H.Wolpert and W.G. Macready: 1995,1997][Y.C. Ho and D.L. Pepyne: 2002]

リスクの概念19• どこを贔屓するか？

モデルの外に真があればそもそも学習方法の優劣を論じることは難しい (どれもドングリの背比べ)
仮にモデルに真が入っていた場合にどこが贔屓されるか：真の分布のモデル：訓練データ ミニマックス最適性
 許容性

：真の分布

推定量

�
つぎのような𝜃𝜃が存在しない:

 ベイズ最適性
ベイズリスク

𝜋𝜋0 : 事前分布

̂を最小にする推定法𝜃𝜃.
(→ ベイズ推定量)

損失関数最小化

20

経験損失（訓練誤差）
𝑛𝑛

𝐿𝐿 𝑊𝑊 = � ℓ(𝑦𝑦𝑖𝑖 , 𝑓𝑓(𝑥𝑥𝑖𝑖 , 𝑊𝑊))ℓ 𝑦𝑦, 𝑦𝑦 ′ = 𝑦𝑦 − 𝑦𝑦 ′ 2
𝐾𝐾

𝑖𝑖=1

二乗損失（回帰）(𝑦𝑦, 𝑦𝑦 ′ ∈ R)ℓ 𝑦𝑦, 𝑦𝑦 ′ = − � 𝑦𝑦𝑘𝑘 log(𝑦𝑦𝑘𝑘′ ) Cross-entropy損失（多値判別）
𝑘𝑘=1(𝑦𝑦𝑘𝑘 ∈ 0,1 , 𝑦𝑦𝑘𝑘′ ∈ 0,1 , ともに和が1)

min 𝐿𝐿 𝑊𝑊𝑊𝑊𝑡𝑡−1

𝑊𝑊 𝑡𝑡 = 𝑊𝑊− 𝜂𝜂𝛻𝛻𝑊𝑊 𝐿𝐿(𝑊𝑊 𝑡𝑡−1 )• 基本的には確率的勾配降下法 (SGD) で最適化を実行• AdaGrad, Adam, Natural gradientといった方法で高速化
微分はどうやって求める？ → 誤差逆伝搬法

21• 勾配降下法−𝛻𝛻𝑊𝑊 𝐿𝐿(𝑊𝑊 𝑡𝑡−1 )𝑊𝑊 𝑡𝑡−1

𝑊𝑊 𝑡𝑡 = 𝑊𝑊 𝑡𝑡−1 − 𝜂𝜂𝛻𝛻𝑊𝑊 𝐿𝐿(𝑊𝑊 𝑡𝑡−1 )21

誤差逆伝搬法
x例：
合成関数

合成関数の微分2223x
微分を逆に伝搬

連鎖律を用いて微分を伝搬

パラメータによる微分と入力による微分は違うが，情報をシェアできる．

の場合

確率的勾配降下法 (SGD)
沢山データがあるときに強力

24(Stochastic Gradient Descent)

重い

大きな問題を分割して個別に処理
普通の勾配降下法：

全データの計算確率的勾配降下法 (SGD)

25(Stochastic Gradient Descent)

沢山データがあるときに強力

重い

大きな問題を分割して個別に処理
普通の勾配降下法：
t=1
t=2
t=3

確率的勾配降下法：

毎回の更新でデータを一つ(または少量)しか見ない26

深層学習の理論理論的課題表現能力 (第一章)
どれだけ難しい問題まで学習できるようになるか？
汎化能力(第二章)
有限個のデータで学習した時，どれだけ正しく初見のデータを正解できるようになるか？
最適化能力(第三章)
最適な重みを高速に計算機で求めることが可能か？

27• 表現能力要点のまとめ重要な関数クラス(Barron, Holder, Sobolev, Besov) はほ
ぼ最適な効率性で近似できる．
適応的な関数近似によりカーネル法を優越する．

• 汎化能力重要な関数クラスの推定精度はミニマックス最適レートを達成できる→特徴抽出機能によりカーネル法を優越．
データサイズがパラメータ数より小さくても過学習しな
い→実質的統計的自由度が小さい．
陰的正則化等により，自由度が小さく抑えられる→汎化
する．

• 最適化能力

横幅を十分広くとれば大域的最適解が勾配法で求まる．
初期パラメータのスケーリングによってNeural Tangent
KernelとMean fieldの二つの状況に大きく分けられる．
ノイズ付加により平滑化・局所解からの脱出を実現．

28

29

第1章
深層学習の表現能力

Kolmororovの加法定理

任意の連続関数は横幅固定の4層の“ニューラルネット”
で表現できる．
定理 (Kolmorov’s superposition theorem)• 定数• 𝐼𝐼 = [0,1]から𝐼𝐼への狭義単調増大連続関数が存在して，任意の連続関数𝑓𝑓 ∈ 𝐶𝐶( 0,1 𝑑𝑑 )が次のように表現できる:
なお，𝑔𝑔 ∈ 𝐶𝐶( 0,1 )は𝑓𝑓にのみ依存した関数．

• 一変数関数の合成で多変数関数が作れてしまう．
• 任意の連続関数は4層ニューラルネットの最終層だけを学習すればよいことになる．しかし，gの滑らかさはfおよび入力の次元dに強く依存し，最適な学習精度は達成できない．

30

表現能力「万能近似能力」
二層ニューラルネットワークはどんな関数も任意の精度で近似できる．

理論的にはデータが無限にあり，素子数が無限にあるニューラルネットワークを用いればどんな問題でも学習できる．
[Hecht-Nielsen,1987][Cybenko,1989]「関数近似理論」
年

基底関数

1987

Hecht-Nielsen

対象毎に構成1988

Gallant & White

Cos

Irie & Miyake

integrable

Carroll & Dickinson

Continuous sigmoidal

CybenkoContinuous sigmoidal

Funahashi

Monotone & bounded1993

Mhaskar + Micchelli

Polynomial growth

2015

Sonoda + Murata

Unbounded, admissible

1989

空間
𝐶𝐶(𝑅𝑅 𝑑𝑑 )𝐿𝐿2 (𝐾𝐾)

𝐿𝐿2 (𝑅𝑅 𝑑𝑑 )𝐿𝐿2 (𝐾𝐾)
𝐶𝐶(𝐾𝐾)

𝐶𝐶(𝐾𝐾)

𝐶𝐶(𝐾𝐾)

𝐿𝐿1 (𝑅𝑅 𝑑𝑑 )/𝐿𝐿2 (𝑅𝑅 𝑑𝑑 )31関数近似の様子

32

関数近似の様子

ReLU活性化関数

33

関数近似の様子

34

関数近似の様子

35

関数近似の様子

36…

連続関数の近似• Cybenkoの理論[Cybenko: Approximation by superpositions of a sigmoidal function.
Mathematics of control, signals and systems, 2(4): 303-314, 1989]

定義
活性化関数hがシグモイド的 ⇔定理
活性化関数hが連続なシグモイド的関数なら，任意の𝑓𝑓 ∈ 𝐶𝐶( 0,1 𝑑𝑑 )に対し，任意の𝜖𝜖 > 0において，ある𝑔𝑔 𝑥𝑥 = ∑𝑁𝑁
𝑗𝑗=1 𝛼𝛼𝑖𝑖 ℎ 𝑎𝑎𝑖𝑖 𝑥𝑥𝑖𝑖 + 𝑏𝑏𝑖𝑖 用いて，
とできる．

37

証明の直感的概略• シグモイド型の関数に対し，が成り立つ．つまり，スケールを適切に選べば，階段関数をいくらでもよく近似できる．
• 階段関数を近似できれば，それらを足し引きすることで，cos 𝛼𝛼 ⊤ 𝑥𝑥 + 𝛽𝛽 や sin 𝛼𝛼 ⊤ 𝑥𝑥 + 𝛽𝛽 をいくらでもよく近似できる．
• cos, sinが実現できるならFourier(逆)変換もできる．

• 任意の連続関数が近似できる．

38

積分表現
有限和近似（３層NN）

39

真の関数

(Sonoda & Murata, 2015)• Ridgelet変換による解析（Fourier変換の親戚）• ３層NNはridgelet変換で双対空間（中間層）に行ってから戻ってくる（出力層）イメージ

積分表現の概略 (Ridgelet変換)ある𝜓𝜓: ℝ → ℝが存在して，以下の「許容条件」が成り立つとする：

40

� 𝜂𝜂はFourie変換)(𝜓𝜓,�

(Ridgelet変換)(双対Ridgelet変換)定理
𝑓𝑓, 𝑓𝑓̂ ∈ 𝐿𝐿1 (ℝ𝑑𝑑 )の時，許容条件を満たす𝜂𝜂, 𝜓𝜓に対し以下がほとんどいたるところの𝑥𝑥 ∈ ℝ𝑑𝑑 に対して成り立つ:.

なお，連続点においては等式が常に成り立つ．
つまり，

と書ける.

Ridgelet変換= Radon変換+Wavelet変換

41

カーネル法との関係

リッジ回帰• カーネル法のアイディア： 機械学習には「内積」が頻繁に現れる．
→ 内積を“工夫”すれば非線形解析ができるはず．

• 例：リッジ回帰（Tikhonov正則化）

新しい入力xに対しては

で予測．

42

43

• リッジ回帰の変数変換版※ 𝑋𝑋𝑋𝑋 ⊤ 𝑖𝑖,𝑗𝑗 = 𝑥𝑥𝑖𝑖⊤ 𝑥𝑥𝑗𝑗 は𝑥𝑥𝑖𝑖 と𝑥𝑥𝑗𝑗 の内積．

• カーネル法のアイディア

x の間の内積を他の関数で置き換える:

このをカーネル関数と呼ぶ．

カーネル関数の満たすべき条件• 対称性：• 正値性：

この条件さえ満たしていればなんでも良いカーネルリッジ回帰

線形代数で非線形な回帰を実現．

[https://scikit-learn.org/stable/auto_examples/plot_kernel_ridge_regression.html]

44

カーネル関数の例

45

再生核ヒルベルト空間46

定義
集合Ω上の再生核ヒルベルト空間（Reproducing kernel Hilbert space, RKHS) ℋとは，Ω 上の関数からなるヒルベルト空間であって, 任意の𝑥𝑥 ∈ Ω に対し𝜙𝜙𝑥𝑥 ∈ ℋが存在し,を満たすものをいう．

𝑓𝑓 𝑥𝑥 = 𝜙𝜙𝑥𝑥 , 𝑓𝑓 ℋ

(𝑓𝑓 ∈ ℋ)• 𝑘𝑘 𝑥𝑥, 𝑦𝑦 ≔ 𝜙𝜙𝑥𝑥 , 𝜙𝜙𝑦𝑦 ℋ は正定値対称カーネル関数• 逆に正定値対称カーネルが与えられたら対応するRKHSが一意に存在定理 (Moore-Aronszajnの定理)

𝑘𝑘 𝑥𝑥, 𝑦𝑦 : 正定値対称カーネル (given)

Ω上の関数からなるヒルベルト空間ℋ𝑘𝑘 で以下の条件を満たすものが一意に存在：
1. 𝑘𝑘 𝑥𝑥,⋅ ∈ ℋ𝑘𝑘
2. 𝑓𝑓 = ∑𝑛𝑛𝑖𝑖=1 𝛼𝛼𝑖𝑖 𝑘𝑘(𝑥𝑥𝑖𝑖 ,⋅)なる有限和はℋ𝑘𝑘 内で稠密
3. 再生成：
𝑓𝑓 𝑥𝑥 = 𝑘𝑘 𝑥𝑥,⋅ , 𝑓𝑓 ℋ𝑘𝑘 ∀𝑥𝑥 ∈ Ω, ∀𝑓𝑓 ∈ ℋ𝑘𝑘 .

再生核ヒルベルト空間のイメージ• 高次元(無限次元)特徴空間に𝜙𝜙で写像して推論を行う．
• 再生核ヒルベルト空間では線形な処理が元の空間では非線形処理になる．

47

多項式カーネル
非線形写像

http://www.eric-kim.net/eric-kim-net/posts/1/kernel_trick.html

48

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

49

カーネル関数の分解とRKHSの表現

50• カーネル関数は対象行列の対角化に対応する分解を許す．

定理

ある非負測度𝜈𝜈に対して，が成り立つなら，高々加算個の正実数列 𝜇𝜇𝑖𝑖 𝑖𝑖∈𝐼𝐼 および𝐿𝐿2 (𝜈𝜈)内の正規直交基底 𝑒𝑒𝑖𝑖 𝑖𝑖∈𝐼𝐼 が存在して，と分解できる (各点収束)．
• このような分解は他にもいろいろとバージョンがある, e.g., Mercer展開．
（詳細は[Steinwart&Scovel: Constructive Approximation, 35(3):363—417, 2012] ）• さらに

𝜇𝜇𝑖𝑖 𝑒𝑒𝑖𝑖 𝑖𝑖∈𝐼𝐼 はRKHS内の正規直交基底になる．

カーネル回帰の再定式化

係数はデータから学習
カーネル法は• 中間層が無限次元RKHS• 第一層は固定• 第二層を学習であるニューラルネットに対応

y51

特徴抽出層はカーネル関数によって定まっている．

x

カーネル法52• 浅い手法の代表格．
• これも万能近似能力がある．
第1層目を固定した横幅無限の2層ニューラルネットワーク
似た手法• スプライン法• 局所多項式回帰• シリーズ推定量(線形推定量と呼ばれるクラス)• 第一層目固定• 無限個の素子

x

y
…

…

学習

固定
：カーネル関数

線形判別機(カーネル法)

再生核ヒルベルト空間の理論
非線形写像

深層NNとカーネル関数53

深層NNは「カーネル関数をデータに合わせて学習する方法」と言える

�ℓ に対応した再生核ヒルベルト空間𝒌𝒌(より正確には同じfを与えるwの中でinfを取る)

54• 深層学習は各層でカーネル関数を逐次的に構築する学習方法であるとも言える．
• データから適応的にカーネル関数を学習する点が通常のカーネル法と異なる．

これまででわかったこと• [理論] 万能近似能力という意味では浅層で十分．
• [実際] 実際は多層を使うことが多い．
→ この差はどう埋める？
カーネル法
浅層

多層ニューラルネット
深層学習→ 「表現力」を比べてみる．

55

56

万能近似理論より二層ニューラルネットでも中間層のユニット数を無限に増やせば任意の関数を任意の精度で近似できる．
歴史的には後にSVMの理論に繋がってゆく．
(例：Gaussian kernelの万能性)

Q : ではなぜ深い方が良いのか？
A : 深さに対して指数的に表現力が増大するから．

表現力と層の数

57

NNの“表現力”：領域を何個の多面体に分けられるか？
• 層の数に対して表現力は指数的に上がる．
• 中間層のユニット数 (横幅) に対しては多項式的．

折り紙のイメージ

𝐿𝐿：層の数𝑛𝑛：中間層の横幅
𝑛𝑛0 ：入力の次元

Montufar, Guido F., et al. "On the number of linear regions of deep neural networks." 2014.

多層で得する理由

58

他にも同様の結論を出している論文多数• 多項式展開，テンソル解析 [Cohen et al., 2016; Cohen & Shashua, 2016]
単項式の次数• 代数トポロジー [Bianchini & Scarselli, 2014]
ベッチ数(Pfaffian)• リーマン幾何 + 平均場理論 [Poole et al., 2016]
埋め込み曲率

対称性の高い関数は，特に層を深くすることで得をする．

ℎ(𝑥𝑥)ℎ ∘ ℎ(𝑥𝑥)ℎ ∘ ℎ ∘ ℎ(𝑥𝑥)多層が得する例

59

gはBessel関数を元に構成

三層 (中間層二層)：O(poly(𝑑𝑑𝑥𝑥 ))ノードで十分
二層 (中間層一層)：Ω(exp(𝑑𝑑𝑥𝑥 ))ノードが必要

三層

まず二乗和𝑥𝑥12 + ⋯ + 𝑥𝑥𝑑𝑑2𝑥𝑥を作ってからgを作用．
𝑥𝑥32

𝑥𝑥22
𝑥𝑥3 𝑥𝑥2 𝑥𝑥1

𝑔𝑔(中間層で座標軸方向だけを見ればよい)
𝑥𝑥12

二層(Eldan&Shamir, 2016)

全方向をケアする必要がある（座標軸方向だけではダメ）区分線形関数の表現60• 任意の区分線形関数(R𝑑𝑑 → R)は深さ log 2 (𝑑𝑑 + 1) のReLU-DNNで表現可能• ある横幅𝑤𝑤，縦幅𝑘𝑘のReLU-DNNが存在して，それを縦幅𝑘𝑘𝑘(< 𝑘𝑘)のネットワークで表現するには横幅𝑘𝑘 ′ 𝑤𝑤 𝑘𝑘/𝑘𝑘𝑘 − 1が必要．
𝑘𝑘

𝑘𝑘’(Arora et al., 2018)

大きな横幅が必要

やはり層の深さに対し指数関数的に表現力が増加

上記のネットワークの例

有理関数の近似

61• 有理関数をReLU-DNNで近似: r次多項式
をReLU-DNNで近似したい

あるReLU-DNNfが存在してノード数と近似誤差が次のように抑えられる：
ノード数

近似誤差

• ReLU-DNNを有理関数で近似
k-層で各層のノード数mの任意のReLU-DNNfに対しては，次数と近似誤差が以下で抑えられる有理関数𝑝𝑝/𝑞𝑞が存在：
次数（分母qと分子pの次数の最大値）

近似誤差

深さに対して指数的に増大• ReLU-DNNを多項式で近似：の次数が必要→有理関数に比べて表現力が低い

有理関数の近似

62• 有理関数をReLU-DNNで近似: r次多項式
をReLU-DNNで近似したい

あるReLU-DNNfが存在してノード数と近似誤差が次のように抑えられる：
ノード数

近似誤差

• ReLU-DNNを有理関数で近似
k-層で各層のノード数mの任意のReLU-DNNfに対しては，次数と近似誤差が以下で抑えられる有理関数𝑝𝑝/𝑞𝑞が存在：
次数（分母qと分子pの次数の最大値）

近似誤差

深さに対して指数的に増大• ReLU-DNNを多項式で近似：の次数が必要→有理関数に比べて表現力が低い

統計的推定理論による比較

63

深層 vs 浅層 の統計理論→「関数近似精度/推定精度」を比べてみる．
「多層」による特徴抽出と推定精度
ノンパラメトリック回帰の設定
𝜉𝜉𝑖𝑖 ∼ 𝑁𝑁 0, 𝜎𝜎 2 は観測誤差

平均二乗誤差：※実はこれは二乗損失の平均余剰誤差になっている．

なぜ深層学習が良いのか？

64• 真の関数𝑓𝑓 ∘ の形状によって深層が有利になる

縮小ランク回帰
特徴空間の次元が低い状況は深層学習が得意

区分滑らかな関数[Imaizumi&Fukumizu, 2019]

不連続な関数の推定は深層学習が得意

Besov空間[Suzuki, 2019]

滑らかさが非一様な関数の推定は深層学習が得意

低次元データ[Schmidt-Hieber, 2019] [Nakada&Imaizumi,
2019][Chen et al., 2019][Suzuki&Nitanda, 2019]

データが低次元部分空間上に分布していたら深層学習が有利

カーネル

推定精度

深層

深層学習の適応能力
深層学習には「高い適応力がある」

65[Suzuki, ICLR2019]

明らかに犬

犬と猫の中間

明らかに猫

少し絵が変わっても「犬」のまま少し絵が変わると犬/猫のどちらかに偏る

少し絵が変わっても「猫」のまま猫の度合い
滑らか

滑らかでない急激に変化

滑らかどこが重要でどこが重要でないかを見分けて，重要な部分を重点的に学習→ 多層だから可能
𝑠𝑠
深層学習はBesov空間(𝐵𝐵𝑝𝑝,𝑞𝑞)の元を推定するのにミニマックス最適レートを達成する．

(複雑な関数形状に適応的にフィットすることができる)

「浅い」学習との比較

66• 深層学習は場所によって解像度を変える適応力がある→学習効率が良い• 浅い学習は様々な関数を表現できる基底をあらかじめ十分用意して“待ち構える”必要がある．
→学習効率が悪い[Suzuki, ICLR2019]
深層学習

深層でない学習方法（カーネルリッジ回帰，KNN法，シーブ法など）≫(𝑛𝑛: sample size，𝑝𝑝: uniformity of smoothness，𝑠𝑠: smoothness)
最適ではない

平均二乗誤差 E 𝑓𝑓̂ − 𝑓𝑓

∗ 2

最適

一様な解像度がサンプルサイズが増えるにつれ減少するレート• ミニマックス最適性の意味で• 理論上これ以上改善できない精度を達成できている．

適応的解像度67

各種関数クラスと深層学習の近似/推定理論

非線形回帰問題
非線形回帰モデル

ただし，𝜉𝜉𝑖𝑖 ∼ 𝑁𝑁(0, 𝜎𝜎 2 )かつ𝑥𝑥𝑖𝑖 ∼ 𝑃𝑃𝑋𝑋 (𝑋𝑋) (i.i.d.).

𝑓𝑓 o をデータ 𝑥𝑥𝑖𝑖 , 𝑦𝑦𝑖𝑖 𝑛𝑛𝑖𝑖=1 から推定したい．

※ 以下の理論は判別問題でも展開可能

68バイアスとバリアンスのトレードオフ

69

推定精度 (汎化誤差)

推定精度 = バイアス (モデル誤差) + バリアンス (分散)

重要な関数クラス• Barronクラス• Hölderクラス• Sobolevクラス• Besovクラス

真の関数が各クラスに含まれているときに近似誤差はどれくらいになるか調べたい．

70

Hölder, Sobolev, Besov空間

71

空間的非一様性

0

滑らかさの度合い

72

• 直感：

• 非整数回の微分も定義したい．
• 整数回微分を“つなげる”→実補間• qはそのつなげ方を制御• sで関数の滑らかさを制御• pで滑らかさの空間的一様性を制御

空間の間の関係

73

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

• 例：

75

• 不連続な領域• 滑らかさが非一様的な場合：𝑝𝑝が小さい状況

これらの性質にも関わらず深層学習は良い学習ができるか？

スパース性との関係
Resolution
k=0
k=1
k=2

76

j=1
𝛼𝛼1,1
j=1

𝛼𝛼0,1

𝛼𝛼1,2
j=2

𝛼𝛼2,1 𝛼𝛼2,2 𝛼𝛼2,3 𝛼𝛼2,4j=1 j=2 j=3 j=4

k=3

Wavelet基底による展開

小さな𝑝𝑝 = スパースな係数
(非凸性)

→

大体ℓ𝒑𝒑 -ノルム

空間的な滑らかさの非一様性深層学習のモデル

77

W
L

•
•
•
•

縦幅：L
横幅：W
枝の数：S
各パラメータの上限：B• 活性化関数はReLUを仮定の深層NNモデルの集合

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

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

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

大体パラメータ数

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

B-spline

次数mのcardinal B-spline:→ 区分多項式

79

Cardinal B-splineによる展開 (DeVore & Popov, 1988)

80• Atomic decomposition:𝑠𝑠
𝑓𝑓 ∈ 𝐵𝐵𝑝𝑝,𝑞𝑞の必要十分条件:と分解できて(ただし，• ノルムの同値性：)

各B-spline基底をNNで近似(see also Bolcskei, Grohs, Kutyniok, Petersen: Optimal Approximation with Sparsely Connected Deep Neural Networks. 2018)

基本戦略• 真の関数𝑓𝑓 ∘ が次のように展開できるとする:• 各基底関数𝜙𝜙𝑘𝑘,𝑗𝑗 をReLU-NNでよく近似できるな
ら，𝑓𝑓 ∘ も良く近似できる．
• Cardinal B-splineはReLU-NNでよく近似でき
る: log(1/𝜖𝜖)層で近似誤差𝜖𝜖を達成する．

• B-splineに関する定理を深層学習に持ち込める．
→ Besov空間に限らない理論を展開可能[Bölcskei et al.: arXiv:1705.01714]

81

比較

82

なる仮定のもとで• 𝑝𝑝 = 𝑞𝑞 = ∞の時，Yarotsky (2016) の結果に帰着 (Hölder空間)• 適応的な非線形近似が必要 (Dung, 2011)
線形近似 (Linear width)：𝑝𝑝 ≠ 𝑟𝑟が重要• 深層NNの適応能力
非適応的近似（N-term approx., Kolmogorov
width）：
特徴量の適切な抽出

Hölder空間では現れない性質

小さな𝑝𝑝

関連研究

83

バイアスとバリアンス分解• これまで示したこと：バイアス（近似誤差）• これから示すこと：経験誤差最小化のバリアンス

84

85

深さ

横幅

スパース性

(非零パラメータ数)

各パラメータの絶対値の上界

なら（局所Rademacher complexityを用いて証明）⇒ バイアスとバリアンスのトレードオフをバランスすればよい．

推定精度

86

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

ただし，(clipping)．

定理 (推定精度),

かつとすることで，

𝑝𝑝 = 𝑞𝑞 = ∞のとき，Schmidt-Hieber (2017) に帰着．

のとき，

線形推定量との比較• 線形推定法

87(Donoho & Johnstone, 1994)と書ける任意の推定量(カーネルリッジ回帰，Sieve法，Nadaraya-Watson推定量...)(d=1の時)• 深層学習𝑝𝑝 < 2で差が出る

pが小さい (p<2) と深層学習が優越→ 空間的に滑らかさが非一様な時（深層学習の適応性「基底の学習・非凸性」）
c.f., 不連続関数の例：Imaizumi&Fukumizu, 2018.

直感

88

事前に設定: 非適応的手法
カーネルリッジ回帰, 最小二乗法，....

係数

基底推定する: 適応的手法
深層学習, スパース推定, Boosting, ....

スパース推定との違い：• スパース:
あらかじめ用意した多数の基底の中から重要な
基底を選択• Deep:
直接，基底を構築する

Adaptive method(deep)

89

David Donoho: ガウス賞 (2018)
スパース推定，wavelet-shrinkage，圧縮センシング，...

数学的に一般化

90「滑らかさの非一様性」「不連続性」「データの低次元性」
凸結合を取って崩れる性質をもった関数の学習は深層学習が強い→ 様々な性質を“凸性”で統一的に説明
例：ジャンプが３か所の区分定数関数

0.5x

0.5x

深層:1/𝑛𝑛, カーネル: 1/ 𝑛𝑛=+
ジャンプ3か所

ジャンプ3か所

ジャンプ6か所→ さらには「スパース推定」という観点からも説明できる．
[Satoshi Hayakawa and Taiji Suzuki: On the minimax optimality and superiority of deep neural network
learning over sparse parameter spaces. arXiv:1905.09195.]線形推定量の最悪誤差
線形推定量：
例: カーネルリッジ回帰

91と書ける任意の推定量(“浅い”学習法とみなす)

さらに条件を仮定すれば「Q-hull」まで拡張できる．
[Hayakawa&Suzuki: 2019][Donoho & Johnstone, 1994]

数学的一般化
区分滑らかな関数

92

Besov空間

縮小ランク回帰
変動指数
Besov空間

非凸性
スパース性

低次元データ例 (1): 低次元データ構造

93

関数値が
変化する方向関数値
ほぼ一定

𝑠𝑠1 , 𝑠𝑠2 , 𝑠𝑠3 : smoothness

推定精度

深層学習

(non-smooth) 𝑠𝑠1 , 𝑠𝑠2 ≪ 𝑠𝑠3 (smooth)

浅い学習（次元の呪い）例 (2): 縮小ランク回帰

94• 縮小ランク回帰
ただし，

，

．
Low rank: non-convex

推定精度の比較(LSやRidge回帰等)

低ランク行列の凸包はフルランク行列

Barronクラスの汎化誤差

95(Fourier変換)

仮定：
(例：

)

二層ニューラルネットワークの汎化誤差 (Barron 1991, 1993)

二層ニューラルネットワークのある種の正則化推定
̂
量𝑓𝑓が存在して次を満たす：

活性化関数の条件：

𝑓𝑓̂

(MDL, PAC-Bayes的解析)
線形推定量を用いると次元の呪い

Sobolevクラスの近似理論

96

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

97

第2章
深層学習の汎化誤差

98• これまでの議論は，実は問題に合わせて「適切なサイズのネットワーク」を用いた場合の議論であった．
• 実際は，かなりサイズの大きなネットワークを
用いる．

過学習

99

「なんでも表現できる方法」が最適とは限らない
少しのノイズにも鋭敏に反応してしまう
悪い学習結果良い学習結果悪い学習結果

過小学習

適切な学習

過学習

説明力が低すぎる

説明力が適切学習に用いるデータには誤りも含まれる

説明力が高すぎる（複雑すぎる）
一見当てはまりが良いので危険「過去問は解けるけれども本番の試験は解けない」という状況を回避したい

従来の学習理論
過小学習

適切な学習

100

過学習

従来の学習理論
過小学習

適切な学習
実際は...

101

過学習[Neyshabur et al., ICLR2019]

ネットワークのサイズを大きくしても過学習しない
データサイズ：120万
モデルパラメータサイズ：10億[Xu et al., 2018]

深層ニューラルネットの冗長性「Overparameterization」
パラメータサイズがデータサイズを超えている状況
での汎化性能を説明したい．

パラメータ数 ≫ データサイズ ≫ 実質的自由度
数十億

数百万

数十万

[仮説] 見かけの大きさ (パラメータ数) よりも実質的な大きさ (自由度) はかなり小さいはず．

“実質的自由度”を調べる研究：• ノルム型バウンド• 圧縮型バウンド「実質的自由度」として何が適切かを見つけることが理論上問題になる．

102

103

汎化誤差バウンド

深層学習の汎化誤差: 損失関数 (1-Lipschitz continuous w.r.t. 𝑓𝑓)
経験誤差 (訓練誤差)

期待誤差 (汎化誤差)• 汎化ギャップ
任意の𝑓𝑓̂ ∈ ℱに対して成り立つ一様バウンドが欲しい:

E.g., Rademacher 複雑度:

104

Uniform bound105Uniform bound“運良くデータに強く当てはまる”場所があるかもしれない．
→ 過学習

106

Uniform bound107

Uniform bound
過学習する場所がないことを保証するために一様なバウンドが必要

Uniform bound

モデルの「複雑さ」がバウンドに影響する→ 複雑すぎないことを保証する必要がある．

Rademacher
complexity

Dudley integral（covering num.）深層学習の汎化誤差バウンド (抜粋)
ノルム型バウンドNaïve bound

圧縮型バウンド108Naïve bound (VC-次元)?
VC-次元 [Harvey et al.2017]L☹ パラメータ数 ∑𝐿𝐿ℓ=1 𝑚𝑚ℓ 𝑚𝑚ℓ+1 がそのままバウンドに現れてしまう．
☹ パラメータ数≫データサイズの状況を説明できていない．

109

どうやって改善するか？

ℱ: ネットワーク全体
� 学習済みモデルが入りℱ:

110

うるネットワークの集合→ データ依存𝑓𝑓̂ ∈ ℱ��
※ ℱはℱよりもはるかに小さいと考えられる．

“典型的な学習済みネットワーク”の集合を解析する．

ノルム型バウンド

111

NNモデル:• Bartlett et al. (2017): 正規化マージンバウンド(最大特異値)• Golowich et al. (2018): Frobeniusノルム(𝑅𝑅ℓ,2 より大きい)☺ 横幅に依存しない. → Overparametrizationの状況を説明！
☹ 縦幅に指数的に依存する場合がある. (バウンドによる)圧縮型バウンド

圧縮可能 ⇔ 単純
学習済みネット（元ネットワーク）

ネットワークが圧縮できるなら汎化する．
圧縮したネットワーク
𝑚𝑚ℓ#

𝑚𝑚ℓ
典型的な圧縮型バウンド:

Bias

圧縮した
ネットワーク112

元のネットワーク(プルーニング等により圧縮)圧縮したネットワークの横幅

Variance
Bias-varianceトレードオフ[Arora et al., 2018; Zhou et al., 2019; Baykal et al., 2019; Suzuki et al., 2018]�
注：これらのバウンドは𝒇𝒇の汎化誤差は与えていない.
“圧縮していない”ネットワーク𝒇𝒇� の汎化誤差も与えられる (次ページ)．

非圧縮ネットの圧縮型バウンド

113

仮定: 𝑓𝑓̂ がより小さなネットワーク𝑓𝑓 # に圧縮できるとする.

� 𝑓𝑓 # ∈ ℱ # ; ℱは学習済みネットの集合,�(𝑓𝑓̂ ∈ ℱ,ℱ # は圧縮したネットの集合)[Suzuki,Abe,Nishimura:ICLR2020]

非圧縮ネットの圧縮型バウンド::圧縮可能性は訓練データのみから判断.

(学習結果が圧縮可能なように学習するのが好ましい)
𝑚𝑚ℓ
𝑚𝑚ℓ#
𝑟𝑟̂

(既存のバウンド)非圧縮ネットの圧縮型バウンド114

仮定: 𝑓𝑓̂ がより小さなネットワーク𝑓𝑓 # に圧縮できるとする.

� 𝑓𝑓 # ∈ ℱ # ; ℱは学習済みネットの集合,�(𝑓𝑓̂ ∈ ℱ,ℱ # は圧縮したネットの集合)[Suzuki,Abe,Nishimura:ICLR2020]

非圧縮ネットの圧縮型バウンド:

バリアンスを小さくできる:圧縮可能性は訓練データのみから判断.
元のネットワークを評価(既存のバウンド)(学習結果が圧縮可能なように学習するのが好ましい)
𝑚𝑚ℓ
𝑚𝑚ℓ#
𝑟𝑟̂

改善される

より正確なステートメント
仮定: 𝑓𝑓̂ がより小さなネットワーク𝑓𝑓 # に圧縮できるとする.
•� 𝑓𝑓 # ∈ ℱ # ; ℱは学習済みネットの集合,�(𝑓𝑓̂ ∈ ℱ,ℱ # は圧縮したネットの集合)•: 局所Rademacher複雑度•: 局所Rad.の不動点
Theorem (非圧縮ネットの圧縮型バウンド)

Fast part (O(1/n))
biaswith probability at least 1 − 𝑒𝑒 −𝑡𝑡 .

Main part (O(1/ 𝒏𝒏))variance115

いつどれくらい圧縮できるか？
•中間層の分散共分散行列の固有値分布•中間層の重み行列の特異値分布が速く減衰するなら圧縮しやすい．
分散共分散行列の固有値

116[実験的観察] 実際に学習した
ネットワークは圧縮しやすい．

重み行列の特異値

元サイズ

圧縮可能
サイズ

すぐ減衰

すぐ減衰

大

分散共分散行列も重み行列も特異値が速く減衰→小さい統計的自由度

小

元のサイズ

(AIC, Mallows’ Cp)

カーネル法の理論(そもそもカーネルは無限次元モデル)• 「テンソル分解」の援用によりCNNの詳細な評価も実現．

[Suzuki: Fast generalization error bound of deep learning from a kernel perspective. AISTATS2018][Li, Sun, Liu, Suzuki and Huang: Understanding of Generalization in Deep Learning via Tensor
Methods. AISTATS2020][Suzuki, Abe, Nishimura: Compression based bound for non-compressed network: unified
generalization error analysis of large compressible deep neural network, ICLR2020][Suzuki et al.: Spectral pruning: Compressing deep neural networks via spectral analysis and its
generalization error. IJCAI-PRICAI 2020]

実質的自由度Near low rank covariance

117

Distribution of eigenvalues of the covariance matrix
in an internal layer
Few large eigenvalues
Many small eigenvalues

9-th layer in VGG-13 trained on CIFAR-10

Output frominternal layer

Compression error

118

compression

Degree of freedom

eigenvalue

𝜆𝜆ℓ

𝑚𝑚ℓ#

�ℓ (𝜆𝜆ℓ )𝑁𝑁:j-th eigenvalue
𝑚𝑚ℓ = 256

IfTheorem
the eigenvalue drops rapidly, then the network can becompressed
Suppose into much smaller one.
for given 𝜆𝜆 .

Then ∃𝑓𝑓 # s.t.

ℓSingular value distribution
Singular value distribution of trained weight matrix
Random initialization

After some epoch training

After several epoch training

Over regularized

Eigenvalues shift
around 0.

[Martin&Mahoney: Traditional and Heavy-Tailed Self Regularization in Neural Network Models. arXiv:1901.08276]

119

Near low rank weight and covariance120• Near low rank weight matrix:•

Both of weight and covarianceare near low rank•
+ Other boundedness condition.

Theorem

where.

Much smaller than the VC-bound:Comparison with existing work

121

Comparison of intrinsic dimensionality between our degree of freedom and that in
Arora et al. (2018). They are computed on VGG-19 network trained on CIFAR-10.

largersmaller2[S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via
a compression approach. ICML2018.]

BigNAS[Yu et al.: BigNAS: Scaling Up Neural Architecture Search with Big Single-Stage Models. ECCV2020](理論と関係あるNAS手法)• 学習後のネットワークが圧縮できるように学習• 大きなネットワークから小さなネットワークを生成できる• EfficientNetを上回る効率性を実現

圧縮できるように学習するとスクラッチ学習より性能が向上することもある．

122

理論の副産物
自由度の理論解析により，ネットワークのどこに着目すればどれだけ圧縮できるかがわかる．

深層ニューラルネットワークの圧縮技術への応用

エッジデバイスでの運用

123

ニューラルネットワークの圧縮
圧縮

124[Suzuki, Abe, Murata, Horiuchi, Ito, Wachi, Hirai, Yukishima, Nishimura:Spectral pruning: Compressing deep neural networks via spectral analysis andits generalization error. IJCAI-PRICAI 2020]• メモリ消費量を減少• 予測にかかる計算量を減少→ 小型デバイスでの作動に有利（自動運転など）

VGG-16ネットワークの圧縮

提案手法：
従来手法より良い精度

ResNet-50ネットワークの圧縮

94%の圧縮（精度変わらず）

約半分に圧縮しても精度落ちず

転移学習のネットワーク構造決定

125[Shinya, Simo-Serra, and Suzuki: Understanding the• ある閾値以上の固有値をカウント (e.g., 10−3).
Effects of Pre-training for Object Detectors via→ 縮小したネットワークのサイズとして使う. Eigenspectrum. ICCV2019, Neural Architects Workshop]• その後，スクラッチから学習 (𝒮𝒮) もしくはImageNet事前学習モデルをファイン
チューニングする (ℐ).

Network size determination alg.

126

Overparameterizeされたネットワークの統計学

Double-descent (二重降下)

127“新しい”バイアス-バリアンスのトレードオフ• モデルがある複雑度 (サンプルサイズ) を超えた後，第二の降下が起きる．
• モデルサイズがデータより多いと推定量のバリアンスがむしろ減る．
※設定によるので注意が必要．

線形回帰における二重降下•

Hastie et al.: Surprises in High-Dimensional Ridgeless Least Squares Interpolation,
arXiv:1903.08560.

• 線形回帰を考察• 最小ノルム解：• 期待予測誤差：
定理
期待予測誤差は以下の値に𝑛𝑛, 𝑑𝑑 → ∞, かつ 𝑑𝑑⁄𝑛𝑛 → 𝛾𝛾 ∈ (0, ∞)の極限で概収束する:

バイアス

バリアンス

128

129

直感：
• 次元(d)>サンプルサイズ(n)だとデータの張る部分空間は全体の一部→実質的自由度がdより低く，バリアンス小注意：• 次元が大きくなると真の関数も変化している設定．
• 単なる線形回帰なので第一層も学習する深層学習とは異なる．

2層NNの二重降下理論

130[Mei, Song, and Andrea Montanari. "The generalization error of random features regression: Precise asymptotics and double
descent curve." arXiv preprint arXiv:1908.05355 (2019)]

Target: linear model

Model: 2層NN

Random featureモデル:(𝑤𝑤𝑚𝑚 はランダムに初期化して固定，二層目 (𝑎𝑎𝑚𝑚 ) のみ学習)
𝑀𝑀, 𝑛𝑛, 𝑑𝑑 → ∞で，𝑀𝑀⁄𝑑𝑑 → 𝜓𝜓1 , 𝑛𝑛⁄𝑑𝑑 → 𝜓𝜓2 という状況．

予測誤差が解析的に求まる． (長いので省略)→ 横幅𝑀𝑀を広くとると二重降下が現れる[Ba, Erdogdu, Suzuki, Wu, Zhang: Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint. ICLR2020]

二層NNの学習．今度は𝑎𝑎𝑚𝑚 を固定して𝑤𝑤𝑚𝑚 を学習．
𝑤𝑤𝑚𝑚 の初期値が大きい状況 (NTK)→ 二重降下現れる
𝑤𝑤𝑚𝑚 の初期値が小さい状況 (平均場)→ 二重降下が弱い

小さな初期値から始めると真の関数を表す最小限の表現を獲得する
大きな初期値から始めるとカーネル法と似た状況で過学習しやすいImplicit regularization (陰的正則化)• ニューラルネットワークの学習では様々な「陽的正則化」を用いる：
バッチノーマリゼーション，Dropout，Weight decay，...
• 実は深層学習の構造が自動的に生み出す「陰的正則化」も強く効いているという説．
例：線形ネットワーク(L2正則化学習)
任意の局所最適解は低ランクになる：

モデルの複雑さが大幅に削減されている．
(見た目のパラメータ数) 𝐿𝐿𝑚𝑚2 → 2𝑚𝑚 (実質的パラメータ数)※ 非線形活性化関数がある場合は完全には解明されていない（論文は多数）

131

勾配法と陰的正則化

132• 小さな初期値から勾配法を始めるとノルム最小化点に収束しやすい→陰的正則化

解集合
勾配法による最適化
初期値（原点付近）

最も「単純な」解
多層の線形NNを判別問題でGDすると“スパースな解”が得られる．

[Gunasekar et al.: Implicit Regularization in Matrix Factorization, NIPS2017][Soudry et al.: The implicit bias of gradient descent on separable data. JMLR2018][Gunasekar et al.: Implicit Bias of Gradient Descent on Linear Convolutional Networks, NIPS2018][Moroshko et al.: Implicit Bias in Deep Linear Classification: Initialization Scale vs Training
Accuracy, arXiv:2007.06738]

133

ResNetResNetのODE解釈

134

ResNetの各層は特徴の最適化の一反復，常微分方程式の離散化とみなせる．
+

𝐹𝐹𝑗𝑗

ℎ𝑗𝑗
ResNet5.1

人間[E, 2017][Sonoda & Murata, 2017][Li & Shi, 2017]
ResNetと常微分方程式をつなげることで常微分方程式の数値解法をネットワーク
構造の決定に持ち込める．
→ PolyNet, FractalNet, RevNet, LinearMultistep-ResNet, ...
[Lu et al.: Beyond Finite Layer Neural Networks:
Bridging Deep Architectures and Numerical Differential
Equations, ICML2018]

ODE-Net

135

連続化

ResNetODE-Net• 層を連続化することですべての層が一つのネットワークに集約される．
• ODEにすることで汎用ODEソルバーを適用できる．
 入力点に応じて離散化の粒度を変えられる．（層の概念がもはやない）[Chen et al. Neural ordinary
differential equations.
NeurIPS2018 Best Paper.]この方向性は現在「流行っている」
しかし，ODE的観点が汎化性能等の意
味で本当に意味があり有用であるかは
慎重な考察が必要である．

ResNetの平均場理論と最適制御• ResNetは入力から出力へ“最短”で繋いでいる．
→ 最適制御理論による特徴付け (HJB方程式)．

𝑥𝑥

最短

𝑦𝑦

[E, Han, Li: A Mean-Field Optimal Control Formulation of Deep Learning. Research in the
Mathematical Sciences, 6-10, 2019][Benning, Celledoni, Ehrhardt, Owren, Schönlieb: Deep learning as optimal control problems:Models and numerical methods. Journal of Computational Dynamics, 2019, 6(2) : 171-198.]• 最適制御を用いたResNetの平均場における最適化理論研究もある．

[Lu, Ma, Lu, Lu, and Ying: A mean-field analysis of deep resnet and beyond: Towards provable
optimization via overparameterization from depth. ICML2020.]

136

137

ResNet型勾配ブースティング法[Nitanda&Suzuki: Functional Gradient Boosting based on Residual Network Perception. ICML2018][Nitanda&Suzuki: Gradient Layer: Enhancing the Convergence of Adversarial Training for Generative Models. AISTATS2018]

ResNetと勾配ブースティング法の類似性• Residual Network

スキップコネクションを持つ巨大な深層ニューラルネットワーク．
画像認識タスク等でSOTA．

• 勾配ブースティング (XGBoost, LightGBM)

予測器についての関数勾配によるブースティング法 (アンサンブル学習法)．
データマイニング系のコンペティションで最も有用とされるモデル．

ResFGB=両者の関連性に着目したブースティング法[ Veit, Wilber, &Belongie 2016, Littwin & Wolf 2016, Weinan 2017, Haber, Ruthotto, & Holtham 2017,
Jastrzebski, Arpit, Ballas, Verma, Che, & Bengio 2017, Chang, Meng, Haber, Tung, and Begert 2017. etc ]1層加える=勾配法1反復

𝑥𝑥

𝑦𝑦

+

𝐹𝐹𝑗𝑗

ℎ𝑗𝑗

層を重ねるごとに目的関数を減少(関数空間での無限次元勾配法)

138

ResFGB: ResNet型勾配ブースティング法

139[Nitanda&Suzuki: Functional Gradient Boosting based on Residual Network Perception. ICML2018]• ResNetの特性を備えた勾配ブースティング法(識別問題の経験損失)

� 𝑥𝑥,𝑦𝑦 𝑙𝑙 𝑊𝑊 ⊤ 𝜙𝜙 𝑥𝑥 , 𝑦𝑦 .
min ℒ𝑛𝑛 𝜙𝜙, 𝑊𝑊 = 𝔼𝔼
𝜙𝜙,𝑊𝑊

特徴写像𝜙𝜙についℒ𝑛𝑛 𝜙𝜙 = min ℒ 𝑛𝑛 𝜙𝜙, 𝑊𝑊 の関数勾配を用いた最適化.
𝑊𝑊

関数勾配𝛻𝛻𝜙𝜙 ℒ𝑛𝑛 𝜙𝜙 : 訓練データの特徴 𝜙𝜙(𝑥𝑥)の線形分類
可能性を向上させるための方向の群れ．

ℎ = 𝜙𝜙(𝑥𝑥)の空間

未知データに適用するには平滑化が必要．
⊤→ カーネル𝑘𝑘 𝑥𝑥, 𝑥𝑥 ′ = 𝜄𝜄 𝜙𝜙 𝑥𝑥 𝜄𝜄 𝜙𝜙 𝑥𝑥 ′ で畳み込む．
𝜄𝜄はNNで十分な降下方向を与えるよう学習．
� 𝑥𝑥,𝑦𝑦 𝛻𝛻𝜙𝜙 ℒ𝑛𝑛 𝜙𝜙 𝑥𝑥 𝜄𝜄 𝜙𝜙 𝑥𝑥
𝑇𝑇𝑘𝑘 𝛻𝛻𝜙𝜙 ℒ𝑛𝑛 𝜙𝜙 = 𝔼𝔼⊤𝜄𝜄 𝜙𝜙 ⋅

残差ブロック：平滑化された関数勾配．
作り方から直交しない限り常に損失関数の降下方向．

𝐷𝐷 = {𝜙𝜙 𝑥𝑥 , 𝑦𝑦}の分類平面
ResFGBの概要

勾配ブースティングの一反復=ResNetの層追加．
関数空間での最適化の観点からマージン分布の最小化を示せる．
→ 新しい勾配ブースティングの理論に基づいた汎化保証付き深層ResNetの学習．

提案手法ResFGBの数値実験

140

中〜大規模データでの多値識別問題．以下の手法と比較．
Random Feature + SVM, Random Forest, Gradient Boosting (LightGBM)

提案手法

SOTAとされるLightGBM以上の精度を確認．
幾つかのデータでは数反復で収束．通常の勾配ブースティングより効率的な最適化．
↑関数勾配の平滑化の仕方の差異による．

141

第３章
深層学習の最適化

深層学習の“学習”142

深層ニューラルネットワークをデー
タにフィットさせるとは？

𝑊𝑊: パラメータ

𝑖𝑖番目のデータで正解していれば小さく，間違っていれば大きく損失関数：データへの当てはまり度合い
損失関数最小化(Wは数十億次元)
通常，確率的勾配降下法で最適化

最適値

誤差逆伝搬法
x例：
合成関数

合成関数の微分143深層学習で主に使われる確率的最適化法

144

問題点

145

目的関数が非凸関数
凸関数

深層学習の損失関数?

局所最適解＝大域的最適解

局所最適解

大域的最適解

局所最適解や鞍点にはまる可能性あり“狭い”ネットワークの学習はNP-完全:••

Judd (1988), Neural Network Design and the Complexity of Learning.
Blum&Rivest (1992), Training a 3-node neural network is NP-complete.

大域的最適性
深層学習の目的関数は非凸
大域的最適解

局所的最適解• 線形深層NNの局所的最適解は全て大域的最適解：
Kawaguchi, 2016; Lu&Kawaguchi, 2017.

※ただし対象は線形NNのみ．
→ 臨界点が大域的最適解であることの条件も出されている(Yun, Sra&Jadbabaie, 2018)• 低ランク行列補完の局所的最適解は全て大域的最適解：
Ge, Lee&Ma, 2016; Bhojanapalli, Neyshabur&Srebro, 2016.

146

Loss landscape147• 横幅の広いNNの訓練誤差には孤立した局所最適解がない．（局所最適解は大域的最適解とつながっている） ※とはいえ，勾配法で大域的最適解に到達可能かは別問題．

定理

𝑛𝑛個の訓練データ 𝑥𝑥𝑖𝑖 , 𝑦𝑦𝑖𝑖 𝑛𝑛𝑖𝑖=1 が与えられているとする．損失関数ℓは凸関数とする．
任意の連続な活性化関数について，横幅がデータサイズより広い𝑀𝑀⊤𝑎𝑎𝑚𝑚 𝜂𝜂(𝑤𝑤𝑚𝑚𝑥𝑥)に対する訓練誤差（𝑀𝑀 ≥ 𝑛𝑛）二層NN𝑓𝑓 𝑎𝑎,𝑊𝑊 (𝑥𝑥) = ∑𝑚𝑚=1
𝐿𝐿� 𝑎𝑎, 𝑊𝑊 = 𝑛𝑛1 ∑𝑛𝑛𝑖𝑖=1 ℓ(𝑦𝑦𝑖𝑖 , 𝑓𝑓 𝑎𝑎,𝑊𝑊 (𝑥𝑥𝑖𝑖 ))の任意のレベルセットの弧状連結
成分は大域的最適解を含む．言い換えると，任意の局所最適解は大域的最適解である．

[Venturi, Bandeira, Bruna: Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes.
JMLR, 20:1-34, 2019.]

こうはならない(つながっていない)

こうなる(参考) 2層NN-非線形活性化関数-148

二層目の重みを固定する設定(Tian, 2017; Brutzkus and Globerson, 2017; Li and Yuan, 2017; Soltanolkotabi, 2017;
Soltanolkotabi et al., 2017; Shalev-Shwartz et al., 2017; Brutzkus et al., 2018)

固定 こちらのみ動かす• Li and Yuan (2017): ReLU，入力はガウス分布を仮定

 SGDは多項式時間で大域的最適解に収束
 学習のダイナミクスは2段階→ 最適解の近傍へ近づく段階 + 近傍での凸最適化的段階• Soltanolkotabi (2017): ReLU，入力はガウス分布を仮定

 過完備 (横幅>サンプルサイズ）なら勾配法で最適解に線形収束(Soltanolkotabi et al. (2017)は二乗活性化関数でより強い帰結)• Brutzkus et al. (2018): ReLU

 線形分離可能なデータなら過完備ネットワークで動かしたSGDは
大域的最適解に有限回で収束し，過学習しない．
(線形パーセプロトロンの理論にかなり依存)

Li and Yuan (2017): Convergence Analysis of Two-layer Neural Networks with ReLU Activation.
Soltanolkotabi (2017): Learning ReLUs via Gradient Descent.
Brutzkus, Globerson, Malach and Shalev-Shwartz (2018): SGD learns over parameterized networks that provably generalizedon linearly separable data.

オーバーパラメトライゼーション

横幅が広いと局所最適解が大域的最適解になる．
狭い横幅

…
0
広い横幅

自由度が上がるため，初期値から最適解(完全フィット)へ到達しやすい．

• 二種類の解析手法

0 Neural Tangent Kernel
 Mean-field analysis (平均場解析)

149

二つのスケーリング

150• Neural Tangent Kernelのregime (lazy learning )[Jacot+ 2018][Du+ 2019][Arora+ 2019] 𝑎𝑎𝑗𝑗 = O(1/ 𝑀𝑀)• 平均場解析のregime[Nitanda & Suzuki (2017), Chizat & Bach 𝑎𝑎𝑗𝑗 = Ο(1/𝑀𝑀)(2018), Mei, Montanari, & Nguyen (2018)]※NTKの1/ 𝑀𝑀自体はそこまで本質ではない，1/𝑀𝑀より大きいことが重要．

初期化のスケーリングによって，初期値と比
べて学習によって動く大きさの割合が変わる．
→ 学習のダイナミクス，汎化性能に影響（解析の難しさも違う）

NTK

151

初期値のスケールが大きいので，初期値周りの線形近似でデータにフィットできてしまう．

初期値
モデルの集合NTKと平均場の違い

152

𝜂𝜂: ReLUとする．𝑎𝑎𝑗𝑗 = 𝑂𝑂 1 , 𝑤𝑤𝑗𝑗 = 𝑂𝑂(1/ 𝑀𝑀)または𝑤𝑤𝑗𝑗 = 𝑂𝑂(1/𝑀𝑀)とスケール変換•各𝑤𝑤𝑗𝑗 が𝑂𝑂(1/𝑀𝑀)だけ動けば，全体としてO(1)の変化(データにフィットできる)．
•横幅は十分大きく取る: 𝑀𝑀 ≫ 𝑛𝑛 (overparameterization)

NTK：相対的変化小平均場：相対的変化大

初期パラメータ

NTKの特徴写像
テイラー展開により線形モデルとみなせる→カーネル法の理論に帰着できる

相対的な変化が大きいのでテイラー展開ができない．
→ 本質的に非凸最適化になる．
（原理的には展開しても良いが，グラム行列の正定値性が保証されない）

Neural Tangent Kernel

153

連続時間ダイナミクスを考える．

• 𝒂𝒂𝒋𝒋 は固定• 𝒘𝒘𝒋𝒋 を学習

Model：[Jacot, Gabriel&Hongler, NeurIPS2018](Gradient descent, GD)

(勾配法に
よる更新)

O(1/𝑀𝑀)：
特徴写像の内積の平均
residual

𝑘𝑘𝑊𝑊 (𝑥𝑥, 𝑥𝑥𝑖𝑖 )(関数勾配)

Neural Tangent Kernel

目的関数の減少速度

154(𝐾𝐾𝑊𝑊 )𝑖𝑖,𝑗𝑗(𝜆𝜆min : グラム行列の最小固有値)
Fact[Du et al., 2018; Allen-Zhu, Li & Song, 2018]• ランダム初期化しておけば, 𝐾𝐾𝑊𝑊 (0) ≻ 𝜖𝜖𝜖𝜖 が高確率で成立．
• 最適化の最中に最小固有値は正のまま (≥ 𝜖𝜖/2).
線形収束 (exp(−𝝀𝝀min 𝒕𝒕))

ランダム初期値とNTKの正定値性
補題(横幅無限大のNTK)

Hoeffdingの不等式より⇒

一様バウンドを取って十分横幅𝑀𝑀が広ければ，ランダム初期化した
𝐾𝐾𝑊𝑊 (0) の正定値性が保証される．

155

Optimization in NTK regime156

以下のように初期化する:• 𝑎𝑎𝑗𝑗 ∼ (±1)

1(+, − is generated evenly)𝑀𝑀• 𝑤𝑤𝑗𝑗 ∼ 𝑁𝑁(0, 𝐼𝐼)

Theorem [Arora et al., 2019]

𝑀𝑀 = Ω(𝑛𝑛2 log(𝑛𝑛)/𝜆𝜆min )とすれば, 勾配法によって大域的最適解へ線形収束し，その汎化誤差は 𝒚𝒚⊤ 𝐾𝐾𝑊𝑊 (0) −1 𝒚𝒚⁄𝑛𝑛 で抑えられる．

See also[Du et al., 2018; Allen-Zhu, Li & Song, 2018; Li & Liang, 2018]• 訓練誤差0の解に線形収束する.
• 汎化誤差も一応抑えられている.
• データに完全にフィットさせてしまうので過学習の可能性あり.
• Early stoppingや正則化を入れれば過学習を防げる．(次ページ)

Spectral bias

• 最適化の観点からはoverparameterizationは有用に見える.
• 汎化誤差はどうであろうか?
NTKの固有値分布

𝑛𝑛 × 𝑛𝑛グラム行列の最小固有値 (𝜆𝜆min )𝑛𝑛• グラム行列の最小固有値は小さい (1/poly(𝑛𝑛)).
• 固有値の減少レートは多項式オーダー (理論+実験).
→ Spectral bias: 汎化の意味では好ましい.

157

Kernelによる平滑化という視点

158• Frechet 微分 in 𝐿𝐿2 (𝑃𝑃𝑛𝑛 ): 𝛻𝛻𝑓𝑓 𝐿𝐿� (𝑓𝑓)
• 平滑化積分作用素:• NTKにおける勾配は関数勾配を平滑化したもの:
勾配を平滑化！

𝑘𝑘𝑊𝑊 が高周波成分に小さな固有値を持てば，𝑇𝑇𝑘𝑘𝑊𝑊 は平滑化作用素として働く→ 帰納的バイアス (inductive bias).

NTK regimeでのSGD
モデル:

目的関数:

(We train both of first and second layers)

期待損失

初期値からのずれ

𝑌𝑌 = 𝑓𝑓 ∗ 𝑋𝑋 + 𝜖𝜖 (ノイズありの観測)

Averaged Stochastic Gradient Descent

𝑗𝑗

159

NTKにおける余剰誤差の速い収束

160[Nitanda&Suzuki: Fast Convergence Rates of Averaged Stochastic Gradient Descent under
Neural Tangent Kernel Regime, 2020.]

仮定：真の関数がNTKの作るRKHSに入っているとする．

NTK設定で適切な正則化を入れたSGDは“速い学習レート”を達成できる．
→ NTKによるsmoothingのおかげ.
Thm (速い収束レート)
𝑓𝑓𝑇𝑇 : 𝑇𝑇回更新後の解𝑀𝑀 → ∞で0に収束する項
2𝑟𝑟𝑟𝑟−2𝑟𝑟𝑟𝑟+1

NTKの固有値の減衰レート

速い学習レート(𝑂𝑂(1/ 𝑇𝑇)より速い)→ 𝑇𝑇
はミニマックス最適レート.
(各種パラメータの意味は次ページに詳細)

仮定

161

2層NNのNTK:

横幅無限における積分作用素:
population

スペクトル分解:,仮定• 𝑓𝑓 ∗ (𝑥𝑥) = E[𝑌𝑌|𝑋𝑋 = 𝑥𝑥] が次のように書ける:

𝑇𝑇𝑘𝑘𝑟𝑟∞ ℎ = 𝑓𝑓 ∗for ℎ ∈ 𝐿𝐿2 (𝑃𝑃𝑋𝑋 ), and 𝑟𝑟 ∈ [1/2,1].

• 固有値減衰条件:
𝜇𝜇𝑗𝑗 = O 𝑗𝑗 −𝛽𝛽 .

真の関数の平滑性

カーネル関数の“複雑さ”

カーネルリッジ回帰の解析における標準的な仮定; see, e.g., Dieuleveut et al.
(2016); Caponnetto and De Vito (2007) (rの条件はやや強め).

162

NTKの固有値分布

NTKの固有値固有関数分解
𝜙𝜙𝑚𝑚 ∞
𝑚𝑚=1 : 固有関数. 𝐿𝐿2 (𝑃𝑃𝑋𝑋 )内の正規直交基底．

実際のNTKの固有値は多項式オーダーで減衰する．
[Bietti&Mairal (2019); Cao et al. (2019);
Ronen et al. (2019)]

低周波成分

低周波成分が最初に補足される．
その後，高周波成分が徐々に補
足される．
高周波成分

Beyond kernel

163

問題点：NTKは解析がしやすいが，結局カーネル法の範疇なので深層学習の“良さ”が現れない．
 NTKをはみ出す理論の試みがいくつかなされている．
（今後発展が予想される）• Allen-Zhu&Li (2019,2020)

Allen-Zhu&Li: What Can ResNet Learn Efficiently, Going Beyond Kernels? NIPS2019.
Allen-Zhu&Li: Backward Feature Correction: How Deep Learning Performs Deep
Learning. arXiv:2001.04413.

(ResNet型ネットワークでカーネルを優越する状況)• Li, Ma&Zhang (2019)

Li, Ma&Zhang: Learning Over-Parametrized Two-Layer ReLU Neural Networks
beyond NTK. arXiv:2007.04596.

(テンソル分解の理論で深層学習がカーネルを優越することを示した)• Bai&Lee (2020)

Bai&Lee: Beyond Linearization: On Quadratic and Higher-Order Approximation ofWide Neural Networks. ICLR2020.

(二次のテイラー展開まで使う)

平均場解析

164• ニューラルネットワークの最適化をパラメータの分布最適化としてみなす．
𝑀𝑀 → ∞(𝑎𝑎, 𝑤𝑤)に関する確率密度𝜌𝜌による平均とみなせる:

𝑓𝑓の最適化 ⇔ 𝜌𝜌の最適化

連続方程式

Wasserstein勾配流[Atsushi Nitanda and Taiji Suzuki: Stochastic Particle Gradient Descent for Infinite Ensembles. arXiv:1712.05438.](各粒子は勾配降下方向へ移動)

MMDとの関係

165

MMD: Maximum Mean Discrepancy[Gretton et al., NIPS2006]: 真の関数𝑘𝑘((𝑎𝑎, 𝑤𝑤), (𝑎𝑎𝑎, 𝑤𝑤’)) = 𝜙𝜙𝑘𝑘 𝑎𝑎, 𝑤𝑤 , 𝜙𝜙𝑘𝑘 𝑎𝑎′ , 𝑤𝑤 ′
↑正定値カーネルになっている．

: MMD

ℋ𝑘𝑘

L2距離最小化⇔ MMD最小化[Arbel et al. arXiv:1906.04370][Sonoda, arXiv:1902.00648]

粒子勾配降下法
1つの粒子

166

• 各ニューロンのパラメータを一つの粒子とみなす．
• 各粒子が誤差を減らす方向に動くことで分布が最適化される．

(分布)

データへの当てはまりを良くする方向に変化(各粒子の移動方向：勾配方向)

M個の粒子が移動[Nitanda&Suzuki, 2017]

𝑀𝑀 → ∞の極限で，最適解への収束が成り立つ場合がある．
[Nitanda&Suzuki, 2017][Chizat&Bach, 2018][Chizat, 2019]

ノイズありのダイナミクス: McKean-Vlasov過程[Mei, Montanari&Nguyen, 2018]

Wasserstein距離について

167

𝜇𝜇, 𝜈𝜈:距離空間(𝒳𝒳, 𝑐𝑐)上の確率測度(通常𝒳𝒳はPoland空間)
Π 𝜇𝜇, 𝜈𝜈 : 周辺分布が𝜇𝜇, 𝜈𝜈である𝒳𝒳 × 𝒳𝒳上の同時分布の集合
周辺分布を固定した同時分布の中で最小化• 分布のサポートがずれていてもwell-defined• 底空間の距離が反映されている※KL-divergenceは距離が反映されない．

（双対表現: Kantorovich双対）「輸送距離」とも言われる

𝑊𝑊𝟐𝟐 距離と粒子勾配降下法の関係

𝑊𝑊2 距離による近接点アルゴリズムを考える：(𝛿𝛿は十分小さいとする)168

𝑓𝑓𝜈𝜈 𝑥𝑥 = ∫ ℎ 𝑤𝑤, 𝑥𝑥 d𝜈𝜈 𝑤𝑤𝜈𝜈について最小化→各𝑤𝑤ごとに𝑣𝑣の条件付分布を最小化 →Dirac測度 (∵局所的に強凸)：最急降下法• 各粒子ごとにみると単純な最急降下法．
• 粒子勾配降下法は𝑊𝑊2 距離を近接項とした近接点アルゴリズムの一次近似→ 𝛿𝛿 → 0の極限 (連続時間)：Wasserstein gradient flow

連続の方程式と勾配流「連続の方程式」

169の意味(∀𝑓𝑓: コンパクトサポート，𝐶𝐶 ∞ -級)• 今，𝜌𝜌𝑡𝑡 は写像𝑇𝑇𝑡𝑡 : 𝑅𝑅𝑑𝑑 → 𝑅𝑅𝑑𝑑 による𝜌𝜌0 の押し出しであるとする：𝜌𝜌𝑡𝑡 = 𝑇𝑇𝑡𝑡# 𝜌𝜌0 .
つまり，𝑤𝑤 ∼ 𝜌𝜌0 に対する𝑇𝑇𝑡𝑡 (𝑤𝑤)の分布が𝜌𝜌𝑡𝑡 であるとする．

• 写像𝑇𝑇𝑡𝑡 を生成するベクトル場を

d𝑇𝑇𝑡𝑡(𝑤𝑤) = 𝑣𝑣𝑡𝑡 (𝑇𝑇𝑡𝑡 (𝑤𝑤))とする．
d𝑡𝑡

(分布)

(連続の方程式)に対し，としたのが前ページの更新式．

接ベクトル定理• 𝜌𝜌𝑡𝑡 = 𝑇𝑇𝑡𝑡# 𝜌𝜌0
•

d𝑇𝑇𝑡𝑡
d𝑡𝑡

𝑤𝑤 = 𝑣𝑣𝑡𝑡 𝑇𝑇𝑡𝑡 𝑤𝑤• ある𝜙𝜙𝑡𝑡 を用いて𝑣𝑣𝑡𝑡 = 𝛻𝛻𝜙𝜙𝑡𝑡 と書けるとする．
この時，以下が成り立つ:

詳細は以下を参照:
Ambrosio, Gigli, and Savaré. Gradient Flows in Metric Spaces and in theSpace of Probability Measures. Lectures in Mathematics. ETH Zürich.
Birkhäuser Basel, 2008.
𝑣𝑣𝑡𝑡

𝑇𝑇𝑡𝑡

170

輸送写像

171

Brenierの定理
𝜌𝜌0 , 𝜌𝜌1 が確率密度関数を持つ時，以下が成り立つ:• Infを達成する写像𝑇𝑇 ∗ が存在する．

• しかも，ある凸関数𝜓𝜓が存在して𝑇𝑇 ∗ 𝑥𝑥 ∈ 𝜕𝜕𝜕𝜕 𝑥𝑥 と書ける．
• この𝑇𝑇 ∗ を最適輸送写像という．

Benamou-Brenier formula (連続の方程式と𝑊𝑊2 距離の関係):
同条件のもと

ただし，infは𝜌𝜌0 から𝜌𝜌1 へ連続の方程式で“繋ぐ”
全ての速度ベクトル場𝑣𝑣𝑡𝑡 に関して取る．
𝜌𝜌0• 𝜌𝜌𝑡𝑡 = 𝑇𝑇𝑡𝑡# 𝜌𝜌0
•

d𝑇𝑇𝑡𝑡
d𝑡𝑡

𝑤𝑤 = 𝑣𝑣𝑡𝑡 𝑇𝑇𝑡𝑡 𝑤𝑤

𝑇𝑇𝑡𝑡

𝑣𝑣𝑡𝑡

𝜌𝜌1

172

• Wasserstein勾配流は𝑊𝑊2 距離を用いた近接点ア
ルゴリズムで特徴づけられることが分かった．
• 目的関数がW2距離に関する凸性（displacement
convexity）が成り立つなら，大域的最適解への収束が示せる（エントロピーなど）:
𝑊𝑊2 𝜌𝜌𝑡𝑡 , 𝜌𝜌∗ ≤ 𝑒𝑒 −𝜆𝜆𝜆𝜆 𝑊𝑊2 (𝜌𝜌0 , 𝜌𝜌∗ ).

• しかし，NNの最適化では凸性は成り立たない．
そのため，大域収束を示すことが難しい．

• もっとも，局所的には凸性が成り立ちうる．
例：スパースな最適解 [Chizat, 2019]

局所最適性条件

173

定理 (Nitanda&Suzuki, 2017)
ある解𝜇𝜇がコンパクトな台の確率密度関数を持つとする．
�
この時，ある𝜇𝜇 ∗ s.t. 𝐿𝐿 𝜇𝜇 ∗ < 𝐿𝐿(𝜇𝜇)が存在して�∗• supp 𝜇𝜇 ∗ ⊆ supp(𝜇𝜇)かつ𝜇𝜇�
は確率密度を持つ，or�• 𝜇𝜇 ∗ は密度を持たずsupp 𝜇𝜇 ∗ はsupp(𝜇𝜇)に内部に含まれる，が満たされるとき，降下方向が存在して粒子降下法によって目的関数値を減らすことができる．

𝜇𝜇̂

𝜇𝜇 ∗

𝜇𝜇 ∗

𝜇𝜇̂

このような場合は降下方向は無い

平均場解析と陰的正則化

174

二値判別をexp-損失を用いて解く (ラベルノイズなしとする):
ただし
符号付測度の中で最適化
平均場解析の設定で最適化する．
初期値が小さいので判別に必要なニューロンだけが「生えてくる」．
[Chizat&Bach:Implicit Bias of
Gradient Descent for WideTwo-layer Neural Networks
Trained with the Logistic Loss.
COLT2020.]→ スパースな解：陰的正則化

最適化の結果として「単純な」解が求まってしまう．

判別平面はL1-正則化解マージン最大化元に収束する:

勾配法と陰的正則化 (再掲)175

• 小さな初期値から勾配法を始めるとノルム最小化点に収束しやすい→陰的正則化

解集合
勾配法による最適化
初期値（原点付近）

最も「単純な」解
多層の線形NNを判別問題でGDすると“スパースな解”が得られる．

[Gunasekar et al.: Implicit Regularization in Matrix Factorization, NIPS2017][Soudry et al.: The implicit bias of gradient descent on separable data. JMLR2018][Gunasekar et al.: Implicit Bias of Gradient Descent on Linear Convolutional Networks, NIPS2018][Moroshko et al.: Implicit Bias in Deep Linear Classification: Initialization Scale vs Training
Accuracy, arXiv:2007.06738]

各regimeにおける陰的正則化
各regimeにおける陰的正則化の種類
Regime対応する正則化

NTK, カーネル法 withearly stopping

L2-正則化

平均場理論

L1-正則化• ニューラルネットワークの学習では様々な「陽的正則化」を用いる：
バッチノーマリゼーション，Dropout，Weight decay，MixUp，...
• 一方で，深層学習の構造が自動的に生み出す「陰的正則化」も強く効いていると考えられる．
→ オーバーパラメタライズしても過学習しない．

176

177

ノイズあり勾配法と大域的最適性

Sharp minima vs flat minima

178

SGDは「フラットな局所最適解」に落ちやすい→良い汎化性能を示すという説

Keskar, Mudigere, Nocedal, Smelyanskiy, Tang (2017):
On large-batch training for deep learning: generalization gap and sharp minima.

≅正規分布→ ランダムウォークはフラットな領域にとどまりやすい•「フラット」という概念は座標系の取り方によるから意味がないという批判．
(Dinh et al., 2017)•PAC-Bayesによる解析 (Dziugaite, Roy,2017)

ノイズによる平滑化効果

179smoothing[Kleinberg, Li, and Yuan, ICML2018]

確率的勾配を用いる ⇒ 解にノイズを乗せている⇒ 目的関数の平滑化

ノイズを加えて平滑化した目的関数を最適化．

関連研究: Graduated optimization• Graduated non-convexity

Blake and Zisserman: Visual reconstruction, volume 2. MIT press Cambridge, 1987.

• Gaussian kernelとの畳み込み

Z. Wu. The effective energy transformation scheme as a special
continuation approach to global optimization with application to molecularconformation. SIAM Journal on Optimization, 6(3):748-768, 1996.

• Graduated optimization
Hazan, Levy, and Shalev-Shwartz: On graduated optimization forstochastic non-convex problems. International conference on machinelearning, pp. 1833-1841, 2016.

𝜎𝜎-nice性の導入．多項式オーダーでの収束．

𝐿𝐿� 𝛿𝛿 𝑥𝑥 = E𝑢𝑢∼𝑈𝑈(B(R𝑑𝑑)) [𝐿𝐿(𝑥𝑥 + 𝛿𝛿𝛿𝛿)]

Survey:Mobahi and Fisher III. On the link between gaussian homotopy
continuation and convex envelopes. Energy Minimization Methods
in Computer Vision and Pattern Recognition, pp. 43-56, 2015.

180

GLD/SGLD

181• Stochastic Gradient Langevin Dynamics (SGLD)(非凸)𝛽𝛽: 逆温度(勾配Langevin動力学)

定常分布：
離散化

[Gelfand and Mitter (1991); Borkar andMitter (1999); Welling and Teh (2011)]

GLD:(Euler-Maruyama近似)

SGLD:
確率的勾配

182

Gaussian noise
Gradient descent収束定理 (有限次元)• 𝑓𝑓𝑖𝑖 : 有界，Lipschitz連続，滑らかな勾配• 散逸条件:(+ その他細かい条件)

Thm [Raginsky, Rakhlin and Telgarsky, COLT2017]• 𝜆𝜆∗ はスペクトルギャップと言われる量．
→ 次元dや逆温度パラメータβに対して指数関数的に依存．
• 逆温度パラメータが十分大きくて，更新を十分な回数回せば最適解付近に近づける．
• Xu et al. (NeurIPS2018) は収束レートを改善しているが，証明にいくつかの間違いあり．

183

184

散逸条件

対数Sobolev不等式

185: 連続時間ダイナミクスの定常分布

1. 散逸条件 (→Poincareの不等式)
2. 平滑性
対数Sobolev不等式

Geometric ergodicity

𝜌𝜌𝑡𝑡 : 𝑋𝑋𝑡𝑡 の周辺分布

定常分布へ線形収束[Bakry, Gentil, and Ledoux: Analysis and Geometry of Markov Diffusion Operators. Springer, 2014. Th. 5.2.1]

連続の方程式再び• 勾配ランジュバン動力学に対応する連続の方程式• 勾配ランジュバン動力学は相対エントロピー (KL-ダイ
バージェンス) をWasserstein勾配流で最適化していることに対応:

Remark:通常の（相対でない）エントロピーは𝑊𝑊2 -距離に関して凸 (displacement
convexity)．つまり，𝑊𝑊2 -距離に関する測地線上で凸関数になる．

186

無限次元への拡張

187[Muzellec, Sato, Massias, Suzuki, arXiv:2003.00306][Suzuki, arXiv:2007.05824]

正則化

Ex.
• ℋ: 𝐿𝐿2 (𝜌𝜌)• ℋ𝐾𝐾 : 再生核ヒルベルト空間 (e.g. Sobolev空間)

最適解

暗黙の仮定: 大域的最適解はℋ𝐾𝐾 で十分に近似できる.

E.g., Bayesian optimization on infinite dimensional space[Zimmermann and Toussaint. Bayesian functional optimization. AAAI, 2018][Vellanki, Rana, Gupta, de Celis Leal, Sutti, Height, and Venkatesh: Bayesian functional optimisation
with shape prior. AAAI, 2019]

例: NNの学習

188• 2層ニューラルネットワーク

Idea: 分布の学習 → 輸送写像の学習“Lift”

以前の表記

189

2層NNの学習: 直接表現

NTKと違い，𝑎𝑎𝑗𝑗 はデータサイズにも横幅にも依存させずスケー
ルを固定できる.
(TNKは𝑎𝑎𝑗𝑗 = 1/ 𝑀𝑀とする)

190

無限次元ランジュバン動力学

191: RKHS with kernel 𝐾𝐾.

ノルム: For
Cylindrical Brownian motion:
時間離散化:(準陰的Eulerスキーム), we let

where

.

定常分布

192

(Hilbert空間上のガウス過程)と解釈しても良い．

（無限次元）勾配ランジュバン動力学の定常分布はガウス過程事前分布を用いたベイズ事後分布に対応する．
→ 過学習を防ぎ汎化する [Suzuki, arXiv:2007.05824]

無限次元の設定

193

ヒルベルト空間

RKHS構造仮定 (固有値の減少)(あまり本質的ではない．𝜇𝜇𝑘𝑘 ∼ 𝑘𝑘 −𝑝𝑝 (𝑝𝑝 > 1) としても良い．)

Assumption (1)194• It either holds:(強):強凸(弱)散逸条件:

Assumption (2)• Smoothness:• Strong smoothness condition:(これが無い場合はレートが遅くなる)(This is not standard, but, is satisfied in the previous examples)• Third order smoothness:

195誤差の解析
𝜋𝜋∞ :定常分布

Thm (informal)[Muzellec, Sato, Massias, Suzuki, 2020]

上記の条件のもと，次が成り立つ：(geometric ergodicity + time discretization)
ただし 𝜅𝜅 > 0 は任意の正の実数, 𝑐𝑐𝛽𝛽 =逸条件).
Remark:𝛽𝛽 (有界な勾配), 𝑐𝑐𝛽𝛽 = 1 (強散for

証明は以下の論文のテクニックを援用: Brehier 2014; Brehier&Kopec 2016;
Mattingly et al., 2002; Goldys&Maslowski, 2006.

196

誤差の解析 (2)197

𝜋𝜋∞ : 定常分布
Thm [Muzellec, Sato, Massias, Suzuki, arXiv:2003.00306 (2020)]
上記の条件のもと，次が成り立つ：(geometric ergodicity+ time discretization)(bias of invariant measure)
ただし 𝜅𝜅 > 0 は任意の正の実数, 𝑐𝑐𝛽𝛽 =
逸条件).

𝛽𝛽 (有界な勾配), 𝑐𝑐𝛽𝛽 = 1 (強散Λ∗𝜂𝜂 : スペクトルギャップ，𝛽𝛽に対して指数的依存がある．

証明は以下の論文のテクニックを援用: Brehier 2014; Brehier&Kopec 2016;
Mattingly et al., 2002; Goldys&Maslowski, 2006.

• 深層学習の最適化への応用と汎化誤差解析：Suzuki, arXiv:2007.05824.

ノイズのコントロール

198• 大域的最適解を得るためには𝛽𝛽 → ∞が必要．
• スペクトルギャップは𝛽𝛽に指数的に依存．
• 大域的最適解まわりで局所的に凸になっていて，離れた場所より目的関数値が真に小さければ途中で勾配法に切り替えても良い．
• 例えば2層NNでは訓練誤差の形状が局所的に強凸になることがある [Li and Yuan, 2017][Chizat, 2019](各ニューロンが適度にばらけている場合はそうなる)

勾配法

誤差の分解199

弱収束を示す:for a smooth function 𝜙𝜙.

• Raginsky et al. (2017),

Bréhier (2014), Bréhier and Kopec (2016):

連続時間𝑋𝑋(𝑡𝑡)遠い• Xu et al. (2018):

𝑋𝑋𝑛𝑛

離散時間

定常分布

𝑋𝑋 𝜋𝜋∞

近い𝑋𝑋𝜇𝜇𝜂𝜂

𝑥𝑥 ∗

レートが速い, 一方でより強い条件が必要(Strong smoothness)

第一項のバウンド
補題 (離散時間ダイナミクスのGeometric ergodicity)

ある定常分布𝜇𝜇𝜂𝜂 がだた一つ存在して (極限分布),
geometric ergodicity (定常分布への線形収束) が成り立つ:
ただし，“スペクトルギャップ” Λ∗𝜂𝜂 は以下のように与えられる,(i) (Strict dissipative)(ii) (Bounded gradient)for• 有限次元の場合と違い，強平滑条件がないとおそらく成り立たない.
• Coupling argument: Lyapunov条件, majorization条件より(Mattingly et al. (2002)とGoldys&Maslowski (2006)のテクニックを合わせる)200

Geometric ergodicity

201• Coupling argument

𝑋𝑋0

𝑋𝑋0′
𝑋𝑋𝑡𝑡

Prob(“couple” until time 𝑡𝑡)≥ 1 − 𝑒𝑒 −𝑐𝑐𝑐𝑐

𝑋𝑋𝑡𝑡′
𝑋𝑋𝑇𝑇

𝑋𝑋𝑇𝑇′
同じ分布に従う

第二項のバウンド
𝑋𝑋𝜇𝜇𝜂𝜂 : 離散時間ダイナミクスの定常分布
𝑋𝑋 𝜋𝜋 : 連続時間ダイナミクスの定常分布 (存在と一意性は保証されている)

補題 (連続・離散時間ダイナミクスの定常分布の違い)

任意の0 < 𝜅𝜅 < 1/2に対し，ある定数𝐶𝐶が存在して，•• 𝑐𝑐𝛽𝛽 =𝛽𝛽 for bounded gradient condition, and 𝛽𝛽 = 1 otherwise• Malliavin解析• ステップサイズ𝜂𝜂を0に近づけると，離散時間ダイナミク
スが連続時間ダイナミクスに近づく.
• 𝛽𝛽はΛ∗0 に影響している.

202

有限次元バージョンとの関係•

203

large 𝑝𝑝

(我々の状況)(optimal)•𝑘𝑘(予想) see [Andersson,Kruse&Larsson, 2016] for finite time horizon.
𝒑𝒑が大きくなるほど関数クラスは“単純”になる.

有限次元の解析は𝑝𝑝 → ∞に対応 (定数を無視すれば):[Xu et al. (2018)]𝑘𝑘

判別問題における速い収束

Assumption• 強低ノイズ条件:

1
1/2

•

0

• 活性化関数はなめらか:• 真の関数はモデルに入っているとする: 𝑓𝑓 ∗ = 𝑓𝑓𝑊𝑊∗ ．
十分大きな𝑛𝑛と𝛽𝛽 ≤ 𝑛𝑛に対し，

ベイズ最適な判別機が高い確率で求まる．(𝛽𝛽は定数のままでも良い)204

内容のアウトライン• 深層学習の理論
 表現能力 汎化能力 最適化能力• 表現力• 万能近似性• 層を深くすることで指数的に表現力増大• 汎化能力• 適応的な学習手法を実現→真の関数に非凸性・スパース性があれば，カーネル法のような特徴写像を固定する方法に優越• 陰的正則化等でoverparametrizedな状況でも汎化• 最適化理論• Overparametrizeされていれば大域的最適解を得る• Neural Tangent Kernelと平均場• スケールの仕方によって凸らしさが変わる→最適化の難しさと陰的正則化の種類が変わる（L2 vs L1）

205

まとめ

206

• 深層学習はなぜうまくいくのか？[世界的課題]• 数学による深層学習の原理究明
 「表現能力」，「汎化能力」，「最適化」

学習

カーネル法

スパース推定特徴抽出

テンソル分解深層学習の理論
Besov空間数学

関数近似理論

連続方程式 Wasserstein幾何

確率集中不等式
確率過程

理論により深層学習を“謎の技術”から“制御可能な技術”へ
深層学習を超える方法論の構築へ