常用優化演算法

㈠ 優化演算法總結

本文介紹一下機器學習和深度學習中常用的優化演算法和優化器以及一些其他我知道的優化演算法,部分演算法我也沒有搞懂,就先記錄下來以後慢慢研究吧.*_*.

1.梯度下降演算法(Gradient Descent)

梯度下降法可以參考我另一篇文章 機器學習-線性回歸 里的講解,這里就不在重復敘述.這里需要強調一下,深度學習里常用的SGD,翻譯過來是隨機梯度下降,但是實質是mini-batch梯度下降(mini-batch-gd),或者說是兩者的結合更准確一些.

SGD的優點是,演算法簡單,計算量小,在函數為凸函數時可以找到全局最優解.所以是最常用的優化演算法.缺點是如果函數不是凸函數的話,很容易進入到局部最優解而無法跳出來.同時SGD在選擇學習率上也是比較困難的.

2.牛頓法

牛頓法和擬牛頓法都是求解無約束最優化問題的常用方法,其中牛頓法是迭代演算法,每一步需要求解目標函數的海森矩陣的逆矩陣,計算比較復雜.

牛頓法在求解方程根的思想:在二維情況下,迭代的尋找某一點x,尋找方法是隨機一個初始點x_0,目標函數在該點x_0的切線與x坐標軸的交點就是下一個x點,也就是x_1.不斷迭代尋找x.其中切線的斜率為目標函數在點x_0的導數(梯度),切必過點(x_0,f(x_0)).所以迭代的方程式如圖1,為了求該方程的極值點,還需要令其導數等於0,也就是又求了一次導數,所以需要用到f(x)的二階導數.

在最優化的問題中,牛頓法提供了一種求解的辦法. 假設任務是優化一個目標函數f, 求函數ff的極大極小問題, 可以轉化為求解函數f導數等於0的問題, 這樣求可以把優化問題看成方程求解問題(f的導數等於0). 剩下的問題就和牛頓法求解方程根的思想很相似了.

目標函數的泰勒展開式:

化簡後:

這樣就得到了與圖1相似的公式,這里是二維的,在多維空間上,求二階導數就是求海森矩陣,因為是分母,所以還需要求海森矩陣的逆矩陣.

牛頓法和SGD的區別:

牛頓法是二階求導,SGD是一階求導,所以牛頓法要收斂的更快一些.SGD只考慮當前情況下梯度下降最快的方向,而牛頓法不僅考慮當前梯度下降最快,還有考慮下一步下降最快的方向.

牛頓法的優點是二階求導下降速度快,但是因為是迭代演算法,每一步都需要求解海森矩陣的逆矩陣,所以計算復雜.

3.擬牛頓法(沒搞懂,待定)

考慮到牛頓法計算海森矩陣比較麻煩,所以它使用正定矩陣來代替海森矩陣的逆矩陣,從而簡化了計算過程.

常用的擬牛頓法有DFP演算法和BFGS演算法.

4.共軛梯度法(Conjugate Gradient)

共軛梯度法是介於最速下降法與牛頓法之間的一個方法,它僅需利用一階導數信息,但克服了最速下降法收斂慢的缺點,又避免了牛頓法計算海森矩陣並求逆的缺點.共軛梯度法不僅是解決大型線性方程組最有用的方法之一,也是解大型非線性最優化最有效的演算法之一.

5.拉格朗日法

參考SVM里的講解 機器學習-SVM

6.動量優化法(Momentum)

動量優化法主要是在SGD的基礎上,加入了歷史的梯度更新信息或者說是加入了速度更新.SGD雖然是很流行的優化演算法,但是其學習過程很慢,因為總是以同樣的步長沿著梯度下降的方向.所以動量是為了加速學習的方法.

其中第一行的減號部分是計算當前的梯度,第一行是根據梯度更新速度v,而α是新引進的參數,在實踐中,α的一般取值為 0.5,0.9 和 0.99.和學習率 一樣,α 也會隨著時間不斷調整.一般初始值是一個較小的值,隨後會慢慢變大.

7.Nesterov加速梯度(NAG, Nesterov accelerated gradient)

