1

数理情報学演習第二深層学習の数理鈴木大慈
東京大学大学院情報理工学系研究科数理情報学専攻
数理第六研究室2019年9月27日

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

統計的学習

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

線形モデルの限界

１９８０年代：
エキスパートシステ
ム

１９８０年代：多層パーセプトロン，誤差逆伝搬，人手による学習ルールの作りこみの限界「膨大な数の例外」

第二次ニューラルネットワークブーム

畳み込みネット

非凸性の問題

１９９２： 非線形サポートベクトルマシン（カーネル法）１９９６： スパース学習 （Lasso）
Siriなどにつながる

2

２００３： トピックモデル （LDA）

２０１２： Supervision （Alex-net）
第三次ニューラルネットワークブーム

データの増加＋計算機の強化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.]

3

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

深層学習

25
20
15
10
5
0

8層

8層

19層

22層

152層

ILSVRCILSVRCILSVRCILSVRCILSVRCILSVRC

2010

2011

2012

2013

2014

2014

2015

VGG

GoogleNet

ResNet

AlexNetHuman

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

ILSVRC4

教師あり学習5

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

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

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

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

𝑊1 𝑥

ℎ1 (𝑊1 𝑥)線形変換 非線形変換ℎ1 𝑢 = ℎ11 𝑢1 , ℎ12 𝑢2 , … , ℎ1𝑑 𝑢𝑑

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

線形変換

非線形変換

𝑇

• ☆ReLU (Rectified Linear Unit)：• シグモイド関数：

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

全結合モデル• 第ℓ層

7

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

シグモイド関数8

訓練誤差と汎化誤差

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

汎化誤差：損失の期待値

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

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

代わりに最小化するもの．
(訓練データはテストデータと同じ分布に従っていると仮定)

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

損失関数の例

10

• 回帰
損失関数
（二乗誤差）
訓練誤差最小化（最小二乗法）線形モデルを深層NNモデルにすれば深層NNを用いた最小二乗回帰になる．

損失関数の例• 二値判別損失関数（ロジスティック損失）
訓練誤差最小化（ロジスティック回帰）

𝑦𝑖 = 1𝑦𝑖 = −111回帰の損失関数12※各損失関数は必ずしも確率モデルと対応するわけではない二値判別の損失関数

13

凸代理損失
で𝜙が凸の時定理 𝜙が判別一致性をもつ⇔ 𝜙が原点で微分可能かつ𝜙 ′ (0) > 0
判別一致性: 期待リスク最小化元が0-1損失の意味でも最適(Bayes最適)[Bartlett et al., 2006]

損失関数最小化

14

経験損失（訓練誤差）𝑛

𝐿 𝑊 = ෍ ℓ(𝑦𝑖 , 𝑓(𝑥𝑖 , 𝑊))𝑖=1ℓ 𝑦, 𝑦 ′ = 𝑦 − 𝑦 ′ 2

二乗損失（回帰）(𝑦, 𝑦 ′ ∈ R)𝐾

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

𝑘=1

min 𝐿 𝑊𝑊
𝑡−1

𝑊𝑡 = 𝑊− 𝜂𝛻𝑊 𝐿(𝑊 𝑡−1 )• 基本的には確率的勾配降下法 (SGD) で最適化を実行• AdaGrad, Adam, Natural gradientといった方法で高速化

微分はどうやって求める？ → 誤差逆伝搬法

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

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

確率的勾配降下法 (SGD)

16(Stochastic Gradient Descent)
沢山データがあるときに強力

重い

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

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

17(Stochastic Gradient Descent)
沢山データがあるときに強力

重い

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

確率的勾配降下法：
毎回の更新でデータを一つ(または少量)しか見ない

t=1
t=2
t=3

18

深層学習の理論理論的課題表現能力 (第一章)
どれだけ難しい問題まで学習できるようになるか？

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

19

20

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

万能近似能力21

ニューラルネットの関数近似能力は80年代に盛んに研究された．

