梯度下降演演算法實現原理(Gradient Descent)

概述

  梯度下降法(Gradient Descent)是一個演演算法，但不是像多元線性迴歸那樣是一個具體做迴歸任務的演演算法，而是一個非常通用的優化演演算法來幫助一些機器學習演演算法求解出最優解的，所謂的通用就是很多機器學習演演算法都是用它，甚至深度學習也是用它來求解最優解。所有優化演演算法的目的都是期望以最快的速度把模型引數θ求解出來，梯度下降法就是一種經典常用的優化演演算法。

梯度下降法的思想

  思想就類比於生活中的一些事情，比如你去詢問你的一個朋友工資多少，他不會告訴你，但是他會讓你去猜，然後告訴你猜的結果。你每說出一次答案，他就會說猜高了或是猜低了，這樣下去你就會奔著對方的回答繼續猜下去，總有一次能猜到正確答案。梯度下降法就是這樣，你得去試很多次，而且我們在試的過程中還得想辦法知道是不是在猜對的路上，說白了就是得到正確的反饋再調整。
  一般你玩兒這樣的遊戲的時候，一開始第一下都是隨機瞎猜一個對吧，那對於計算機來說是不是就是隨機取值，也就是說你有θ =W1...Wn，這裡θ強調一下不是一個值，而是一個向量就是一組 W，一開始的時候我們通過隨機把每個值都給它隨機出來。有了θ我們可以去根據演演算法就是公式去計算出來^y ，比如 y^ = Xθ ，然後根據計算^y 和真實y之間的損失，比如 MSE，然後調整θ再去計算MSE。
  這個調整正如咱們前面說的肯定不是瞎調整，當然這個調整的方式很多，你可以整體θ每個值調大一點，也可以整體θ每個值調小一點，也可以一部分調大一部分調小。第一次θ 0我們可以得到第一次的 MSE 就是 Loss0，調整後第二次θ1對應可以得到第二次的 MSE 就是 Loss1，如果 loss 變小是不是調對了，就應該繼續調，如果loss反而變大是不是調反了，就應該反過來調。直到 MSE 我們找到最小值時計算出來的θ^ 就是我們的最優解。這個就好比下山過程，我們把 loss 看出是曲線就是山谷，如果走過來就再往回撥，所以是一個迭代的過程。

梯度下降法公式

  這裡梯度下降法的公式就是一個式子指導計算機迭代過程中如何去調整θ，不需要推導和證明，就是總結出來的。
公式: W_j^t+1 = W_j^t - η × gradient_j
  這裡的 W_j就是θ中的某一個 j=0…n，這裡的η就是圖裡的 learningstep，很多時候也叫學習率 learning rate，很多時候也用α表示，這個學習率我們可以看作是下山邁的步子的大小，步子邁的大下山就快。

  學習率一般都是正數，那麼在山左側梯度是負的，那麼這個負號就會把 W 往大了調，如果在山右側梯度就是正的，那麼負號就會把 W 往小了調。每次 W_j 調整的幅度就是η*gradient，就是橫軸上移動的距離。
  如果特徵或維度越多，那麼這個公式用的次數就越多，也就是每次迭代要應用的這個式子 n+1 次，所以其實上面的圖不是特別準，因為θ對應的是很多維度，應每一個維度都可以畫一個這樣的圖，或者是一個多維空間的圖。
W₀^t+1 =W₀^t - h×g₀
W₁^t+1 =W₁^t - h × g₁
Wjt+1 =Wjt - h × g_j
W_n^t+1 =W_n^t - h × g_n

所以觀察圖我們可以發現不是某一個θ₀ 或θ₁找到最小值就是最優解，而是它們一起找到 J 最小的時候才是最優解。

學習率設定的學問

公式: W_j^t+1 = W_j^t - η × gradient_j
  根據我們上面講的梯度下降法公式，我們知道η是學習率，設定大的學習率 Wj 每次調整的幅度就大，設定小的學習率 Wj 每次調整的幅度就小，然而如果步子邁的太大也會有問題其實，可能一下子邁到山另一頭去了，然後一步又邁回來了，使得來來回回震盪。步子太小呢就一步步往前挪，也會使得整體迭代次數增加。

  學習率的設定是門學問，一般我們會把它設定成一個比較小的正整數，0.1、0.01、0.001、0.0001，都是常見的設定數值，一般情況下學習率在整體迭代過程中是一直不變的數，但是也可以設定成隨著迭代次數增多學習率逐漸變小，因為越靠近山谷我們就可以步子邁小點，省得走過，還有一些深度學習的優化演演算法會自己控制調整學習率這個值。

