深層学習に関わる驚異の発見：Neural Tangent Kernel

自分用メモ

1. over-parameterisation 幅無限
    - NTK regime
    - mean field regime 
2. 勾配流 (gradient flow)
    - 

#over-parameterisation
幅を十分広くとってランダム初期化すれば経験誤差0の解へ線形収束する[[Du, 2018](https://arxiv.org/abs/1811.03804)],[[Allen-Zhu, 2018](https://arxiv.org/abs/1811.03962)],[[Li, 2018](https://arxiv.org/abs/1808.01204)]

- 初期値のごく近傍に最適解が存在
- 目的関数が凸"的"


---
- 宝くじ仮説

#ガウス過程

GY「幅の広いランダムなNNは$\mathcal{GP}$という意味は異なる２つの画像を同じNNに食わせると（異なるランダム初期化により）ガウス分布を吐き出す」
![mlpasgp_.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/196262/ad3715a8-7dc6-7994-13a6-60e70618c3da.png)



- ニューラルネット(NN)の重みは例えばXavier初期化ならば$W^{(l)}_{ij} \sim \mathcal{N}(0,\frac{1}{p})$で初期化される. $p$は(一段前の)層のユニット数である. 初期値の分散が$\frac{1}{\sqrt{p}}$でスケールされている. これは入力信号が膨らんでいってしまうことを防ぐ. 

- ガウス過程はガウス分布に従う確率変数の一般化
> ガウス過程とは長さ$N$の平均ベクトルと$N \times N$の$C_{ij} = C(X_i,X_j)$の共分散行列をパラメータとした多変量正規分布

```math
\begin{pmatrix}
f(X_1) \\
f(X_2) \\
\vdots \\
f(X_N)
\end{pmatrix} \sim \mathcal{N}(\mu(X_1,X_2,\cdots,X_N),C(X_1,X_2,\cdots,X_N))
```

- 3層の(単一の隠れ層)の全結合NN(入力$\boldsymbol{x}\in\mathbb{R}^{N}$ から出力$y\in\mathbb{R}$への写像$f: \mathbb{R}^N \to \mathbb{R}$) について隠れ層の活性化関数を$\phi$として$y=\sum V^k\phi\left(\sum W^{kj}X^j\right)$で定義できる. 初期状態のとき, $V$と$W$の要素は独立なガウス分布に従い, $V$の分散は$\frac{1}{\sqrt{p}}$でスケールしている ($p$は隠れ層のユニット数). 
    - 隠れ層のニューロン$h^k$は各入力$X_i$に対して値を持つ $h^k(X_i)=\phi(\sum W^{kj}X_i^j)$. 
    - $W$ はランダムなので各ユニット$k$に対して, $h^k(\vec{X})$は独立なランダムベクトル ($\vec{X} = (X_1,\dots,X_N)$)になる. これらのランダムベクトルは同じ分布に従い, ネットワークの出力$\vec{y}=f(\vec{X})$は単にこれら単変量ガウス分布の$V^k$とi.i.d.の積の和になっている. (多次元の)中心極限定理より, この和は多変量ガウス分布になる. 

- 単一の隠れ層でユニット数$p$が無限の(全結合でガウス分布に従う重みとバイアス項をもつ)ニューラルネット(初期状態)がガウス過程$\mathcal{GP}$で表現できる．[[Neal, 1994](https://www.cs.toronto.edu/~radford/ftp/pin.pdf)]
「ランダム(ガウス)初期値から(多次元の)中心極限定理でカーネルを構成する」
    - MLP [[Lee, 2017](https://arxiv.org/abs/1711.00165)]
    - CNN [[Novak, 2018](https://arxiv.org/abs/1810.05148)]
        - フィルター数を無限に飛ばしている. 
    - だいたい全部のNN [[Yang, 2019](https://arxiv.org/abs/1902.04760)]

「最終層だけ学習し, ほかの層はランダム初期値のままにすることに対応」

#Neural Tangent Kernel (NTK) : 接神経核理論

- 損失関数

```math
\mathcal{L}(f_t(\mathcal{X})) = \frac{1}{2}\ell^2
```

```math
\ell := f_t(\mathcal{X}) - y
```

を減らすようにパラメータを学習していく (勾配降下). 

- パラメータの時間変化

```math
\begin{align}
\frac{\partial \boldsymbol{\theta}}{\partial t} &= -\eta\frac{\partial\mathcal{L}}{\partial \boldsymbol{\theta}} \\ 
&= -\eta\frac{\partial f_t(\mathcal{X})}{\partial \boldsymbol{\theta}}^{\mathsf{T}}\frac{\partial \mathcal{L}}{\partial f_t(\mathcal{X})} \\
&=\eta\nabla_{\boldsymbol{\theta}_t}f_{t}(\mathcal{X})^{\mathsf{T}}\nabla_{f_{t} (\mathcal{X})}\mathcal{L}
\end{align}
```


- 関数勾配

```math
\begin{align}
\frac{\partial \ell}{\partial t} = \frac{\partial f_t(\mathcal{X})}{\partial t} &= \frac{\partial f}{\partial \boldsymbol{\theta}_t}\frac{\mathrm{d}\boldsymbol{\theta}_t}{\mathrm{d}t} = - \eta\color{red}{\boxed{\nabla_{\boldsymbol{\theta}_t}f_{t}(\mathcal{X})\nabla_{\boldsymbol{\theta}_t}f_{t}(\mathcal{X})^{\mathsf{T}}}}\nabla_{f_{t}}\mathcal{L}
\end{align}
```


- **Neural Tangent Kernel (NTK)**

```math
\nabla_{\boldsymbol{\theta}_t}f_{t}(\mathcal{X})\nabla_{\boldsymbol{\theta}_t}f_{t}(\mathcal{X})^{\mathsf{T}}
```

- lossの一般解

```math
|\ell| = \exp (- t\Theta)
```

- 

メモ


```math
\begin{align}
\frac{\partial \mathscr{L}[f^{\boldsymbol{\theta}}]}{\partial t}
&= \sum_{i,j} \frac{\mathrm{d}\theta_j}{\mathrm{d}t}\int_{\mathcal{X}} \frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}}(x)_i \frac{\partial f^{\boldsymbol{\theta}}}{\partial \theta_j} (x)_i \mathrm{d}x \\
&=-\sum_{i,j,k}\int_{\mathcal{X}} \frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}}(x^{\prime})_k \frac{\partial f^{\boldsymbol{\theta}}}{\partial \theta_i}(x^{\prime})_k \mathrm{d}x^{\prime}\int_{\mathcal{X}}\frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}}(x)_j\frac{\partial f^{\boldsymbol{\theta}}}{\partial \theta_i}(x)_j \mathrm{d}x \\
&=  - \sum_{j,k = 1}^{N}\int_{\mathcal{X}} \frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}}(x)_j\left(\sum_{i=1}^{P}\frac{\partial f^{\boldsymbol{\theta}}}{\partial \theta_i}(x)_j\frac{\partial f^{\boldsymbol{\theta}}}{\partial \theta_i}(x^{\prime})_k\right)\frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}}(x^{\prime})\mathrm{d}x\mathrm{d}x^{\prime} \\
&= -\int_{\mathcal{X}} \frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}}(x)^{\mathsf{T}} \Theta(x,x^{\prime})\frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}} (x^{\prime})\mathrm{d}x\mathrm{d}x^{\prime} \\
&= -\left\|\frac{\delta \mathscr{L}}{\delta f^{\boldsymbol{\theta}}}\right\|^2 \Theta(x,x^{\prime})
\end{align}
```

```math
\Theta = \sum_{i=1}^{P}\frac{\partial f^{\boldsymbol{\theta}}}{\partial \theta_i} \otimes\frac{\partial f^{\boldsymbol{\theta}}}{\partial \theta_i}
```


>**定理** $n_1,\dots, n_{L-1} \to \infty$ のとき,  $t\in [0,T]$に対して, NTKは確率収束して, $\Theta_t \to \Theta_0$

- 


1次元の入出力でユニット数(=層の幅)が$p$の隠れ層（中間層）が2層のMLP. 

![neural_network.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/196262/4e5c7696-b115-0271-9f20-16acd980d8e4.png)


$$
f=(\boldsymbol{x},\boldsymbol{\theta})
$$

##後続研究(&関連研究)
- 
- 網羅的実験 [[Lee, 2019](https://arxiv.org/abs/1902.06720)]
- CNNでNTK成立 [[Arora, 2019](https://arxiv.org/abs/1904.11955)]
- RNNとか他のNNモデルでNTK成立 [[Yang, 2019](https://arxiv.org/abs/1902.04760)]