グラム行列とover-parameterization - ややプログラム紀行

今の所卒論ではover-parameterization周りの事をできたらいいな〜と思ってて(理論系書ける気がしないけど)、ちまちまその話題の論文を読んでるのでブログに自分用メモを書いておく*1

over-parameterizationというのはニューラルネットワークにおいてニューロンの数をめちゃくちゃデカくする事を指し、over-parameterized networkは色々興味深い現象が起こって不思議なのでそれを研究しようって分野がここ数年熱くなってきてる*2

まとめ

[1810.02054] Gradient Descent Provably Optimizes Over-parameterized Neural Networks

グラム行列の最小固有値を用いて2層over-parameterized NNの出力の収束レートの上限を求めた

[1901.08584] Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks

上の論文の結果を利用する事で収束レートの推移をより正確に求めた

さらにパラメータがあまり変化しない事を利用して汎化誤差の上限を求めた

Gradient Descent Provably Optimizes Over-parameterized Neural Networks

状況として2層NN、つまり $f(\mathbf{W}, \mathbf{a}, \mathbf{x}) = \frac{1}{\sqrt{m}} \sum_{r=1}^m a_r \sigma(\mathbf{w}_r^\mathrm{T} \mathbf{x})$ を考える(ここで $\mathbf{x} \in \mathbb{R}^d$ は入力、 $\mathbf{w}_r \in \mathbb{R}^d, a_r \in \mathbb{R}$ は各ニューロン $r$ のパラメータ、 $\sigma( \cdot )$ はReLU)

このNNを損失関数として二乗誤差を用いた最急降下法で学習させるとき、この論文曰く「データが互いに平行でなく*3 ニューロン数 $m$ が十分大きければ、最急降下法は訓練誤差0に1次収束する」

証明は最急降下法の式である $\mathbf{W}(k+1) = \mathbf{W}(k) - \eta \frac{\partial L(\mathbf{W}(k), a)}{\partial \mathbf{W}(k)}$ を微分方程式として捉えてみると比較的綺麗な式に書き直すことができて、(おそらくそれをヒントに)改めて離散版の式を帰納的に示すという流れ

もう少し具体的に見てみる

まず以下ではパラメータを $\mathbf{w}_r \sim N(\mathbf{0}, \mathbf{1}), a_r \sim \mathrm{unif}[\{-1, 1\}]$ で初期化し、 $\mathbf{W}$ の更新のみを考える( $\mathbf{a}$ の更新も少し修正すればできるらしい)

パラメータ更新のステップをどんどん細かくしていくことでグラディエントフローを考えることができ、微分方程式は次のようになる \begin{align} \frac{d\mathbf{w}_r(t)}{dt} = -\frac{\partial L(\mathbf{W}(t), \mathbf{a})}{\partial \mathbf{w}_r(t)} \end{align}

この時、 $u_i (t) := f(\mathbf{W}(t), \mathbf{a}, \mathbf{x}_i ), \mathbf{H}_{ij}(t) := \frac{1}{m}\mathbf{x}_i^\mathrm{T} \mathbf{x}_j \sum_{r=1}^m 1_{\{ \mathbf{x}_i^\mathrm{T}\mathbf{w}_r(t) \geq 0, \mathbf{x}_j^\mathrm{T} \mathbf{w}_r(t) \geq 0 \} }$ と定義すると、 $\frac{d}{dt}\mathbf{u}(t) = \mathbf{H}(t) (\mathbf{y} - \mathbf{u}(t))$ と書けることが証明できる(まずこれがすごい)

いきなり出てきた行列 $\mathbf{H}$ ってなんじゃって話だけど、これは $\frac{\partial f(\mathbf{W}(t), \mathbf{a}, \mathbf{x}_i)}{\partial \mathbf{w}_r(t)}$ のグラム行列になってて、まぁ割と自然に導出される

ところでこのグラム行列は何もこの論文が初出ではなくて、たとえば

[1810.02054] Gradient Descent Provably Optimizes Over-parameterized Neural Networks

でカーネルの球面調和関数展開のスペクトルとの関係みたいなのが書いてあるんだけど、自分はまださっと読んだだけ*4