全域性最優解

  上圖可以看出如果損失函數是非凸函數，梯度下降法是有可能落到區域性最小值的，所以其實步長不能設定的太小太穩健，那樣就很容易落入區域性最優解，雖說區域性最小也沒大問題，因為模型只要是堪用的就好嘛，但是我們肯定還是儘量要奔著全域性最優解去。

梯度下降法流程：

1. 隨機θ，隨機一組數值W₀...W_n
2. 求梯度，為什麼是梯度？因為梯度代表曲線某點上的切線的斜率，沿著切線往下下降就相當於沿著坡度最陡峭的方向下降
3. if g<0, θ 變大，if g>0, θ 變小
4. 判斷是否收斂 convergence，如果收斂跳出迭代，如果沒有達到收斂，回第 2 步繼續
   
   Question?
   1.. 如何隨機？
   2..怎麼求梯度？
   3..如何調整θ或W?
   4..怎麼判斷收斂？
   Answer
   1..np.random.rand()或者 np.random.randn()
   2..gradient_j = \(\frac{∂Loss}{W_j}\)
   3..W_i^t+1 = W_i^t - h × gradient_i
   4..判斷收斂這裡使用 g=0 其實並不合理，因為當損失函數是非凸函數的話 g=0 有可能是極大值對嗎！所以其實我們判斷 loss 的下降收益更合理，當隨著迭代 loss 減小的幅度即收益不再變化就可以認為停止在最低點，收斂！
     總結，講解完梯度下降法流程同學們會發現這裡仍然第 2 步不是很清楚怎麼去做，但是其它步驟其實都已經清楚比如用程式設計如何去做對吧，下面就來講第 2 步該怎麼去進一步推匯出來表示式。

損失函數的導函數

求解上面梯度下降的第 2 步，即我們要推匯出損失函數的導函數來。
θ = θ - α · \(\frac{∂J(θ)}{∂θ}\)
  下面公式推導 J(θ)是損失函數，q j 是某個特徵維度 Xj 對應的權值係數，也可以寫成 Wj。這裡我們還是在接著之前的多元線性迴歸往下講，所以損失函數是 MSE，所以下面公式表達的是因為我們的 MSE 中 X、y 是已知的，θ是未知的，而θ不是一個變數而是一堆變數，所以我們只能對含有一推變數的函數 MSE 中的一個變數求導，即偏導，下面就是對θj 求偏導。

  \(x^2\) 的導數就是 2x，根據鏈式求導法則，我們可以推出第一步。然後是多元線性迴歸，所以 h_θ(x) 就是 w^Tx 也是w₀·x₀+w₁·x₁+...+w_n·x_n亦是\(\sum_{n=0}^n{w_ix_i}\)，到這裡我們是對θ_j 來求偏導，那麼和 W_j 沒有關係的可以忽略不計，所以只剩下 X_j。
  我們可以得到結論就是θ_j 對應的 gradient 與預測值^y 和真實值 y 有關，這裡^y 和 y 是列向量，同時還與θ_j 對應的特徵維度 X_j 有關，這裡 X_j 是原始資料集矩陣的第 j 列。如果我們分別去對每個維度 W₀...W_n 求偏導，即可得到所有維度對應的梯度值。
g₀ = (h_θ(x) - y)·X₀
g₁ = (h_θ(x) - y)·X₁
g_j = (h_θ(x) - y)·X_j
g_n = (h_θ(x) - y)·X_n

總結：

θ_j^t+1 = θ_j^t - η · g_j = θ_j^t - η · (h_θ(x) - y) · x_j

三種梯度下降法

三種梯度下降區別和優缺點

區別：其實三種梯度下降的區別僅在於第 2 步求梯度所用到的 X 資料集的樣本數量不同！它們每次學習(更新模型引數)使用的樣本個數，每次更新使用不同的樣本會導致每次學習的準確性和學習時間不同。

全量梯度下降

Batch Gradient Descent
θ_j^t+1 = θ_j^t - η · \(\sum_{i=1}^m{(h_θ(x^i) - y^i)} · x^i_j\)
  在梯度下降中，對於θ的更新，所有的樣本都有貢獻，也就是參與調整θ。其計算得到的是一個標準梯度。因而理論上來說一次更新的幅度是比較大的。如果樣本不多的情況下，當然是這樣收斂的速度會更快啦。全量梯度下降每次學習都使用整個訓練集，因此其優點在於每次更新都會朝著正確的方向進行，最後能夠保證收斂於極值點(凸函數收斂於全域性極值點，非凸函數可能會收斂於區域性極值點)，但是其缺點在於每次學習時間過長，並且如果訓練集很大以至於需要消耗大量的記憶體，並且全量梯度下降不能進行線上模型引數更新。

