ICML 2018 Tutorial學習筆記

09-10

4 人贊了文章

近期和實驗室的 @佶佶國王一起準備整理一下ICML 2018的tutorial----Toward Theoretical Understanding of Deep Learning. 希望可以從中看出一些發展趨勢，指導科研思路。由於實驗室一部分研究方向集中在優化方面，所以從優化角度來整理這篇tutorial。歡迎大家指出錯誤:)

Part 1: Optimization in deep learning

優化在深度學習中的主要困難主要是非凸的困難，很難利用凸優化的方式去求解最優點，要從中搜索出最優點將會在某種情況下面臨NP-hard的問題。

如果 $abla f(x) eq 0$ 那麼就會存在使得函數值下降的方向（局部地：負梯度方向）

在優化中我們把尋找最優值的目標轉化為三步的目標：

找到臨界點（梯度為 0 ）

找到局部最優點（梯度為0，hessen矩陣半正定）

找到全局最優點

對於初始值的假設：

所有的初始值的收斂性

隨機的初始值的收斂性

選定的初始值的收斂性

目標：在特徵空間維數為 d 的時候，希望運行在 $poly(d,1/epsilon)$ （多項式時間， $epsilon$ 為精確度）

但是維度帶來的是NP-hard的搜索難度（數學上，在 $R^d$ 中，存在 $exp(d)$ 數量級的方向，使得每個方向之間的夾角大於60度）。

深度學習中的分析是一個黑箱，因為我們很難去知道深度學習所構建的函數的幾何特徵（有一些統計上的工作，但是不是那麼成功），並且沒有一個乾淨的數學表達來表示 $x_i, y_i (input, output)$ ，那麼去找到全局最優值基本上是不可能的。

有句話叫，物理上能量守恆，數學上難度守恆，既然繞不開NP-hard的問題，我們只能退而求其次，尋找一個局部的解，使得它足夠好，所以大家把關注放在了非凸問題的局部最優值上。

梯度下降

$heta_{t+1} = heta_t - eta abla f( heta_t)$

如果hessen矩陣過大，意味著梯度的變化很快，所以向負梯度方向走一個步長，不一定能保證函數值下降，為了保證迭代後函數值下降，我們需要一個足夠小的步長，這個步長依賴於連續性（Lipschitz-ness）的要求：

$abla^2 f( heta) le eta I$

我們取步長 $eta = 1/2eta$ ，可以得到：

$Delta f = f( heta_t) - f( heta_{t+1}) geq - abla f ( heta_t)( heta_{t+1} - heta_t) - frac{1}{2} eta | heta_t - heta_{t+1}| = frac{1}{2eta}| abla_t|^2$

實際上這個步長是對函數的二次上界取最小值（quadratic upper bound），二次上界的下降量可以bound住函數的下降量。

這樣可以使得函數值每次下降 $epsilon ^2 /2eta$ ，就保證我們通過迭代可以得到一個接近0的梯度。

但梯度下降只完成了尋找臨界點的目標，並不能判斷局部最優或全局最優，要達到局部最優，還需要考慮避開鞍點。

如何避開鞍點（Saddle points）

在上面我們介紹了達到臨界值的方式，但這個臨界值可以是局部最優或者是鞍點，[Ge,Huang, Jin, Yuan15 ] 提出在梯度上增加雜訊（perturbed GD），使得可以逃離從幾何上不那麼穩定的鞍點，數學上可以證明在多項式 $poly(d/epsilon)$ 時間內，加入雜訊的梯度演算法可以逃離所有的鞍點[Jin et al17]，並且可以使得hessen矩陣接近半正定：

$| abla f| le epsilon, abla ^2 f geq -sqrt{epsilon} I$

（perturbed GD with large noise）這樣我們可以在得到臨界點的基礎上避開鞍點得到局部最優點。

實際上一般情況下不推薦使用perturbed GD，SGD能夠達到同樣的效果（避開鞍點）。

二階優化演算法

在凸優化中，二階演算法充分利用了函數的二階性質，使得收斂的速度比一節演算法快，二階演算法中最著名的是牛頓法：

$x_{t+1} = x_t - eta [ abla^2 f(x)]^{-1} abla f(x)$

[Pearlmutter』94]提出對於任意的向量 $v$ ，計算 $( abla ^2 f) v$ 只需要線性時間。

在高維的情況下，計算hessen矩陣的逆，會消耗很大的計算量，[Agarwal et al』17, Carmon et al』17] 提出用近似的方法估計矩陣的逆：

$( abla ^2)^{-1} = sumlimits_{i=0 ightarrow infty} (I - abla)^i$

在實際操作中往往使用有限階擬合。

二階方法雖然可以更快的達到收斂，但依然沒有能力找到更好的局部最優值。

去黑箱的分析

由於深度學習的理論體系不是很完善，但是在效果上卻擊敗了很大一部分傳統的機器學習演算法，所以大家對於深度學習的內部原因一直以來都有很大的興趣。

很多機器學習的問題實際上是一種二層網路的深度學習問題：

經常對網路結構和數據分布等有假設

使用除了隨機梯度以外演算法(eg, tensor decomposition, alternating minimization, convex optimization …)

Example：Matrix completion，假設我們有 $n imes n$ 的rank為 $r$ 矩陣 $M$ ，其中有一些缺失元素：

$M = U cdot V^T$

目標是恢復這些缺失元素，這個問題可以當作2層神經網路來學習。

來自於tutorial的例子：

Topic modeling [A., Ge, Moitra』12] [A. et al』13] Sparse coding [A., Ge, Ma, Moitra』14, 『15] [Anandkumar et al』14] Phase retrieval [Candes et al』15] Matrix completion [Many papers, eg Jain et al.』13] Matrix sensing Learning Noisy Or nets [A., Ge, Ma』17]

深度學習中的局部最優點

一些統計上的理論提出很多局部最優基本上和全局最優一樣好，能夠找到一個有效的局部最優點已經足以滿足應用上的需求，使用SGD在深度網路訓練出來的模型能夠擁有足夠好的效果。

多層網路的理論

現存的理論大部分是針對線性的網路的（激活函數 $f(x) = x$ ) ([Baldi, Hornik』88], [Saxe et al 『13] (dynamics of training) [Kawaguchi』16] [Hardt and Ma』16] (landscape of linear resnets); [A., Cohen, Hazan』18]))，但是線性網路依然還是一個線性變換，無法捕捉數據中的非線性關係。打開深度學習的黑箱，依然是一個巨大的挑戰。