なる関数が𝑚 → ∞で任意の関数を任意の精度で近似できるか？
（「任意の関数」や「任意の精度」の意味はどのような関数空間を考えるかに依存）hがシグモイド関数やReLUなら万能性を有する．
年

基底関数

空間

1987

Hecht-Nielsen

対象毎に構成𝐶(𝑅𝑑 )

1988

Gallant & White

Cos

𝐿2 (𝐾)

Irie & Miyake

integrable

𝐿2 (𝑅𝑑 )Carroll & Dickinson

Continuous sigmoidal

𝐿2 (𝐾)

CybenkoContinuous sigmoidal

𝐶(𝐾)Funahashi

Monotone & bounded

𝐶(𝐾)

1993

Mhaskar + Micchelli

Polynomial growth

𝐶(𝐾)

2015

Sonoda + Murata

Unbounded, admissible

𝐿1 (𝑅𝑑 )1989

Kは任意のコンパクト集合

参考：園田, “ニューラルネットの 積分表現理論”, 2015.

連続関数の近似• 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 𝛼𝑖 ℎ 𝑎𝑖 𝑥𝑖 + 𝑏𝑖 用いて，

とできる．

22

証明の直感的概略• シグモイド型の関数に対し，が成り立つ．つまり，スケールを適切に選べば，階段関数をいくらでもよく近似できる．

• 階段関数を近似できれば，それらを足し引きすることで，cos 𝛼 ⊤ 𝑥 + 𝛽 や sin 𝛼 ⊤ 𝑥 + 𝛽 をいくらでもよく近似できる．
• cos, sinが実現できるならFourier(逆)変換もできる．
• 任意の連続関数が近似できる．

23

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

24

真の関数

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