NAG是在動量優化演算法的基礎上又進行了改進.根據下圖可以看出,Nesterov 動量和標准動量之間的區別體現在梯度計算上, Nesterov 動量中,梯度計算在施加當前速度之後.因此,Nesterov 動量可以解釋為往標准動量方法中添加了一個校正因子

8.AdaGrad演算法

AdaGrad演算法,自適應優化演算法的一種,獨立地適應所有模型參數的學習率,縮放每個參數反比於其所有梯度歷史平均值總和的平方根.具有代價函數最大梯度的參數相應地有個快速下降的學習率,而具有小梯度的參數在學習率上有相對較小的下降.通俗一點的講,就是根據實際情況更改學習率,比如模型快要收斂的時候,學習率步長就會小一點,防止跳出最優解.

其中g是梯度,第一行的分母是計算累計梯度的平方根, 是為了防止分母為0加上的極小常數項,α是學習率.

Adagrad的主要優點是不需要人為的調節學習率,它可以自動調節.但是依然需要設置一個初始的全局學習率.缺點是隨著迭代次數增多,學習率會越來越小,最終會趨近於0.

9.RMSProp演算法

RMSProp修改 AdaGrad 以在非凸設定下效果更好,改變梯度積累為指數加權的移動平均.AdaGrad旨在應用於凸問題時快速收斂.

10.AdaDelta演算法

11.Adam演算法

Adam是Momentum和RMSprop的結合體,也就是帶動量的自適應優化演算法.

12.Nadam演算法

13.模擬退火演算法

14.蟻群演算法

15.遺傳演算法

動量是為了加快學習速度,而自適應是為了加快收斂速度,注意學習速度快不一定收斂速度就快,比如步長大學習速度快,但是很容易跳出極值點,在極值點附近波動,很難達到收斂.

未完待定....

參考:

《統計學習方法》  李航    著

《深度學習》  花書

㈡ 常用優化器演算法歸納介紹

優化器是神經網路訓練過程中，進行梯度下降以尋找最優解的優化方法。不同方法通過不同方式（如附加動量項，學習率自適應變化等）側重於解決不同的問題，但最終大都是為了加快訓練速度。

這里就介紹幾種常見的優化器，包括其原理、數學公式、核心思想及其性能；

核心思想： 即針對每次輸入的訓練數據，計算輸出預測與真值的Loss的梯度；

從表達式來看，網路中參數的更新，是不斷向著最小化Loss函數的方向移動的：

優點:
簡單易懂，即對於相應的最優解（這里認為是Loss的最小函數），每次變數更新都是沿著局部梯度下降最快的方向，從而最小化損失函數。

缺點:

不同於標准梯度下降法（Gradient Descent）一次計算所有數據樣本的Loss並計算相應的梯度，批量梯度下降法（BGD, Batch Gradient Descent）每次只取一個小批次的數據及其真實標簽進行訓練，稱這個批次為mini-batch；

優點：

缺點：
隨機梯度下降法的 batch size 選擇不當可能導致模型難以收斂；由於這種方法是在一次更新中，就對整個數據集計算梯度，所以計算起來非常慢，遇到很大量的數據集也會非常棘手，而且不能投入新數據實時更新模型。

我們會事先定義一個迭代次數 epoch，首先計算梯度向量 params_grad，然後沿著梯度的方向更新參數 params，learning rate 決定了我們每一步邁多大。

Batch gradient descent 對於凸函數可以收斂到全局極小值，對於非凸函數可以收斂到局部極小值。

和 BGD 的一次用所有數據計算梯度相比，SGD 每次更新時對每個樣本進行梯度更新，對於很大的數據集來說，可能會有相似的樣本，這樣 BGD 在計算梯度時會出現冗餘，而 SGD 一次只進行一次更新，就沒有冗餘，而且比較快，並且可以新增樣本。

即訓練時，每次只從一批訓練樣本中隨機選取一個樣本進行梯度下降；對隨機梯度下降來說，只需要一次關注一個訓練樣本，一點點把參數朝著全局最小值的方向進行修改了。

整體數據集是個循環，其中對每個樣本進行一次參數更新

缺點：

梯度下降速度比較慢，而且每次梯度更新時往往只專注與局部最優點，而不會恰好指向全局最優點；

