常用的三種機器學(xué)習(xí)優(yōu)化算法介紹和比較

在本文中，作者對常用的三種機器學(xué)習(xí)優(yōu)化算法（牛頓法、梯度下降法、最速下降法）進行了介紹和比較，并結(jié)合算法的數(shù)學(xué)原理和實際案例給出了優(yōu)化算法選擇的一些建議。

閱讀本文的基礎(chǔ)準備

線性代數(shù)

多變量微積分

對凸函數(shù)的基本知識

我們都知道，機器學(xué)習(xí)中最重要的內(nèi)容之一就是優(yōu)化問題。因此，找到一個能夠?qū)瘮?shù)做合理優(yōu)化的算法始終是我們關(guān)注的問題。當(dāng)前，我們使用最多的優(yōu)化算法之一是梯度下降算法。在本文中，我們會對梯度下降算法以及一些其他的優(yōu)化算法進行介紹，并嘗試從理論角度來理解它們。本文介紹的核心算法包括：

牛頓法（Newton’s Method）

最速下降法（Steep Descent）

梯度下降法（Gradient Descent）

如果想對這些算法有更多了解，你可以閱讀斯坦福大學(xué)的《凸函數(shù)優(yōu)化—：第三部分》教材。在本文中，我們主要關(guān)注二次函數(shù)和多項式函數(shù)。

對待優(yōu)化函數(shù)的基本假設(shè)

一般而言，我們假設(shè)我們處理的函數(shù)的導(dǎo)數(shù)都是連續(xù)的（例如，f ∈ C1）。對于牛頓法，我們還需要假設(shè)函數(shù)的二階導(dǎo)數(shù)也是連續(xù)的（例如， f ∈ C2）。最后，我們還需要假設(shè)需要最小化的函數(shù)是凸函數(shù)。這樣一來，如果我們的算法集中到一個點（一般稱為局部最小值），我們就可以保證這個值是一個全局最優(yōu)。

牛頓法

單變量函數(shù)的情況

x_n = starting pointx_n1 = x_n - (f'(x_n)/f''(x_n))while (f(x_n) != f(x_n1)): x_n = x_n1 x_n1 = x_n - (f'(x_n)/f''(x_n))

牛頓法的基本思想是，需要優(yōu)化的函數(shù)f在局部可以近似表示為一個二次函數(shù)。我們只需要找到這個二次函數(shù)的最小值，并將該點的x值記錄下來。之后重復(fù)這一步驟，直到最小值不再變化為止。

多變量函數(shù)的情況

對于單變量的情況，牛頓法比較可靠。但是在實際問題中，我們處理的單變量情形其實很少。大多數(shù)時候，我們需要優(yōu)化的函數(shù)都包含很多變量（例如，定義在實數(shù)集?n的函數(shù)）。因此，這里我們需要對多變量的情形進行討論。

假設(shè)x∈ ?n，則有：

x_n = starting_pointx_n1 = x_n - inverse(hessian_matrix) (gradient(x_n))while (f(x_n) != f(x_n1)):x_n = x_n1x_n1=x_n-inverse(hessian_matrix)(gradient(x_n))

其中，gradient(x_n)是函數(shù)位于x_n點時的梯度向量，hessian_matrix是一個尺寸為 nxn 的黑塞矩陣（hessian matrix），其值是函數(shù)位于x_n的二階導(dǎo)數(shù)。我們都知道，矩陣轉(zhuǎn)換的算法復(fù)雜度是非常高的（O(n3)），因此牛頓法在這種情形下并不常用。

梯度下降

梯度下降是目前為止在機器學(xué)習(xí)和其他優(yōu)化問題中使用的最多的優(yōu)化算法。梯度算法的基本思想是，在每次迭代中向梯度方向走一小步。梯度算法還涉及一個恒定的alpha變量，該變量規(guī)定每次跨步的步長。下面是算法示例：

alpha = small_constantx_n = starting_pointx_n1 = x_n - alpha * gradient(x_n)while (f(x_n) != f(x_n1)): # May take a long time to converge x_n = x_n1 x_n1 = x_n - alpha * gradient(x_n)

這里，alpha是在每次迭代中更新x_n時都需要使用的變量（一般稱為超參數(shù)）。下面我們對alpha值的選擇進行簡單分析。

如果我們選擇一個很大的alpha，我們很可能會越過最優(yōu)點，并離最優(yōu)點越來越遠。事實上，如果alpha的值過大，我們甚至?xí)耆x最優(yōu)點。

當(dāng)alpha的值過大時，10次迭代后的梯度下降情況

另外，如果我們選擇的alpha值過小，則可能需要經(jīng)過非常多次迭代才能找到最優(yōu)值。并且，當(dāng)我們接近最優(yōu)值時，梯度會接近于0。因此 ，如果alpha的值過小，我們有可能永遠都無法到達最優(yōu)點。

