機器學習中的優(yōu)化算法!
每日干貨?&?每月組隊學習,不錯過
作者:李祖賢,Datawhale高校群成員,深圳大學
1.1?最速下降法的原理
,我們想求
處使得?
?下降最快的方向。由上一章可知:這個方向應首先滿足下降條件
。雖然下降方向有無窮多個,但是根據(jù)Cauchy-Schwarz不等式:
當且僅當
時等式成立,
達到最小。由于在
方向上要考慮步長,故取
為負梯度方向:
。


我們從上面可以看到,不同的G矩陣使用最速下降法的迭代速度有明顯的差異,原因在后文給出。
1.2 最速下降法的收斂速度
1.2.1? 收斂性
向量u在矩陣G度量下的范數(shù):
矩陣G度量下的Cauchy-Schwarz不等式:

Kantorovich不等式:

1.2.3? 收斂速度的上界


由此可知,最速下降法的收斂速度是線性的,這個速度依賴于G的最大最小特征值。
我們假設G和b產(chǎn)生了微小擾動變成了
?,正定二次函數(shù):?
的導函數(shù)方程相應變成了?
?,方程的解記為
?,其中
非奇異,
?滿足
?非零。那么:

條件數(shù)與范數(shù)有關,因此是G的相對誤差與b的相對誤差之和的放大倍數(shù)。若矩陣G的條件數(shù)很大,擾動對解的影響很大,我們稱這個問題是病態(tài)的,或G是病態(tài)的。若矩陣G的條件數(shù)不大,擾動對解的影響程度不大,我們就成這樣的問題是良性的,或G是良性的。
因此:

這說明最速下降法的收斂速度依賴G的條件數(shù),當G的條件數(shù)接近于1時,
接近于0,最速下降法的收斂速度接近于超線性收斂;而當G的條件數(shù)很大時,
接近于1,則收斂很慢。


缺點:
收斂慢:線性收斂。
Zigzag現(xiàn)象(收斂慢的原因):若迭代步?
?是?
?的精確最小點,則
,因此:?
?,也就是上一步的方向與下一步的方向垂直。

沒有二次終止性:即不具備對于任意的正定二次函數(shù),從任意點出發(fā),都可以經(jīng)過有限步迭代取得極小值的性質。
二、Newton方法
2.1 基本Newton方法
設
?具有連續(xù)二階偏導數(shù),當前迭代點是
?。
?在?
?的泰勒展開為:
?
?
。在點
的鄰域內,用二次函數(shù)
去近似
,求解問題
?。
正定,則迭代方向
為問題的唯一解。我們稱
為Newton方向。(Hesse的逆矩陣度量下的最速下降法)我們來看看牛頓迭代的方向和梯度下降的方向有什么不一樣?(黑色為牛頓下降方向,紅色為負梯度下降方向)

下面我們用一個具體的例子來看看牛頓迭代法的效果:


(3)迭代過程可能會出現(xiàn)奇異矩陣或者病態(tài),以至于求逆很困難,導致迭代失敗。
當
的特征值
,
求不出來。當
的特征值
?不一定小于0,牛頓方向未必是下降方向。
(4)每一步迭代需要計算Hesse矩陣,即計算n(n+1)/2個二階偏導數(shù),相當于求解一個線性方程組,計算量為O(
)
2.2 阻尼Newton方法
為了改善基本Newton方法的局部收斂準則,我們采用帶一維線搜索的的Newton方法,即

其中
是一維搜索的結果,該方法叫做阻尼Newton方法。此方法能保證對正定矩陣
,
?單調下降;即使?
?離x稍遠,由該方法產(chǎn)生的點列
仍能收斂到
。(對嚴格凸函數(shù)具有全局收斂性)
2.3 混合方法
幾乎正交的情形。為了解決這個問題,我們可以采用基本Newton方法與最速下降法相互混合的方式。
奇異或者
與
幾乎正交時,采用負梯度方向;在
負定,但是
存在時,取
?。
2.4 LM方法
奇異、不正定等情況的一個最簡單有效的方法,它是指求解?
來確定迭代方向的Newton型方法,這里的
是單位陣。顯然,若
足夠大,可以保證
正定。(1)?
?的大小對于方向的影響:
當?
?很小,求出的步長偏向于Newton方向。當?
?很大,求出的步長則偏向于負梯度方向。
(2)當
不正定時,可以簡單取




三、擬牛頓方法
Newton方法的優(yōu)缺點:
(1)當初始點接近極小點時,迭代序列收斂于極小點,并且收斂很快(二階收斂);
(2)當初始點不接近極小點時,迭代序列容易收斂到鞍點或者極大點(局部收斂性而不是全局收斂)。
(3)迭代過程可能會出現(xiàn)奇異矩陣或者病態(tài),以至于求逆很困難,導致迭代失敗。
當
的特征值
,
求不出來。當
的特征值
,?
不一定小于0,牛頓方向未必是下降方向。
)為此,我們考慮構造一種方法,她既不需要計算二階偏導數(shù),又有較快的收斂速度。
3.1 擬牛頓條件
,已知條件為
,我們使用拉格朗日中值定理:?
我們可以使用矩陣
似
得到?
?n個方程,n(n+1)/2個變量。
得到:?
因此擬牛頓條件為:
?
?