單樣本梯度更新時會引入許多雜訊（跟訓練目標無關的特徵也會被歸為該樣本分類的特徵）；

SGD 因為更新比較頻繁，會造成 cost function 有嚴重的震盪。

BGD 可以收斂到局部極小值，當然 SGD 的震盪可能會跳到更好的局部極小值處。

當我們稍微減小 learning rate，SGD 和 BGD 的收斂性是一樣的。

優點：

當處理大量數據時，比如SSD或者faster-rcnn等目標檢測模型，每個樣本都有大量候選框參與訓練，這時使用隨機梯度下降法能夠加快梯度的計算。

隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況，那麼可能只用其中部分的樣本，就已經將 迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。缺點是SGD的噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。所以雖然訓練速度快，但是准確度下降，並不是全局最優。雖然包含一定的隨機性，但是從期望上來看，它是等於正確的導數的。

梯度更新規則：

MBGD 每一次利用一小批樣本，即 n 個樣本進行計算，這樣它可以降低參數更新時的方差，收斂更穩定，另一方面可以充分地利用深度學習庫中高度優化的矩陣操作來進行更有效的梯度計算。

和 SGD 的區別是每一次循環不是作用於每個樣本，而是具有 n 個樣本的批次。

超參數設定值: n 一般取值在 50～256

缺點：（兩大缺點）

鞍點就是：一個光滑函數的鞍點鄰域的曲線，曲面，或超曲面，都位於這點的切線的不同邊。例如這個二維圖形，像個馬鞍：在x-軸方嚮往上曲，在y-軸方嚮往下曲，鞍點就是（0，0）。

為了應對上面的兩點挑戰就有了下面這些演算法

核心思想：

不使用動量優化時，每次訓練的梯度下降方向，都是按照當前批次訓練數據計算的，可能並不能代表整個數據集，並且會有許多雜訊，下降曲線波動較大：

添加動量項之後，能夠有效減小波動，從而加快訓練速度：

當我們將一個小球從山上滾下來時，沒有阻力的話，它的動量會越來越大，但是如果遇到了阻力，速度就會變小。
加入的這一項，可以使得梯度方向不變的維度上速度變快，梯度方向有所改變的維度上的更新速度變慢，這樣就可以加快收斂並減小震盪。

優點：

通過動量更新，參數向量會在有持續梯度的方向上增加速度；
使梯度下降時的折返情況減輕，從而加快訓練速度；

缺點：

如果數據集分類復雜，會導致 和 時刻梯度 向量方向相差較大；在進行向量求和時，得到的 會非常小，反而使訓練速度大大下降甚至模型難以收斂。

這種情況相當於小球從山上滾下來時是在盲目地沿著坡滾，如果它能具備一些先知，例如快要上坡時，就知道需要減速了的話，適應性會更好。

目前為止，我們可以做到，在更新梯度時順應 loss function 的梯度來調整速度，並且對 SGD 進行加速。

核心思想：

自適應學習率優化演算法針對於機器學習模型的學習率，採用不同的策略來調整訓練過程中的學習率，從而大大提高訓練速度。

這個演算法就可以對低頻的參數做較大的更新，對高頻的做較小的更新，也因此，對於稀疏的數據它的表現很好，很好地提高了 SGD 的魯棒性，例如識別 Youtube 視頻裡面的貓，訓練 GloVe word embeddings，因為它們都是需要在低頻的特徵上有更大的更新。

Adagrad 的優點是減少了學習率的手動調節

式中， 表示第 個分類， 表示第 迭代同時也表示分類 累計出現的次數。 表示初始的學習率取值（一般為0.01）

AdaGrad的核心思想： 縮放每個參數反比於其所有梯度歷史平均值總和的平方根。具有代價函數最大梯度的參數相應地有較大的學習率，而具有小梯度的參數又較小的學習率。

缺點：

它的缺點是分母會不斷積累，這樣學習率就會收縮並最終會變得非常小。

這個演算法是對 Adagrad 的改進，

和 Adagrad 相比，就是分母的 換成了過去的梯度平方的衰減平均值，指數衰減平均值

這個分母相當於梯度的均方根 root mean squared (RMS)，在數據統計分析中，將所有值平方求和，求其均值，再開平方，就得到均方根值 ，所以可以用 RMS 簡寫：

