機器學習的優化算法概述

機器學習的問題最終都會歸結為對一個優化問題進行求解，而優化問題可以分為無約束優化問題和有約束優化問題。有約束的優化問題是指對于目標函數中的變量有顯式約束條件的，比如0<=x<=100。無約束優化問題是指對于目標函數的變量沒有顯式約束的，或者說可以將約束轉化成目標函數的懲罰項的，比如說正則化項。

大多數機器學習問題最終都要解一個無約束的優化問題，因此本文主要對無約束優化問題及其優化算法做一個概述。下文提到的優化問題都指無約束優化問題。

提到優化問題，自然就要知道優化算法。需要注意的是，沒有一種通用的優化算法可以解決所有的優化問題，不同的算法適用于不同的問題。

一般來講，優化算法采用的是迭代求解的方式。算法會設定一個初始值，然后不斷迭代，直到找到一個最優解。關于如何迭代，不同的算法采取了不同的策略，有的算法利用了目標函數的值，有的算法利用了目標函數的一階導數和二階導數的信息，有的算法利用了前幾輪迭代的信息，有的算法則利用了當前點的局部信息。

對于一個優化問題，如果我們能夠求出它的全局最優，那么問題就一步到位了。而實際上，求解目標函數的全局最優解是很難的，原因在于我們對于目標函數的了解只能是它的局部信息，機器學習所使用的優化算法大都只能求出局部最優值。可能有人會有疑問，既然這些算法只能求出局部最優，那在機器學習中使用這些算法豈不是總也得不到全局最優？幸運的是，機器學習最后所要求解的目標函數大都是凸函數，我們知道，對于凸函數來講，其局部最優就是全局最優，那么這樣一來，那些求解局部最優解的算法就可以用了。

對于這些凸函數來講，有的是可微的，有的則不是。對于后者的求解是相對困難的，但是如果函數只在個別點處不可微，比如f（x） = ||x||₁。這樣的函數求解還是相對容易的。

下面總體介紹一下求解無約束優化問題的算法。

所有求解無約束優化問題的算法都需要設定一個初始值x₀，算法從x₀開始進行迭代，直到取得最優值或者滿足收斂條件為止。關于算法如何從x_k迭代到x_k+1，基本上有兩種做法，這里主要講講直線搜索（line search）。

搜索方向

在直線搜索的方式中，算法首先選擇一個搜索方向（不同的算法選擇的搜索方向不同）p_k，然后沿著這個方向從x_k開始去搜索x_k+1，使得目標函數在x_k+1處的值要更優于在x_k處的值。現在的問題是要沿著p_k走多長，才能找到最優的x_k+1，所以在直線搜索中，一旦搜索方向確定了之后，搜索的是這個步長t的值。這可以通過下面的公式獲得：

（1）

通過求解式（1），我們可以得到最優的t值，但是在實踐中，這樣做的代價是十分大的，也沒有必要，因此實踐中只需要找到一個最小值的近似就可以了，也就是說f（x_k+1）的值相對于f（x_k）的值有足夠的減小即可。在得到x_k+1后，算法會重新計算新的迭代方向和步長。如此往復，直到最終問題求解。

對于直線搜索，我們已經提到了不同的算法會選擇不同的搜索方向。這里我們介紹兩個方向，一個是最速下降方向（steepest descent direction），另一個是牛頓方向（newtown direction）。前者對應的是目標函數的一階導數，而后者對應的是目標函數的二階導數。

最速下降方向

在直線搜索中，對于從x_k出發的所有搜索方向，直覺上來講，沿著梯度負方向是使得目標函數減小最多的方向，也就是我們的最速下降方向。表達式如下：

 （2）

由（2）式可知：

 （3）

基于最速下降法的優化算法在每一步迭代都沿著梯度的負方向進行直線搜索。它的優點是只需要計算目標函數的一階導數；缺點就是算法呈線性收斂，在處理一些復雜問題時速度很慢，甚而至于慢到沒有實用價值。

需要注意的是，最速下降方向僅僅是算法的局部性質。

牛頓方向

