機器學習：用梯度下降法實現線性回歸

02-26

之前在機器學習演算法數學基礎之 —— 線性代數篇中，總結過求解線性回歸的兩種方法：

最小二乘法
梯度下降法

這篇文章重點總結一下梯度下降法中的一些細節和需要注意的地方。

梯度下降法是什麼

假設有一個估計函數： $h_{0}(x)= heta^{T}X$ ，

其代價函數（cost function）為： $J( heta)=frac{1}{2}sum_{i=1}^{m}{(h_{ heta}(x^{(i)})-y^{(i)})^{2}}$

這個代價函數是 x(i) 的估計值與真實值 y(i) 的差的平方和，前面乘上 1/2，是因為在求導的時候，這個係數就不見了。

梯度下降法的流程：

1）首先對 θ 賦值，這個值可以是隨機的，也可以讓 θ 是一個全零的向量。
2）改變 θ 的值，使得 J(θ) 的值按梯度下降的方向減小。

參數 θ 與誤差函數 J(θ) 的關係圖

紅色部分表示 J(θ) 有著比較高的取值，我們希望能夠讓 J(θ) 的值儘可能的低，也就是取到深藍色的部分。θ0、θ1 表示 θ 向量的兩個維度。上面提到梯度下降法的第一步，是給 θ 一個初值，假設隨機的初值位於圖上紅色部分的十字點。然後我們將 θ 按梯度下降的方向進行調整，就會使 J(θ) 往更低的方向進行變化，如圖所示，演算法的結束將在 θ 下降到無法繼續下降為止。

θ 的更新： $heta_{i}= heta_{i}-alphafrac{partial}{partial heta}J( heta)$

θi 表示更新前的值，減號後邊的部分表示按梯度方向減少的量，α 表示步長，也就是每次按梯度減少的方向變化多少。

梯度是有方向的，對於一個向量 θ，每一維分量 θi 都可以求出一個梯度的方向，我們就可以找到一個整體的方向，在變化的時候，我們就朝著下降最多的方向進行變化，就可以達到一個最小點，不管它是局部的還是全局的。

所以梯度下降法的原理簡單來說就是：

在變數空間的某個點，函數沿梯度方向的變化率最大，所以在優化目標函數的時候，沿著負梯度方向減小函數值，可以最快達到優化目標。

特徵縮放（Feature Scaling）

在 Stanford 的 Machine Learning 課程中，老師提到了使用梯度下降法時可能用到的特徵縮放法，為的是當所要研究的數據集中出現數據值範圍相差較大的 feature 時，保證所有 feature 有相近範圍內的值。

以課程中的房價問題為例，數據集的 feature 中有房屋尺寸 $x_{1}$ 和房間數量 $x_{2}$ 兩項，房屋尺寸的範圍是 0~2000 feet^2，房間數量的範圍是 1~5。此時以兩個參數 $heta_{1}$ 和 $heta_{2}$ 為橫縱坐標，繪製代價函數 $J( heta)$ 的等高線圖如下：

代價函數的等高線圖

解決方法是對兩個 feature 進行歸一化處理：

x1 = size / 2000
x2 = number of rooms / 5

進行特徵縮放後，代價函數的等高線圖就變成了這樣：

特徵縮放後的代價函數等高線圖

很明顯，歸一化處理前，代價函數的等高線圖高又窄，在梯度下降過程中，需要反覆迭代很多次，才能達到理想的位置，會花費較長的時間。歸一化處理後，兩個 feature 的數值大小處於相近的範圍內，因此橫縱坐標 $heta_1$ 和 $heta_2$ 兩個參數的變化範圍也變得相近，對 $y$ 的影響不再有 feature 值在範圍大小傷的影響，從而反映代價函數上。在等高線圖上，梯度下降過程中變化受 x1 大小影響的 $heta_{1}$ 的變化減小了，變得和 x2 的變化趨勢一致，從而等高線圖近似圓形。

至於把 feature 縮小到什麼範圍，沒有特別的要求，只要各個 feature 的數值範圍相近就可以了，只是為了計算速度可以有所提升。

順便引用一下 Andrew Ng 老師在課程中用到的例題：

步長 α（學習率）的選擇

在參數 $heta$ 的更新式： $heta_{i}= heta_{i}-alphafrac{partial}{partial heta}J( heta)$ 中， $alpha$ 稱為步長，決定了參數每次被增加或減小的大小，步長如何選擇是決定梯度下降法表現的一個因素。如果步長過大，可能會直接越過最佳點，導致無法收斂，甚至發散；如果步長過小，可能導致迭代次數過多，降低效率。

步長的選擇過大時，導致越過最佳點

關於步長的選擇，有很多種方法，如果初始步長不合適，在後邊要不斷進行調整，調整的方法有很多種，關於這個問題國內外也有很多論文對其研究過。一旦找到了合適的步長，大多數情況下就不需要再改變了，有人會覺得隨著 $J( heta)$ 越來越小，如果步長不變，更新式中第二項的值也會越來越小，迭代的進度會慢下來。但是，隨著越來越接近最佳點，梯度也會越來越大，也就是 $J( heta)$ 的微分值也會越來越大，所以迭代的速度並不會變慢。

最常用的選擇步長的方法是按3倍調整，即：0.001、0.003、0.01、0.03、0.1、0.3、1 …… 按這個倍率進行測試，尋找能使 $J( heta)$ 下降速度最快的步長範圍，確定範圍後再對其進行微調。

用 Python 實現梯度下降法

import numpy as npimport randomdef gradient_descent(alpha, x, y, ep=0.0001, max_iter=10000): converged = False iter = 0 m = x.shape[0] # 數據的行數 # 初始化參數(theta) t0 = np.random.random(x.shape[1]) t1 = np.random.random(x.shape[1]) # 代價函數, J(theta) J = sum([(t0 + t1*x[i] - y[i])**2 for i in range(m)]) # 進行迭代 while not converged: # 計算訓練集中每一行數據的梯度 (d/d_theta j(theta)) grad0 = 1.0/m * sum([(t0 + t1*x[i] - y[i]) for i in range(m)]) grad1 = 1.0/m * sum([(t0 + t1*x[i] - y[i])*x[i] for i in range(m)]) # 更新參數 theta # 此處注意，參數要同時進行更新，所以要建立臨時變數來傳值 temp0 = t0 - alpha * grad0 temp1 = t1 - alpha * grad1 t0 = temp0 t1 = temp1 # 均方誤差 (MSE) e = sum( [ (t0 + t1*x[i] - y[i])**2 for i in range(m)] ) if abs(J-e) <= ep: print Converged, iterations: , iter, !!! converged = True J = e # 更新誤差值 iter += 1 # 更新迭代次數 if iter == max_iter: print Max interactions exceeded! converged = True return t0,t1

參考：3 Types of Gradient Descent Algorithms for Small & Large Data Sets