擬牛頓法之DFP演算法剖析

05-12

DFP擬牛頓法也稱為DFP校正方法，是第一個擬牛頓法，由Davidon最早提出，後經Fletcher和Powell解釋和改進，在命名時以三個人名字的首字母命名。那擬牛頓法多數時候均為對二階導hessian矩陣或其逆矩陣的近似逼近，DFP所逼近的就是hessian逆矩陣。

其演算法步驟如下：假設已知目標函數 $f(X)$ 及梯度 $g(X)$ ,迭代輪數n，終止條件 $varepsilon>0$ .

取初始點 $X_0in R^n$ ，精度 $varepsilon>0$ ；
計算 $g_0=Delta f(X)$ ，若 $egin{Vmatrix}g_0end{Vmatrix}leqslant varepsilon$ 則停止，得到權重 $X^*=X_0$ ;否則轉3；
令 $k=1$ ， $H_0=E$ ;
令 $d_k=-{H_k}{g_k}$ ;
求 $lambda_k:min{f(X_k+{lambda}{d_k})}=f(X_k+{lambda_k}{d_k})$ ，令 $s_k={lambda_k}{d_k},X_{k+1}=X_k+s_k$ ;
計算 $g_{k+1}=Delta f(x_{k+1})$ ,若 $egin{Vmatrix}g_{k+1}end{Vmatrix}leqslant varepsilon$ 則停止，得到權重 $X^*=X_{k+1}$ ;否則轉7；
計算 $y_k=g_{k+1} - g_k$ ;
計算 $H_{k+1}=H_k+frac{{s_k}{{s_k}^T}}{{{s_k}^T}{y_k}}-frac{{H_k}{y_k}{{y_k}^T}{H_k}}{{{y_k}^T}{H_k}{y_k}}$ ;
令 $k=k+1$ ，轉4.

求得的X即為每個特徵的權重。一般而言，針對公式 $H_k$ 會補充一個正定的充要條件： ${s_k}^T{y_k}>0$ 。但是在實際實現中，本人發現很多時候， ${s_k}^T{y_k}$ 並不一定大於0，但距離0差距很小，一般在0.0001以內，因此可以將該約束進行放鬆， ${s_k}^T{y_k}>-0.0001$ 這樣。

相比於之前介紹的基於GD的方法，二階擬牛頓法要的實現要複雜的多。就以DFP這個演算法為例。首先，其每次所求必須過全量樣本，這就導致其無法執行如minibatch等類似的方式。當然，這本身是SGD或BGD等的優勢所在。其次，在第5步的求最小步長的過程，該問題本身也是一個優化問題。解決該優化目標的過程叫一維搜索。一維搜索的方法有很多，這裡主要介紹一下採用黃金分割法的實現。主要分為倆步：a. 找出滿足條件的大致下降區間。b. 採用黃金分隔法找出最合適的極小值點。

DFP實現時，在步驟a中，每輪迭代中均採用試探法進行嘗試（假設當前迭代輪數為k）：

初始設定 $lambda_1=0$ ，前進步長 $h_1 in (0,1)$ ，則 $lambda_2=lambda_1+h_1$ ;
計算 $f1={f(X_k+{lambda_1}{d_k})}，f2={f(X_k+{lambda_2}{d_k})}$ ，比較 $f1$ 和 $f2$ ，若 $f1>f2$ ，說明前進方向正確，應該再次前進，因此可激進一些，讓下一次直接前進2倍，即 $h=2h$ ；否則，就後退 $h$ ，並 $swap(f1,f2)$ 和 $swap(lambda_1,lambda_2)$ ，以保持下降方向。
可以再找一個 $lambda_3=lambda_2+h$ ， $f3={f(X_k+{lambda_3}{d_k})}$ 來把控下一次終點是否合理，以用於終止尋找。那通過剛剛的第二步得知， $f2<f1$ ，這裡比較下 $f2$ 和 $f3$ ，看看是否符合下降方向，若符合（ $f2>f3$ ），則繼續尋找，並更新 $f1=f2$ ， $f2=f3$ ， $lambda_1=lambda_2$ ， $lambda_2=lambda_3$ ，這樣的用意是進一步查找到了最小的一個下降區間 $(lambda_1,lambda_2)$ 。這裡如果不滿足下降條件，即（ $f2<=f3$ ），即認為尋找的方向已經終止了，那麼比較下 $lambda_1$ 和 $lambda_3$ 即可找到最小區間，因為 $f2$ 是在這兩個對應的函數 $f1$ 和 $f3$ 之間，極小值點應該就存在這樣的區間內，如此即可終止，返回區間結果。
重新轉向2，再次進行試探。

針對步驟b，採用黃金分割法要簡單的多。畢竟這是初高中的知識，主要是每次採用黃金分割比例（0.618）不斷的縮小區間，然後看區間起始點的f值是否小於最小閾值，若滿足，則將其中間的點返回，否則繼續查找。整個步驟有點類似二分查找。

okay，這裡主要介紹的是採用黃金分割法的DFP擬牛頓法。本人在之前的scalaML工程中進行了實現，DFP代碼為https://github.com/sloth2012/scalaML/blob/master/src/main/scala/com/lx/algos/ml/optim/newton/DFP.scala，使用樣例在https://github.com/sloth2012/scalaML/blob/master/src/test/scala/com/lx/algos/ml/NewtonTest.scala中。