一階梯度類最優化演算法簡介

Ⅰ 梯度下降法是什麼

梯度下降法（英語：Gradient descent）是一個一階最優化演算法，通常也稱為最陡下降法。

要使用梯度下降法找到一個函數的局部極小值，必須向函數上當前點對應梯度（或者是近似梯度）的反方向的規定步長距離點進行迭代搜索。如果相反地向梯度正方向迭代進行搜索，則會接近函數的局部極大值點；這個過程則被稱為梯度上升法。

梯度下降一般歸功於柯西，他在 1847 年首次提出它。Hadamard在 1907 年獨立提出了類似的方法。Haskell Curry在 1944 年首先研究了它對非線性優化問題的收斂性，隨著該方法在接下來的幾十年中得到越來越多的研究和使用，通常也稱為最速下降。

梯度下降適用於任意維數的空間，甚至是無限維的空間。在後一種情況下，搜索空間通常是一個函數空間，並且計算要最小化的函數的Fréchet 導數以確定下降方向。

梯度下降適用於任意數量的維度（至少是有限數量）可以看作是柯西-施瓦茨不等式的結果。那篇文章證明了任意維度的兩個向量的內（點）積的大小在它們共線時最大化。在梯度下降的情況下，當自變數調整的向量與偏導數的梯度向量成正比時。

修改

為了打破梯度下降的鋸齒形模式，動量或重球方法使用動量項，類似於重球在被最小化的函數值的表面上滑動，或牛頓動力學中的質量運動在保守力場中通過粘性介質。具有動量的梯度下降記住每次迭代時的解更新，並將下一次更新確定為梯度和前一次更新的線性組合。

對於無約束二次極小化，重球法的理論收斂速度界與最優共軛梯度法的理論收斂速度界漸近相同。

該技術用於隨機梯度下降，並作為用於訓練人工神經網路的反向傳播演算法的擴展。

Ⅱ 幾種常用最優化方法

學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習演算法，大部分的機器學習演算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的優化方法(optimization)有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。

1. 梯度下降法（Gradient Descent）

梯度下降法是最早最簡單，也是最為常用的最優化方法。梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。 梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。

梯度下降 法的缺點：

（1）靠近極小值時收斂速度減慢;

（2）直線搜索時可能會產生一些問題；

（3）可能會「之字形」地下降。

在機器學習中，基於基本的梯度下降法發展了兩種梯度下降方法，分別為隨機梯度下降法和批量梯度下降法。

比如對一個線性回歸（Linear Logistics）模型，假設下面的h(x)是要擬合的函數，J( )為損失函數， 是參數，要迭代求解的值，求解出來了那最終要擬合的函數h( )就出來了。其中m是訓練集的樣本個數，n是特徵的個數。

1）批量梯度下降法（Batch Gradient Descent，BGD）

（1）將J( )對 求偏導，得到每個theta對應的的梯度：