あとこちらも参照されてた

[1711.09090] Invariance of Weight Distributions in Rectified MLPs

話を戻すと、当然 $\mathbf{H}(t)$ は時間に依存しているからこの微分方程式はそう簡単に解けない、、、と思いきや、実はニューロン数 $m$ が十分大きい時、学習中に $\mathbf{H}(t)$ はあまり変化しないことがわかる(これがこの論文のキモ)

もう少しちゃんと言うと、まず $\mathbf{H}^\infty \in \mathbb{R}^{n \times n}$ を \begin{align} \mathbf{H}_{ij}^\infty := \mathbb{E}_{\mathbf{w} \sim N(\mathbf{0}, \mathbf{1})} [ \mathbf{x}_i^\mathrm{T} \mathbf{x}_j 1_{\{ \mathbf{w}^\mathrm{T}\mathbf{x}_i \geq 0, \mathbf{w}^\mathrm{T}\mathbf{x}_j \geq 0 \} } ] \end{align} と定義すると、データが平行であれば $\mathbf{H}^\infty$ の最小固有値 $\lambda_0$ は正となり、さらに $m$ が十分大きければ初期化時の $H(0)$ が $H^\infty$ と十分近くなり、 $H(0)$ の最小固有値も正となる*5

さらに、学習途中のパラメータ $\mathbf{w}_r$ に対して $\| \mathbf{w}_r(0) - \mathbf{w}_r \|_2$ が十分小さければ、その時のグラム行列 $\mathbf{H}$ について $\| \mathbf{H} - \mathbf{H}(0) \|_2$ が十分小さくなり、 $\mathbf{H}$ の最小固有値も正となるので、その範疇では \begin{align} \frac{d}{dt} \| \mathbf{y} - \mathbf{u}(t) \|_2^2 = -2(\mathbf{y}-\mathbf{u}(t))^\mathrm{T} \mathbf{H}(t) (\mathbf{y} - \mathbf{u}(t)) \leq -\lambda_0 \|\mathbf{y} - \mathbf{u}(t) \|_2^2 \end{align} \begin{align} \therefore \quad \|\mathbf{y} - \mathbf{u}(t)\|_2^2 \leq \mathrm{exp}(-\lambda_0 t) \|\mathbf{y} - \mathbf{u}(0)\|_2^2 \end{align} となることがわかる*6

幸いなことに、over-parameterizationの力によってパラメータがこの範疇にいるまま学習を終えることができるのでめでたしめでたし

離散的な場合は以上の考察をもとに帰納法とゴリゴリの計算によって導出される(それも十分すごいんだけど*7 )

さらに著者曰く、今回の方法は多層の場合も同様に計算できると予想できるらしい(詳細はconclusion and discussionに書いてある)

Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks

over-parameterization系の論文に必ず引用されてるZhangさんの有名な論文

[1611.03530] Understanding deep learning requires rethinking generalization

では、実際のラベルをランダムラベルに置き換えても訓練誤差0になった！！！みたいなことが書かれてる(実はまだちゃんと読んでない)けど、それに関する2つの疑問、

(i) なぜ実際のラベルでの学習はランダムラベルでの学習より早く訓練誤差が0に収束するのか？
(ii) 実際のラベルとランダムラベルとの差別化ができる、容易に測れる複雑度は存在するのか？

について、この論文では先の論文の結果を洗練することで答えている

状況設定はさっきとほぼ同じ

先ほどの論文で最終的に得られる離散的な収束レートの不等式っていうのは \begin{align} \| \mathbf{u}(k) - \mathbf{y} \|_2^2 \leq \left( 1 - \frac{ η \lambda_0 }{ 2 } \right) \| \mathbf{u}(0) - \mathbf{y} \|_2^2 \end{align} で、これは損失関数 $\Phi(\mathbf{W}) := \frac{1}{2} \sum_{i=1}^n (y_i - f_{\mathbf{W}, \mathbf{a}}(\mathbf{x}_i))^2$ とおけば $\Phi(\mathbf{W}(k+1)) \leq \left(1 - \frac{η\lambda_0}{2} \right) \Phi(\mathbf{W}(k))$ と書ける

