機器學習之梯度下降法（GD）和坐標軸下降法（CD）

梯度下降法

梯度下降法（Gradient Descent, GD）常用于求解無約束情況下凸函數（Convex Function）的極小值，是一種迭代類型的算法，因為凸函數只有一個極值點，故求解出來的極小值點就是函數的最小值點

$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h(x^{(i)}_{\theta})-y^{(i)})^{2}$

$\theta^{*}=\arg_\theta^m\min{J(\theta)}$

梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以梯度下降法也被稱為“最速下降法”。梯度下降法中越接近目標值，變量變化越小。計算公式如下

$\theta_{j+1}=\theta_{j}-\alpha\frac{\partial}{\partial{\theta_j}}J(\theta)$

梯度下降法（數值解）過程

Step1:初始化θ（隨機初始化）
Step2:沿著負梯度方向迭代，新的θ 能夠使得J(θ) 更小 $\theta_{j+1}=\theta_{j}-\alpha\frac{\partial}{\partial{\theta_j}}J(\theta)$ ?α：學習率、步長
Step3:如果J(θ) 能夠繼續減小，返回Step2，直到迭代完成。

收斂條件：當目標函數的函數值變化非常小的時候或者達到最大迭代次數的時候，就結束循環。

注：僅考慮單個樣本的單個 θ 參數的梯度值

$\begin{aligned}\frac{\partial}{\partial{\theta_j}}J(\theta) &=\frac{\partial}{\partial{\theta_j}}\frac{1}{2}(h_{\theta}(x)-y)^2 \\&=2\cdot \cdot \frac(h_{\theta}(x)-y)\cdot \frac{\partial}{\partial{\theta_j}}(h_{\theta}(x)-y)\\&=(h_{\theta}(x)-y)\frac{\partial}{\partial{\theta_j}}(\sum_{i=0}^{n}\theta_{i}x_{i}-y)\\& =(h_{\theta}(x)-y)x_{j}\end{aligned}$

4.2批量梯度下降法（BGD）

使用所有樣本的梯度值作為當前模型參數θ 的更新

$\begin{aligned}\frac{\partial{J(\theta)}}{\partial{\theta_{j}}}&=\sum_{i=1}^{m}\frac{\partial}{\partial{\theta_j}}\\&=\sum_{i=1}^{m}x_{j}^{(i)}(h_{\theta}(x^{(i)})-y^{(i)})\\&=\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}\end{aligned}$

4.3隨機梯度下降法（SGD）

使用單個樣本的梯度值作為當前模型參數θ的更新

$\frac{\partial}{\partial{\theta_j}}J(\theta)=(h_{\theta}(x)-y)x_{j}$

for i= 1 to m,{

$\theta_{j}=\theta_{j}+\alpha{(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}}$

}

BGD和SDB的區別

SGD速度比BGD快（整個數據集從頭到尾執行的迭代次數少）
SGD在某些情況下（全局存在多個相對最優解，J(θ)不是一個二次函數），SGD有可能會跳出某些小的局部最優解，所以一般情況下不會比BGD差；SGD在收斂的位置會存在J(θ)函數波動的情況，抗噪聲很差。
BGD一定能夠得到一個局部最優解（在線性回歸模型中一定是得到一個全局最優解），SGD由于隨機性的存在可能導致最終結果比BGD差
注意：優先選擇SGD

小批量梯度下降法（MBGD）

如果要滿足算法訓練過程較快，又需要保證最終參數訓練的準確率較高，提出小批量梯度下降法（Mini-batch Gradient Descent，簡稱MBGD）。
MBGD中是把樣本劃分為b個樣本（b一般為10），然后以這b個樣本的平均梯度為更新方向：

for i = 1 to m/10,{

$\theta_{j}=\theta_{j}+\alpha{\sum_{k=i}^{i+10}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}}$

}

學習率選擇和參數初始化

由于梯度下降法中負梯度方向作為變量的變化方向，所以有可能導致最終求解的值是局部最優解，所以在使用梯度下降的時候，一般需要進行一些調優策略