牛頓方向對應的優化算法稱為牛頓法。牛頓方向的確定用到了目標函數的二階導數，下式為在第k步迭代時確定的搜索方向。

（4）

這樣一來，x_k+1 = x_k + p_k。這里需要注意的是，我們假設步長t始終等于1。實踐中是以1為初始值對步長進行直線搜索。

將目標函數在x_k處作二階泰勒展開，可得：

 （5）

式（5）的右邊為v的二次函數，要使得式子最小，那么對v求導并令結果式等于0可得：

（6）

求解式（6）可得：

（7）

由此可知，當搜索方向為牛頓方向時，目標函數減少最多。

對于多元函數，其二階導數是一個矩陣，名叫海森矩陣（Hessian Matrix）。

牛頓法在接近局部最小值時為二次收斂，僅需5到6次就可以達到很高的精度，特別是在計算大規模問題時，無論是從收斂速度還是精度來講，都有著最速下降法無法比擬的優勢。牛頓法的缺點在于算法在執行過程中需要計算和存儲海森矩陣以及海森矩陣的逆，當矩陣太大時，計算負荷太重。更為致命的是，目標函數的海森矩陣無法在算法執行期間保持正定，從而使得牛頓法失效。

擬牛頓方向

基于擬牛頓方向的優化算法稱為擬牛頓法。擬牛頓法的思路實際上就是在迭代的每一步用一個矩陣B_k來替代海森矩陣，從而不必計算海森矩陣。B_k在迭代的每一步都會更新，只要B₀為正定，那么任何一步迭代更新的B_k一定保證正定。通過B_k我們可以得到每一步向下一步迭代時的搜索方向。

需要注意的是，擬牛頓法的每一次迭代不能保證一定是最優的下降方向，但是一定是下降的，這樣就保證了每一次迭代后，目標函數的值總會降低。

擬牛頓法的收斂速度沒有牛頓法收斂得快，但是要好于最速下降法的線性收斂。

歸一化

有時候優化算法的性能取決于問題的形式。這其中一個重要的方面就是模型參數（目標函數系數）的歸一化。當目標函數的某一個變量發生變化時，它使得目標函數的值發生很大的變化，而在另外的變量上做相同的改變時，目標函數值的變化遠遠不及上述變化，那么這個問題被認為是沒有歸一化的。比如目標函數為：f(x) = 10¹⁰x₁+ 0.1x₂，那么很小的變化發生在x₁上時，f的值會有很大的變化，但x₂卻不然。這個目標函數就沒有做歸一化。

基于一階導數（梯度）的優化算法對于沒有歸一化的目標函數十分敏感，收斂很慢并且效果不好。但是基于二階導數的牛頓法就不受此影響。

下圖是兩個凸二次函數的等值線，其中第一個表示沒有歸一化的目標函數，第二個表示歸一化后的目標函數。對于第一個等值線，我們可以看出它的一邊被拉得特別長，另一邊又特別扁平，這種問題在工程上屬于病態問題，基于梯度的方法無法快速的收斂到最優值。但是在兩種情況下，基于二階導數的牛頓法（或是擬牛頓法）都能很快收斂到很好的結果。由于實際工程中很多問題無法歸一化，因此這些問題往往是病態的，因此我們在工程上一般都會選用基于二階導數的擬牛頓法來求解無約束的最優化問題。

以上的討論從大體上介紹了求解無約束優化問題的算法。在實際工程的應用中，還是會有些變化。比如說，解決超大規模的優化問題時，即便是擬牛頓法，比如BFGS，也無法很好地解決，原因在于擬牛頓法雖然不用計算和存儲海森矩陣，但要計算和存儲海森矩陣的近似矩陣B，當近似矩陣B很稠密時，算法的計算量和存儲量也是巨大的。因此實踐中一定會用到的方法是L-BFGS算法。該方法十分的重要，掌握了它不僅僅是掌握了一個算法，更重要的是掌握了求解大規模優化問題的一種思想。這個算法將會單獨介紹。

來自： http://blog.csdn.net//henryczj/article/details/41085667