其中 的計算公式如下， 時刻的依賴於前一時刻的平均和當前的梯度：

梯度更新規則:

此外，還將學習率 換成了 RMS[Δθ]，這樣的話，我們甚至都不需要提前設定學習率了：

超參數設定值: 一般設定為 0.9

RMSprop 是 Geoff Hinton 提出的一種自適應學習率方法。

RMSprop 和 Adadelta 都是為了解決 Adagrad 學習率急劇下降問題的，

梯度更新規則:

RMSprop 與 Adadelta 的第一種形式相同：（使用的是指數加權平均，旨在消除梯度下降中的擺動，與Momentum的效果一樣，某一維度的導數比較大，則指數加權平均就大，某一維度的導數比較小，則其指數加權平均就小，這樣就保證了各維度導數都在一個量級，進而減少了擺動。允許使用一個更大的學習率η）

超參數設定值:

Hinton 建議設定 為 0.9, 學習率 為 0.001。

這個演算法是另一種計算每個參數的自適應學習率的方法。相當於 RMSprop + Momentum

除了像 Adadelta 和 RMSprop 一樣存儲了過去梯度的平方 vt 的指數衰減平均值 ，也像 momentum 一樣保持了過去梯度 mt 的指數衰減平均值：

如果 和 被初始化為 0 向量，那它們就會向 0 偏置，所以做了偏差校正，通過計算偏差校正後的 和 來抵消這些偏差：

梯度更新規則:

超參數設定值:
建議

示例一

示例二

示例三

上面情況都可以看出，Adagrad, Adadelta, RMSprop 幾乎很快就找到了正確的方向並前進，收斂速度也相當快，而其它方法要麼很慢，要麼走了很多彎路才找到。

由圖可知自適應學習率方法即 Adagrad, Adadelta, RMSprop, Adam 在這種情景下會更合適而且收斂性更好。

如果數據是稀疏的，就用自適用方法，即 Adagrad, Adadelta, RMSprop, Adam。

RMSprop, Adadelta, Adam 在很多情況下的效果是相似的。

Adam 就是在 RMSprop 的基礎上加了 bias-correction 和 momentum，

隨著梯度變的稀疏，Adam 比 RMSprop 效果會好。

整體來講，Adam 是最好的選擇。

很多論文里都會用 SGD，沒有 momentum 等。SGD 雖然能達到極小值，但是比其它演算法用的時間長，而且可能會被困在鞍點。

如果需要更快的收斂，或者是訓練更深更復雜的神經網路，需要用一種自適應的演算法。

各種優化器Optimizer原理：從SGD到AdamOptimizer

深度學習——優化器演算法Optimizer詳解（BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam）

㈢ 實際工程中的優化演算法主要有哪些

優化演算法有很多，關鍵是針對不同的優化問題，例如可行解變數的取值（連續還是離散）、目標函數和約束條件的復雜程度（線性還是非線性）等，應用不同的演算法。
對於連續和線性等較簡單的問題，可以選擇一些經典演算法，如梯度、Hessian 矩陣、拉格朗日乘數、單純形法、梯度下降法等。
而對於更復雜的問題，則可考慮用一些智能優化演算法，如遺傳演算法和蟻群演算法，此外還包括模擬退火、禁忌搜索、粒子群演算法等。

㈣ 想知道優化演算法是什麼

優化演算法是通過改善計算方式來最小化或最大化損失函數E(x)。模型內部有些參數是用來計算測試集中目標值Y的真實值和預測值的偏差程度的，基於這些參數就形成了損失函數E(x)，比如說，權重(W)和偏差(b)就是這樣的內部參數，一般用於計算輸出值，在訓練神經網路模型時起到主要作用。

優化演算法分的分類