これは上限を抑える不等式で、収束率だとかの話にはこれでも十分だったけど、前回の連続版での議論をもう少し精査すると、 $m$ が十分大きいとき $\{ \mathbf{u}(k) \}_{k=0}^\infty$ はもう一つの数列 $\{ \tilde{\mathbf{u}}(k) \}_{k=0}^\infty$ の挙動に極めて近いことが判明する

ここで $\{ \tilde{\mathbf{u}}(k) \}_{k=0}^\infty$ とは、 \begin{align} \tilde{\mathbf{u}}(0) = \mathbf{0},\ \tilde{\mathbf{u}}(k+1) = \tilde{\mathbf{u}}(k) - η\mathbf{H}^\infty (\tilde{\mathbf{u}}(k) - \mathbf{y}) \end{align} という式によって更新されていく数列で、よく見ると先の論文の微分方程式によく似てる

以上より $\tilde{\mathbf{u}}(k)$ の方を調べればよく、これは $\mathbf{H}^\infty = \sum_{i=1}^n \lambda_i \mathbf{v}_i \mathbf{v}_i^\mathrm{T}$ と固有値分解すれば \begin{align} (\mathbf{1} - η\mathbf{H}^\infty)^k = \sum_{i=1}^n (1 - η\lambda_i)^k \mathbf{v}_i \mathbf{v}_i^\mathrm{T},\quad \mathbf{y} = \sum_{i=1}^n (\mathbf{v}_i^\mathrm{T} \mathbf{y})\mathbf{v}_i \end{align} であることから $\| \tilde{\mathbf{u}}(k) - \mathbf{y}\|_2^2 = \sum_{i=1}^n (1 - η\lambda_i)^{2k} (\mathbf{v}_i^\mathrm{T} \mathbf{y})^2$ と書き下せることがわかる

$\| \tilde{\mathbf{u}}(k) - \mathbf{y}\|_2^2$ の収束スピードを考えてみると、これは総和の各項の収束スピードと考えればあとは $(1 - η\lambda_i)^2$ の大きさによってその速度が決まり、疑問(i)への答えとして「ラベル $\mathbf{y}$ が $\mathbf{H}^\infty$ の最大固有値のベクトルに沿っているほど(すなわち大きな固有値 $\lambda_i$ に対する $(\mathbf{v}_i^\mathrm{T} \mathbf{y})^2$ が大きいほど)最急降下法は早く収束すると推察できる

以上の考察で $\Phi(\mathbf{W}) \approx \frac{1}{2} \|(\mathbf{1} - η\mathbf{H}^\infty)^k \mathbf{y}\|_2^2$ ということがわかったけれど、この結果を使って(ある程度)もう1つの結果にも答えることができる

こちらは気持ち的にはストレートなんだけどかなり数式をごちゃごちゃやってて、やはり底力的なのがホシィってなる

気持ちだけ書くと、先の論文で触れていたようにover-parameterized networkでは学習中 $\| \mathbf{w}_r (k) - \mathbf{w}_r(0)\|_2$ が小さい値のままな訳だけど、 $\Phi(\mathbf{W})$ の挙動がある程度わかったことで、さらに $\| \mathbf{W}(k) - \mathbf{W}(0)\|_F$ がおおよそ $\sqrt{\mathbf{y}^\mathrm{T} (\mathbf{H}^\infty)^{-1} \mathbf{y} }$ 以下であることも証明できる

よってパラメータが初期値から近いまま訓練誤差0を達成できることがわかり、これはつまりGDによって学習されるNNはパラメータの値が制限された関数クラスに属することを意味するので、この関数クラスのRademacher complexityを気合いで計算することで標本誤差をおよそ $\sqrt{\frac{2\mathbf{y}^\mathrm{T} (\mathbf{H}^\infty)^{-1} \mathbf{y}}{n} }$ で抑えることができる

この右辺がこの論文なりの疑問(ii)への答えであり、データから直接計算可能でNNのサイズとも独立しているというのがメリットらしい

