1. 機器學習中的優(yōu)化算法!

        共 6170字,需瀏覽 13分鐘

         ·

        2020-08-09 07:26

        ↑↑↑關注后"星標"Datawhale

        每日干貨?&?每月組隊學習,不錯過

        ?Datawhale干貨?

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

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

        1.1?最速下降法的原理

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

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

        1.2 最速下降法的收斂速度

        1.2.1? 收斂性

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

        • Kantorovich不等式:

        1.2.3? 收斂速度的上界

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

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

        1.2.4? 收斂速度的差異性來源

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

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

        缺點

        • 收斂慢:線性收斂。

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

        • 沒有二次終止性:即不具備對于任意的正定二次函數(shù),從任意點出發(fā),都可以經(jīng)過有限步迭代取得極小值的性質。

        二、Newton方法

        2.1 基本Newton方法

        ?具有連續(xù)二階偏導數(shù),當前迭代點是?。?在??的泰勒展開為:

        ??

        其中。在點的鄰域內,用二次函數(shù)去近似,求解問題?。
        正定,則迭代方向為問題的唯一解。我們稱為Newton方向。(Hesse的逆矩陣度量下的最速下降法)

        我們來看看牛頓迭代的方向和梯度下降的方向有什么不一樣?(黑色為牛頓下降方向,紅色為負梯度下降方向)

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

        從上面的例子我們可以看到:
        (1)當初始點接近極小點時,迭代序列收斂于極小點,并且收斂很快(二階收斂);
        (2)當初始點不接近極小點時,迭代序列容易收斂到鞍點或者極大點(局部收斂性而不是全局收斂)。

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

        2.4 LM方法

        LM方法是處理奇異、不正定等情況的一個最簡單有效的方法,它是指求解?來確定迭代方向的Newton型方法,這里的是單位陣。顯然,若足夠大,可以保證正定。

        (1)??的大小對于方向的影響:

        • 當??很小,求出的步長偏向于Newton方向。

        • 當??很大,求出的步長則偏向于負梯度方向。

        (2)當不正定時,可以簡單取

        三、擬牛頓方法

        Newton方法的優(yōu)缺點:

        (1)當初始點接近極小點時,迭代序列收斂于極小點,并且收斂很快(二階收斂);

        (2)當初始點不接近極小點時,迭代序列容易收斂到鞍點或者極大點(局部收斂性而不是全局收斂)。

        (3)迭代過程可能會出現(xiàn)奇異矩陣或者病態(tài),以至于求逆很困難,導致迭代失敗。

        • 的特征值求不出來。

        • 的特征值,?

          不一定小于0,牛頓方向未必是下降方向。

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

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

        3.1 擬牛頓條件

        假定當前迭代點為,已知條件為,我們使用拉格朗日中值定理:?

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

        得到:

        ?

        因此擬牛頓條件為:

        ??

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

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

        那么,算法的核心就是怎么由去修正,即,而的取法是多種多樣的,但是他應該具有簡單、計算量小、有效的特點。

        3.2 擬牛頓方法的修正公式

        3.2.1 對稱秩1公式

        即取為對稱秩1矩陣,即有
        。

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

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

        代入得到

        ??

        因此,由此得到

        ?.
        最終得到對稱秩1公式:

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

        最終得到對稱秩1公式:

        3.2.2 對稱秩2公式

        為對稱秩2矩陣,即,其中?待定。

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

        (1)DFP方法

        中,化簡為

        ??

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

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

        根據(jù)SMW公式:

        (2)BFGS公式(對偶)

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

        根據(jù)SMW公式:

        (3)Broyden族公式

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

        3.3 三種擬牛頓方法的對比試驗

        (1)擴展Rosenbrock問題

        (BFGS與DFP差異不大,SR1差些)(迭代次數(shù)與函數(shù)調用次數(shù))

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

        四、使用牛頓法優(yōu)化Rosenbrock函數(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 = []

        # 準備數(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_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') # 設定顯示范圍 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_time print("優(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)化的步長0.01

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

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

        “整理不易,三連

        瀏覽 48
        點贊
        評論
        收藏
        分享

        手機掃一掃分享

        分享
        舉報
        評論
        圖片
        表情
        推薦
        點贊
        評論
        收藏
        分享

        手機掃一掃分享

        分享
        舉報
          
          

            1. 婷婷国产夫妻 | 7777淫语有声小说 | 被狂cao喷水了啊~视频 | 操B无码视频国产 | 公交车艳遇辣文h婷 |