SGD and SGD with momentum

by allenlu2007

 

Gradient Descent (GD, aka steepest descent), Stochastic Gradient Descent (SGD), Newton method, etc.  都是 optimization 的算法。Optimization 問題就是 (1) define a cost function C(x); (2) find C(x) 的 minimum (or maximum).

我們可以有不同的分類: 

1st order optimization vs. 2nd order optimization

用一個 example, C(x) = a x^2  (a > 0)

GD, SGD, etc. 都是 1st order optimization algorithm.  主要是利用 1st order derivative (gradient) information 做 optimization.

Gradient descent 如下:

C'(x) = 2ax  =>  x(t+1) = x(t) – r * C'(x) = x(t) – r * (2ax(t)) = x(t) (1-2ar)    r 稱為 learning rate

只要 -1< 1-2ar < 1   or  -2 < -2ar < 0  =>  1/a > r > 0   x(t+1) 就可以 converge 到 minimum.

一般而言,r 愈小 (r~0) 愈容易 converge.  但 converging speed 很慢。r 變大 converge 會變快,特別當 r ~ 1/2a 時收歙非常快。但 r 再大收歙又變慢 (overshoot oscillation), 如果 r > 1/a,又變成不收歙。

因此如何選 r 是 GD 最大的問題。r(opt) = 1/2a

由上文 r 的選取 highly depending on a.   也就是 2nd order derivative (曲率)。

如果是一個二維的 cost function, C(x, y) = a (x+y)^2 + b (x-y)^2  而且 a >> b or a << b 代表很扁的斜橢圓。這時 GD 就會有問題。因為只是 x and y 方向的 optimization 會被最 max(a, b) 所限制住。必須讓 r 很小,因此收歙速度會很慢。

如果更高 dimension 會更容易出現 bottleneck.  

Newton method 則大幅改善這個問題。基本的觀念就是使用 2nd order derivative 再加上 1st order derivative (gradient + curvature).  就可以大幅增加收歙速度。據 Stephen Boyd 說,任何 convex optimization 問題,使用 Newton method 只需要 12 次 iteration 就收歙到非常非常精準。實務上大約用 5-7次就夠解決 90% 的 convex optimization 問題。如果 cost function 是 parabolic, 只需要 1 次 iteration 就 ok.

Newton method or 2nd order optimization 最大的問題就是無法處理 non-convex optimization.  要不然就是 stuck 在 local minimum/maximum.  要不然就是無法收歙 (oscillation).

對於 machine learning 的問題,大多數是 non-convex optimization (e.g. neural network).  因此 Newton method or other 2nd order optimization 大多無用武之地。

 

Deterministic vs. Stochastic

前面提到的 GD or Newton method, 都是 deterministic optimization.  一般單純 deterministic optimization 問題的 dimension 是固定且不大,可以用 GD or Newton method.  

但對一些很多 training samples (high dimension input) 但 low parameter dimension 的 optimization 問題。如下圖的 curve fitting (or linear regression) 問題。cost function 就是 mean square error function.   可以看出來 input sample (dimension) 可能很大 (e.g. > 100), 但 parameter space 只是 2 dimensions (a and b).  

可以有兩種方式來解 optimization 問題。一是 GD, 不過要等到所有 samples (>100, e.g.) 收到,再做 iteration.

另一種方式就是 sample-by-sample iteration.  就是從 one sample (or two samples) 先算 (a, b), 每多一個 sample 就 iterate (a, b) 一次。 這就是 stochastic gradient descent (SGD) 的觀念。

NewImage

當然這也有假設 input samples 是 stationary 且 random.   可以想像如果一開始的 samples 都是集中在某一區,算出來的 (a, b) 可能就會有很大的誤差。

下圖是 (a, b) 經過 iteration 的 trajectory.  Red trajectory 是 GD,  Pink trajectory 是 SGD.  

SGD 的好處是不用等所有的 samples 就開始 learning, 因此收歛速度可能一開始比較快。但最後似乎 jittering a lot.  因此另一種 algorithm 是 mini-batch GD.  故名思義就是介於 all samples iteration 和 one sample iteration 之間。

NewImage

下圖是 mini-batch GD 的收歙 trajectory.  

NewImage

SGD 另外一個很大的優點是可以 on-line learning.  如果有新的 training set 進來,可以 incremental 改善原來的 weight.  而不需要全部重新 train/learn.  例如 ImageNet 是從幾張 sample photos 成長到現在 1.5M 張,之後還會再增加。如果用 GD 很難每次更新都重算,實務上不可能。

 

綜上所述,machine learning 所需要的 optimizer 是 SGD

 1. First order optimization,  因為 machine learning 的 optimization 絕大多數是 non-convex, 存在很多的 local miin/max.  

2. Stochastic optimization 而非 deterministic optimization.  因為 training set 太多而且會變動。

SGD 最主要的問題就是收歙太慢。特別是扁斜橢圓的 error contour.  因此有再針對如何加速 1st order optimization 的改進算法。 另一個問題是如何選 r (learning rate)?

 

Momentum Base Gradient Descent

以下參考此文 : “On the momentum term in gradient descent learning algorithms” by Ning Qian Columbia.