學習率的選擇：學習率過大，表示每次迭代更新的時候變化比較大，有可能會跳過最優解；學習率過小，表示每次迭代更新的時候變化比較小，就會導致迭代速度過慢，很長時間都不能結束；
算法初始參數數值的選擇：初始值不同，最終獲得的最小值也有可能不同，因為梯度下降法求解的是局部最優解，所以一般情況下，選擇多次不同初始值運行算法，并最終返回損失函數最小情況下的結果值；
標準化：由于樣本不同特征值的取值范圍不同，可能會導致在各個不同參數上迭代速度不同，為了減少特征取值的影響，可以將特征進行標準化操作。

BGD、SGD、MBGD的區別

當樣本量為m的時候，每次迭代BGD算法中對于參數值更新一次，SGD算法中對于參數值更新m次，MBGD算法中對參數值更新m/n次，相對來講SGD的更新速度最快；

SGD算法中對于每個樣本都需要更新參數值，當樣本值不太正常的時候，就有可能會導致本次的參數更新會產生相反的影響，也就是說SGD算法的結果并不完全收斂，而是在收斂結果處波動；

SGD算法是每個樣本都更新一次參數值，所以SGD算法特別適合樣本數據量特別大的情況以及在線機器學習（Online ML）

梯度下降法案例代碼

坐標軸下降法

坐標軸下降法（Coordinate Descent，CD）是一種迭代法，通過啟發式的方法一步步的迭代求解函數的最小值，和梯度下降法（GD）不同的時候，坐標軸下降法是沿著坐標軸的方向去下降，而不是采用梯度的負方向下降。

坐標軸下降法利用EM算法的思想，在參數更新過程中，每次均先固定m-1個參數值，求解剩下的一個參數的局部最優解；然后進行迭代式的更新操作。

坐標軸下降法的核心思想是多變量函數F(X)可以通過每次沿著一個方向優化來獲取最小值。

其數學依據是：對于一個可微凸函數f(θ)，其中θ 為?n*1 的向量，如果對于一個解? $\theta=(\theta_1, \theta_2, \dots, \theta_n)$ ?,使得f(θ) 在某個坐標軸? $\theta_i(i=1,2,..,n)$ ?上都能達到最小值，則? $\theta=(\theta_1, \theta_2, \dots, \theta_n)$ 就是 f(θ) 的全局的最小值點。

在坐標軸下降法中，優化方向從算法的一開始就固定了，即沿著坐標的方向進行變化。在算法中，循環最小化各個坐標方向的目標函數。即：如果? $x_k$ ??給定，那么? $x_{k+1}$ ?的第i維度為：

$x_i^{k+1}=\arg\min_{y\in R}f(x_1^{k+1}, \dots, x_{i-1}^{k+1}, y, x_{i+1}^k, \dots, x_n^k)$

因此，從一個初始的? $x_0$ 求得函數F(x)的局部最優解，可以迭代獲取? $x_0,x_1,x_2...$ ?的序列，從而可以得到：

$F(x_0)\ge F(x_1)\ge F(x_2)\ge\dots$

坐標軸下降法算法過程：

給θ 向量隨機選取一個初值，記做? $\theta_0$
?對于第k輪的迭代，從? $\theta_1^k$ ? 開始計算， $\theta_n^k$ ? 到為止，計算公式如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????? $\begin{aligned}\theta_1^k&=\arg\min_{\theta_1}J(\theta_1,\theta_2^{k-1}, \theta_3^{k-1}, \dots, \theta_n^{k-1}) \\\theta_2^k&=\arg\min_{\theta_2}J(\theta_1^k,\theta_2, \theta_3^{k-1}, \dots, \theta_n^{k-1}) \\\dots \\\theta_n^k&=\arg\min_{\theta_n}J(\theta_1^k,\theta_2^k, \theta_3^k, \dots, \theta_n)\end{aligned}$

檢查? $\theta_k$ ??和? $\theta_{k-1}$ ?向量在各個維度上的變化情況，如果所有維度的變化情況都比較小的話，那么認為結束迭代，否則繼續k+1輪的迭代
在求解每個參數局部最優解的時候可以求導的方式來求解
?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/454217.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/454217.shtml
英文地址，請注明出處：http://en.pswp.cn/news/454217.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！