隨機梯度下降

Stochastic Gradient Descent
θ_j^t+1 = θ_j^t - η · (h_θ(x⁽ⁱ⁾) - y⁽ⁱ⁾) · x_j⁽ⁱ⁾
  梯度下降演演算法每次從訓練集中隨機選擇一個樣本來進行學習。批次梯度下降演演算法每次都會使用全部訓練樣本，因此這些計算是冗餘的，因為每次都使用完全相同的樣本集。而隨機梯度下降演演算法每次只隨機選擇一個樣本來更新模型引數，因此每次的學習是非常快速的，並且可以進行線上更新。隨機梯度下降最大的缺點在於每次更新可能並不會按照正確的方向進行，因此可以帶來優化波動(擾動)。
  不過從另一個方面來看，隨機梯度下降所帶來的波動有個好處就是，對於類似盆地區域（即很多區域性極小值點）那麼這個波動的特點可能會使得優化的方向從當前的區域性極小值點跳到另一個更好的區域性極小值點，這樣便可能對於非凸函數，最終收斂於一個較好的區域性極值點，甚至全域性極值點。由於波動，因此會使得迭代次數（學習次數）增多，即收斂速度變慢。不過最終其會和全量梯度下降演演算法一樣，具有相同的收斂性，即凸函數收斂於全域性極值點，非凸損失函數收斂於區域性極值點。

小批次梯度下降

Mini-Batch Gradient Descent
θ_j^t+1 = θ_j^t - η · \(\sum_{i=1}^b{(h_θ(x^i) - y^i)} · x^i_j\)
注：b = batch_size
  Mini-batch 梯度下降綜合了 batch 梯度下降與 stochastic 梯度下降，在每次更新速度與更新次數中間取得一個平衡，其每次更新從訓練集中隨機選擇 batch_size，batch_size< m 個樣本進行學習。相對於隨機梯度下降演演算法，小批次梯度下降演演算法降低了收斂波動性，即降低了引數更新的方差，使得更新更加穩定。相對於全量梯度下降，其提高了每次學習的速度。並且其不用擔心記憶體瓶頸從而可以利用矩陣運算進行高效計算。一般而言每次更新隨機選擇[50,256]個樣本進行學習，但是也要根據具體問題而選擇，實踐中可以進行多次試驗，選擇一個更新速度與更次次數都較適合的樣本數。

梯度下降法的問題與挑戰

  雖然梯度下降演演算法效果很好，並且廣泛使用，但是不管用上面三種哪一種，都存在一些挑戰與問題需要解決：

1. 選擇一個合理的學習速率很難。如果學習速率過小，則會導致收斂速度很慢。如果學習速率過大，那麼其會阻礙收斂，即在極值點附近會振盪。
   
