前言：

?????? 機器學習從目標函數到模型構建到特征提取，需要模型依據目標函數約束，根據回歸方式進行調整數學模型，最基本最常用的一種方法是梯度下降法，以梯度下降為指導準則，優化目標函數到最優解。? 原文地址：再談最速/梯度下降法???????

一、算法過程

最速下降法（又稱梯度法，或Steepest Descent），是無約束最優化領域中最簡單的算法，單獨就這種算法來看，屬于早就“過時”了的一種算法。但是，它的理念是其他某些算法的組成部分，或者說是在其他某些算法中，也有最速下降法的“影子”。因此，我們還是有必要學習一下的。
我很久以前已經寫過一篇關于最速下降法的文章了，但是這里我還打算再寫一篇，提供更多一些信息，讓大家可以從更簡單生動的方面去理解它。

『1』名字釋義
最速下降法只使用目標函數的一階導數信息——從“梯度法”這個名字也可見一斑。并且，它的本意是取目標函數值“最快下降”的方向作為搜索方向。于是我們就想知道這個問題的答案：沿什么方向，目標函數f(x) 的值下降最快呢？

『2』函數值下降最快的方向
先說結論：沿負梯度方向? d=?gk ，函數值下降最快。
下面就來推導一下。
將目標函數 f(x) 在點 xk 處泰勒展開（這是我們慣用的“伎倆”了）——
f(x)=f(xk)+αgTkdk+o(α)
高階無窮小 o(α) 可忽略，由于我們定義了步長 α>0 ，因此，當 gTkdk<0 時， f(x)<f(xk) ，即函數值是下降的。此時 dk 就是一個下降方向。
但是 dk 具體等于什么的時候，可使目標函數值下降最快呢？
文章來源：http://www.codelast.com/
由Cauchy-Schwartz不等式（柯西-許瓦茲不等式）可得：
∣∣dTkgk∣∣≤∥dk∥∥gk∥
當且僅當 dk=gk 時，等號成立， dTkgk 最大（>0）。
所以 dk=?gk 時， dTkgk 最小（<0）， f(x) 下降量最大。
所以 ?gk 是最快速下降方向。

『3』缺點
它真的“最快速”嗎？答案是否定的。
事實是，它只在局部范圍內具有“最速”性質。
對整體求解過程而言，它的下降非常緩慢。

『4』感受一下它是如何“慢”的
先來看一幅圖（直接從維基百科上弄過來的，感謝Wiki）：

文章來源：http://www.codelast.com/
這幅圖表示的是對一個目標函數的尋優過程，圖中鋸齒狀的路線就是尋優路線在二維平面上的投影。
這個函數的表達式是：
f(x1,x2)=(1?x1)2+100?(x2?x12)2
它叫做Rosenbrock function（羅森布羅克方程），是個非凸函數，在最優化領域，它通常被用來作為一個最優化算法的performance test函數。
我們來看一看它在三維空間中的圖形：

文章來源：http://www.codelast.com/
它的全局最優點位于一個長長的、狹窄的、拋物線形狀的、扁平的“山谷”中。 找到“山谷”并不難，難的是收斂到全局最優解（全局最優解在 (1,1) 處）。 正所謂：世界上最遙遠的距離，不是你離我千山萬水，而是你就在我眼前，我卻要跨越千萬步，才能找到你。 文章來源：http://www.codelast.com/
我們再來看另一個目標函數 f(x,y)=sin(12x2?14y2+3)cos(2x+1?ey) 的尋優過程： 和前面的Rosenbrock function一樣，它的尋優過程也是“鋸齒狀”的。
它在三維空間中的圖形是這樣的： 總而言之就是：當目標函數的等值線接近于圓(球)時，下降較快；等值線類似于扁長的橢球時，一開始快，后來很慢。 文章來源：http://www.codelast.com/
『5』為什么“慢”的分析
上面花花綠綠的圖確實很好看，我們看到了那些尋優過程有多么“慘烈”——太艱辛了不是么？
但不能光看熱鬧，還要分析一下——為什么會這樣呢？
由精確line search滿足的一階必要條件，得：
?f(xk+αkdk)Tdk=0 ，即 gTk+1dk=0
故由最速下降法的 dk=?gk 得：
gTk+1dk=gTk+1(?gk)=?gTk+1gk=?dTk+1dk=0?dTk+1dk=0
即：相鄰兩次的搜索方向是相互直交的（投影到二維平面上，就是鋸齒形狀了）。
文章來源：http://www.codelast.com/
如果你非要問，為什么 dTk+1dk=0 就表明這兩個向量是相互直交的？那么我就耐心地再解釋一下：
由兩向量夾角的公式：