Momentum 

 

1. GD 基本上如之前所述

NewImage

NewImage

 

2.  GD 加上 momentum term (Rumelhart et al. 1986)

以下這段話的意思是: 加上 p*dW(t-1) 的修正項是避免 error vector (dW) 在橢圓短軸方向 oscillation 而影響收歙的速度。但如何選取 p and epsilon?

NewImage 

 

上文是 hand-waving 的說法,Qian 給了一個力學的想法。

GD 在 dt 趨近 0 時,可以把 iteration 的過程變成力學問題如下:

NewImage

剛才說過 epsilon 如果太大會造成收歙的問題,所以 epsilon 要小。當然以 Eq(3) 來看,epsilon 不管大小都會收歙,收歙速度是 exponential decay.  這是因為假設 dt 趨近 0, 所以 (epsilon * dt) 還是無窮小。

我們想做的是如何在同樣的 epsilon 可以改善收歙速度,特別是在 epsilon 很小的 case. 

在力學的經驗中,eq(3) 就是粒子在 highly damped 的力學公式。如果還原為完整的牛頓力學公式如下:

NewImage

m 是質量,u 是磨擦系數 (u ~ 1/epsilon or epsilon ~ 1/u).   

所以 (3) 是 (4) 的 special case when u >> m.  

此時因為磨擦力太大,gradient 所提供的吸力無法讓粒子加速,只能慢慢的滑入最低點。

不論是圓坑,橢圓坑,扁橢圓坑都可以收歙。唯一的問題就是慢。如何加速收歙?

 

有兩個方法: (1) 之前談過讓 epsilon 變小 (或增加 learning rate), 不過會有收歙的問題。

(2) 增加 m (多一個參數) 讓 gradient 提供的吸力可以加速粒子。

不過直覺想如果 m 太大,也會造成粒子 circle around 而不收歙。因此 m 也需要在一個範圍內。

m=0 就回到 GD,  m > 0 但必須小於某個 value 才有更快的收歙。

 

其實 (4) 的 discrete time 公式就是 Eq (2).

NewImage

NewImage

NewImage

如果 p = 0 ==>  m = 0.   epsilon ~ 1/(u*dt)

因此 GD with a momentum term 相當於一個牛頓力學粒子在 viscous medium under a conservative force field.

 

Energy Function

再從能量的觀點來看。之前的 Energy function (or cost function) = E(w).

加入 momentum term 之後, total energy function (or cost function) 變為: 動能+位能

NewImage

加上動能項可以改變原來的 energy function (cost function) 的 profile.  例如之前很難收歙的扁橢圓在加入動能後可能就不是扁橢圓而加快收歙速度。另外有 m (m > 0) 之後也會改變每次 weight change (=velocity=dw/dt) 的方向。

當然最後 dw/dt = 0,   Et –>  E(w),  所以改變 cost function (energy function) 對最後的 optimization 並無影響 。但是可以改變收歙的速度。

如果 m 讓動能 >> 位能,那就像沒磨擦力的 case, 也要很久才收歙。反過來如果動能 << 位能,又回到磨擦力 dominant case.  所以最佳的情況似乎是讓(initial)動能 ~ 位能。最終當然動能=0, 位能-> min 位能。

 

Qian 的 paper 給了一個定量的解釋如下:

NewImage

假設 H (Hessian, symmetry and positive definite) 可以被分解成 H=QKQ’

NewImage

NewImage

Equation (18) 對應是 GD 的 exponential decay time constant (m=0).

GD with momentum (m <> 0) 則變成 2nd order differential equations.

NewImage

NewImage

以下是結果。如果選 m 滿足 eq(23) 可以加速 exponential decay rate. 

NewImage

 

可以快多少。下面 Result2 告訴我們 eigenvalue 可以最大變 X2.  當然 exponential decay rate X2 代表平方 (e.g.  原來的 GD error = 0.1,  GD with momentum error 最好可以 (0.1)^2 = 0.01. 

NewImage

 

Discrete Case

上節是用 continuous and 力學 analogy 來解釋 momentum GD. 

回到 real discrete case, 也可以得到收歙加速的效果。

NewImage

NewImage

和 continuous time 不同。discrete time 的 eigenvalue 愈小愈好,同時需要小於1.

NewImage

NewImage

 

NewImage

結論就是 0 < p < 1  以及  p < 1- sqrt(epsilon*ki).   同樣最小 ki 也是 bottleneck. 

NewImage

 

可以參考 Hinton 的 optimzation note

NewImage 

p = beta = 0.95

(1-beta) epsilon = 0.05*epsilon

看來 epsilon 一般會設的很小。 

 

————————————————————————– 

以上部份在另文討論。

SGD 有 noise average 好處? 

Conjugate Gradient Descent or Hamiltonian Dynamic GD

Conjugate GD –> Solve Energy Optimization problem –> Leverage Hamiltonian dynamic

 

SGD  Check Zaid’s talk in CVPR 2013 (but no momentum)

SGD with momentum

Hamiltonian dynamics 

MCMC 

 

The other thing is Energy function

Advertisements