當(dāng)alpha的值過小時，10次迭代后的梯度下降情況

因此，我們可能需要多嘗試一些alpha的值，才能找到最優(yōu)的選擇。如果選擇了一個合適的alpha值，我們在迭代時往往能節(jié)省很多時間。

當(dāng)alpha的值合理時，10次迭代后的梯度下降情況

最速下降法

最速下降法和梯度下降法非常相似，但是最速下降法對每次迭代時要求步長的值為最優(yōu)。下面是最速下降法的算法示例：

x_n = starting_pointalpha_k = get_optimizer(f(x_n - alpha * gradient(x_n)))x_n1 = x_n - alpha_n * gradient(x_n)while (f(x_n) != f(x_n1)): x_n = x_n1 alpha_k = get_optimizer(f(x_n - alpha * gradient(x_n))) x_n1 = x_n - alpha_n * gradient(x_n)

其中，x_n和x_n1是?n上的向量，是算法的輸入，gradient是函數(shù) f 在點x_n的梯度，alpha_k的數(shù)學(xué)表示如下：

因此，在對原始函數(shù)進行優(yōu)化時，我們需要在每一次迭代中對一個內(nèi)部函數(shù)進行優(yōu)化。這樣做的優(yōu)點是，這個內(nèi)部優(yōu)化函數(shù)是一個單變量函數(shù)，它的優(yōu)化不會非常復(fù)雜（例如，我們可以使用牛頓法來作為這里的函數(shù)）。但是在更多情形下，在每一步中優(yōu)化這個函數(shù)都會帶來比較昂貴的花銷。

二次式函數(shù)的特殊情形

對于均方誤差函數(shù)：

其中，I是單位矩陣，y=Qw + b。為了簡化討論，這里我們只考慮尋找權(quán)重w最優(yōu)值的情形（假設(shè)b是連續(xù)的）。將等式y(tǒng)=Qw + b帶入上式并進行一定整理后，我們可以得到如下等式：

現(xiàn)在我們重新查看一下g(α)， 我們會發(fā)現(xiàn)，如果我們使用點αk處的梯度，由于其為最優(yōu)值，該梯度應(yīng)當(dāng)為0。因此我們有如下等式：

對上式進行簡化，并將f的梯度帶入后，我們可以得到對于αk的表示如下：

這就是在二次函數(shù)情形下αk的值。

對二次函數(shù)的收斂性分析

對于定義在?2上的二次函數(shù)，最速下降法一般用來在非常接近最優(yōu)值時使用，使用步數(shù)不超過十步。

二維中的最速下降在4次迭代后的情形

在上圖中，每一次迭代中的改變方向都是垂直的。在3到4次迭代后，我們可以發(fā)現(xiàn)導(dǎo)數(shù)的變化基本可以忽略不計了。

為什么最速下降法應(yīng)用很少？

最速下降法算法遠遠滿足了超參數(shù)調(diào)優(yōu)的需求，并且保證能找到局部最小值。但是為什么該算法應(yīng)用不多呢？最速下降法的問題在于，每一步都需要對 aplha_k 進行優(yōu)化，這樣做的成本相對高昂。

例如，對于二次函數(shù)，每次迭代都需要計算多次矩陣乘法以及向量點乘。但對于梯度下降，每一步只需要計算導(dǎo)數(shù)并更新值就可以了，這樣做的成本遠遠低于最速下降算法。

最速下降算法的另一個問題是對于非凸函數(shù)的優(yōu)化存在困難。對于非凸函數(shù)，aplha_k 可能沒有固定的值。

對于梯度下降法和最速下降法的對比

在這一部分，我們對梯度下降法和最速下降法進行對比，并比較它們在時間代價上的差異。首先，我們對比了兩種算法的時間花銷。我們會創(chuàng)建一個二次函數(shù)：f:?2???→?（該函數(shù)為一個2000x2000的矩陣）。我們將對該函數(shù)進行優(yōu)化，并限制迭代次數(shù)為1000次。之后，我們會對兩種算法的時間花銷進行對比，并查看 x_n 值與最優(yōu)點的距離。

我們先來看一下最速下降法：

0 Diff: 117727672.56583363 alpha value: 8.032725864804974e-06 100 Diff: 9264.791000127792 alpha value: 1.0176428564615889e-05 200 Diff: 1641.154644548893 alpha value: 1.0236993350903281e-05 300 Diff: 590.5089467763901 alpha value: 1.0254560482036439e-05 400 Diff: 279.2355946302414 alpha value: 1.0263893422517941e-05 500 Diff: 155.43169915676117 alpha value: 1.0270028681773919e-05 600 Diff: 96.61812579631805 alpha value: 1.0274280663010468e-05 700 Diff: 64.87719237804413 alpha value: 1.027728512597358e-05 800 Diff: 46.03102707862854 alpha value: 1.0279461929697766e-05 900 Diff: 34.00975978374481 alpha value: 1.0281092917213468e-05 Optimizer found with x = [-1.68825261 5.31853629 -3.45322318 ... 1.59365232 -2.85114689 5.04026352] and f(x)=-511573479.5792374 in 1000 iterationsTotal time taken: 1min 28s