over-parameterization系の論文は自分が読んでる限りだいたい同じような結論にたどり着いてて*8、結局自分なりの解釈では「パラメータを激増させるとパラメータ空間が豊かになって初期位置から十分近いところに望ましい(訓練誤差0を達成できる)パラメータが存在し、初期位置からゴールまで比較的ストレートに進んでくため結果出来上がるNNもシンプルなものになり標本誤差が減る」という感じ

後半の「初期位置からゴールまで云々」ってところはなんとなく前から想像してたけどこの論文を読んで本当にそうだったんだと感動すると共に、思ってたことを式にするにはこんなに労力がかかるのかと愕然とした

特にRademacher Complexityあたりの話はまだ全然知らないから、早く勉強しなきゃ

この2つの論文は見た感じ両者とも2層特有の何かを使ってる訳でもなく、いつかは多層に一般化できるんだろうなぁって感じがする

ただこの結果を多層版over-parameterizationに適用するのは既に多くの人が作業に取り掛かってるだろうし、同時に労力の割に得られる新規性が少ない気もするから到底自分が取り組めることじゃなさそう

個人的にこの論文の結果はかなり綺麗だと思うんだけど、綺麗すぎて少し疑いたくなってしまう

というのも、2つ目の論文で $\Phi(\mathbf{W})$ がこれこれで近似できるって話があるけど、何となくこれは線形の世界になってるだけでは？？という感じがする

実際、1つ目の論文のOpen Reviewを見てみると似たようなこと言ってる人がいた(このOpen Review普通にタメになる)

Gradient Descent Provably Optimizes Over-parameterized Neural Networks | OpenReview

もともと1つ目の論文は(おそらく)over-parameterized NNは学習中パラメータのパターン(つまりReLUで0になるか否か)が殆ど変化しないことが基礎になってると思うんだけど、この変化しないって性質と線形っぽいことがなんか関係あるのかなぁー(コナミ

ちなみにパターンが変化しない云々の話は1つ目の論文の"comparison with previous results"曰くこの論文由来らしい

[1808.01204] Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data

あとこういうパラメータ更新を連続化したグラディエントフローを解析する系の論文に対して、導出結果で要求される学習率がありえん小さくなって、現実的には不可能なのでは？？！みたいな気持ちもある

ただ、こういう論文の強いところとして、事実over-parameterized NNがうまく動いてるわけだから懸念するだけ無駄かもしれない(意志薄弱

卒論で何を書けばいいのかまだ全く思い浮かばないけど、正直この論文の結果が綺麗すぎて、もしこれがマジならもうやることないのでは？？みたいな気持ちになってしまった(もちろんそんなことはないと思うけど

2つ目の論文のAroraさんは深層線形ネットワークには陰的正則化の力があるみたいな論文も書いてて、こんな感じで今回と違って横幅じゃなく深さ方向にover-parameterizationした場合に何が起こるかみたいなのはまだ余り研究されてないかもしれない

それかover-parameterized NNが十分初期値の近傍にいることを利用して何かできるかもしれない、例えばcatastrophic forgettingがどうなるかみたいなのは少し気になってる

最後に、今まで論文の文字列上でばかりNNに触れてきたからover-parameterizationは完全無欠だと勝手に思ってたけど、これは良くないとtensorflowでちょっと実験してみたら普通に学習失敗して洗礼を受けた気分になった

*1:マジで自分用まとめだからこの記事だけ読んでもよくわからないと思う

*2:というより常に発展は望まれてるけどようやく少し進展が見えたって感じなのかな？モチベーション的にはかなり王道を往くものだと思う

*3:実数倍で等しくならないという事

*4:状況設定の条件が割と強めで、かつ割と数学ゴリゴリやってるから後回しにしてるけど、内容的にいつか読んでおかないとダメそう😇

*5:どうやら $\mathbf{H}^\infty$ の無限は、ニューロン数を無限にした時に $\mathbf{H}(t) \to \mathbf{H}^\infty$ となる事を表してる...?

*6:論文では"This lemma clearly demonstrates the power of over-parameterization"と言ってる

*7:と言うか、今の自分にはそういう馬力のようなものが足りてない気がする

*8:本当に最近盛り上がってきた分野だから、これが今の全力なんだろうか