2. 學習速率調整(又稱學習速率排程，Learning rate schedules 試圖在每次更新過程中，改變學習速率，如退火。一般使用某種事先設定的策略或者在每次迭代中衰減一個較小的閾值。無論哪種調整方法，都需要事先進行固定設定，這邊便無法自適應每次學習的資料集特點。
   
3. 模型所有的引數每次更新都是使用相同的學習速率。如果資料特徵是稀疏的或者每個特徵有著不同的取值統計特徵與空間，那麼便不能在每次更新中每個引數使用相同的學習速率，那些很少出現的特徵應該使用一個相對較大的學習速率。
   
4. 對於非凸目標函數，容易陷入那些次優的區域性極值點中，如在神經網路中。那麼如何避免呢。Dauphin 指出更嚴重的問題不是區域性極值點，而是鞍點(These saddle points are usually surrounded by a plateau of the same error, which makes it notoriously hard for SGD to escape, as the gradient is close to zero in all dimensions.)
   

輪次和批次

輪次：epoch，輪次顧名思義是把我們已有的訓練集資料學習多少輪
批次：batch，批次這裡指的的我們已有的訓練集資料比較多的時候，一輪要學習太多資料，那就把一輪次要學習的資料分成多個批次，一批一批資料的學習。
  舉個例子，這就好比有一本唐詩 300 首需要大家背誦，如果要給你一週時間要你背誦完，或許你很聰明可以背完，但是估計也不敢說一下子全都記得特別牢，甚至到可以出口成章的地步吧。那通常人是怎麼做的呢？是不是就是接下來多花幾周，重複之前一週的動作，把 300 首唐詩多背幾次，比如花 10 周把 300 首唐詩全部倒背如流了，然後又花了 10 周時間把 300 首唐詩又背誦到了滾瓜爛熟的地步終於可以出口成唐詩了。那麼剛提到的 10 周、又 10 周放在 AI 領域那麼就是所謂的訓練了10個輪次又 10 個輪次，總共 20 個輪次。
  再回顧上面一段話，我們假設你很聰明，也就是 AI 訓練的電腦效能處理能力非常好，如果是普通人或者一般的電腦，很有可能一週都不可能背誦完 300 首，也就是記憶體一下子裝不下那麼大的資料量，或者處理器計算能力沒有那麼快。當資料量大的情況下，這是很常見的現在，那麼為了可以順利背下來 300 首唐詩到舉一反三出口成章的地方，也就是為了訓練出來 model 模型，我們只能把一個輪次需要的資料分成多個批次來一點點計算，放到背唐詩的例子中，說白了就是一週背不下來 300 首唐詩，那麼我們就一週背 50 首唐詩吧比如說，這樣我們就需要 6 個批次把一輪資料背完，一個批次所需要的資料batch_size 就是50。
  還有就是對於三種梯度下降來說，全量梯度下降就是每一輪次用到全量的資料，然後一次迭代就是一個輪次，然後用全量資料計算梯度來更新一下 W。隨機梯度下降每一個輪次也需要計算所有資料，但是有多少資料就會分為多少個批次，即是一個批次一次迭代，就只用一條資料計算梯度來更新一下 W，所以隨機梯度下降一個輪次中的更新 W 的次數等於樣本總數。最後就是 mini-batch 梯度下降，每一個輪次也需要計算所有資料，但是輪次分成多 少 個 批 次 取 決 於 batch_size ， batch_size 大 需 要 的 輪 次 就 少 ， 比 如batch_size=num_samples，那就等價於全量批次梯度下降，batch_size=1 那就等價於隨機梯度下降。

程式碼實戰梯度下降法與優化

全量梯度下降

建立資料集 X、y

np.random.seed(1)
X = 2 * np.random.rand(100, 1)
y = 4 + 3 * X + np.random.randn(100, 1)
X_b = np.c_[np.ones((100, 1)), X

learning_rate = 0.001
n_iterations = 1000

theta = np.random.randn(2, 1)

# 4，不會設定閾值，直接設定超引數，迭代次數，迭代次數到了，我們就認為收斂了
for _ in range(n_iterations):
  # 2，接著求梯度 gradient
  gradients = X_b.T.dot(X_b.dot(theta)-y)
  # 3，應用公式調整 theta 值，theta_t + 1 = theta_t - grad * learning_rate
  theta = theta - learning_rate *

隨機梯度下降

建立資料集 X、y

X = 2 * np.random.rand(100, 1)
y = 4 + 3 * X + np.random.randn(100, 1)
X_b = np.c_[np.ones((100, 1)), X]

n_epochs = 10000
m = 100
learning_rate = 0.001

theta = np.random.randn(2, 1)

for epoch in range(n_epochs):
  for i in range(m):
    # 2, 求 gradient Xi.T * (Xi * theta - yi)
    random_index = np.random.randint(m)
    xi = X_b[random_index:random_index+1]
    yi = y[random_index:random_index+1]
    gradients = xi.T.dot(xi.dot(theta)-yi)
    # 3, 調整 theta
    theta = theta - learning_rate *

小批次梯度下降

建立資料集 X、y

X = 2 * np.random.rand(100, 1)
y = 4 + 3 * X + np.random.randn(100, 1)
X_b = np.c_[np.ones((100, 1)), X]

learning_rate = 0.001
n_epochs = 10000
m = 100
batch_size = 10
num_batches = int(m/batch_size)

theta = np.random.randn(2, 1)

for epoch in range(n_epochs):
  for i in range(num_batches):
    # 2, 求 gradient Xi.T * (Xi * theta - yi)
    random_index = np.random.randint(m)
    x_batch = X_b[random_index:random_index+batch_size]
    y_batch = y[random_index:random_index+batch_size]
    gradients = x_batch.T.dot(x_batch.dot(theta)-y_batch)
    # 3, 調整 theta
    theta = theta - learning_rate * gradient

至此，就基本介紹完了梯度下降法的基本思想和演演算法流程