<kbd id="afajh"><form id="afajh"></form></kbd>
<strong id="afajh"><dl id="afajh"></dl></strong>
    <del id="afajh"><form id="afajh"></form></del>
        1. <th id="afajh"><progress id="afajh"></progress></th>
          <b id="afajh"><abbr id="afajh"></abbr></b>
          <th id="afajh"><progress id="afajh"></progress></th>

          機(jī)器學(xué)習(xí)中的優(yōu)化算法!

          共 6170字,需瀏覽 13分鐘

           ·

          2020-08-09 07:26

          ↑↑↑關(guān)注后"星標(biāo)"Datawhale

          每日干貨?&?每月組隊(duì)學(xué)習(xí),不錯(cuò)過

          ?Datawhale干貨?

          作者:李祖賢,Datawhale高校群成員,深圳大學(xué)

          在機(jī)器學(xué)習(xí)中,有很多的問題并沒有解析形式的解,或者有解析形式的解但是計(jì)算量很大(譬如,超定問題的最小二乘解),對(duì)于此類問題,通常我們會(huì)選擇采用一種迭代的優(yōu)化方式進(jìn)行求解。
          負(fù)梯度方法與Newton型方法在最優(yōu)化方法中發(fā)揮著重要作用,也在現(xiàn)代金融科技,大規(guī)模的機(jī)器學(xué)習(xí)發(fā)揮不可或缺的作用。接下來(lái),我們將針對(duì)這兩種優(yōu)化方法在機(jī)器學(xué)習(xí)中的應(yīng)用進(jìn)行討論。
          一、最速下降法

          1.1?最速下降法的原理

          假定在第k步的迭代點(diǎn),我們想求處使得??下降最快的方向。由上一章可知:這個(gè)方向應(yīng)首先滿足下降條件。雖然下降方向有無(wú)窮多個(gè),但是根據(jù)Cauchy-Schwarz不等式:當(dāng)且僅當(dāng)時(shí)等式成立,達(dá)到最小。由于在方向上要考慮步長(zhǎng),故取為負(fù)梯度方向:。
          特別的,我們稱采用負(fù)梯度方向以及精確線搜索的方法稱為最速下降法。

          我們從上面可以看到,不同的G矩陣使用最速下降法的迭代速度有明顯的差異,原因在后文給出。

          1.2 最速下降法的收斂速度

          1.2.1? 收斂性

          最速下降法具有全局收斂性!
          1.2.2? 預(yù)備知識(shí)
          • 量u在矩陣G度量下的范數(shù):
          • 矩陣G度量下的Cauchy-Schwarz不等式:

          • Kantorovich不等式:

          1.2.3? 收斂速度的上界

          正定二次函數(shù):?
          收斂速度的上界:

          由此可知,最速下降法的收斂速度是線性的,這個(gè)速度依賴于G的最大最小特征值。

          1.2.4? 收斂速度的差異性來(lái)源

          我們假設(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,則收斂很慢。

          1.2.5??最速下降法的優(yōu)缺點(diǎn)
          優(yōu)點(diǎn):算法每次迭代的計(jì)算量少,儲(chǔ)存量也少,從一個(gè)不太好的初始點(diǎn)出發(fā)也能靠近極小點(diǎn)。

          缺點(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)看看牛頓迭代法的效果:

          從上面的例子我們可以看到:
          (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,牛頓方向未必是下降方向。

          (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 混合方法

          基本Newton方法在迭代過程中會(huì)出現(xiàn)Hesse矩陣奇異、不正定的情形,基本Newton方法還會(huì)出現(xiàn)與幾乎正交的情形。為了解決這個(gè)問題,我們可以采用基本Newton方法與最速下降法相互混合的方式。
          該方法采用Newton方法,但是在Hesse矩陣奇異或者幾乎正交時(shí),采用負(fù)梯度方向;在負(fù)定,但是存在時(shí),取?。

          2.4 LM方法

          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,牛頓方向未必是下降方向。

          (4)每一步迭代需要計(jì)算Hesse矩陣,即計(jì)算n(n+1)/2個(gè)二階偏導(dǎo)數(shù),相當(dāng)于求解一個(gè)線性方程組,計(jì)算量為O()

          為此,我們考慮構(gòu)造一種方法,她既不需要計(jì)算二階偏導(dǎo)數(shù),又有較快的收斂速度。

          3.1 擬牛頓條件

          假定當(dāng)前迭代點(diǎn)為,已知條件為,我們使用拉格朗日中值定理:?

          我們可以使用矩陣得到??n個(gè)方程,n(n+1)/2個(gè)變量。

          得到:

          ?

          因此擬牛頓條件為:

          ??

          滿足這兩個(gè)方程的矩陣有很多,因此擬牛頓方法是一類方法。

          在上述算法中,初始矩陣一般取單位矩陣,第一步迭代方向取為負(fù)梯度方向。

          那么,算法的核心就是怎么由去修正,即,而的取法是多種多樣的,但是他應(yīng)該具有簡(jiǎn)單、計(jì)算量小、有效的特點(diǎn)。

          3.2 擬牛頓方法的修正公式

          3.2.1 對(duì)稱秩1公式

          即取為對(duì)稱秩1矩陣,即有
          。

          代入擬牛頓方程??得到:?

          ?
          即有:?。
          由于是一個(gè)數(shù),因此u與共線,從而存在使得:?。

          代入得到

          ??

          因此,由此得到

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

          如果我們想將換成等價(jià)的,則需要用到SMW公式:

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

          3.2.2 對(duì)稱秩2公式

          為對(duì)稱秩2矩陣,即,其中?待定。

          代入中,得到的修正公式。

          (1)DFP方法

          中,化簡(jiǎn)為

          ??

          由于的選擇不是唯一的,為了計(jì)算方便,我們選擇:

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

          根據(jù)SMW公式:

          (2)BFGS公式(對(duì)偶)

          考慮的修正公式:?用相同的推斷實(shí)現(xiàn):

          根據(jù)SMW公式:

          (3)Broyden族公式

          DFP方法與BFGS公式的線性組合:

          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)

          Rosenbrock函數(shù)的數(shù)據(jù)探索:
          ?
          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 = 1        self.b = 1        self.newton_times = 1000        self.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_i x1_init = x_0[0,0] x2_init = x_0[1,0] answer = x_0 return 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 = 1 b = 1 z = 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_time print("優(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

          請(qǐng)輸入隨機(jī)優(yōu)化的步長(zhǎng)0.01

          優(yōu)化的時(shí)間:8.10秒!

          本文電子版 后臺(tái)回復(fù)?優(yōu)化算法?獲取

          “整理不易,點(diǎn)三連

          瀏覽 48
          點(diǎn)贊
          評(píng)論
          收藏
          分享

          手機(jī)掃一掃分享

          分享
          舉報(bào)
          評(píng)論
          圖片
          表情
          推薦
          點(diǎn)贊
          評(píng)論
          收藏
          分享

          手機(jī)掃一掃分享

          分享
          舉報(bào)
          <kbd id="afajh"><form id="afajh"></form></kbd>
          <strong id="afajh"><dl id="afajh"></dl></strong>
            <del id="afajh"><form id="afajh"></form></del>
                1. <th id="afajh"><progress id="afajh"></progress></th>
                  <b id="afajh"><abbr id="afajh"></abbr></b>
                  <th id="afajh"><progress id="afajh"></progress></th>
                  久久久成人免费电影 | 操阿姨| 黄色美女操逼视频 | 先锋影音AV成人电影 | 国产精品色国产在线 |