積分表現の概略 (Ridgelet変換)25ある𝜓: ℝ → ℝが存在して，以下の「許容条件」が成り立つとする：
෠ 𝜂はFourie変換)(𝜓,ො(Ridgelet変換)(双対Ridgelet変換)定理
𝑓, 𝑓መ ∈ 𝐿1 (ℝ𝑑 )の時，許容条件を満たす𝜂, 𝜓に対し以下がほとんどいたるところの𝑥 ∈ ℝ𝑑 に対して成り立つ:.
なお，連続点においては等式が常に成り立つ．

つまり，

と書ける.

Ridgelet変換= Radon変換+Wavelet変換[Sonoda & Murata, 2015]

26

カーネル法との関係

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

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

新しい入力xに対しては

で予測．

27

28

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

• カーネル法のアイディア
x の間の内積を他の関数で置き換える:

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

カーネル関数の満たすべき条件• 対称性：• 正値性：
この条件さえ満たしていればなんでも良いカーネルリッジ回帰

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

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

29

カーネル関数の例30

再生核ヒルベルト空間31

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

𝑓 𝑥 = 𝜙𝑥 , 𝑓 ℋ(𝑓 ∈ ℋ)• 𝑘 𝑥, 𝑦 ≔ 𝜙𝑥 , 𝜙𝑦 ℋ は正定値対称カーネル関数• 逆に正定値対称カーネルが与えられたら対応するRKHSが一意に存在定理 (Moore-Aronszajnの定理)
𝑘 𝑥, 𝑦 : 正定値対称カーネル (given)
Ω上の関数からなるヒルベルト空間ℋ𝑘 で以下の条件を満たすものが一意に存在：
1. 𝑘 𝑥,⋅ ∈ ℋ𝑘
2. 𝑓 = σ𝑛𝑖=1 𝛼𝑖 𝑘(𝑥𝑖 ,⋅)なる有限和はℋ𝑘 内で稠密
3. 再生性：𝑓 𝑥 = 𝑘 𝑥,⋅ , 𝑓 ℋ𝑘 ∀𝑥 ∈ Ω, ∀𝑓 ∈ ℋ𝑘 .

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

32

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

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

33

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

34

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

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

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

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

カーネル回帰の再定式化

係数はデータから学習

カーネル法は• 中間層が無限次元RKHS• 第一層は固定• 第二層を学習というニューラルネットに対応

y36

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

x

カーネル法と深層学習の関係
深層学習とカーネル法の違い：• 第一層(特徴抽出機)も学習するのが深層学習• 第一層は固定するのがカーネル法→ この違いが学習法の“適応力”に影響 (後述)

Multiple Kernel Learning• データに合わせてカーネル関数も学習する方法• ILSVRCでは2011年までMKLが一位

37

38

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

カーネル法の表現力

39• Universal kernel
𝐶0 (ℝ𝑑 ) をℝ𝑑 上の連続関数𝑓で無限遠点で消える関数の集合とする:∀𝜖 > 0, {𝑥 ∣ 𝑓 𝑥 ≥ 𝜖}がコンパクト．
あるカーネルに対し，そのRKHSが𝐶0 (ℝ𝑑 )内で一様ノルムに関して稠密な時，そのカーネルは「𝑐0 -universal」であるという．
（∀𝑓 ∈ 𝐶 𝑋 , ∀𝜖 > 0, ∃𝑔 ∈ ℋ𝑘 , s.t. 𝑓 − 𝑔 ∞ < 𝜖）と, ある有界連続な𝜓を用いて書けるとき（平行移動不変）𝑘が正定値対称⇔𝑘が𝑐0 -univeral⇔

ある有限非負測度Λが存在して以下のように書ける(Bochner)

Λのサポートが全域: supp Λ = ℝ𝑑 .

ガウスカーネル，ラプラスカーネル，Maternカーネルなどはこれを満たす．
多項式カーネルはuniversalではない．
[Sriperumbudur, Fukumizu, Lanckriet: Universality, Characteristic Kernels and RKHS
Embedding of Measures, ICML2010]

40

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

汎化誤差
汎化誤差：損失の期待値

汎化ギャップ：

余剰誤差：

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

41通常の学習理論

42

バイアス

訓練誤差
(バイアス)

バリアンス

バリアンス

期待誤差＝バイアス+バリアンス(古典的)バイアス-バリアンスのトレードオフ
cf., AIC, BIC, MDL

過学習

43

現象を説明できる範囲でなるべく単純なモデルを当てはめるべき
悪い学習結果良い学習結果過学習している

過学習していない

説明力が高い（複雑）説明力が低い（単純）

適度にデータに当てはまるモデルが良い

44

過学習

訓練誤差
汎化誤差

汎化誤差と次元dの関係

深層学習の汎化誤差45• 深層学習の汎化誤差において，「Overparameterization」
は特に重要な問題である．
パラメータ数 ≫ サンプルサイズ[Zhang et al.: Understanding deep learning requires rethinking generalization. ICLR2017.][Neyshabur et al., ICLR2019]

訓練誤差が0になるくらいパラメータ数を増やしてもなお汎化誤差が減り続ける．

通常のVC次元を用いた解析では説明不能

Double-descent (二重降下)

46“新しい”バイアス-バリアンスのトレードオフ[Belkin el al., Reconciling modern machine learning practice and the bias-variance trade-of, arXiv:1812.11118]• モデルがある複雑度 (サンプルサイズ) を超えた後，第二の降下が起きる．
• モデルサイズがデータより多いと推定量のバリアンスがむしろ減る．
※設定によるので注意が必要．

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

47

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

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

バイアス

バリアンス

48

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

49

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

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

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

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

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

50

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

51

推定精度 (汎化誤差)

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

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

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

52

各種関数クラスのノルム• Barronクラス [Barron 1991, 1993](Fourier変換)(高い周波数成分は少ない)• Hölderクラス (𝒞 𝛽 )• Soblevクラス (𝑊𝑝𝑘 ) (kは自然数)

53近似誤差と推定誤差 (Hölder class)54•縦幅L，横幅w，非ゼロパラメータ数sの深層NNモデルの集合•ReLU活性化関数
深層NNの近似精度（Mhaskar, 1996; Yarotskey, 2016）
ある整数𝑁 ≫ 1に対し，
縦幅𝐿 = O(log(𝑁))，横幅𝑤 = O(𝑁)，非ゼロ要素𝑠 = O(𝑁log(𝑁))

深層学習の汎化誤差（Schmidt-Hieber, 2017）

縦幅𝐿 = O(log(𝑛))，横幅𝑤 = O(𝑛

𝑑
2𝛽+𝑑

−

log(𝑛))，非ゼロ要素𝑠 = O(𝑛

𝑑
2𝛽+𝑑

−

log(𝑛))

ミニマックス
最適レート

でバランス
バリアンス

バイアス

55

• Hölder空間ならカーネル法でも最適レートを達成できる．
• なぜ深層が良いか？

議論を一般化• 対象とする関数のクラスを一般化：
Hölder空間→Besov空間• 滑らかさが空間的に非一様• 有界変動関数を含む（不連続）

深層学習が線形推定量を優越

深層学習の高い適応力

56

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

57[Suzuki: Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces:
optimal rate and curse of dimensionality. ICLR2019]

機械学習では様々な形状をした複雑な関数が現れる

不連続点

急な変化

全体的に滑らか

難しい

易しい

急な変化に対応させようとすると必要以上にモデルが複雑に. → 過学習.
滑らかな部分を重視すると急な変化に対応できない. → 過小学習.

“適応的近似能力” が重要

Theorem𝑠
深層学習はBesov空間(𝐵𝑝,𝑞)の元を推定するのにミニマックス最適レートを達成する．

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

収束レートの比較

58

深層学習

線形推定量 (浅い学習)
e.g., カーネルリッジ回帰:

≫
非最適

最適

(𝑛: sample size，𝑝:uniformity of smoothness，𝑠：smoothness)
深層学習
線形推定量

一様な粒度
cf. Imaizumi&Fukumizu (2018)

荒い 細かい 荒い直感59

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

係数

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

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

Adaptive method(deep)

Hölder, Sobolev, Besov空間

60

空間的非一様性

0

滑らかさの度合い

61

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

空間の間の関係

62

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

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

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

64

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

スパースな係数→空間的な滑らかさの非一様性（非凸モデル）

深層学習のモデル

65

W
L

•
•
•
•

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

推定精度

66

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

ただし，(clipping)．

定理 (推定精度),

かつ

縦幅𝐿 = O(log(𝑛))，横幅𝑊 = O(𝑛とすることで，

のとき，
𝑑
2𝑠+𝑑

−

log(𝑛))，非ゼロ要素𝑆 = O(𝑛𝑝 = 𝑞 = ∞のとき，Schmidt-Hieber (2017) に帰着．

𝑑
2𝑠+𝑑

−

log(𝑛))

他手法との比較• 線形推定法

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

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

Why does this difference happen?

68

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

[Hayakawa&Suzuki: 2019][Donoho & Johnstone, 1994]その他の例69[Hayakawa&Suzuki: arXiv:1905.09195, 2019.]

𝐾個のジャンプしかない (スパース).
→ 凸包は有界変動関数のクラスを含む．

深層学習：

1
O
𝑛

例 (1)• Low dimensional feature extractor

70(Schmidt-Hieber, 2018)

Dim. reduction

g is a univariate smooth function.

w
Deep

Shallow (linear): suffers from curse of dim.

• Piece-wise smooth function (Imaizumi & Fukumizu, 2018)

where 𝑅𝑘 is a region with smooth boundary and ℎ𝑘 is a smooth function.
➢ Deep is better than a kernel method (linear estimator).

例 (2)

71• Reduced rank regression

where

and

．

Low rank: non-convex
Comparison of accuracy(LS, Ridge reg)

Convex hull of the low rank model is full-rank.

72

第３章
深層学習の最適化

勾配降下法
深層学習における最適化(確率的) 勾配降下法：

GD

SGD

73

問題点

74

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

臨界点

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

局所的最適解

大域的最適解

局所最適解や鞍点にはまる可能性あり

局所最適性
深層学習の目的関数は非凸

局所的最適解
大域的最適解• 深層NNの局所的最適解は全て大域的最適解：
Kawaguchi, 2016; Lu&Kawaguchi, 2017.
※ただし対象は線形NNのみ．

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

75

2層NN最適化の重要事項• Overparameterization➢Neural Tangent Kernel (NTK)➢Mean-field regime→ 横幅を広くとったNNは勾配法で大域的最適解を求めやすい．
• 勾配流 (Gradient flow)→ NNのパラメータの学習は「パラメータの分布」を学習していると解釈できる．
→ 確率測度の収束解析を援用(Langevin dynamics, Wasserstein gradient flow)76

Over-parametrization• 横幅が広いと局所最適解が大域的最適解になる．

横幅を十分広くとって(NTK regimeで)ランダム初期化
すれば，経験誤差0の解へ線形収束する．
[Du et al., 2018; Allen-Zhu, Li & Song, 2018; Li & Liang, 2018]

誤差 ≤ 𝐶′exp(−𝑐𝑇)• 横幅が十分広いと最適解の近くに初期値が来る．
• 目的関数が強凸的になる (PL-条件)．

77

二つのスケーリング

𝒂𝒋 を動かせば単なる線形モデルなので，𝒘𝒋 のみを動かす問題を考える (𝒂𝒋 は固定)．

• Neural Tangent Kernel regime (lazy learning )➢ 𝑎𝑗 = O(1/ 𝑀)(スケールが大きい)• Mean field regime➢ 𝑎𝑗 = Ο(1/𝑀)(スケールが小さい)

初期化のスケーリングによって，初期値に比した学習による変動分の割合が変わる．
→ 解析の難しさ，汎化性能に影響

78

Neural Tangent Kernel

79• 簡単のため連続時間で考える．
• 𝑎𝑗 は固定• 𝑤𝑗 を動かすモデル：[Jacot, Gabriel&Hongler, NIPS2018](勾配降下)(連鎖律)(関数勾配)𝑘𝑊 (𝑥, 𝑥𝑖 )Neural Tangent Kernel

目的関数値の減少

80

NTK regimeにおける最適化

81

以下の要領でランダム初期化:• 𝑎𝑗 ∼ (±1)

1𝑀(+, −は等確率で生成)• 𝑤𝑗 ∼ 𝑁(0, 𝐼)
要点：• 横幅Mが十分大きければ，高い確率でNTKのグラム行列は正定値であり，最適化の間に大きく変化しない．
• 結果として，大域的最適解に線形収束する．
定理
6𝑀 = Ο(𝑛 log(𝑛))で十分．

[Du et al., 2018; Allen-Zhu, Li & Song,2018; Li & Liang, 2018]※ 判別ならoverparameterizeしないでも良い (𝑀 = Ο(𝑛1/4 )で十分) :[Nitanda&Suzuki:arXiv:1905.09870]

NTKの様子82

初期値

モデルの集合• 非凸なモデルも局所的に線形近似（接空間）すれば，ほぼ線形モデル• 大きめのスケールを取っておけば，初期値の周りにおいて相対的に小さな変動で最適解に到達できる．
• 横幅を広くとればデータをすべて説明可能，大きなスケールを用いれば局所線形近似に最適解を含められる．

スケールが小さい場合

初期値

モデルの集合ここを大きめのスケールを用いて拡大したのがNTK

83

まとめ
• 深層学習の理論• 表現能力• 汎化能力• 最適化能力• 表現力• 万能近似性• 層を深くすることで指数的に表現力増大• 汎化能力• 様々な関数クラスでほぼ最適レート達成• 最適化理論• Overparameterizeされていれば大域的最適解を得る• Neural Tangent Kernel: 関数勾配の特徴づけ• Mean field regime: 分布の収束とMMD

84

85

補足

Mean field regime• ニューラルネットワークの最適化をパラメータの分布最適化としてみなす．

NTKはO(1/ 𝑀), MFではO(1/𝑀)(𝑎, 𝑤)に関する分布𝜈による平均とみなせる:

𝑓の最適化 ⇔ 𝜈の最適化

86

MMDとの関係

87

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

: MMD

ℋ𝑘

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

MF-regimeの研究動向

88• Wasserstein勾配流を用いた収束の解析：[Nitanda&Suzuki, 2017][Chizat and Bach, 2018][Sirignano an d
Spiliopoulos, 2018] [Rotskoff and Vanden-Eijnden, 2018]その他多数• SGLDを用いた最適解への収束解析 (McKean-Vlasov diffusion)：[Mei, Montanari, and Nguyen, 2018]（同グループからの後続研究多数）, [Rotskoff&Vanden-Eijnden, NeurIPS2018],(ある種の強凸性を仮定した線形収束)[Hu et al., arXiv1905.07769]• MMD最適化としての収束解析：[Arbel et al., 2019]• MCMCサンプリングおよび貪欲解法(Frank- Wolfe):[Barron, 1993][Bengio et al., 2006][Le Roux and Bengio, 2007][Bach,2017][Sonoda, 2019]
NTKと比べると難しい．
第一層の学習がより本質的に影響するので汎化性能は良いと考えられている．
（陰的正則化） [Ghorbani et al: Limitations of Lazy Training of Two-layers Neural
Networks, arXiv:1906.08899 ]

MMD

89

: あるRKHS (ℋ𝑘 ) への特徴写像: 二つの分布

分布を𝔼𝑃 [𝜙𝑘 (𝑋)]でRKHS内に埋め込み，そこで距離を測る．
定理ℝ𝑑 × ℝ𝑑 上のカーネル関数が連続かつ特性的 (後述)
⇔ MMDが弱収束位相を距離付けする．
[Simon-Gabriel&Scholkopf: Kernel Distribution Embeddings: Universal Kernels,
Characteristic Kernels and Kernel Metrics on Distributions, JMLR2018.]

特性的カーネル

90• 特性的カーネルがℝ𝑑 上ボレル確率測度に対して単射
つまり，MMD(P,P’)=0がP=P’と同値の時，そのカーネルを特性的と言う．
𝑀𝑏 (ℝ𝑑 ) をℝ𝑑 上の有限な符号付ボレル測度の集合とする．

カーネル関数kが𝑐0 -universal

⇔

が単射．

確率測度に限定したら必ずしも同値ではない．しかし，次が成り立つ．

カーネルkが平行移動不変で𝑘 𝑥, 𝑦 = 𝜙(𝑥 − 𝑦) (𝜙 ∈ 𝐶0 (ℝ𝑑 ))と書けるとき，「𝑐0 -universal」 ⇔ 「特性的」[Sriperumbudur, Fukumizu, Lanckriet: Universality, Characteristic Kernels and RKHS
Embedding of Measures, ICML2010]

MMDとその仲間

91• 積分型確率測度距離• f(x)としてf(x)=xのみを用いれば平均値の差を見ていることになる．
• f(x)として，f(x)=xおよびf(x)=x^2も考えれば二次モーメントの差も考慮できる．
• Fとしてもっと広い関数の集合を考えれば分布の“距離”になる．

• 1-Wasserstein距離=1-リプシッツ連続な関数の集合• MMD (Maximum Mean Discrepancy)=ある再生核ヒルベルト空間の単位球

Wasserstein距離について• 「輸送距離」とも言われる

周辺分布を固定した同時分布の中で最小化• 分布のサポートがずれていてもwell-defined• 底空間の距離が反映されている（双対表現）

92