下面是梯度下降法的情況，其中 alpha = 0.000001：

0 Diff: 26206321.312622845 alpha value: 1e-06 100 Diff: 112613.38076114655 alpha value: 1e-06 200 Diff: 21639.659786581993 alpha value: 1e-06 300 Diff: 7891.810685873032 alpha value: 1e-06 400 Diff: 3793.90934664011 alpha value: 1e-06 500 Diff: 2143.767760157585 alpha value: 1e-06 600 Diff: 1348.4947955012321 alpha value: 1e-06 700 Diff: 914.9099299907684 alpha value: 1e-06 800 Diff: 655.9336211681366 alpha value: 1e-06 900 Diff: 490.05882585048676 alpha value: 1e-06 Optimizer found with x = [-1.80862488 4.66644055 -3.08228401 ... 2.46891076 -2.57581774 5.34672724] and f(x)=-511336392.26658595 in 1000 iterationsTotal time taken: 1min 16s

我們可以發(fā)現(xiàn)，梯度下降法的速度比最速下降法略快（幾秒或幾分鐘）。但更重要的是，最速下降法采取的步長比梯度下降法更加合理，盡管梯度下降法的α的值并非最優(yōu)。在上述示例中， 對于梯度下降算法，f(xprex)和f(curr)在第900次迭代時的差為450。而最速下降法在很多次迭代前就已經(jīng)達到這個值了（大約在第300次到第400次迭代之間）。

因此，我們嘗試限制最速下降法的迭代次數(shù)為300，輸出如下：

0 Diff: 118618752.30065191 alpha value: 8.569151292666038e-06 100 Diff: 8281.239207088947 alpha value: 1.1021416896567156e-05 200 Diff: 1463.1741587519646 alpha value: 1.1087402059869253e-05 300 Diff: 526.3014997839928 alpha value: 1.1106776689082503e-05 Optimizer found with x = [-1.33362899 5.89337889 -3.31827817 ... 1.77032789 -2.86779156 4.56444743] and f(x)=-511526291.3367646 in 400 iterationsTime taken: 35.8s

可以發(fā)現(xiàn)，最速下降法的速度實際更快。在此情形中，我們在每次迭代使用更少的步數(shù)就能逼近最優(yōu)值。事實上，如果你的目標(biāo)是估計最優(yōu)值，最速下降法會比梯度下降法更合適。對于低維度的函數(shù)，10步的最速下降法就會比經(jīng)過1000次迭代的梯度下降法更接近最優(yōu)值。

下面這個例子中，我們使用了一個定義在?3?→?上的二次函數(shù)。10步后，最速下降法的得到函數(shù)值為 f(x) = -62434.18。而梯度下降法在1000步后得到的函數(shù)值為 f(x) = -61596.84?？梢园l(fā)現(xiàn)，最速下降法在10步后的結(jié)果就優(yōu)于梯度下降法在1000步后的結(jié)果。

需要記住的是，這種情形僅在處理二次函數(shù)的時候適用。整體而言，在每次迭代中都找到 αk的最優(yōu)值是較為困難的。對函數(shù) g(α) 求最優(yōu)值并不總能得到 αk 的最優(yōu)值。通常，我們會使用迭代的算法來對優(yōu)化函數(shù)求最小值。在這種情形下，最速下降法與梯度下降法相比就比較慢了。因此，最速下降法在實際應(yīng)用中并不常見。

總結(jié)

在本文中，我們學(xué)習(xí)了三種下降算法：

牛頓法（Newton's method）

牛頓法提供了對函數(shù)的二階近似，并在每一步都對函數(shù)進行優(yōu)化。其最大的問題在于，在優(yōu)化過程中需要進行矩陣轉(zhuǎn)換，對于多變量情形花銷過高（尤其是向量的特征較多的時候）。

梯度下降（Gradient Descent）

梯度下降是最常用的優(yōu)化算法。由于該算法在每步只對導(dǎo)數(shù)進行計算，其花銷較低，速度更快。但是在使用該算法時，需要對步長的超參數(shù)進行多次的猜測和嘗試。

最速下降法（Steepest Descent）

最速下降法在每步都對函數(shù)的梯度向量尋找最優(yōu)步長。它的問題在于，在每次迭代中需要對相關(guān)的函數(shù)進行優(yōu)化，這會帶來很多花銷。對于二次函數(shù)的情形，盡管每步都涉及很多矩陣運算，最速下降法的效果仍然更優(yōu)。