一階優化演算法是使用各參數的梯度值來最小化或最大化損失函數E(x），最常用的一階優化演算法是梯度下降。函數梯度導數dy/dx的多變數表達式，用來表示y相對於x的瞬時變化率。

二階優化演算法是使用了二階導數也叫做Hessian方法來最小化或最大化損失函數，由於二階導數的計算成本很高，所以這種方法並沒有廣泛使用。

㈤ 優化演算法筆記（一）優化演算法的介紹

（以下描述，均不是學術用語，僅供大家快樂的閱讀）

        我們常見常用的演算法有排序演算法,字元串遍歷演算法,尋路演算法等。這些演算法都是為了解決特定的問題而被提出。

        演算法本質是一種按照固定步驟執行的過程。

        優化演算法也是這樣一種過程，是一種根據概率按照固定步驟尋求問題的最優解的過程。與常見的排序演算法、尋路演算法不同的是，優化演算法不具備等冪性，是一種 概率演算法 。演算法不斷的 迭代 執行同一步驟直到結束，其流程如下圖。

        等冪性即 對於同樣的輸入，輸出是相同的 。

        比如圖1，對於給定的魚和給定的熊掌，我們在相同的條件下一定可以知道它們誰更重，當然，相同的條件是指魚和熊掌處於相同的重力作用下，且不用考慮水分流失的影響。在這些給定的條件下，我們（無論是誰）都將得出相同的結論，魚更重或者熊掌更重。我們可以認為，秤是一個等冪性的演算法（工具）。

        現在把問題變一變，問魚與熊掌你更愛哪個，那麼現在，這個問題，每個人的答案可能不會一樣，魚與熊掌各有所愛。說明喜愛這個演算法不是一個等冪性演算法。當然你可能會問，哪個更重，和更喜歡哪個這兩個問題一個是客觀問題，一個是主觀問題，主觀問題沒有確切的答案的。當我們處理主觀問題時，也會將其轉換成客觀問題，比如給喜歡魚和喜歡熊掌的程度打個分，再去尋求答案，畢竟計算機沒有感情，只認0和1（量子計算機我不認識你）。

        說完了等冪性，再來說什麼是概率演算法。簡單來說就是看臉、看人品、看運氣的演算法。

        有一場考試，考試的內容全部取自課本，同時老師根據自己的經驗給同學們劃了重點，但是因為試卷並不是該老師所出，也會有考試內容不在重點之內，老師估計試卷中至少80%內容都在重點中。學霸和學渣參加了考試，學霸為了考滿分所以無視重點，學渣為了pass，因此只看了重點。這樣做的結果一定是score(學霸)>=score(學渣)。

        當重點跟上圖一樣的時候，所有的內容都是重點的時候，學霸和學渣的學習策略變成了相同的策略，則score(學霸)=score(學渣)。但同時，學渣也要付出跟學霸相同的努力去學習這些內容，學渣心裡苦啊。

        當課本如下圖時

        學霸？學霸人呢，哪去了快來學習啊，不是說學習一時爽，一直學習一直爽嗎，快來啊，還等什麼。

        這時，如果重點內容遠少於書本內容時，學渣的學習策略有了優勢——花費的時間和精力較少。但是同時，學渣的分數也是一個未知數，可能得到80分也可能拿到100分，分數完全取決於重點內容與題目的契合度，契合度越高，分數越高。對學渣來說，自己具體能考多少分無法由自己決定，但是好在能夠知道大概的分數范圍。

        學霸的學習策略是一種遍歷性演算法，他會遍歷、通讀全部內容，以保證滿分。

        學渣的學習策略則是一種概率演算法，他只會遍歷、學習重點內容，但至於這些重點是不是真重點他也不知道。

        與遍歷演算法相比，概率演算法的結果具有不確定性，可能很好，也可能很差，但是會消耗更少的資源，比如時間（人生），空間（記憶）。概率演算法的最大優點就是 花費較少的代價來獲取最高的收益 ，在現實中體現於節省時間，使用很少的時間得到一個不與最優解相差較多的結果。

        「莊子：吾生也有涯，而知也無涯；以有涯隨無涯，殆矣。」的意思是：人生是有限的，但知識是無限的（沒有邊界的），用有限的人生追求無限的知識，是必然失敗的。

        生活中概率演算法（思想）的應用其實比較廣泛，只是我們很少去注意罷了。關於概率演算法還衍生出了一些有趣的理論，比如墨菲定律和倖存者偏差，此處不再詳述。

        上面說到，優化演算法就是不停的執行同樣的策略、步驟直到結束。為什麼要這樣呢？因為優化演算法是一種概率演算法，執行一次操作就得到最優結果幾乎是不可能的，重復多次取得最優的概率也會增大。

        栗子又來了，要從1-10這10個數中取出一個大於9的數，只取1次，達到要求的概率為10%，取2次，達到要求的概率為19%。

        可以看出取到第10次時，達到要求的概率幾乎65%，取到100次時，達到要求的概率能接近100%。優化演算法就是這樣簡單粗暴的來求解問題的嗎？非也，這並不是一個恰當的例子，因為每次取數的操作之間是相互獨立的，第2次取數的結果不受第1次取數結果的影響，假設前99次都沒達到要求，那麼再取一次達到要求的概率跟取一次達到要求的概率相同。

        優化演算法中，後一次的計算會依賴前一次的結果，以保證後一次的結果不會差於前一次的結果。這就不得不談到馬爾可夫鏈了。

        由鐵組成的鏈叫做鐵鏈，同理可得，馬爾可夫鏈就是馬爾可夫組成的鏈。

        言歸正傳, 馬爾可夫鏈（Markov Chain, MC） ,描述的是 狀態轉移的過程中,當前狀態轉移的概率只取決於上一步的狀態,與其他步的狀態無關 。簡單來說就是當前的結果只受上一步的結果的影響。每當我看到馬爾可夫鏈時，我都會陷入沉思，生活中、或者歷史中有太多太多與馬爾可夫鏈相似的東西。西歐封建等級制度中「附庸的附庸不是我的附庸」與「昨天的努力決定今天的生活，今天的努力決定明天的生活」，你的下一份工作的工資大多由你當前的工資決定，這些都與馬爾可夫鏈有異曲同工之處。

        還是從1-10這10個數中取出一個大於9的數的這個例子。基於馬爾可夫鏈的概率演算法在取數時需要使當前取的數不小於上一次取的數。比如上次取到了3，那麼下次只能在3-10這幾個數中取，這樣一來，達到目標的概率應該會顯著提升。還是用數據說話。

        取1次達到要求的概率仍然是

        取2次內達到要求的概率為

        取3次內達到要求的概率為

        取4次內……太麻煩了算了不算了

        可以看出基於馬爾可夫鏈來取數時，3次內能達到要求的概率與不用馬爾可夫鏈時取6次的概率相當。說明基於馬爾可夫鏈的概率演算法求解效率明顯高於隨機概率演算法。那為什麼不將所有的演算法都基於馬爾可夫鏈呢？原因一，其實現方式不是那麼簡單，例子中我們規定了取數的規則是復合馬爾可夫鏈的，而在其他問題中我們需要建立適當的復合馬爾科夫鏈的模型才能使用。原因二，並不是所有的問題都符合馬爾科夫鏈條件，比如原子內電子出現的位置，女朋友為什麼會生（lou）氣，彩票號碼的規律等，建立模型必須與問題有相似之處才能較好的解決問題。

        介紹完了優化演算法，再來討論討論優化演算法的使用場景。

        前面說了優化演算法是一種概率演算法，無法保證一定能得到最優解，故如果要求結果必須是確定、穩定的值，則無法使用優化演算法求解。

        例1，求城市a與城市b間的最短路線。如果結果用來修建高速、高鐵，那麼其結果必定是唯一確定的值，因為修路寸土寸金，必須選取最優解使花費最少。但如果結果是用來趕路，那麼即使沒有選到最優的路線，我們可能也不會有太大的損失。

        例2，求城市a與城市b間的最短路線，即使有兩條路徑，路徑1和路徑2，它們從a到b的距離相同，我們也可以得出這兩條路徑均為滿足條件的解。現在將問題改一下，求城市a到城市b耗時最少的線路。現在我們無法馬上得出確切的答案，因為最短的線路可能並不是最快的路線，還需要考慮到天氣，交通路況等因素，該問題的結果是一個動態的結果，不同的時間不同的天氣我們很可能得出不同的結果。

        現實生產、生活中，也有不少的場景使用的優化演算法。例如我們的使用的美圖軟體，停車場車牌識別，人臉識別等，其底層參數可能使用了優化演算法來加速參數計算，其參數的細微差別對結果的影響不太大，需要較快的得出誤差范圍內的參數即可；電商的推薦系統等也使用了優化演算法來加速參數的訓練和收斂，我們會發現每次刷新時，推給我們的商品都有幾個會發生變化，而且隨著我們對商品的瀏覽，系統推給我們的商品也會發生變化，其結果是動態變化的；打車軟體的訂單系統，會根據司機和客人的位置，區域等來派發司機給客人，不同的區域，不同的路況，派發的司機也是動態變化的。

        綜上我們可以大致總結一下推薦、不推薦使用優化演算法的場景的特點。

        前面說過，優化演算法處理的問題都是客觀的問題，如果遇到主觀的問題，比如「我孰與城北徐公美」，我們需要將這個問題進行量化而轉換成客觀的問題，如身高——「修八尺有餘」，「外貌——形貌昳麗」，自信度——「明日徐公來，孰視之，自以為不如；窺鏡而自視，又弗如遠甚」，轉化成客觀問題後我們可以得到各個解的分數，通過比較分數，我們就能知道如何取捨如何優化。這個轉化過程叫做問題的建模過程，建立的問題模型實際上是一個函數，這個函數對優化演算法來說是一個黑盒函數，即不需要知道其內部實現只需要給出輸入，得到輸出。

        在優化演算法中這個黑盒函數叫做 適應度函數 ， 優化演算法的求解過程就是尋找適應度函數最優解的過程 ，使用優化演算法時我們最大的挑戰就是如何將抽象的問題建立成具體的模型，一旦合適的模型建立完成，我們就可以愉快的使用優化演算法來求解問題啦。（「合適」二字談何容易）

        優化演算法的大致介紹到此結束，後面我們會依次介紹常見、經典的優化演算法，並探究其參數對演算法性能的影響。

——2019.06.20

[目錄]

[下一篇 優化演算法筆記（二）優化演算法的分類]

㈥ 幾種常用最優化方法

學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習演算法，大部分的機器學習演算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的優化方法(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的筆記 - 博客園

㈦ 優化演算法是什麼呢

優化演算法是指對演算法的有關性能進行優化，如時間復雜度、空間復雜度、正確性、健壯性。

大數據時代到來，演算法要處理數據的數量級也越來越大以及處理問題的場景千變萬化。為了增強演算法的處理問題的能力，對演算法進行優化是必不可少的。演算法優化一般是對演算法結構和收斂性進行優化。

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

遺傳演算法

遺傳演算法也是受自然科學的啟發。這類演算法的運行過程是先隨機生成一組解，稱之為種群。在優化過程中的每一步，演算法會計算整個種群的成本函數，從而得到一個有關題解的排序，在對題解排序之後，一個新的種群----稱之為下一代就被創建出來了。首先，我們將當前種群中位於最頂端的題解加入其所在的新種群中，稱之為精英選拔法。新種群中的餘下部分是由修改最優解後形成的全新解組成。

常用的有兩種修改題解的方法。其中一種稱為變異，其做法是對一個既有解進行微小的、簡單的、隨機的改變；修改題解的另一種方法稱為交叉或配對，這種方法是選取最優解種的兩個解，然後將它們按某種方式進行組合。爾後，這一過程會一直重復進行，直到達到指定的迭代次數，或者連續經過數代後題解都沒有改善時停止。

㈧ 100維度用什麼優化演算法

神經網路中常用的優化演算法。
優化演算法的目的：
1. 跳出局部極值點或鞍點，尋找全局最小值；
2.使訓練過程更加穩定，更加容易收斂。
優化演算法：深度學習優化學習方法（一階、二階）
一階方法：隨機梯度下降（SGD）、動量（Momentum）、牛頓動量法（Nesterov動量）、AdaGrad（自適應梯度）、RMSProp（均方差傳播）、Adam、Nadam。
二階方法：牛頓法、擬牛頓法、共軛梯度法（CG）、BFGS、L-BFGS。
自適應優化演算法有哪些？（Adagrad（累積梯度平方）、RMSProp（累積梯度平方的滑動平均）、Adam（帶動量的RMSProp，即同時使用梯度的一、二階矩））。
梯度下降陷入局部最優有什麼解決辦法？可以用BGD、SGD、MBGD、momentum，RMSprop，Adam等方法來避免陷入局部最優。