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


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

Kantorovich不等式:

1.2.3? 收斂速度的上界


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

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

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


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

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

下面我們用一個(gè)具體的例子來(lái)看看牛頓迭代法的效果:


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

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




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

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

最終得到對(duì)稱秩1公式:

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

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


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

(3)Broyden族公式

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


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



四、使用牛頓法優(yōu)化Rosenbrock函數(shù)實(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 = []# 準(zhǔn)備數(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# 隨機(jī)牛頓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')# 設(shè)定顯示范圍ax4.set_xlabel('X')ax4.set_ylabel('Y')ax4.set_zlabel('Z')plt.show()# 開始def start(self):times = int(input("請(qǐng)輸入需要隨機(jī)優(yōu)化的次數(shù):"))alpha = float(input("請(qǐng)輸入隨機(jī)優(yōu)化的步長(zhǎng)"))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)化的時(shí)間:%.2f秒!" % running_time)self.plot_data(optimal_x1,optimal_x2,optimal_z)if __name__ == '__main__':snt = Rosenbrock()snt.start()
請(qǐng)輸入需要隨機(jī)優(yōu)化的次數(shù):100
優(yōu)化的時(shí)間:8.10秒!

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