louvian算法 缺点 优化_机器学习中的优化算法(1)-优化算法重要性,SGD,Momentum(附Python示例)...
生活随笔
收集整理的這篇文章主要介紹了
louvian算法 缺点 优化_机器学习中的优化算法(1)-优化算法重要性,SGD,Momentum(附Python示例)...
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
本系列文章已轉(zhuǎn)至
機器學習的優(yōu)化器?zhuanlan.zhihu.com優(yōu)化算法在機器學習中扮演著至關重要的角色,了解常用的優(yōu)化算法對于機器學習愛好者和從業(yè)者有著重要的意義。
這系列文章先講述優(yōu)化算法和機器學習的關系,然后羅列優(yōu)化算法分類,尤其是機器學習中常用的幾類.接下來明確下數(shù)學符號,開始按照歷史和邏輯順序,依次介紹各種機器學習中常用的優(yōu)化算法.
這篇先講其中基于一階導數(shù)的標準梯度下降法和Momentum,其中穿插學習率退火方法和基于二階導數(shù)的優(yōu)化算法來輔助說明各算法的意義和背后的想法.
優(yōu)化算法和機器學習的關系
機器學習的過程往往是
可見優(yōu)化算法和損失函數(shù)在機器學習中占有重要的地位.
損失函數(shù)比較的一個例子請參看
郝曌駿：MSE vs 交叉熵?zhuanlan.zhihu.com優(yōu)化算法分類
優(yōu)化算法有很多種,常見的包括
- 基于導數(shù)的,比如基于一階導數(shù)的梯度下降法(GD, Grandient Descent)和基于二階導數(shù)的牛頓法等,要求損失函數(shù)(運籌學中更多叫做目標函數(shù))可導
- 群體方法(population method),比如遺傳算法(Genetic Algo)和蟻群算法(Ant Colony Optimization),不依賴于問題(problem-independent),不需要對目標函數(shù)結(jié)構(gòu)有太多的了解
- 單體方法(single-state method),比如模擬退火算法(Simulated Annealing),同樣,不依賴于問題(problem-independent),不需要對目標函數(shù)結(jié)構(gòu)有太多的了解
等.
機器學習中常用的是基于導數(shù),尤其是基于一階導數(shù)的優(yōu)化算法,包括
- 標準梯度下降法(GD, standard Gradient Descent)
- 帶有momentum的GD
- RMSProp (Root Mean Square Propagation)
- AdaM (Adaptive Moment estimates)
- AdaGrad (Adaptive Gradient Algo)
- AdaDelta
符號規(guī)定
在具體解釋前先規(guī)定下符號
- 損失函數(shù)為 （很多地方也會寫作 ）
- 梯度為
- 表示第t次迭代的梯度,
- 第t次迭代時,
- 學習率為
- 表示 的高階無窮小,也就是當 無限接近0時, ,比如 就是 的高階無窮小
標準梯度下降法(GD, standard Gradient Descent)
每次迭代的更新為
其中
表示第t次迭代的梯度, 為人工預先設定的學習率(learning rate).圖1標準GD的想法來源于一階泰勒展開
其中
叫做皮亞諾(Peano)余項,當 很小時,這個余項可以忽略不計.當
和一階導數(shù)也就是梯度相反方向時, (在機器學習中指的的損失函數(shù))下降最快.一個經(jīng)典的解釋是:想象我們從山上下來,每步都沿著坡度最陡的方向.這時,水平面是我們的定義域,海拔是值域.
GD缺點
但GD有兩個主要的缺點:
考慮
所以人們考慮
學習率退火 (Learning Rate Annealing)
出于考慮1,人們參考了單體優(yōu)化方法中的模擬退火(Simulated Annealing),學習率隨著迭代次數(shù)的增加或者損失函數(shù)在驗證集上的表現(xiàn)變好而衰減(decay).
學習率退化可以直接加在GD上.
改進方向
AdaGrad等算法(
郝曌駿：機器學習中的優(yōu)化算法(3)-AdaGrad, Adadelta?zhuanlan.zhihu.com介紹)就借鑒了退火的學習率衰減的思想.不過這個不是這篇的重點.
牛頓法 (Newton's Method)
出于考慮2(為每個維度選擇合適的學習率
),基于二階導數(shù)的牛頓法被提出.它來源于泰勒二階展開.對于多元函數(shù)
,其中
為黑塞矩陣_百度百科?baike.baidu.com我們有
.這樣每次迭代都會考慮損失函數(shù)的曲率(二階導數(shù))來選擇步長.對比圖2中的標準GD,牛頓法可以一步就到達最優(yōu)點.
牛頓法缺點
但是牛頓法的計算復雜度很高,因為Hessian矩陣的維度是參數(shù)個數(shù)的平方,而參數(shù)的個數(shù)往往很多.
改進方向
不同的方法隨即被提出,比如
- Becker和LeCun提出的
- 依靠歷史的梯度信息來模擬二階方法,包括Momentum,RMSProp(用二階距來模擬二階導數(shù)),AdaM(用一階矩和二階矩的比例來模擬二階導數(shù))等.
我們先介紹Momentum
Momentum
Sutskeverd等人在2013年?proceedings.mlr.press,借鑒了物理中動量(momentum)的概念,讓
保留一部分之前的方向和速度.Classical Momentum每次迭代的更新為
這樣預期可以達到兩個效果:
如圖3所示,加入了Classical Momentum,前期的訓練加快了,靠近低點時也減小了震蕩.
關于NAG(Nesterov's Accelerated Gradient)可參看附錄1中的代碼.
附錄1
import math import numpy as np import matplotlib.pyplot as pltRATIO = 3 # 橢圓的長寬比 LIMIT = 1.2 # 圖像的坐標軸范圍class PlotComparaison(object):"""多種優(yōu)化器來優(yōu)化函數(shù) x1^2 + x2^2 * RATIO^2.每次參數(shù)改變?yōu)?d1, d2).梯度為(dx1, dx2)t+1次迭代,標準GD,d1_{t+1} = - eta * dx1d2_{t+1} = - eta * dx2帶Momentum,d1_{t+1} = eta * (mu * d1_t - dx1_{t+1})d2_{t+1} = eta * (mu * d2_t - dx2_{t+1}) 帶Nesterov Momentum,d1_{t+1} = eta * (mu * d1_t - dx1^{nag}_{t+1})d2_{t+1} = eta * (mu * d2_t - dx2^{nag}_{t+1})其中(dx1^{nag}, dx2^{nag})為(x1 + eta * mu * d1_t, x2 + eta * mu * d2_t)處的梯度"""def __init__(self, eta=0.1, mu=0.9, angles=None, contour_values=None,stop_condition=1e-4):# 全部算法的學習率self.eta = eta# 啟發(fā)式學習的終止條件self.stop_condition = stop_condition# Nesterov Momentum超參數(shù)self.mu = mu# 用正態(tài)分布隨機生成初始點self.x1_init, self.x2_init = np.random.uniform(LIMIT / 2, LIMIT), np.random.uniform(LIMIT / 2, LIMIT) / RATIOself.x1, self.x2 = self.x1_init, self.x2_init# 等高線相關if angles == None:angles = np.arange(0, 2 * math.pi, 0.01)self.angles = anglesif contour_values == None:contour_values = [0.25 * i for i in range(1, 5)]self.contour_values = contour_valuessetattr(self, "contour_colors", None)def draw_common(self, title):"""畫等高線,最優(yōu)點和設置圖片各種屬性"""# 坐標軸尺度一致plt.gca().set_aspect(1)# 根據(jù)等高線的值生成坐標和顏色# 海拔越高顏色越深num_contour = len(self.contour_values)if not self.contour_colors:self.contour_colors = [(i / num_contour, i / num_contour, i / num_contour) for i in range(num_contour)]self.contour_colors.reverse()self.contours = [[list(map(lambda x: math.sin(x) * math.sqrt(val), self.angles)),list(map(lambda x: math.cos(x) * math.sqrt(val) / RATIO, self.angles))]for val in self.contour_values]# 畫等高線for i in range(num_contour):plt.plot(self.contours[i][0],self.contours[i][1],linewidth=1,linestyle='-',color=self.contour_colors[i],label="y={}".format(round(self.contour_values[i], 2)))# 畫最優(yōu)點plt.text(0, 0, 'x*')# 圖片標題plt.title(title)# 設置坐標軸名字和范圍plt.xlabel("x1")plt.ylabel("x2")plt.xlim((-LIMIT, LIMIT))plt.ylim((-LIMIT, LIMIT))# 顯示圖例plt.legend(loc=1)def forward_gd(self):"""SGD一次迭代"""self.d1 = -self.eta * self.dx1self.d2 = -self.eta * self.dx2self.ite += 1def draw_gd(self, num_ite=5):"""畫基礎SGD的迭代優(yōu)化.包括每次迭代的點,以及表示每次迭代改變的箭頭"""# 初始化setattr(self, "ite", 0)setattr(self, "x1", self.x1_init)setattr(self, "x2", self.x2_init)# 畫每次迭代self.point_colors = [(i / num_ite, 0, 0) for i in range(num_ite)]plt.scatter(self.x1, self.x2, color=self.point_colors[0])for _ in range(num_ite):self.forward_gd()# 迭代的箭頭plt.arrow(self.x1, self.x2, self.d1, self.d2,length_includes_head=True,linestyle=':',label='{} ite'.format(self.ite),color='b',head_width=0.08)self.x1 += self.d1self.x2 += self.d2print("第{}次迭代后,坐標為({}, {})".format(self.ite, self.x1, self.x2))plt.scatter(self.x1, self.x2) # 迭代的點if self.loss < self.stop_condition:breakdef forward_momentum(self):"""帶Momentum的SGD一次迭代"""self.d1 = self.eta * (self.mu * self.d1_pre - self.dx1)self.d2 = self.eta * (self.mu * self.d2_pre - self.dx2)self.ite += 1self.d1_pre, self.d2_pre = self.d1, self.d2def draw_momentum(self, num_ite=5):"""畫帶Momentum的迭代優(yōu)化."""# 初始化setattr(self, "ite", 0)setattr(self, "x1", self.x1_init)setattr(self, "x2", self.x2_init)setattr(self, "d1_pre", 0)setattr(self, "d2_pre", 0)# 畫每次迭代self.point_colors = [(i / num_ite, 0, 0) for i in range(num_ite)]plt.scatter(self.x1, self.x2, color=self.point_colors[0])for _ in range(num_ite):self.forward_momentum()# 迭代的箭頭plt.arrow(self.x1, self.x2, self.d1, self.d2,length_includes_head=True,linestyle=':',label='{} ite'.format(self.ite),color='b',head_width=0.08)self.x1 += self.d1self.x2 += self.d2print("第{}次迭代后,坐標為({}, {})".format(self.ite, self.x1, self.x2))plt.scatter(self.x1, self.x2) # 迭代的點if self.loss < self.stop_condition:breakdef forward_nag(self):"""Nesterov Accelerated的SGD一次迭代"""self.d1 = self.eta * (self.mu * self.d1_pre - self.dx1_nag)self.d2 = self.eta * (self.mu * self.d2_pre - self.dx2_nag)self.ite += 1self.d1_pre, self.d2_pre = self.d1, self.d2def draw_nag(self, num_ite=5):"""畫Nesterov Accelerated的迭代優(yōu)化."""# 初始化setattr(self, "ite", 0)setattr(self, "x1", self.x1_init)setattr(self, "x2", self.x2_init)setattr(self, "d1_pre", 0)setattr(self, "d2_pre", 0)# 畫每次迭代self.point_colors = [(i / num_ite, 0, 0) for i in range(num_ite)]plt.scatter(self.x1, self.x2, color=self.point_colors[0])for _ in range(num_ite):self.forward_nag()# 迭代的箭頭plt.arrow(self.x1, self.x2, self.d1, self.d2,length_includes_head=True,linestyle=':',label='{} ite'.format(self.ite),color='b',head_width=0.08)self.x1 += self.d1self.x2 += self.d2print("第{}次迭代后,坐標為({}, {})".format(self.ite, self.x1, self.x2))plt.scatter(self.x1, self.x2) # 迭代的點if self.loss < self.stop_condition:break@propertydef dx1(self, x1=None):return self.x1 * 2@propertydef dx2(self):return self.x2 * 2 * (RATIO ** 2)@propertydef dx1_nag(self, x1=None):return (self.x1 + self.eta * self.mu * self.d1_pre) * 2@propertydef dx2_nag(self):return (self.x2 + self.eta * self.mu * self.d2_pre) * 2 * (RATIO ** 2)@propertydef loss(self):return self.x1 ** 2 + (RATIO * self.x2) ** 2def show(self):# 設置圖片大小plt.figure(figsize=(20, 20))# 展示plt.show()def main_2():"""畫圖2"""xixi = PlotComparaison()xixi.draw_gd()xixi.draw_common("Optimize x1^2+x2^2*{} Using SGD".format(RATIO ** 2))xixi.show()def main_3(num_ite=15):"""畫圖3"""xixi = PlotComparaison()xixi.draw_gd(num_ite)xixi.draw_common("Optimize x1^2+x2^2*{} Using SGD".format(RATIO ** 2))xixi.show()xixi.draw_momentum(num_ite)xixi.draw_common("Optimize x1^2+x2^2*{} Using SGD With Momentum".format(RATIO ** 2))xixi.show()附錄2
帶Momentum機制的GD在pytorch中的實現(xiàn)為
import torch torch.optim.SGD(lr, momentum) # lr為學習率,momentum為可選參數(shù) 《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的louvian算法 缺点 优化_机器学习中的优化算法(1)-优化算法重要性,SGD,Momentum(附Python示例)...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ue4导入倾斜摄影_倾斜摄影入门必学｜C
- 下一篇： a*算法的优缺点_轻松理解机器学习算法-