=> θ=π2
兩向量夾角為90度，因此它們直交。

『6』優點
這個被我們說得一無是處的最速下降法真的就那么糟糕嗎？其實它還是有優點的：程序簡單，計算量小；并且對初始點沒有特別的要求；此外，許多算法的初始/再開始方向都是最速下降方向（即負梯度方向）。
文章來源：http://www.codelast.com/
『7』收斂性及收斂速度
最速下降法具有整體收斂性——對初始點沒有特殊要求。
采用精確線搜索的最速下降法的收斂速度：線性。

二、梯度下降算法的代碼

//梯度下降法 float gsdFindArc(std::vector<cv::Point2f> & inlierPs,cv::Point2f ￠er, float radius) {//弧的殘差函數為 f = A - 2nXiX - 2nYiY//double matrix[4][2]={{1,4},{2,5},{5,1},{4,2}};Eigen::MatrixXf M(inlierPs.size(),2);for (int i=0;i< M.rows();++i ){M(i,0) = inlierPs[i].x;M(i,1) = inlierPs[i].y;}//初始化三個優化參數std::vector<float > xi(3);xi[0] = center.x;xi[1] = center.y;xi[2] = radius;//初始化result//double result[4]={19,26,19,20};std::vector<float > result(inlierPs.size() );float r = xi[2];for (int i=0;i< M.rows();++i ){float x = M(i,0);float y = M(i,1);result[i] = x*x + y*y - 2*x*xi[0] - 2*y*xi[1] + xi[0]*xi[0] + xi[1]*xi[1] - r*r;}//double w[2]={0,0};//初始為零向量double w[3] = {0,0,0};double loss = 10.0;const double n = 0.01; //步長 int numIter = 100*inlierPs.size();for(int i=0;i< numIter && loss>0.001; i++){double error_sum=0;int j = i % inlierPs.size();{ double h = 0;for(int k=0; k<xi.size() ; k++)h += M(j,k)* w[k];error_sum = h - result[j];for(int k=0; k<xi.size(); k++)w[k] -= n * (error_sum) * M(j,k);//更新權值,權值更新過程為整個關鍵過程}double loss=0;for(int j=0; j< M.rows() ;j++){double sum = 0;for( int k=0; k<xi.size() ; k++)sum += M(j,k) * w[k];loss += (sum - result[j]) * (sum-result[j]);}std::cout<< "Loss!"<< loss << std::endl;}return 1.0; }
延伸 GD方法，從復雜方程解的高原區向梯度的負方向進行迭代，遇到了鞍點該怎么走，走錯了怎么辦？隨機走下去嗎？隨機走下去的恰好是局部最優又怎么辦？ 還有 一個，GD算法的學習率一般不能太大，必須小步小步，否則極易落入局部最優解，再也走不出來或者在局部最優解處反復震蕩。

??????

???? 這就引入了SGD。兩大缺陷竟然可以用同一個方法解決, 就是Stochastic Gradient Descent (SGD) 算法.

SGD 算法的表達式和GD差不多:

這里 就是所謂的Stochastic Gradient，它滿足

也就是說，雖然包含一定的隨機性，但是從期望上來看，它是等于正確的導數的．用一張圖來表示，其實SGD就像是喝醉了酒的GD，它依稀認得路，最后也能自己走回家，但是走得歪歪扭扭．（紅色的是GD的路線，偏粉紅的是SGD的路線）．

仔細看的話，其實SGD需要更多步才能夠收斂的，畢竟它喝醉了．可是，由于它對導數的要求非常低，可以包含大量的噪聲，只要期望正確就行（有時候期望不對都是可以的．．），所以導數算起來非常快．

SGD的引入帶來ML界一個非常本質的變化，訓練模型開始依賴經驗怎樣指導去調參，越深的模型越像在煉丹.....

總結

以上是生活随笔為你收集整理的最优化方法：梯度下降法、SGD的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。