Table of Contents
機器學習自學筆記04: Gradient Descent
今日的課程來自於: https://youtu.be/yKKNr-QKz2Q
參考筆記: https://github.com/Sakura-gh/ML-notes/blob/master/ML-notes-pdf/5_Gradient%20Descent.pdf
Tip 1 : Tuning your learning rates
gradient descent 過程中，影響结果的一個很關鍵的因素就是 learning rate的大小
- 如果learning rate剛剛好，就可以像下圖中紅色線段一樣順利地到達到loss的最小值
- 如果learning rate太小的话，像下圖中的藍色線段，雖然最後能夠走到local minimal的地方，但是它可能會走得非常慢，以至於你無法接受
- 如果learning rate太大，像下圖中的綠色線段，它的步伐太快了，它永遠没有辦法走到特别低的地方，可能永遠在這個“山谷”的口上震盪而無法走下去
- 如果learning rate非常大，就會像下圖中的黃色線段，一瞬間就飛出去了，结果會造成update参數以后，loss反而會越来越大(這一點在上次的demo中有體會到，當lr過大的時候，每次更新loss反而會變大)
當參數超過3個時，可以將loss function 隨著每個參數的變化視化出來。
可以將每次update 次數作為唯一的一個參數，將Loss 隨著update的增加而變化的趨勢給視化出來
把不同的 learning rate 下，loss每次 update 的變化線畫出來，這樣就可以提醒我們該如何調整learning rate 的大小，直到出現穩定的曲線。
Adaptive Learning rates
顯然每次都手動調整learning rate 很麻煩，因此我們需要有一些自動調整learning rate的方法
最基本、最簡單的大原則是: learning rate 通常是隨著參數的update 越來越小的
因為在起始點的時候，通常是離最低點是比較遠的，這時候步伐就要跨大一點；而經過幾次更新以後，會比較靠近目標，這時候就應該減小learning rate ，讓它能夠收斂在最低點的地方
舉例：假設到了第t次更新，此時 formula 01
這種方法使所有參數以同樣的方式同樣的learning rate 進行更新，而最好的狀況是每個參數都給他不同的learning rate去更新
Adagrad ( adaptive的其中一種方法)
Divide the learning rate of each parameter by the root mean square of its previous derivatives ( 每個參數的learning rate 都把他除上，之前算出來的微分值得 root mean square)
Adagrad就是將不同參數的learning rate分開考慮的一種算法(adagrad算法update到後面速度會越來越慢，當然這只是adaptive算法中最簡單的一種)
- 每個參數都分開討論
- w是function 的某個參數
- t 代表為第t次的update
- g^t 為Loss對w偏微分的值
- σ^t 過去所有微分值得root mean square
Adagrad 他的參數update 其實整體而言是越來越慢的(因為她有加上time depend)
Adagrad 的 contradiction 解釋
Adagrad 的表達式裡面有一件很矛盾的事情:
我們在做gradient descent 的時候，希望的是當梯度值及微分值 g^t 越大的時候(此時斜率越大，還沒有接近最低點)更新的步伐要更大一些，但是Adagrad 的表達式中，分母表示梯度越大步伐越大，分子卻表示梯度越大步伐越小，兩者似乎相互矛盾。
在一些paper 是這樣解釋的: Adagrad 要考慮的是，這個gradient 的反差有多大，假設t=4時，g⁴ 與前面的gradient 反差特別大，那麼g^t 與 下面那像的反差就會比較大，他們的商會將反差的效果體現出來。
造成反差效果，就是gradient 。
gradient 越大，離最低點越遠。在多個參數的情況下是不一定成立的。
做 gradient descent 時，參數update取決於兩件事:
1. Learning rate 2. Gradient
Tip 2 : Stochastic Gradient Descent
隨機梯度下降的方法可以讓訓練更快速(看一個example 就update 一個參數)。
只考慮一個example 對這個example 的 y 的估計值再減掉他正確答案，再平方，不summation 所有的example 。
Loss function 只考慮一個example。
Gradient Descent vs Stochastic Gradient Descent
- 傳統的gradient descent 的思路是看完所有的樣本點之後再設立loss function ，然後去update 參數 。
- stochastic gradient descent 的作法是，看到一個樣本點就update一次，因此他的Loss function 不適所有樣本點的error平方和，而是這個隨機樣本點的error平方。
Stochastic Gradient Descent 與傳統的Gradient Descent 的效果對比如下:
Tip 3 : Feature Scaling (特徵縮放)
特徵縮放，當多個特徵的分布範圍很不一樣時，最好將這些不同的feature的範圍縮放成一樣
可以看到上圖的公式，假設X1 的值都很小，但是X2的時都很大。此時去化Loss 的error surface ，如果對w1和w2 都做一個同樣的變動Δw ，那麼w1的變化對y的影響是比較小的，而w2的變化對y的影響是比較大。
左邊的error surface表示，w1對y的影響比較小，所以w1對loss是有比較小的偏微分的，因此在w1的方向上圖像是比較平滑的； w2對y的影響比較大，所以w2對loss的影響比較大，因此在w2的方向上圖像是比較sharp的
如果x1和x2的值，它們的比例是接近的，那麼w1和w2對loss就會有差不多的影響力，loss的圖像接近於圓形，那由此對gradient descent有什麼好處呢？
對gradient decent的幫助
之前我們做的demo已經表明了，對於這種長橢圓形的錯誤表面，如果不使用Adagrad之類的方法，是很難搞定它的，因為在像w1和w2這樣不同的參數方向上，會需要不同的learning rate ，用相同的lr很難達到最低點。
如果有scale的話，loss在參數w1，w2平面上的投影就是一個正圓形，更新參數會比較容易
而且gradient descent的每次更新並不都是向著最低點走的，每次update的方向是順著等高線的方向（梯度 gradient 下降的方向），而不是徑直走向最低點；但是當經過對input的scale使損耗的投影是一個正圓的話，不管在這個區域的哪一個點，它都會向著圓心走。因此功能縮放對參數更新的效率是有幫助的。
如何做feature scaling
假設有R 個example (上標 i 表示第 i 個樣本點) ， x¹ ，x² ， x³….. x^r ….. x ^R ，每一筆example 它裡面都有一組feature (下標 j 表示該樣本點的第j個特徵)
對每一個demension i ,都去算出他的平均值以及標準差
對第r個 example 的第 i 個 component ，減掉均值，除以標準差
事實上就是將每一個參數都歸一化成標準常態分布。
Gradient descent 的理論基礎
Taylor Series :
Let h(x) be any function infinitely differentiable around x=x0
從泰勒展開式推導出gradient descent
對於loss 圖像上的某一個點 (a,b) ，如果我們想要找這個點附近loss最小的點，就可以用泰勒展開式思考
假設用一個 red circle 設定點的範圍，這個圓足夠小以滿足泰勒展開的精度，那麼此時我們的loss function 就可以化簡為 :
觀察圖形可知，當向量(θ1-a ,θ2-b) 與向量(u,v)反向 ，且剛好達到red circle 的邊緣時 ( 用 η 去控制向量的長度) ，L(θ) 最小
這就是gradient descent在數學上的推導，注意它的重要前提是，給定的那個紅色圈圈的範圍要足夠小，這樣泰勒展開給我們的近似才會更精確，而η的值是與圓的半徑成正比的，因此理論上learning rate要無窮小才能夠保證每次gradient descent在update參數之後的loss會越來越小，於是當learning
rate沒有設置好，泰勒近似不成立，就有可能使gradient descent過程中的loss沒有越來越小
當然泰勒展開可以使用二階、三階乃至更高階的展開，但這樣會使得運算量大大增加，反而降低了運行效率
Gradient descent 的限制
之前已經討論過，gradient descent有一個問題是它會停在local minima的地方就停止update了
事實上還有一個問題是，微分值是0的地方並不是只有local minima，settle point的微分值也是0
以上都是理論上的探討，到了實踐的時候，其實當gradient的值接近於0的時候，我們就已經把它停下
來了，但是微分值很小，不見得就是很接近local minima，也有可能像下圖一樣在一個高原的地方
總和以上，gradient descent的限制是，它在gradient即微分值接近於0的地方就會停下來，而這個地方不一定是global minima，它可能是local minima，可能是saddle point鞍點，甚至可能是一個loss很高的plateau平緩高原
