淺談梯度下降法/Gradient descent
當今世界，深度學習應用已經滲透到了我們生活的方方面面，深度學習技術背后的核心問題是最優化(Optimization)。最優化是應用數學的一個分支，它是研究在給定約束之下如何尋求某些因素(的量)，以使某一(或某些)指標達到最優的一些學科的總稱。
梯度下降法(Gradient descent，又稱最速下降法/Steepest descent)，是無約束最優化領域中歷史最悠久、最簡單的算法，單獨就這種算法來看，屬于早就“過時”了的一種算法。但是，它的理念是其他某些算法的組成部分，或者說在其他某些算法中，也有梯度下降法的“影子”。例如，各種深度學習庫都會使用SGD(Stochastic Gradient Descent，隨機梯度下降)或變種作為其優化算法。
今天我們就再來回顧一下梯度下降法的基礎知識。
1. 名字釋義
在很多機器學習算法中，我們通常會通過多輪的迭代計算，最小化一個損失函數(loss function)的值，這個損失函數，對應到最優化里就是所謂的“目標函數”。
在尋找最優解的過程中，梯度下降法只使用目標函數的一階導數信息——從“梯度”這個名字也可見一斑。并且它的本意是取目標函數值“最快下降”的方向作為搜索方向，這也是“最速下降”這個名字的來源。
于是自然而然地，我們就想知道一個問題的答案：沿什么方向，目標函數 f(x) 的值下降最快呢?
2. 函數值下降最快的方向是什么
先說結論：沿負梯度方向
函數值下降最快。此處，我們用 d 表示方向(direction)，用 g 表示梯度(gradient)。
下面就來推導一下。
將目標函數 f(x) 在點
處泰勒展開(在最優化領域，這是一個常用的手段)：
高階無窮小 o(α)可忽略，由于我們定義了步長α>0(在ML領域，步長就是平常所說的learning rate)，
因此，當
時
即函數值是下降的。
此時
就是一個下降方向。
但是
具體等于什么的時候，可使目標函數值下降最快呢?
數學上，有一個非常著名的不等式：Cauchy-Schwartz不等式(柯西-許瓦茲不等式)①，它是一個在很多場合都用得上的不等式：
當且僅當：
時等號成立。
由Cauchy-Schwartz不等式可知：
當且僅當
時，等號成立，
最大(>0)。
所以，
時
最小(<0)，f(x) 下降量最大。
所以，
是最快速下降方向。
3. 缺點
它真的如它的名字所描述的，是“最快速”的嗎?從很多經典的最優化書籍你會了解到：并不是。
事實上，它只在局部范圍內具有“最速”性質；對整體求最優解的過程而言，它讓目標函數值下降非常緩慢。
4. 感受一下它是如何“慢”的
先來看一幅圖②
這幅圖表示的是對一個目標函數尋找最優解的過程，圖中鋸齒狀的路線就是尋優路線在二維平面上的投影。從這幅圖我們可以看到，鋸齒一開始比較大(跨越的距離比較大)，后來越來越小；這就像一個人走路邁的步子，一開始大，后來步子越邁越小。
這個函數的表達式是這樣的：
它叫做Rosenbrock function(羅森布羅克函數)③，是個非凸函數，在最優化領域，它可以用作一個最優化算法的performance test函數。這個函數還有一個更好記也更滑稽的名字：banana function(香蕉函數)。
我們來看一看它在三維空間中的圖形：
它的全局最優點位于一個長長的、狹窄的、拋物線形狀的、扁平的“山谷”中。
找到“山谷”并不難，難的是收斂到全局最優解(在 (1,1) 處)。
正所謂：
| 世界上最遙遠的距離，不是你離我千山萬水，而是你就在我眼前，我卻要跨越千萬步，才能找到你。 |
我們再來看下面這個目標函數的尋優過程④：
和前面的Rosenbrock function一樣，它的尋優過程也是“鋸齒狀”的。
它在三維空間中的圖形是這樣的：
總而言之就是：當目標函數的等值線接近于圓(球)時，下降較快；等值線類似于扁長的橢球時，一開始快，后來很慢。
5. 為什么“慢”?
從上面花花綠綠的圖，我們看到了尋找最優解的過程有多么“艱辛”，但不能光看熱鬧，還要分析一下原因。
在最優化算法中，精確的line search滿足一個一階必要條件，即：梯度與方向的點積為零
(當前點在
方向上移動到的那一點
處的梯度，與當前點的搜索方向
的點積為零)。
由此得知：
即：
故由梯度下降法的
得：
即：相鄰兩次的搜索方向是相互直交的(投影到二維平面上，就是鋸齒形狀了)。
如果你非要問，為什么
就表明這兩個向量是相互直交的?那是因為，由兩向量夾角的公式：
可知兩向量夾角為90度，因此它們直交。
6. 優點
這個被我們說得一無是處的方法真的就那么糟糕嗎?
其實它還是有優點的：程序簡單，計算量小；并且對初始點沒有特別的要求;此外，許多算法的初始/再開始方向都是最速下降方向(即負梯度方向)。
7. 收斂性及收斂速度
梯度下降法具有整體收斂性——對初始點沒有特殊要求。
采用精確的line search的梯度下降法的收斂速度：線性。
引用：
- https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality
- https://en.wikipedia.org/wiki/Gradient_descent
- https://en.wikipedia.org/wiki/Rosenbrock_function
- https://en.wikipedia.org/wiki/Gradient_descent
【本文是51CTO專欄機構360技術的原創文章，微信公眾號“360技術（ id: qihoo_tech）”】
