When gradient is small...

Optimization Fails because...

• 參數對loss的微分等於0 (gradient=0)，因此參數不再更新，我們稱之為critical point。
• critical point 有兩種情況
  • local minima：局部loss的最小值。
  • saddle point：非local minima也不是local maxima，但gradient為0。
  • 處於local minima代表loss已經位於相對低點，但處於saddle point則代表我們的loss仍有很多優化空間。

How to find out we stuck at local minima or saddle point?

Tayler Series Approximation

• 直接講結論就是，我們無法知道 $L(θ)$ 確切的樣子，但我們可以透過 $L(θ')$ 大約算出來。 (公式如圖2)
• $L(θ')$ ：給$L(θ)$ 訂某一組參數，而$L(θ')$ 附近的參數是有辦法被寫出來的，就是Tayler Serise Approximation。
• 當g (gradient)等於0時，就只剩下公式右半邊的數值，我們就可以透過這個 $L(θ')$ 來畫出 error surface，藉此了解我們是處於local minima還是saddle point，這種方式稱之為Hessian。

圖2

圖3

Hessian

• 判斷
  • $[(θ-θ')^T * H(θ-θ')]/2$，縮寫成$v^THv$，
  • 對於任何 $v$ 而言，只要$v^T*Hv > 0$，那麼 $L(\theta) > L(\theta’)$，代表 $L(\theta’)$是附近最低點 (local minma)。
  • 若$L(\theta) < L(\theta’)$，那就是local maxima。
  • 有時大於0，有時小於0，那就是處於saddle point。
• 我們不可能帶入所有有可能的 $v$ ，透過線性代數理論有更簡單的方式去判斷。
  • local minima：$v^THv$，Hessian是positive definite的矩陣，這種矩陣的特性是所有eigen 跟 values都是正的，那麼 $v^THv > 0$ 就會成立。
  • local maxima：反之亦然。
  • saddle point：eigen 跟 values 有正有負。
• 結論
  • 我們會算出一個 $H$ 的矩陣叫做hessian，裡面會有eigen 跟 values，只需要去判斷它們是正或負，就可以知道目前的function處於哪一個critical point。

Example

圖片解釋

• 假設我們有個史上最爛的function， $y = w1w2x$，和史上最爛的training data，只有一筆data (input=1, label=1)。
• 當我們爆量蒐集各種 $w1 w2$，所畫出來的 error surface 就如下圖。