【Python機器學習】106：使用梯度遞減尋找最佳解的相關演算法
Algorithms for finding the best solution using Gradient Descent
接下來要介紹另外一種在機器學習、深度學習中更為廣泛使用的演算方法稱為「梯度遞減」
關於梯度遞減(Gradient Descent)
我們目前已經會使用兩種方法在給定 h=Xw的前提之下，尋找最佳的w：
- sklearn.linear_model 的 LinearRegression() 或 Ridge()
直接呼叫Predictor，fit training data之後就可以把截距項和係數項回傳，就能得到我們的w
- 自行撰寫正規方程(normal equations)，包含無正規化效果以及有正規化效果的
除了前述這兩種方法以外，還有第三種方法稱為梯度遞減(Gradient Descent)，同樣能夠在給定 ℎ=𝑋𝑤 的前提之下，尋找最佳的 𝑤
什麼是梯度遞減(Gradient Descent)？
梯度遞減(Gradient Descent)是一種透過「迭代」實踐最佳化的演算法。利用一組隨機賦予的 𝑤 作為起始，計算該點每個 𝑤𝑖 對成本函數偏微分的斜率，並依照偏微分斜率的正負值與學習速率，決定目前的 𝑤 應該減少或者增加多少。
在適當的學習速率設定下，經過足夠次數的迭代後可以得到一組逼近成本函數最小的係數組合 𝑤
讓我們先將 ℎ 簡化為只有1個特徵x1，而這個特徵對應到的係數自然就是𝑤1：
給定一組x1與y：
假設我們看不出來 𝑤1是3：
由於現在我們不知道 𝑤1是多少，所以嘗試在 1 到 5 之間窮舉了 100 個 𝑤1，將每個 𝑤1都帶入成本函數 MSE 中計算，接著就會得到100個 MSE：
在我們窮舉的 100 個 𝑤1 之中第 49 個 𝑤1 能夠讓 MSE 最低，其值為2.97979797979798 :
如上圖，我們計算得到的w_1，確實和我們一開始肉眼觀察的3很接近。如果我們想要輸值再更精確一點，可以試著窮舉10000個w_1。
但是這個窮舉的做法是對的嗎？？
這個做法其實有非常大的問題，到底是誰跟你說可以在1到5之間窮舉的？這次不過是運氣好在一個有包含 𝑤1=3 的區間窮舉而已，假如在其他區間窮舉 100 個 𝑤1，像是 5 到 9：
在我們窮舉的 100 個 𝑤1 之中，我還是可以找到一個最低MSE的點：第 0 個 𝑤1 能夠讓 MSE 最低，但這顯然並不是理想中的 𝑤1=3
梯度遞減的演算法就是為了因應這樣窮舉式、大海撈針式的找 𝑤1 方法
我要用什麼判斷的準則來看我現在離我的目標又更遠了還是更進一步了？假設一開始的w1是隨機給定的，那我要怎麼知道到底是要往左邊去找窮舉還是往右邊去找窮舉呢？有個很簡單的概念就是看梯度（斜率）來決定他要往左還右。比如說現在最佳解是三角形，如果我位於菱形位置的梯度（斜率）是正的，所以我就要往左邊移動。一樣的道理，如果我在圈圈的位置，梯度（斜率）是負的，那我就知道接下來我要往右邊窮舉。那這樣就是有意識的窮舉，而不是像無頭蒼蠅隨便亂找w1。
何謂有意識地、在窮舉的 𝑤1 中向正確的方向修正？
第三種找出 𝑤 的方法：梯度遞減（Gradient Descent）指的就是從隨機指定的 𝑤1 起始透過迭代、有意識地朝 𝑤1*(最佳解)修正、更新：
有意識地向正確方向修正特定幅度:
𝑤1 修正的速度與 𝛼 相關，𝛼 稱為學習速率（Learning Rate）。如何挑選學習速率?
如果學習速率夠小，成本函數每一次都會下降
學習速率太小，收斂的速度太慢
學習速率太大，可能會無法收斂
推導對 𝑤1 偏微分的成本函數（梯度）:
先前在算正規方程式時，公式為微分後=0直接求 𝑤1*出來。但是梯度遞減(Gradient Descent)是從隨機指定的 𝑤1 起始透過迭代、有意識地朝 𝑤1* 修正、更新:
公式看完了，但是要怎麼實作梯度遞減呢？給定一組 𝑥1 與 𝑦，我們試著根據梯度遞減（Gradient Descent）的演算法，利用 1000 次的迭代、𝛼=0.0001 找出 𝑤1：
w_1的初始值是用numpy的random函數隨機產生的，上圖例子中w_1是從0.72868開始移動，經過一次更新後w_1為1.95147。我們知道w_1的正確解答為3，而w_1也確實在慢慢地往右靠近3。
將迭代過程的成本(MSE)記錄起來並作圖，把成本函數(MSE)紀錄起來時必備的步驟，因為我們事後可能要修正學習速率(learning rate):
如果看到MSE在不斷的往下降，說明w1在往正確解答前進。我們可以透過上左圖中去判斷是否要調整學習速率的大小或是迭代的次數。因此學習速率的大小以及迭代的次數都是事後去檢查MSE再作決定的。
由於在一開始的時候w1會被賦予一個隨機值（在我們的例子中是位於[0.0，1.0)中的隨機數），因此目前所用的演算法又被稱為隨機梯度遞減(Stochastic Gradient Descent,簡稱為 SGD)
接著讓我們將 𝑤0 加回先前簡化只有 𝑤1 的 ℎ 之中：
給定 𝑥0、𝑥1 與 𝑦:
假設我們看不出來 𝑤0=5、𝑤1=6，透過先前的經驗，我們知道可以利用梯度遞減求 𝑤0 與 𝑤1：
推導對 𝑤0 與 𝑤1 偏微分的成本函數（梯度）：
梯度遞減（Gradient Descent）：從隨機指定的 (𝑤0,𝑤1)起始透過迭代、有意識地朝 (𝑤0*,𝑤1*)修正、更新：
試著給定 𝑥0、𝑥1 與 𝑦，根據新增 w0 的梯度遞減（Gradient Descent）的演算法，利用 200000 次的迭代、𝛼=0.0001 找出 (𝑤0,𝑤1)：
將迭代過程的成本（MSE）記錄起來並作圖：
最後我們將 ℎ 還原為泛化的外觀：
透過先前的經驗，我們知道可以利用梯度遞減求 𝑤：
利用梯度遞減求 𝑤，寫成泛化的外觀：
推導對 𝑤𝑖 偏微分的成本函數（梯度）：
梯度遞減（Gradient Descent）：從隨機指定的 (𝑤)起始透過迭代、有意識地朝 (𝑤∗) 修正、更新：
給定 𝑥0、𝑥1 與 𝑦，根據泛化的梯度遞減（Gradient Descent）演算法，找出 𝑤：
將迭代過程的成本（MSE）記錄起來並作圖:
泛化的公式搞懂了之後，我們終於可以離開無聊的x0和x1了，接著我們試著在NBA球員資料集上應用梯度遞減求w。我們把球員的得分、籃板、助攻當成 X 的特徵去訓練模型來預測薪資。用 LinearRegression()函數來求w：
如果我們的學習速率設0.01跑模型了話，會發現第0次迭代的時候還有資訊，但是跑到後面就顯示nan呢？原因是學習速率的值太大了，導致w不管跑幾次都沒辦法收斂，因此只要把學習速率的值調低一點就可以了：
已經有了正規方程可以得到精確的 𝑤∗， 為什麼還需要梯度遞減？
原因是因為使用正規方程(Normal equations）求解，在變數個數增多的時候會遭遇計算複雜性的議題。
感謝你閱讀完這篇文章，如果你覺得這些文章對你有幫助請在底下幫我拍個手（長按最多可以拍50下手）。
