梯度下降法及其Python實現

05-23

梯度下降法及其Python實現

來自專欄經管人學數據分析

基本介紹

梯度下降法（gradient descent），又名最速下降法（steepest descent）是求解無約束最優化問題最常用的方法，它是一種迭代方法，每一步主要的操作是求解目標函數的梯度向量，將當前位置的負梯度方向作為搜索方向。

梯度下降法特點：越接近目標值，步長越小，下降速度越慢。

下面將通過公式來說明梯度下降法。

建立模型為擬合函數 $h(θ)$

$h(θ)= heta_{0}+ heta_{1} x_{1}+....+ heta_{n} x_{n}=sum_{j=0}^{n} heta_{j} x_{j}$

接下來的目標是將該函數通過樣本的擬合出來，得到最佳的函數模型。因此構建損失函數 $J(θ)$ （目的是通過求解 $min J(θ)$ ，得到在最優解下的 $θ$ 向量），其中的每一項 $h_{θ}(x^{i})-y^{i}$ 都表示在已有的訓練集上我們的擬合函數與之間的殘差，計算其平方損失函數作為我們構建的風險函數（這裡採用最小二乘法構造損失函數，在邏輯回歸中也可採用最大似然估計構造損失函數從而估計參數）。

$min J(θ)=frac{1}{2}sum_{i=0}^{m}(h_{θ}(x^{i})-y^{i})^2$

要使得 $J(θ)$ 最小，則對其 $J(θ)$ 求導等於零。

$θ_{j}:=θ_{j}-frac{partial J( heta)}{partial θ_{j} }$

在處理以下步驟時，可以用批量梯度下降演算法（BGD）與隨機梯度下降演算法(SGD)。

批量梯度下降演算法（BGD）

單個特徵 $x^{i}$ 的迭代如下：

$θ_{j}:=θ_{j}+a(y^i-h_θ(x^i))x^i_j$

$a$ 為步長，如果太小，則找到函數最小值的速度就很慢，如果太大，則可能會錯過最小值，而使得函數值發散。初始點不同，獲得的最小值也不同，因此梯度下降求得的只是局部最小值。

多個特徵的迭代如下：

repeat until convergence{

$θ_{j}:=θ_{j}+asum^m_{i=1}(y^i-h_θ(x^i))x^i_j$ (for every )

}

當上式收斂時則退出迭代，一開始設置一個具體參數，當前後兩次迭代差值小於該參數時候結束迭代。

使用梯度下降法，越接近最小值時，下降速度越慢。計算批量梯度下降法時，計算每一個θ值都需要遍歷計算所有樣本，當數據量比較大時這是比較費時的計算。

隨機梯度下降演算法(SGD)

為解決數據量大的時批量梯度下降演算法費時的困境。隨機梯度下降演算法，每次迭代只是考慮讓該樣本點的 $J(θ)$ 趨向最小，而不管其他的樣本點，這樣演算法會很快，但是收斂的過程會比較曲折，整體效果上，大多數時候它只能接近局部最優解，而無法真正達到局部最優解。該演算法適合用於較大訓練集的例子。

Loop{

for i=1 to m,{

$θ_{j}:=θ_{j}+a(y^i-h_θ(x^i))x^i_j$ (for every )

}

改進的隨機梯度下降演算法

為了避免迭代時係數出現周期性波動，同時讓係數很快收斂，這裡改進隨機梯度下降演算法。

1）在每次迭代時，調整更新步長 $a$ 的值。隨著迭代的進行， $a$ 越來越小，這會緩解係數的高頻波動。同時為了避免 $a$ 隨著迭代不斷減小到接近於0，約束 $a$ 一定大於一個稍微大點的常數項。

2）每次迭代，改變樣本的優化順序。也就是隨機選擇樣本來更新回歸係數。這樣做可以減少周期性的波動，因為樣本順序的改變，使得每次迭代不再形成周期性。

演算法應用和python實現

梯度下降法可以用於在前面提到的logistic回歸分類器中，主要是求解模型中的cost函數，這裡用泰坦尼克數據集進行演示，並且使用python中的sklearn庫進行實現，代碼如下：

import pandasfrom sklearn.linear_model import LinearRegression, LogisticRegressionfrom sklearn.model_selection import KFold, cross_val_scoreimport numpy as nptitanic = pandas.read_csv(E:TitanicDataTitanic\train.csv)# print(titanic.describe())titanic[Age] = titanic[Age].fillna(titanic[Age].mean())# print(titanic.describe())# print(titanic[Sex].unique())titanic.loc[titanic[Sex] == male, Sex] = 0titanic.loc[titanic[Sex] == female, Sex] = 1# print(titanic[Embarked].unique())titanic[Embarked] = titanic[Embarked].fillna(S)titanic.loc[titanic[Embarked] == S, Embarked] = 0titanic.loc[titanic[Embarked] == C, Embarked] = 1titanic.loc[titanic[Embarked] == Q, Embarked] = 2# print(titanic.columns)predictors = [Pclass, Sex, Age, SibSp, Parch, Fare, Embarked]#開始線性回歸預測alg = LinearRegression()X = titanic[predictors]kf = KFold(n_splits=3)prediction = []for train, test in kf.split(X): x_train = titanic[predictors].iloc[train, :] y_train = titanic[Survived].iloc[train] x_test = titanic[predictors].iloc[test, :] y_test = titanic[Survived].iloc[test] alg.fit(x_train, y_train) test_prediction = alg.predict(x_test) prediction.append(test_prediction)prediction = np.concatenate(prediction)prediction[prediction > 0.5] = 1prediction[prediction < 0.5] = 0accuracy_linear = sum(prediction[prediction == titanic[Survived]])/len(prediction) #查准率#score1 = cross_val_score(alg, X, titanic[Survived], cv=3).mean()# cross_val_score是直接將演算法得到的值與y_test進行對比算scoring# 這個步驟錯誤，因為線性回歸得到的是概率值，需要後期判別到{0,1}上，才能和原y_test的數據進行比較算accuracy，所以LinearRegression不適合做cross_val_score的estimator。print(accuracy_linear, score1)#開始邏輯回歸預測alh = LogisticRegression()score = cross_val_score(alh, X, titanic[Survived], cv=3).mean()#logisticregression的演算法結果直接是{0,1}兩值，所以可以直接進行score比較算accuracy，所以這個alh適合這個estimator。print(score)