(2）由於是要最小化風險函數，所以按每個參數 的梯度負方向，來更新每個 ：

        （3）從上面公式可以注意到，它得到的是一個全局最優解，但是每迭代一步，都要用到訓練集所有的數據，如果m很大，那麼可想而知這種方法的迭代速度會相當的慢。所以，這就引入了另外一種方法——隨機梯度下降。

對於批量梯度下降法，樣本個數m，x為n維向量，一次迭代需要把m個樣本全部帶入計算，迭代一次計算量為m*n2。

2）隨機梯度下降（Stochastic Gradient Descent，SGD）

        （1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：

（2）每個樣本的損失函數，對 求偏導得到對應梯度，來更新 ：

（3）隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能只用其中幾萬條或者幾千條的樣本，就已經將

迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。但是，SGD伴隨的一個問題是噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。

隨機梯度下降每次迭代只使用一個樣本，迭代一次計算量為n2，當樣本個數m很大的時候，隨機梯度下降迭代一次的速度要遠高於批量梯度下降方法。 兩者的關系可以這樣理解：隨機梯度下降方法以損失很小的一部分精確度和增加一定數量的迭代次數為代價，換取了總體的優化效率的提升。增加的迭代次數遠遠小於樣本的數量。

對批量梯度下降法和隨機梯度下降法的總結：

批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小，但是對於大規模樣本問題效率低下。

隨機梯度下降---最小化每條樣本的損失函數，雖然不是每次迭代得到的損失函數都向著全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近，適用於大規模訓練樣本情況。

2. 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）

1）牛頓法（Newton's method）

牛頓法是一種在實數域和復數域上近似求解方程的方法。方法使用函數 f  ( x )的泰勒級數的前面幾項來尋找方程 f  ( x ) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。

具體步驟：

首先，選擇一個接近函數 f  ( x )零點的x0，計算相應的 f  ( x 0)和切線斜率 f  '  ( x 0)（這里 f '  表示函數 f   的導數）。然後我們計算穿過點( x 0, f   ( x 0))並且斜率為 f  '( x 0)的直線和 x  軸的交點的 x 坐標，也就是求如下方程的解：

我們將新求得的點的 x  坐標命名為 x 1，通常 x 1會比 x 0更接近方程 f   ( x ) = 0的解。因此我們現在可以利用 x 1開始下一輪迭代。迭代公式可化簡為如下所示：

已經證明，如果 f   '是連續的，並且待求的零點 x 是孤立的，那麼在零點 x 周圍存在一個區域，只要初始值 x 0位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果 f   ' ( x )不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。下圖為一個牛頓法執行過程的例子。

由於牛頓法是基於當前位置的切線來確定下一次的位置，所以牛頓法又被很形象地稱為是"切線法"。

關於牛頓法和梯度下降法的效率對比：

從本質上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。（牛頓法目光更加長遠，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優，沒有全局思想。）

根據wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。

註：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。

牛頓法的優缺點總結：

優點：二階收斂，收斂速度快；

缺點：牛頓法是一種迭代演算法，每一步都需要求解目標函數的Hessian矩陣的逆矩陣，計算比較復雜。

2）擬牛頓法（Quasi-Newton Methods）

擬牛頓法是求解非線性優化問題最有效的方法之一，於20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種演算法在當時看來是非線性優化領域最具創造性的發明之一。不久R. Fletcher和M. J. D. Powell證實了這種新的演算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。

擬牛頓法的本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。 擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。

具體步驟：

擬牛頓法的基本思想如下。首先構造目標函數在當前迭代xk的二次模型：

這里Bk是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點：

其中我們要求步長ak 滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣Bk 代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣Bk的更新。現在假設得到一個新的迭代xk+1，並得到一個新的二次模型：

我們盡可能地利用上一步的信息來選取Bk。具體地，我們要求

從而得到

這個公式被稱為割線方程。常用的擬牛頓法有DFP演算法和BFGS演算法。

原文鏈接： [Math] 常見的幾種最優化方法 - Poll的筆記 - 博客園

Ⅲ 梯度下降法是什麼

梯度下降法（英語：Gradient descent）是一個一階最優化演算法，通常也稱為最陡下降法，但是不該與近似積分的最陡下降法（英語：Method of steepest descent）混淆。

要使用梯度下降法找到一個函數的局部極小值，必須向函數上當前點對應梯度（或者是近似梯度）的反方向的規定步長距離點進行迭代搜索。

如果相反地向梯度正方向迭代進行搜索，則會接近函數的局部極大值點；這個過程則被稱為梯度上升法。

梯度下降演算法使用當前位置的梯度迭代計算下一個點，然後對其進行縮放（按學習率）並從當前位置減去獲得的值（邁出一步）。它減去該值，因為我們想要最小化函數（最大化它會增加）。

缺點

梯度下降法的缺點包括：

1、靠近局部極小值時速度減慢。

2、直線搜索可能會產生一些問題。

3、可能會「之字型」地下降。

Ⅳ 為什麼隨機梯度下降方法能夠收斂

其實這個還是要好好的看看論文，然後讓導師再給你好好的講解一下吧，我這里只能說我自己的理解。

隨機梯度下降演算法

首先要知道什麼是隨機並行梯度下降演算法。其實等於沒有模型的優化的演算法，就是更加的適用於那種控制變數比較多的，但是系統比較復雜的，又沒有辦法准確的去建立數學模型的優化控制的過程。

總結

其實我覺得我說這么多，不一定說明白啥，基本上我個人是覺得對於這種隨機梯度下降的方法是期望收斂而已，真的是沒有辦法確定是否收斂的。

畢竟我沒有論文專業，更沒有導師專業，我只是用我自己的知識能力去回答的問題，所以說我由衷的建議你去看論文，看不懂就去問導師了，那才是正道啊，像我們這種人，畢竟沒有那麼專業，我害怕讓你誤入歧途。

Ⅳ 梯度下降法是什麼

梯度下降法是一個最優化演算法，通常也稱為最速下降法。

最速下降法是求解無約束優化問題最簡單和最古老的方法之一，雖然現已不具有實用性，但是許多有效演算法都是以它為基礎進行改進和修正而得到的。最速下降法是用負梯度方向為搜索方向的，最速下降法越接近目標值，步長越小，前進越慢。

可以用於求解非線性方程組。

簡介

梯度下降是迭代法的一種，可以用於求解最小二乘問題（線性和非線性都可以）。在求解機器學習演算法的模型參數，即無約束優化問題時，梯度下降（Gradient Descent）是最常採用的方法之一，另一種常用的方法是最小二乘法。

在求解損失函數的最小值時，可以通過梯度下降法來一步步的迭代求解，得到最小化的損失函數和模型參數值。反過來，如果我們需要求解損失函數的最大值，這時就需要用梯度上升法來迭代了。

在機器學習中，基於基本的梯度下降法發展了兩種梯度下降方法，分別為隨機梯度下降法和批量梯度下降法。

Ⅵ 機器學習中的降維演算法和梯度下降法

機器學習中有很多演算法都是十分經典的，比如說降維演算法以及梯度下降法，這些方法都能夠幫助大家解決很多問題，因此學習機器學習一定要掌握這些演算法，而且這些演算法都是比較受大家歡迎的。在這篇文章中我們就給大家重點介紹一下降維演算法和梯度下降法。
降維演算法
首先，來說一說降維演算法，降維演算法是一種無監督學習演算法，其主要特徵是將數據從高維降低到低維層次。在這里，維度其實表示的是數據的特徵量的大小，當特徵量大的話，那麼就給計算機帶來了很大的壓力，所以我們可以通過降維計算，把維度高的特徵量降到維度低的特徵量，比如說從4維的數據壓縮到2維。類似這樣將數據從高維降低到低維有兩個好處，第一就是利於表示，第二就是在計算上也能帶來加速。
當然，有很多降維過程中減少的維度屬於肉眼可視的層次，同時壓縮也不會帶來信息的損失。但是如果肉眼不可視，或者沒有冗餘的特徵，這怎麼辦呢？其實這樣的方式降維演算法也能工作，不過這樣會帶來一些信息的損失。不過，降維演算法可以從數學上證明，從高維壓縮到的低維中最大程度地保留了數據的信息。所以說，降維演算法還是有很多好處的。
那麼降維演算法的主要作用是什麼呢？具體就是壓縮數據與提升機器學習其他演算法的效率。通過降維演算法，可以將具有幾千個特徵的數據壓縮至若干個特徵。另外，降維演算法的另一個好處是數據的可視化。這個優點一直別廣泛應用。
梯度下降法
下面我們給大家介紹一下梯度下降法，所謂梯度下降法就是一個最優化演算法，通常也稱為最速下降法。最速下降法是求解無約束優化問題最簡單和最古老的方法之一，雖然現在已經不具有實用性，但是許多有效演算法都是以它為基礎進行改進和修正而得到的。最速下降法是用負梯度方向為搜索方向的，最速下降法越接近目標值，步長越小，前進越慢。好比將函數比作一座山，我們站在某個山坡上，往四周看，從哪個方向向下走一小步，能夠下降的最快;當然解決問題的方法有很多，梯度下降只是其中一個，還有很多種方法。
在這篇文章中我們給大家介紹了關於機器演算法中的降維演算法以及梯度下降法，這兩種方法是機器學習中十分常用的演算法，降維演算法和梯度下降法都是十分實用的，大家在進行學習機器學習的時候一定要好好學習這兩種演算法，希望這篇文章能夠幫助大家理解這兩種演算法。

Ⅶ 梯度下降法是什麼

梯度下降法是一個一階最優化演算法，通常也稱為最陡下降法，但是不該與近似積分的最陡下降法（英語：Method of steepest descent）混淆。

梯度下降演算法使用當前位置的梯度迭代計算下一個點，然後對其進行縮放（按學習率）並從當前位置減去獲得的值（邁出一步）。它減去該值，因為我們想要最小化函數（最大化它會增加）。

注意事項

從數學上的角度來看，梯度的方向是函數增長速度最快的方向，那麼梯度的反方向就是函數減少最快的方向。那麼，如果想計算一個函數的最小值，就可以使用梯度下降法的思想來做。

注意得到的函數臨界點，臨界點並不一定是全局最大值或者全局最小值，甚至不是局部的最大值或者局部最小值。