在上述算法中,初始矩陣
一般取單位矩陣,第一步迭代方向取為負梯度方向。
那么,算法的核心就是怎么由
去修正
,即
,而
的取法是多種多樣的,但是他應該具有簡單、計算量小、有效的特點。
3.2 擬牛頓方法的修正公式
3.2.1 對稱秩1公式
為對稱秩1矩陣,即有
。將
代入擬牛頓方程?
?得到:?
?
?。
是一個數(shù),因此u與
共線,從而存在
使得:
?。將
代入
得到
?因此
,由此得到
?.
如果我們想將
換成等價的
,則需要用到SMW公式:

最終得到對稱秩1公式:

3.2.2 對稱秩2公式
為對稱秩2矩陣,即
,其中?
待定。將
代入
中,得到
的修正公式
。
(1)DFP方法
中,化簡為?
?
由于
的選擇不是唯一的,為了計算方便,我們選擇:

代入公式中可得?
?,得到DFP公式:


(2)BFGS公式(對偶)
的修正公式:?
用相同的推斷實現(xiàn):
根據(jù)SMW公式:

(3)Broyden族公式

3.3 三種擬牛頓方法的對比試驗
(1)擴展Rosenbrock問題
(BFGS與DFP差異不大,SR1差些)(迭代次數(shù)與函數(shù)調用次數(shù))


(2)由人工神經(jīng)網(wǎng)絡解微分方程的問題:



四、使用牛頓法優(yōu)化Rosenbrock函數(shù)實例(基于python)


import numpy as npimport pandas as pdimport matplotlib.pyplot as pltimport time%matplotlib inlinefrom mpl_toolkits.mplot3d import Axes3Dclass Rosenbrock():def __init__(self):self.x1 = np.arange(-100, 100, 0.0001)self.x2 = np.arange(-100, 100, 0.0001)#self.x1, self.x2 = np.meshgrid(self.x1, self.x2)self.a = 1self.b = 1self.newton_times = 1000self.answers = []self.min_answer_z = []# 準備數(shù)據(jù)def data(self):z = np.square(self.a - self.x1) + self.b * np.square(self.x2 - np.square(self.x1))#print(z.shape)return z# 隨機牛頓def snt(self,x1,x2,z,alpha):rand_init = np.random.randint(0,z.shape[0])x1_init,x2_init,z_init = x1[rand_init],x2[rand_init],z[rand_init]x_0 =np.array([x1_init,x2_init]).reshape((-1,1))#print(x_0)for i in range(self.newton_times):x_i = x_0 - np.matmul(np.linalg.inv(np.array([[12*x2_init**2-4*x2_init+2,-4*x1_init],[-4*x1_init,2]])),np.array([4*x1_init**3-4*x1_init*x2_init+2*x1_init-2,-2*x1_init**2+2*x2_init]).reshape((-1,1)))x_0 = x_ix1_init = x_0[0,0]x2_init = x_0[1,0]answer = x_0return answer# 繪圖def plot_data(self,min_x1,min_x2,min_z):x1 = np.arange(-100, 100, 0.1)x2 = np.arange(-100, 100, 0.1)x1, x2 = np.meshgrid(x1, x2)a = 1b = 1z = np.square(a - x1) + b * np.square(x2 - np.square(x1))fig4 = plt.figure()ax4 = plt.axes(projection='3d')ax4.plot_surface(x1, x2, z, alpha=0.3, cmap='winter') # 生成表面, alpha 用于控制透明度ax4.contour(x1, x2, z, zdir='z', offset=-3, cmap="rainbow") # 生成z方向投影,投到x-y平面ax4.contour(x1, x2, z, zdir='x', offset=-6, cmap="rainbow") # 生成x方向投影,投到y(tǒng)-z平面ax4.contour(x1, x2, z, zdir='y', offset=6, cmap="rainbow") # 生成y方向投影,投到x-z平面ax4.contourf(x1, x2, z, zdir='y', offset=6, cmap="rainbow") # 生成y方向投影填充,投到x-z平面,contourf()函數(shù)ax4.scatter(min_x1,min_x2,min_z,c='r')# 設定顯示范圍ax4.set_xlabel('X')ax4.set_ylabel('Y')ax4.set_zlabel('Z')plt.show()# 開始def start(self):times = int(input("請輸入需要隨機優(yōu)化的次數(shù):"))alpha = float(input("請輸入隨機優(yōu)化的步長"))z = self.data()start_time = time.time()for i in range(times):answer = self.snt(self.x1,self.x2,z,alpha)self.answers.append(answer)min_answer = np.array(self.answers)for i in range(times):self.min_answer_z.append((1-min_answer[i,0,0])**2+(min_answer[i,1,0]-min_answer[i,0,0]**2)**2)optimal_z = np.min(np.array(self.min_answer_z))optimal_z_index = np.argmin(np.array(self.min_answer_z))optimal_x1,optimal_x2 = min_answer[optimal_z_index,0,0],min_answer[optimal_z_index,1,0]end_time = time.time()running_time = end_time-start_timeprint("優(yōu)化的時間:%.2f秒!" % running_time)self.plot_data(optimal_x1,optimal_x2,optimal_z)if __name__ == '__main__':snt = Rosenbrock()snt.start()
請輸入需要隨機優(yōu)化的次數(shù):100
優(yōu)化的時間:8.10秒!

本文電子版 后臺回復?優(yōu)化算法?獲取
“整理不易,點贊三連↓
