八、梯度下降法和拟牛顿法
- 1、梯度
- 2、梯度上升和梯度下降
- 3、梯度下降算法詳解
- 3.1 直觀解釋
- 3.2 梯度下降相關概念
- 3.3 梯度下降的矩陣描述
- 3.4 梯度下降的算法調優
- 4、梯度下降法大家族
- 5、梯度下降法和其他無約束優化算法的比較
- July解釋
- 6、擬牛頓法
- 6.1 牛頓法
- 6.2 擬牛頓法
1、梯度
梯度下降經典總結
微積分里邊，對多元函數求偏導數，把求得的各個參數的偏導數以向量的形式寫出來就是梯度。
對函數f(x,y)f(x,y)分別求x，y的偏導數，求得的梯度向量就是(?f?x,?f?y)T(?f?x,?f?y)T
梯度向量的意義：就是函數變化增加最快的地方，也就是函數在某點上，沿著其梯度向量的方向就是函數增加最快的地方。或者說沿著梯度向量的方向，更容易找到函數的最大值，換句話說沿著梯度向量相反的方向，梯度減小的最快，更容易找到函數的最小值。
2、梯度上升和梯度下降
機器學習算法中，在最小化損失函數的時候，可以通過梯度下降法來一步步迭代求解，得到最小化的損失函數和模型參數。相反，如果需要求解損失函數的最大值，這時就需要用梯度上升法來迭代了。
梯度上升和梯度下降可以通過添加負號來轉換。
3、梯度下降算法詳解
3.1 直觀解釋
首先來看看梯度下降的一個直觀的解釋。比如我們在一座大山上的某處位置，由于我們不知道怎么下山，于是決定走一步算一步，也就是在每走到一個位置的時候，求解當前位置的梯度，沿著梯度的負方向，也就是當前最陡峭的位置向下走一步，然后繼續求解當前位置梯度，向這一步所在位置沿著最陡峭最易下山的位置走一步。這樣一步步的走下去，一直走到覺得我們已經到了山腳。當然這樣走下去，有可能我們不能走到山腳，而是到了某一個局部的山峰低處。
從上面的解釋可以看出，梯度下降不一定能夠找到全局的最優解，有可能是一個局部最優解。當然，如果損失函數是凸函數，梯度下降法得到的解就一定是全局最優解。
3.2 梯度下降相關概念
在詳細了解梯度下降的算法之前，我們先看看相關的一些概念。
步長（Learning rate）：步長決定了在梯度下降迭代的過程中，每一步沿梯度負方向前進的長度。用上面下山的例子，步長就是在當前這一步所在位置沿著最陡峭最易下山的位置走的那一步的長度。
特征（feature）：指的是樣本中輸入部分，比如2個單特征的樣本（x(0),y(0)）,（x(1),y(1)）（x(0),y(0)）,（x(1),y(1)），則第一個樣本特征為x(0)x(0)，第一個樣本輸出為y(0)y(0)。
假設函數（hypothesis function）：在監督學習中，為了擬合輸入樣本，而使用的假設函數，記為hθ(x)hθ(x)。比如對于單個特征的m個樣本（x(i),y(i)）(i=1,2,...m),（x(i),y(i)）(i=1,2,...m),可以采用擬合函數如下： hθ(x)=θ0+θ1xhθ(x)=θ0+θ1x。
損失函數（loss function）：為了評估模型擬合的好壞，通常用損失函數來度量擬合的程度。損失函數極小化，意味著擬合程度最好，對應的模型參數即為最優參數。在線性回歸中，損失函數通常為樣本輸出和假設函數的差取平方。比如對于m個樣本（xi,yi）(i=1,2,...m)（xi,yi）(i=1,2,...m),采用線性回歸，損失函數為：
J(θ0,θ1)=∑i=1m(hθ(xi)?yi)2J(θ0,θ1)=∑i=1m(hθ(xi)?yi)2J(θ0,θ1)=∑i=1m(hθ(xi)?yi)2J(θ0,θ1)=∑i=1m(hθ(xi)?yi)2
其中xixi表示第i個樣本特征，yiyi表示第ii個樣本對應的輸出，hθ(xi)hθ(xi)為假設函數。
3.3 梯度下降的矩陣描述
3.4 梯度下降的算法調優
在使用梯度下降時，需要進行調優。哪些地方需要調優呢？
算法的步長選擇。在前面的算法描述中，我提到取步長為1，但是實際上取值取決于數據樣本，可以多取一些值，從大到小，分別運行算法，看看迭代效果，如果損失函數在變小，說明取值有效，否則要增大步長。前面說了。步長太大，會導致迭代過快，甚至有可能錯過最優解。步長太小，迭代速度太慢，很長時間算法都不能結束。所以算法的步長需要多次運行后才能得到一個較為優的值。
算法參數的初始值選擇。 初始值不同，獲得的最小值也有可能不同，因此梯度下降求得的只是局部最小值；當然如果損失函數是凸函數則一定是最優解。由于有局部最優解的風險，需要多次用不同初始值運行算法，關鍵損失函數的最小值，選擇損失函數最小化的初值。
歸一化。由于樣本不同特征的取值范圍不一樣，可能導致迭代很慢，為了減少特征取值的影響，可以對特征數據歸一化，也就是對于每個特征x，求出它的期望xˉˉˉxˉ和標準差std(x)，然后轉化為：
x?xstd(x)x?xstd(x)這樣特征的新期望為0，新方差為1，迭代次數可以大大加快。
4、梯度下降法大家族
普通的梯度下降算法在更新回歸系數時要遍歷整個數據集，是一種批處理方法，這樣訓練數據特別忙龐大時，可能出現如下問題：
1）收斂過程可能非常慢；
2）如果誤差曲面上有多個局極小值，那么不能保證這個過程會找到全局最小值。
為了解決上面的問題，實際中我們應用的是梯度下降的一種變體被稱為隨機梯度下降。
5、梯度下降法和其他無約束優化算法的比較
在機器學習中的無約束優化算法中，除了梯度下降以外，還有最小二乘法、牛頓法和擬牛頓法。
梯度下降法：
- 需要選擇步長
- 迭代求解
- 當樣本量很大的時候，求解速度快
最小二乘法：
- 不需要選擇步長
- 計算解析解
- 如果樣本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有優勢，計算速度很快。但是如果樣本量很大，用最小二乘法由于需要求一個超級大的逆矩陣，這時就很難或者很慢才能求解解析解了，
擬牛頓法 / 牛頓法：
二階收斂，收斂速度快
同樣也是迭代求解，但是梯度下降法是梯度求解，而牛頓法是用二階的Hessian矩陣的逆矩陣或偽矩陣求解
牛頓法收斂更快，但是每次迭代的時間比梯度下降法長
最小二乘：使誤差「所謂誤差，當然是觀察值與實際真實值的差量」平方和達到最小以尋求估計值的方法，就叫做最小二乘法，用最小二乘法得到的估計，叫做最小二乘估計。
勒讓德在論文中對最小二乘法的優良性做了幾點說明：
- 最小二乘使得誤差平方和最小，并在各個方程的誤差之間建立了一種平衡，從而防止某一個極端誤差取得支配地位
- 計算中只要求偏導后求解線性方程組，計算過程明確便捷
- 最小二乘可以導出算術平均值作為估計值
July解釋
下面是一個典型的機器學習的過程，首先給出一個輸入數據，我們的算法會通過一系列的過程得到一個估計的函數，這個函數有能力對沒有見過的新數據給出一個新的估計，也被稱為構建一個模型。
我們用X1，X2..XnX1，X2..Xn去描述feature里面的分量，比如X1=房間的面積，X2=房間的朝向等等，我們可以做出一個估計函數：
θ在這兒稱為參數，在這兒的意思是調整feature中每個分量的影響力，就是到底是房屋的面積更重要還是房屋的地段更重要。為了如果我們令X0 = 1，就可以用向量的方式來表示了：
我們程序也需要一個機制去評估我們θ是否比較好，所以說需要對我們做出的h函數進行評估，一般這個進行評估的函數稱為損失函數（loss function），描述h函數不好的程度，在下面，我們稱這個函數為J函數
在這兒我們可以做出下面的一個損失函數：
換言之，我們把對x(i)的估計值與真實值y(i)差的平方和作為損失函數，前面乘上的1/2是為了在求導的時候，這個系數就不見了。
如何調整θ以使得J(θ)取得最小值有很多方法，其中有最小二乘法(min square)，是一種完全是數學描述的方法，另外一種就是梯度下降法。
梯度下降法的算法流程如下：
首先對θ賦值，這個值可以是隨機的，也可以讓θ是一個全零的向量。
改變θ的值，使得J(θ)按梯度下降的方向進行減少。
為了描述的更清楚，給出下面的圖：
這是一個表示參數θ與誤差函數J(θ)J(θ)的關系圖，紅色的部分是表示J(θ)J(θ)有著比較高的取值，我們需要的是，能夠讓J(θ)的值盡量的低，也就是達到深藍色的部分。θ0θ0，θ1θ1表示θθ向量的兩個維度。
在上面提到梯度下降法的第一步是給θ給一個初值，假設隨機給的初值是在圖上的十字點。
然后我們將θ按照梯度下降的方向進行調整，就會使得J(θ)J(θ)往更低的方向進行變化，如下圖所示，算法的結束將是在θθ下降到無法繼續下降為止。
當然，可能梯度下降的最終點并非是全局最小點，即也可能是一個局部最小點，如下圖所示：
上面這張圖就是描述的一個局部最小點，這是我們重新選擇了一個初始點得到的，看來我們這個算法將會在很大的程度上被初始點的選擇影響而陷入局部最小點。
下面我將用一個例子描述一下梯度減少的過程，對于我們的函數J(θ)求偏導J：
下面是更新的過程，也就是θi會向著梯度最小的方向進行減少。θi表示更新之前的值，-后面的部分表示按梯度方向減少的量，α表示步長，也就是每次按照梯度減少的方向變化多少。
一個很重要的地方值得注意的是，梯度是有方向的，對于一個向量θ，每一維分量θi都可以求出一個梯度的方向，我們就可以找到一個整體的方向，在變化的時候，我們就朝著下降最多的方向進行變化就可以達到一個最小點，不管它是局部的還是全局的。
用更簡單的數學語言進行描述步驟2）是這樣的：
梯度下降法找到的一定是下降最快的方向么？機器學習 ML基礎 中
梯度下降法并不是下降最快的方向，它只是目標函數在當前的點的切平面（當然高維問題不能叫平面）上下降最快的方向。在practical implementation中，牛頓方向（考慮海森矩陣）才一般被認為是下降最快的方向，可以達到superlinear的收斂速度。梯度下降類的算法的收斂速度一般是linear甚至sublinear的（在某些帶復雜約束的問題）。
6、擬牛頓法
6.1 牛頓法
假設x?x?為函數f(x)f(x)的根，那么有f(x?)=0f(x?)=0，在xkxk處進行一階展開，有：
f(x)=f(xk)+f′(xk)(x?xk)f(x)=f(xk)+f′(xk)(x?xk)假定xk+1xk+1為該方程的根，則有：
f(xk+1)=f(xk)+f′(xk)(xk+1?xk)=0f(xk+1)=f(xk)+f′(xk)(xk+1?xk)=0那么就有：
xk+1=xk?f(xk)f′(xk)xk+1=xk?f(xk)f′(xk)于是就有了一個遞歸方程，可以通過迭代的方式不斷逼近f(x)f(x)的解
牛頓法的思想：因為函數的二階導數反映了函數的凹凸性，而二階導數越大，一階導數的變化越大，所以在搜索中，利用一階導/二階導的形式，可以做些搜索方向的修正。
牛頓法的迭代過程：已知xk處的函數值，和該點的一階導和二階導，可以根據這三個信息，可以擬合得到藍色的線，并且可以求得其極小點，極值點對應xk+dk，這就是一次迭代，就是xk->xk+dk，在xk+dk點，再次通過二次曲線擬合，直至迭代至收斂
牛頓法最優值的步驟如下：
依據迭代公式xk+1=xk?H?1kf'kxk+1=xk?Hk?1f′k 更新xx值
如果E(f(xk+1)?f(xk))<?E(f(xk+1)?f(xk))<?，則收斂返回，否則繼續步驟2,3直至收斂
6.2 擬牛頓法
雅克比矩陣：函數對各自變量的一階導數
Hessian矩陣：函數對自變量的二次微分
當Hessian是正定的(所有特征值都是正的)，則該臨界點是局部極小點。
當Hessian是負定的(所有特征值都是負的)，則該臨界點是局部極大點。
我們這里討論的點都是臨界點，即f’(x) = 0的點，且函數都是連續可導的。
擬牛頓法的思想：
我們可以看到，當我們的特征特別多的時候，求海森矩陣的逆的運算量是非常大且慢的，這對于在實際應用中是不可忍受的，因此我們想能否用一個矩陣來代替海森矩陣的逆呢，這就是擬牛頓法的基本思路。
求Hessian矩陣的逆會影響計算效率，同時，只有搜索方向滿足和負梯度的夾角小于90°即可，所有可以用近似矩陣代替Hessian矩陣，只要其滿足正定、容易求逆即可。
我們要選擇一個矩陣來代替海森矩陣的逆，那么我們首先要研究一下海森矩陣需要具有什么樣的特征才能保證牛頓法成功的應用。通過上面的描述我們將下面的公式稱為擬牛頓條件：
因此對于選擇的代替矩陣GkGk，需要滿足兩個條件：
擬牛頓條件，即Gk(f′(xk+1)?f′(xk))=xk+1?xkGk(f′(xk+1)?f′(xk))=xk+1?xk
要保證GkGk為正定矩陣，因為只有保證為正定矩陣，才能保證牛頓法的搜索方向是下降的。
如何得到替代矩陣：
Goldfeld等于提出，可以用正定矩陣Gk+vkIGk+vkI來代替Hessian矩陣GkGk，計算修正的牛頓方向。
根據下式：
f′(xk)=f′(xk+1)+f′′(xk+1)(xk?xk+1)f′(xk)=f′(xk+1)+f″(xk+1)(xk?xk+1)可得：
gk=gk+1+Hk+1(xk?xk+1)gk=gk+1+Hk+1(xk?xk+1)所以有：
gk+1?gk=Hk+1(xk+1?xk)gk+1?gk=Hk+1(xk+1?xk)為了簡化下面的符合表達式，令：
yk=gk+1?gkyk=gk+1?gk
sk=xk+1?xksk=xk+1?xk
Bk+1=f′′(xk+1)Bk+1=f″(xk+1)
Dk+1=B?1k+1Dk+1=Bk+1?1
于是有：
yk=Bk+1?skyk=Bk+1?sk
sk=Dk+1?yksk=Dk+1?yk
其中：Bk+1Bk+1為Hessian矩陣，Dk+1Dk+1為Hessian矩陣的逆
我們可以看出，Hessian矩陣滿足上面兩個式子
如何在上面兩個條件的基礎上構造Hessian矩陣呢：DFP和BFGS
1、DFP
該算法的核心思想在于通過迭代的方法，逐步改善近似海塞矩陣。我們使用D來表示近似海塞矩陣的逆矩陣。
2、BFGS
BFGS算法是用直接逼近海塞矩陣的方式來構造近似海塞矩陣，同樣，我們使用迭代的方式來逐步逼近。
總結
以上是生活随笔為你收集整理的八、梯度下降法和拟牛顿法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 维信诺：2022 年预计营收超 73 亿
- 下一篇： 什么是 CMOS 传感器