-
2021-07-17 15:52:41
目录
神经网络参数更新方法
1、SGD
-
SGD(Stochastic Gradient Descent)就是最常见的随机梯度下降。
-
向着参数的梯度的负方向改变(梯度方向是增加的方向)。
x + = − l e a r n i n g _ r a t e ∗ d x x += -learning\_rate*dx x+=−learning_rate∗dx
这里的x可以是权值w也可以是偏置b。
2、MBGD
-
MBGD(Mini Batch Gradient Descent)小批量梯度下降
-
对每个批次中的n个训练样本,这种方法只执行一次更新。
-
为了避免SGD和标准梯度下降中存在的问题。
使用小批量梯度下降的优点是:
- 可以减少参数更新的波动,最终得到效果更好和更稳定的收敛。
- 还可以使用最新的深层学习库中通用的矩阵优化方法,使计算小批量数据的梯度更加高效。
- 通常来说,小批量样本的大小范围是从50到256,可以根据实际问题而有所不同。
- 在训练神经网络时,通常都会选择小批量梯度下降算法。
3、Momentum update
- SGD方法中的高方差振荡使得网络很难稳定收敛。
- 研究者提出了一种称为动量(Momentum)的技术,通过优化相关方向的训练和弱化无关方向的振荡,来加速SGD训练。
受到物理中的启发:例子的力与势能梯度有相对关系。例子感受到的力,正是损失函数的负梯度。F=ma,负梯度正比于粒的加速度。与普通SGD不同,梯度直接作用于位置,这里用物理的角度来看,梯度直接影响速度,速度再影响位置。
x + = − l e a r n i n g _ r a t e ∗ d x x + = v \begin{aligned} x +=& -learning\_rate*dx\\ x +=& \quad v \end{aligned} x+=x+=−learning_rate∗dxv4、Nestrevo Momentum update
与Momentum稍稍有点不同。对于凸函数具有较强的理论收敛保证,实际中效果比Mnmentum稍好。
- 通过使网络更新与误差函数的斜率相适应,并依次加速SGD。
- 也可根据每个参数的重要性来调整和更新对应参数,以执行更大或更小的更新幅度。
当前参数向量在点x处,从Momentum更新中看v,忽略第二项v变成mu*v。做一个提前量用x_ahead=x+mu*v代替x。
x _ a h e a d = x + m u ∗ v v = m u ∗ v − l e a r n i n g _ r a t e ∗ d x _ a h e a d x + = v \begin{aligned} & x\_ahead = x + mu*v\\ & v = mu*v - learning\_rate*dx\_ahead\\ & x += \quad v \end{aligned} x_ahead=x+mu∗vv=mu∗v−learning_rate∗dx_aheadx+=v每个参数适应学习率方法
前面的方法对每个参数学习了是固定的,调整学习率是一个耗时的过程。可以使用对每个参数都适应的学习率。
5、Adagrad
c a c h e + = ( d x ) 2 x + = − l e a r n i n g _ r a t e ∗ d x ( n p . s q r t ( c a c h e ) + e p s ) \begin{aligned} & cache += (dx)^2\\ &x += -learning\_rate*\frac{dx}{(np.sqrt(cache)+eps)} \end{aligned} cache+=(dx)2x+=−learning_rate∗(np.sqrt(cache)+eps)dx
Adagrad方法是通过参数来调整合适的学习率η,对稀疏参数进行大幅更新和对频繁参数进行小幅更新。因此,Adagrad方法非常
适合处理稀疏数据
。对于大的梯度,会使他的有效学习率减小;对于小的梯度会使他的有效学习率增大。这种方法的一个缺点是,在深度学习中,单调的学习率通常证明太激进,会使学习停止过早。
6、AdaDelta
AdaDelta方法是AdaGrad的延伸方法,它倾向于解决其学习率衰减的问题。Adadelta不是累积所有之前的平方梯度,而是将累积之前梯度的窗口限制到某个固定大小w。
7、RMSprop
RMSprop是一种有效,但目前还未公开发布的自适应学习率方法。RMSprop改进Adagrad方法,减小他的激进,使用单调减小学习率。特别的,它使用了梯度平方移动平均值。
c a c h e = d e c a y _ r a t e ∗ c a c h e + ( 1 − d e c a y _ r a t e ) ∗ ( d x ) 2 x + = − l e a r n i n g _ r a t e ∗ d x ( n p . s q r t ( c a c h e ) + e p s ) \begin{aligned} &cache = decay\_rate*cache+(1-decay\_rate)*(dx)^2\\ &x += -learning\_rate*\frac{dx}{(np.sqrt(cache)+eps)} \end{aligned} cache=decay_rate∗cache+(1−decay_rate)∗(dx)2x+=−learning_rate∗(np.sqrt(cache)+eps)dx
decay_rate是一个超参数,典型值为[0.9, 0.99, 0.999]。
根据梯度尺度来调整学习率是一个有利均衡的效果,但与Adagrad不同,更新不是单调小。8、Adam
Adam算法即自适应时刻估计方法(Adaptive Moment Estimation),能计算每个参数的自适应学习率。这个方法不仅存储了AdaDelta先前平方梯度的指数衰减平均值,而且保持了先前梯度M(t)的指数衰减平均值,有点像RMSprop结合momentum。
简单的更新如下:
m = b e l t a l ∗ m + ( 1 − b e l t a 1 ) ∗ d x v = b e l t a 2 ∗ v + ( 1 − b e l t a 2 ) ∗ ( d x ) 2 x + = − l e a r n i n g _ r a t e ∗ d x ( n p . s q r t ( v ) + e p s ) \begin{aligned} &m =beltal*m + (1-belta1)*dx\\ &v = belta2*v+(1-belta2)*(dx)^2\\ &x += -learning\_rate*\frac{dx}{(np.sqrt(v)+eps)} \end{aligned} m=beltal∗m+(1−belta1)∗dxv=belta2∗v+(1−belta2)∗(dx)2x+=−learning_rate∗(np.sqrt(v)+eps)dx
与RMSProp类似,使用smooth版本的梯度m代替原始梯度dx。论文中的推荐值eps=1e-8,belta1=0.9,belta2=0.999。使用推荐值的Adam方法效果RMSprop稍好。但SGD加Nestrevo Momentum也值得使用。完整的Adam方法还包括一个bias校正机制。对前几部m,v设置成0进行补偿。更多相关内容 -
-
流体势能场分析方法的改进 (2004年)
2021-05-10 04:08:39采用场论的数值算法,对平面流体势能等值线做数值离散化处理,计算各点势能梯度,确定流体运动的方向及强度,并用拉普拉斯算子计算确定油气汇聚区的范围。应用改进的方法分析了乌尔逊凹陷北部油气运移过程,结果表明... -
论文研究 - 涡旋的压力梯度,功率和能量
2020-05-27 07:24:59我们考虑了小旋涡,例如龙卷风,尘埃,水龙卷,低纬度的小飓风和漩涡,可以忽略科里奥利力,因此在其中是回旋的。 这样的旋涡关于(穿过穿过平静的... 然后讨论了以流体涡流,地转流和摩擦平衡流以及重力系统中的势能 -
【全局路径规划】人工势场 Artificial Potential Field
2020-04-29 16:11:38Real-Time Obstacle Avoidance for Manipulators and Mobile Robots Oussama Khatib 1. 人工势场 UartU_{art}Uart: 表现为目标引力场UxdU_{x_d}Uxd和障碍物斥力场UOU_{O}UO的...机器人总势能 UUU,在Uar...
Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
Oussama Khatib
1. 人工势场 U a r t U_{art} Uart:
表现为目标引力场 U x d U_{x_d} Uxd和障碍物斥力场 U O U_{O} UO的和,其中 x x x为机器人Configuration参数,表示机器人位姿
机器人总势能 U U U,在 U a r t U_{art} Uart的基础上在加上重力势能 U g U_{g} Ug
在人工势场中,单位质量的受力情况在 F a r t ∗ F_{art}^* Fart∗表示为在引力和斥力的和
其中,机器人受到的引力和斥力都分别沿着两个场的负梯度方向,即势能减小最快的方向(引力向着目标,斥力背离障碍)
2. 目标引力场 U x d U_{x_d} Uxd:
当目标引力场 U x d U_{x_d} Uxd如下设置时
对应受到的引力 F x d ∗ F_{x_d}^* Fxd∗如下,为 U x d U_{x_d} Uxd对x的负导数
其中 K p K_p Kp对应位置增益,联系弹簧弹力和弹性势能的对应关系比较好理解。这里可以理解成一个通过引力来控制位置的控制系统,仅有比例控制时,不具有前瞻性,不稳定,容易产生超调,也就是造成机器人无法停在目标处,而是开过头再倒回来,经过震荡后稳定在目标位置。
为了增加稳定性,引入微分项 x ˙ \dot x x˙即机器人运动速度,形成PD控制
这样,引力场将与机器人速度产生联系,当速度过大,引力场会减弱,提前避免超调,文章中格外提到需要注意,要限制机器人最大的运动速度,以免过大的运动速度将引力场完全抵消,使机器人失去目标。
3. 障碍物斥力场 U O U_O UO:
方法1:当有障碍物边缘方程f(x)=0时,可以如下设置,x0为斥力场边界
方法2:直接根据离障碍物的距离远近来设置斥力场,这个方法比较简易,ρ0为斥力场边界
对于高维空间,用PSP(Point Subjected to the Potential)来表达各维度上的斥力场
偏导数的含义类似与距离在各维上的投影
斥力场的可加性:同一个障碍物的不同部分(primitives)形成的斥力场、不同障碍物形成的斥力场都具有可加性:
从点受到的斥力作用可以扩展到link受到的斥力作用,问题转化为找到link距离障碍物的最近距离。同样地,也可以扩展到joint运动限制问题上,类比可以把运动范围的上下界看作两个障碍物,生成两个斥力场,让joint在其之间运动。
4. 存在的问题:
1) 局部极小值(local minima)的干扰
人工势场通过将目标点处设置为引力场势能极小点,引导机器人不断向目标点靠近,同时每个障碍物都在生成斥力场以使机器人在行进过程中远离障碍物,实现避障。
能成功生成一条到达目标的路径的重点在于,全局只有一个最小势能点,即目标点,这样机器人不论以何处为起点,都可以沿势场下降梯度找到目标。
然而,复杂环境中,如U形障碍物,会生成具有局部极小值的势场,机器人一旦到达局部极小值,则无法再沿梯度向目标处移动,造成路径规划失败。
作者将该方法的这个特点形容为:local perspective,即局部视野、短视。
2) 欠缺实时性
计算势场、连接一条从起点沿梯度下降到目标点的路径计算量比较大,往往无法达到实时规划,所以这个方法常作为实时规划系统(high level planning system)的其中一个组成部分。作者简述了提高算法实时性的一些方法,这里不叙述。
-
梯度向量与梯度下降法
2017-10-27 15:37:16要掌握“梯度下降法”,就需要先搞清楚什么是“梯度”,本文将从这些基本概念:方向导数(directional derivative)与偏导数、梯度(gradient)、梯度向量(gradient vector)等出发,带您领略
最近非常热门的“深度学习”领域,用到了一种名为“梯度下降法”的算法。梯度下降法是机器学习中常用的一种方法,它主要用于快速找到“最小误差”(the minimum error)。要掌握“梯度下降法”,就需要先搞清楚什么是“梯度”,本文将从这些基本概念:方向导数(directional derivative)与偏导数、梯度(gradient)、梯度向量(gradient vector)等出发,带您领略“深度学习”中的“最小二乘法”、“梯度下降法”和“线性回归”。- 偏导数(Partial derivate)
- 方向导数(Directional derivate)
- 梯度(Gradient)
- 线性回归(linear regression)
- 梯度下降(Gradient descent)
一、方向导数
1,偏导数
先回顾一下一元导数和偏导数,一元导数表征的是:一元函数 f(x) f ( x ) 与自变量 x x 在某点附近变化的比率(变化率),如下:
而二元函数的偏导数表征的是:函数 F(x,y) F ( x , y ) 与自变量 x x (或 ) 在某点附近变化的比率(变化率),如下:
Fx(x0,y0)=∂F∂x∣x=x0,y=y0=limΔx→0F(x0+Δx,y0)−F(x0,y0)Δx F x ( x 0 , y 0 ) = ∂ F ∂ x ∣ x = x 0 , y = y 0 = lim Δ x → 0 F ( x 0 + Δ x , y 0 ) − F ( x 0 , y 0 ) Δ x
以长方形的面积 z=F(x,y) z = F ( x , y ) 为例,如下图:
如果说 z=F(x,y)=x⋅y z = F ( x , y ) = x ⋅ y 表示以 P(x,y) 点和原点为对角点的矩形的面积,那么 z=F(x,y) z = F ( x , y ) 在 P0 P 0 点对x 的偏导数表示 P0 P 0 点沿平行于 x 轴正向移动,矩形的面积变化量与 P0 P 0 点在 x方向的移动距离的比值
Fx(x0,y0)=∂F∂x=limΔx→0ΔSΔx F x ( x 0 , y 0 ) = ∂ F ∂ x = lim Δ x → 0 Δ S Δ x
同样地,可得
Fy(x0,y0)=∂F∂y=limΔy→0ΔSΔy F y ( x 0 , y 0 ) = ∂ F ∂ y = lim Δ y → 0 Δ S Δ y
需要注意的是:
矩形面积的这个例子有时候也很容易让人混淆,上图中无论 x 还是 y ,都是输入变量,输出变量 S 并没有用坐标轴的形式画出来。也就是说,这个例子实际上是一个三维空间的函数关系,而不是二维平面的函数关系。
向量角度看偏导数:
偏导数向量 [FxFy] [ F x F y ] 是坐标向量(原向量) [xy] [ x y ] 的线性变换,详见《Essence of linear algebra》:求导是一种线性变换。
扩展一下:如果 P0 P 0 点不是沿平行于 x 轴方向或平行于 y 轴方向,而是 沿与 x 轴成夹角 α α 的一条直线 l l 上移动,那么面积的增量与 点在该直线上移动的距离的比值关系是什么呢?
假设 P0 P 0 点在这条直线上移动的距离为 Δt Δ t ,则有
{Δx=Δt⋅cosαΔy=Δt⋅sinα { Δ x = Δ t ⋅ c o s α Δ y = Δ t ⋅ s i n α
那么,矩形面积增量与移动距离的增量比值是:
limΔt→0ΔSΔt=limΔt→0(x0+Δt⋅cosα)⋅(y0+Δt⋅sinα)−x0⋅y0Δt=limΔt→0y0Δt⋅cosα+x0Δt⋅sinα+(Δt)2⋅cosα⋅sinαΔt=y0cosα+x0sinα lim Δ t → 0 Δ S Δ t = lim Δ t → 0 ( x 0 + Δ t ⋅ c o s α ) ⋅ ( y 0 + Δ t ⋅ s i n α ) − x 0 ⋅ y 0 Δ t = lim Δ t → 0 y 0 Δ t ⋅ c o s α + x 0 Δ t ⋅ s i n α + ( Δ t ) 2 ⋅ c o s α ⋅ s i n α Δ t = y 0 c o s α + x 0 s i n α
与偏导数类似,上式也是一个“一元导数”。事实上,这就是方向导数,可记作Fl=∂F∂l F l = ∂ F ∂ l
2,矢量描述
从矢量角度来看, P0 P 0 点沿与 x 轴成夹角 α α 的一条直线 l l 移动,这个移动方向可以看作是一个矢量 —— “方向矢量”
如果 α=0 α = 0 ,即沿平行 x 轴方向移动;如果 α=π2 α = π 2 ,即沿平行 y 轴方向移动。因此,偏导数实际上是方向导数的一种特例。
在回顾一下上一节“二元全微分的几何意义”:用切平面近似空间曲面。这个切平面实际上是由两条相交直线确定的平面,而这两条直线分别是 x 方向的偏导数向量 Px→ P x → 和 y 方向的偏导数向量 Py→ P y → 。很显然,这两个向量不但位于同一个平面,而且相互垂直。那么这两个向量合成的新向量也一定位于这个“切平面”。
注:关于偏导数向量相互垂直,可以很容易从偏导数“切片法”推导出来。
将偏导数合成向量记作 P⃗ =(Fx,Fy)=(∂F∂x,∂F∂y) P → = ( F x , F y ) = ( ∂ F ∂ x , ∂ F ∂ y ) 。如果对偏导数向量和方向向量进行矢量“内积”,则有:
P⃗ ⋅l⃗ =∂F∂xcosα+∂F∂ysinα=∂F∂l P → ⋅ l → = ∂ F ∂ x c o s α + ∂ F ∂ y s i n α = ∂ F ∂ l
这个内积在数值上刚好等于 l⃗ l → 方向的方向导数。
换句话说:方向导数就是偏导数合成向量与方向向量的内积。
从向量角度看:
内积在几何上表示投影,也就是说,方向导数(向量)是原向量在某个方向上的投影的变化率。
3,多元方向导数
从上面的矢量内积出发,将 l⃗ l → 与 y 轴方向的夹角表示为 β β ,则方向导数的公式可以变化为:
∂F∂l=∂F∂xcosα+∂F∂ycosβ ∂ F ∂ l = ∂ F ∂ x c o s α + ∂ F ∂ y c o s β
类似地,推广到多维空间
∂F∂l=∂F∂xcosα1+∂F∂ycosα2+∂F∂zcosα3+⋅⋅⋅ ∂ F ∂ l = ∂ F ∂ x c o s α 1 + ∂ F ∂ y c o s α 2 + ∂ F ∂ z c o s α 3 + ⋅ ⋅ ⋅
当然,从向量内积的角度更容易得到这个公式
P⃗ ⋅l⃗ =(∂F∂x,∂F∂,∂F∂z,⋅⋅⋅)⋅(cosα1,cosα2,cosα3,⋅⋅⋅) P → ⋅ l → = ( ∂ F ∂ x , ∂ F ∂ , ∂ F ∂ z , ⋅ ⋅ ⋅ ) ⋅ ( c o s α 1 , c o s α 2 , c o s α 3 , ⋅ ⋅ ⋅ )
二、梯度
1,梯度(gradient)
还是从上面的矩形面积这个例子出发,来探索什么是“梯度”。
假设 P0 P 0 点的坐标是 (3–√,1) ( 3 , 1 ) , 则
Fx=1,Fy=3–√,Fl=cosα+3–√sinα F x = 1 , F y = 3 , F l = c o s α + 3 s i n α
很明显,方向导数(标量)的大小随 矢量 l⃗ l → 的方向不同而不同。那么,这些方向导数中是否存在一个最大值呢?
答案是肯定的!这就是“梯度”(标量)。
∇F=gradF=max{∂F∂l} ∇ F = g r a d F = m a x { ∂ F ∂ l }
所以,梯度的第一层含义就是“方向导数的最大值”。
2,梯度矢量
梯度的第一层含义是“方向导数的最大值”,那么这个最大值是多少呢?或者说 矢量 l⃗ l → 取什么值时才能找到这个最大值?
还是以矩形面积为例
gradF(3–√,1)=max{∂F∂l}=max{cosα+3–√sinα}=max{2sin(π6+α)} g r a d F ( 3 , 1 ) = m a x { ∂ F ∂ l } = m a x { c o s α + 3 s i n α } = m a x { 2 s i n ( π 6 + α ) }
显然, α=π3 α = π 3 时,取值最大,此时
l⃗ =(cosα,sinα)=(12,3–√2) l → = ( c o s α , s i n α ) = ( 1 2 , 3 2 )
在比较一下偏导数向量
P⃗ =(Fx,Fy)=(1,3–√) P → = ( F x , F y ) = ( 1 , 3 )
是不是似曾相识?对的,后者单位化后就变成了前者。
从向量内积的角度来看,更容易理解:
∇F=gradF=max{∂F∂l}=max{P⃗ ⋅l⃗ }=max{∣∣P⃗ ∣∣⋅∣∣l⃗ ∣∣⋅cosθ} ∇ F = g r a d F = m a x { ∂ F ∂ l } = m a x { P → ⋅ l → } = m a x { | P → | ⋅ | l → | ⋅ c o s θ }
很明显, 两个向量的夹角 θ=0 θ = 0 时,取得最大值。
至此,我们引出了梯度的第二层含义,或者说叫“梯度矢量”
∇F⃗ =gradF=(∂F∂x,∂F∂y) ∇ F → = g r a d F = ( ∂ F ∂ x , ∂ F ∂ y )
注意:
上面提到的夹角 θ θ 在几何上表示原向量(坐标向量)与导数向量(变化率向量)之间的夹角,所以,梯度的几何含义就是:沿向量所在直线的方向变化率最大。
顺便扩展一下散度(divergence)和旋度(curl)的记号,它们都使用了Nabla算子(微分向量算子),分别如下:
∇⋅F⃗ ,∇×F⃗ ∇ ⋅ F → , ∇ × F →
3,举例
总结一下这一节的思路: 偏导数向量合成 → → 合成向量与方向向量内积 → → 方向导数 → → 方向导数的最值 → → 梯度 → → 梯度向量与偏导数合成向量相同
转了一圈,又回来了。
从偏导数合成向量到梯度矢量,让我想起了高中物理中的“力的合成与分解”和“沿合力方向做功最有效率”这些物理知识,恰好能与这些数学概念对应上。
如上图,合力表示偏导数合成向量,“垂直分力”表示x方向和y方向的偏导数向量,那么方向向量则对应“做功”路径,而“沿合力方向做功”则表示方向向量与偏导数合成向量重合。Perfect !
注:在重力场或电场中,做功的结果是改变势能,因此,“做功最有效率”又可以表述为“势能变化率最快”。
注:关于梯度(gradient)可以参考以下文章:
https://math.oregonstate.edu/home/programs/undergrad/CalculusQuestStudyGuides/vcalc/grad/grad.html
https://betterexplained.com/articles/vector-calculus-understanding-the-gradient/
三、梯度下降法
1,梯度下降法
梯度下降法(gradient descent)是一个一阶最优化算法,它的核心思想是:要想最快找到一个函数的局部极小值,必须沿函数当前点对应“梯度”(或者近似梯度)的反方向(下降)进行规定步长“迭代”搜索。如下图:
看到上面这幅图,你能想到什么?
我想到了两个概念:一是地理学中的“梯田”和“等高线”,下面的链接中,有一篇文章的作者将“梯度下降”形象的比作“从山顶找路下到山谷”,这么看来,等高线肯定与梯度下降有某种关联。
第二个想到的是电学中的“带电物体的等势面”或者说是“电场等势线”。看一下wiki - potential gradient,可以扩展一下“势能梯度”的知识。
很明显,梯度常常和势能联系在一起,那么势能是什么呢?它就是上图中的弧线圈。这个解释有点虚,给个更贴切的:我们可以把势能看作是 z=f(x,y) z = f ( x , y ) 中的这个 z z ,即函数值。这些弧线圈就表示在它上面的点 对应的 z=f(x,y) z = f ( x , y ) 的值相等。从空间几何的角度来看这些“弧线圈”,更容易理解: z=f(x,y) z = f ( x , y ) 表示空间曲面,用 z=c z = c 这样一个平面去截空间曲面,它们的交线就是“弧线圈”,公式表示为
{z=f(x,y)z=c { z = f ( x , y ) z = c
当然啦,上图是把多个弧线圈画到(投影)了一个平面上。
我们也可以这样来理解“梯度下降法”: 导数表征的是“函数值随自变量的变化率” → → 梯度是各方向导数中的最大值 → → 沿 “梯度矢量”移动必定变化最快 → → 沿“梯度矢量” 反方向下降(减少)最快。
google MLCC - Gradient descent
2,梯度下降法求极值
求下列函数的极小值
f(x)=x4−3∗x3+2⇒f′(x)=4x3−9x2 f ( x ) = x 4 − 3 ∗ x 3 + 2 ⇒ f ′ ( x ) = 4 x 3 − 9 x 2# From calculation, it is expected that the local minimum occurs at x=9/4 cur_x = 6 # The algorithm starts at x=6 gamma = 0.01 # step size multiplier precision = 0.00001 previous_step_size = cur_x def df(x): return 4 * x**3 - 9 * x**2 while previous_step_size > precision: prev_x = cur_x cur_x += -gamma * df(prev_x) previous_step_size = abs(cur_x - prev_x) print("The local minimum occurs at %f" % cur_x)
The local minimum occurs at 2.249965
注:关于“gradient descent”还可以参考以下资料:
https://www.analyticsvidhya.com/blog/2017/03/introduction-to-gradient-descent-algorithm-along-its-variants/
http://ruder.io/optimizing-gradient-descent/
3,梯度下降法与最小二乘法
“机器学习”中有六个经典算法,其中就包括“最小二乘法”和“梯度下降法”,前者用于“搜索最小误差”,后者用于“用最快的速度搜索”,二者常常配合使用。代码演示如下:
# y = mx + b # m is slope, b is y-intercept def compute_error_for_line_given_points(b, m, coordinates): totalerror = 0 for i in range(0, len(coordinates)): x = coordinates[i][0] y = coordinates[i][1] totalerror += (y - (m * x + b)) ** 2 return totalerror / float(len(coordinates)) # example compute_error_for_line_given_points(1, 2, [[3, 6], [6, 9], [12, 18]])
22.0
以上就是用“最小二乘法”来计算误差,当输入为 (1,2) ( 1 , 2 ) 时,输出为 22.0 22.0
很显然,最小二乘法需要不停地调整(试验)输入来找到一个最小误差。而应用“梯度下降法”,可以加快这个“试验”的过程。
以上面这段程序为例,误差是斜率 m 和常数 b 的二元函数,可以表示为
e=g(m,b) e = g ( m , b )
那么,对最小二乘法的参数调优就转变为了求这个二元函数的极值问题,也就是说可以应用“梯度下降法”了。
“梯度下降法”可以用于搜索函数的局部极值,如下,求下列函数的局部极小值
f(x)=x5−2x3−2 f ( x ) = x 5 − 2 x 3 − 2
分析:这是一个一元连续函数,且可导,其导函数是:
f′(x)=5x4−6x2 f ′ ( x ) = 5 x 4 − 6 x 2
根据“一阶导数极值判别法”:若函数f(x)可导,且f’(x)在 x0 x 0 的两侧异号,则 x0 x 0 是f(x)的极值点。那么,怎么找到这个 x0 x 0 呢?
很简单,只需要沿斜率(导数值)的反方向逐步移动即可,如下图:导数为负时,沿x轴正向移动;导数为正时,沿x轴负方向移动。
current_x = 0.5 # the algorithm starts at x=0.5 learning_rate = 0.01 # step size multiplier num_iterations = 60 # the number of times to train the function # the derivative of the error function (x ** 4 = the power of 4 or x^4) def slope_at_given_x_value(x): return 5 * x ** 4 - 6 * x ** 2 # Move X to the right or left depending on the slope of the error function x = [current_x] for i in range(num_iterations): previous_x = current_x current_x += -learning_rate * slope_at_given_x_value(previous_x) x.append(current_x) #print(previous_x) print("The local minimum occurs at %f, it is %f" % (current_x, current_x ** 5 - 2 * current_x ** 3 - 2))
The local minimum occurs at 1.092837, it is -3.051583
import numpy as np import matplotlib.pyplot as plt plt.plot(x, marker='*') plt.show()
沿梯度(斜率)的反方向移动,这就是“梯度下降法”。如上图所示,不管初始化值设为什么,在迭代过程只会越来越接近目标值,而不会偏离目标值,这就是梯度下降法的魅力。
上面这张图是表示的是一个一元函数搜索极值的问题,未必能很好展示梯度下降法的魅力,你再返回去看上面那张“势能梯度图”,那是一个二元函数搜索极值的过程。左边的搜索路径很简洁,而右边的搜索路径,尽管因为初始值的设定,导致它的路径很曲折,但是,你有没有发现,它的每一次迭代事实上离目标都更近一步。我想,这就是梯度下降法的优点吧!
注:这段代码是一元函数求极值,如果是二元函数,则需要同时满足两个分量的偏导数的值为零,下面的线性回归程序算的就是二元偏导数。
通过组合最小二乘法和梯度下降法,你可以得到线性回归,如下:
# Price of wheat/kg and the average price of bread wheat_and_bread = [[0.5,5],[0.6,5.5],[0.8,6],[1.1,6.8],[1.4,7]] def step_gradient(b_current, m_current, points, learningRate): b_gradient = 0 m_gradient = 0 N = float(len(points)) for i in range(0, len(points)): x = points[i][0] y = points[i][1] b_gradient += -(2/N) * (y -((m_current * x) + b_current)) m_gradient += -(2/N) * x * (y -((m_current * x) + b_current)) new_b = b_current -(learningRate * b_gradient) new_m = m_current -(learningRate * m_gradient) return [new_b, new_m] def gradient_descent_runner(points, starting_b, starting_m, learning_rate, num_iterations): b = starting_b m = starting_m for i in range(num_iterations): b, m = step_gradient(b, m, points, learning_rate) return [b, m] gradient_descent_runner(wheat_and_bread, 1, 1, 0.01, 1000)
[3.853945094921183, 2.4895803107016445]
上面这个程序的核心思想就是:在内层迭代的过程中,算出每一步误差函数相当于 m 和 b 的偏导数(梯度),然后沿梯度的反方向调整 m 和 b ;外层迭代执行梯度下降法,逐步逼近偏导数等于0的点。
其中需要注意偏导数的近似计算公式,已知误差函数
E(m,b)=1N⋅∑i=0N[yi−(m⋅xi+b)]2 E ( m , b ) = 1 N ⋅ ∑ i = 0 N [ y i − ( m ⋅ x i + b ) ] 2
即各点与拟合直线的距离的平方和,再做算术平均。然后可以计算偏导数为
∂E∂m=−2N⋅xi⋅∑i=0N[yi−(m⋅xi+b)]∂E∂b=−2N⋅∑i=0N[yi−(m⋅xi+b)] ∂ E ∂ m = − 2 N ⋅ x i ⋅ ∑ i = 0 N [ y i − ( m ⋅ x i + b ) ] ∂ E ∂ b = − 2 N ⋅ ∑ i = 0 N [ y i − ( m ⋅ x i + b ) ]
其中的求和公式在程序中表现为内层for循环
下面再给出拟合后的效果图
import numpy as np import matplotlib.pyplot as plt a = np.array(wheat_and_bread) plt.plot(a[:,0], a[:,1], 'ro') b,m = gradient_descent_runner(wheat_and_bread, 1, 1, 0.01, 1000) x = np.linspace(a[0,0], a[-1,0]) y = m * x + b plt.plot(x, y) plt.grid() plt.show()
对比Numpy
import numpy as np import matplotlib.pyplot as plt a = np.array(wheat_and_bread) plt.plot(a[:,0], a[:,1], 'ro') m, b = np.polyfit(a[:,0], a[:,1], 1) print([b,m]) x = np.linspace(a[0,0], a[-1,0]) y = m * x + b plt.plot(x, y) plt.grid() plt.show()
[4.1072992700729891, 2.2189781021897814]
-
用于反弹解决方案的简单梯度流方程
2020-04-10 02:44:56受Chigusa,Moroi和Shoji近期工作的推动,我们提出了一个新的简单梯度流方程来推导反弹解,这有助于虚假真空的衰减。 我们的讨论利用了Coleman,Glaser和Martin的讨论,我们在固定势能的同时解决了动能的最小化问题... -
张力索杆结构最小势能分析方法与结构特性研究 (2010年)
2021-05-09 01:58:27本文基于势能最小化迭代建立平衡态的最小势能方法,推导了体系势能、下降向量及步长列式,建立势能最小化共轭梯度法迭代格式,并用 VC+ +编程实现了算法。通 过正交四边形网格索网数值分析算例验证了程序正确性,并分析... -
广义梯度系统完全稳定的充要条件 (2007年)
2021-06-12 08:25:20该文研究了广义梯度系统的拓扑性质,应用微分拓扑学原理证明,广义梯度系统的完全稳定性与势能界面的有界性是等价的;广义梯度系统完全稳定当且仅当该系统既有渊点又有源点。在此基础上提出了一种检验广义梯度系统... -
梯度下降法
2020-10-21 20:30:001.梯度下降法是求解最优化问题最常用的算法之一2.只要没有到达梯度为0的点,则函数值会沿着序列xk递减,最终会收敛到梯度为0的点,这就是梯度下降法3.初始值设定与学习率设置是影响梯度下降...1.梯度下降法是求解最优化问题最常用的算法之一
2.只要没有到达梯度为0的点,则函数值会沿着序列xk递减,最终会收敛到梯度为0的点,这就是梯度下降法
3.初始值设定与学习率设置是影响梯度下降法求解效率的两个重要参数
4.梯度下降法会遇到局部极值点和鞍点的问题,凸优化问题则没有该问题存在
5.梯度下降法的变种大概有加动量项的梯度下降、AdaGrad算法、RMSProp算法和Adam算法等
6.动量项累积了之前的梯度信息,使得梯度下降效率更快,合适的衰减率有机会让优化点逃脱局部极值点
7.AdaGrad跟踪梯度平方之和,它的思路是更新的特征越多,将来更新的越少,这样就有机会让其它特征(稀疏特征)赶上来
8.AdaGrad迭代效率特别慢,Rmsprop算法增加衰减因子来改善这个问题
9.Rmsprop算法的衰减因子从两个方面起作用:只对最近的梯度平方有意义,充当缩放因子
10.Adam算法兼顾动量和RMSProp 的优点
11.实际实现中,有批量梯度下降法、随机梯度下降法和小批量梯度下降法
梯度下降法(Gradient Descent)是求解最优化问题最常用算法之一。熟悉该算法的人都应该听说过这张“下山图”:
它的本质是求解“如何快速求解函数极值点”问题。本文我们就对梯度下降法做一个详细的介绍,分别从算法推导、算法变种、算法实现和算法局限四个部分讲解,这过程中我们会实例化每种算法实现的细节,我们也会看到梯度下降不同变种的区别和联系。
本文需要用到的基础知识点见传送门无穷小、梯度向量和泰勒展开
算法推导
梯度下降法是根据泰勒展开作为推导起点的,我们直接从多元函数开始,多元函数f(x)在x点处的泰勒展开有:
如果 Δx足够小,在x的某一邻域内,则我们可以忽略二次及以上的项,有:
这里Δx是一个向量,有无穷多个方向,要保证函数值递减(下山方向走),则有:
根据向量的余弦夹角定义
所以,只要保证梯度和Δx的夹角的余弦值小于0就可以了,又cos有极小值-1,从而有:
注:直接Δx=- ▽f(x)用可能会有问题,因为x+Δx可能会超出x的邻域范围之外,此时是不能忽略泰勒展开中的二次及以上的项的,因此步伐不能太大。一般设:
其中α为一个接近于0的正数,称为步长(学习率),由人工设定,用于保证x+Δx在x的邻域内,从而可以忽略泰勒展开中二次及更高的项,则有:
从初始点x0开始,使用如下迭代公式:
只要没有到达梯度为0的点,则函数值会沿着序列xk递减,最终会收敛到梯度为0的点,这就是梯度下降法。
虽然迭代终止的条件是函数的梯度值为0,但实际实现时是接近于0,此时认为已经达到极值点
注:应用梯度下降法要注意两点,第一就是初始值的设置,通常置为0或者随机数;第二就是学习率的设置,一般设置为0.001,实际上也可以采取更复杂的策略,前1万次迭代为0.001,接下来1万次迭代时设置为0.0001
如果学习率设置得太大,可能导致结果不会收敛,来回震荡;如果学习率设置得太小,学习速率太慢,效率太低。下面通过动态化来感受一下。
学习率设置恰当,函数收敛到极值点:
注:这里即使收敛到了极值点,但是局部极小值点,这就是后面我们要提到的梯度下降的局限性以及它的某些变种可以改善这种情况
学习率设置过小,迭代效率低:
学习率设置过大,函数无法收敛:
可见,学习率的设置直接影响梯度下降法的求解效率。
算法局限
梯度下降法会遇到一些问题,可能使得求解的极值点不是全局极值点,而是局部极值点或鞍点。局部极值点和鞍点都是导数为0的点,但导数为0是取得极值点的必要条件而不是充分条件。对于该问题,我们待会就在下一节中看到一些改进的策略,还有另外一种问题无需担心极值点是鞍点或者局部极值点,这个就是凸优化问题,对于凸优化,小编会在接下来新出文章讲解,这里只需要知道结论:凸优化问题利用梯度下降求解的都是全局极值点,不会是鞍点或者局部极值点。且幸运的是,很多优化问题都是凸优化问题。
算法变种
梯度下降算法的变种有很多,基本都只利用之前迭代时的梯度信息来构造每次的更新值,小编这里介绍四个变种,其各自的适用场景各不相同,我们逐一介绍。
加动量项(Momentum)
最直接的改进是为迭代公式加上动量项,动量项累积了之前的梯度信息,加上此项之后的参数更新公式为
式中的u称为衰减率(decay_rate),它是对动量项vt限制的一个参数,它是从物理概念动量来的,为了形象说明这一点,我们引入下面一张图
假设一个球放在光滑(无摩擦阻力)的灰色曲面的红色点,由于重力的因素,小球会下滑,它的势能将会转化为动能,由于曲面光滑,根据能量守恒定律,只有动能与势能的相互转化,小球会无限循环的来回震荡。动量项就是小球获得的动能大小,而衰减率u可以理解为对动量项施加的一个外力,如果为1,表示没有任何外力作用;小于1,表示施加负的外力,使得动能减少;大于1,表示施加正的外力,使得动能增加(一般不这么设置);特别地,如果衰减率为0,梯度更新公式退化为常规的梯度下降法。
下面我们沿用上面动态化例子来理解这个过程。
衰减率设置为0.8:
衰减率设置为0.9:
衰减率设置为1:
由此我们得到如下结论:
动量移动得更快(因为它积累的所有动量)
动量有机会逃脱局部极小值(因为动量可能推动它脱离局部极小值)
过大的动量使得函数无法收敛(因为外力过大,动力永不枯竭)
Adaptive Gradient算法
adaptive gradient算法为自适应梯度,简写是AdaGrad,它不是像动量一样跟踪梯度之和,而是跟踪梯度平方之和,并使用这种方法在不同的方向上调整梯度。参数更新公式为:
在机器学习优化中,一些特征是非常稀疏的。稀疏特征的平均梯度通常很小,所以这些特征的训练速度要慢得多。解决这个问题的一种方法是为每个特征设置不同的学习率,但这很快就会变得混乱。
AdaGrad 解决这个问题的思路是: 你已经更新的特征越多,你将来更新的就越少,这样就有机会让其它特征(例如稀疏特征)赶上来。用可视化的术语来说,更新这个特征的程度即在这个维度中移动了多少,这个概念由梯度平方的累积和表达
注:白色球是AdaGrad算法,青色球是常规的梯度下降
但AdaGrad有一个很致命的缺点,就是迭代的速率实在是太慢了,这是因为梯度的平方和只会增加而不会减小。到底有多慢呢,来一张感受一下什么叫慢生活:
注:白色球是AdaGrad算法,青色球是常规的梯度下降,红色球是加动量梯度下降
为此,Rmsprop (Root Mean Square Propagation)通过添加衰减因子δ来修复这个问题。
Root Mean Square Propagation
RMSProp算法由梯度值构造一个向量MS,初始化为0,更新公式为:
参数更新公式为:
来看看实际效果
注:白色球是AdaGrad算法,绿色球是RMSProp
可见,加上衰减因子δ后,效率高出了许多个量级
更精确地说,梯度的平方和实际上是梯度平方的衰减和。衰减率表明的是只是最近的梯度平方有意义,而很久以前的梯度基本上会被遗忘。这里的衰减率还有一个缩放效应: 它以一个因子(1 - 衰减率)向下缩放整个项。换句话说,如果衰减率设置为0.99,除了衰减之外,梯度的平方和将是 sqrt (1-0.99) = 0.1,因此对于相同的学习率,这一步大10倍
在这个对比中,AdaGrad (白色)最初与 RMSProp (绿色)差不多,正如调整学习率和衰减率的预期。但是 AdaGrad 的梯度平方和累计(动画中方块的大小)得非常快,以至于它们很快变得非常巨大,最终 AdaGrad 几乎停止了。另一方面,由于衰变率的原因,RMSProp 一直将方块保持在一个可控的大小。这使得 RMSProp 比 AdaGrad 更快
Adaptive Moment Estimation
Adam (Adaptive Moment Estimation)同时兼顾了动量和 RMSProp 的优点.由梯度项构造了两个向量m和v,它们的初始值为0,更新公式为:
依靠这两个值构造参数的更新值,参数的更新公式为:
Beta1是一阶矩梯度之和(动量之和)的衰减率,通常设置为0.9。Beta2是二阶矩梯度平方和的衰减率,通常设置为0.999
注:白色球是AdaGrad算法,绿色球是RMSProp,蓝色球是Adam
算法实现
具体的,给定一个数据集,确定最优化问题后,怎么利用样本进行梯度下降法的求解呢。这里有三种,主要是考虑到样本量的大小会影响计算效率而提出的。
批量梯度下降法(Batch Gradient Descent,BGD)
是梯度下降法最常用的形式,具体做法也就是在更新参数时使用所有的样本来进行更新
随机梯度下降法(Stochastic Gradient Descent,SGD)
其实和批量梯度下降法原理类似,区别在与求梯度时没有用所有的m个样本的数据,而是仅仅选取一个样本j来求梯度
小批量梯度下降法(Mini-batch Gradient Descent,MBGD)
小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷,也就是对于m个样本,我们采用x个样本来迭代,1<x<m。一般可以取x=10,当然根据样本的数据,可以调整这个x的值
参考资料
https://www.cnblogs.com/pinard/p/5970503.html
https://mp.weixin.qq.com/s/lqwUkimO4irkIZmAnp0bcg
https://mp.weixin.qq.com/s/juh2jhoOzYDARtUDGUxoyg
-
python与计算物理:正负离子势能随距离的变化
2013-10-26 00:04:00正负离子势能随距离的变化曲线,如下图: 直接上代码: #!/usr/bin/env python #coding=utf-8 ''' Created on 2013年10月12日 @author: yanghl 正负离子势能随距离的变化 ''' import ... -
梯度下降优化算法总结
2017-07-05 16:21:31一篇review:https://arxiv.org/abs/1609.04747三个梯度下降变种:批梯度...我们需要去计算整个数据集的梯度,然后计算的结果只拿去更新一步梯度,很明显随着数据集变大,批梯度下降会变得很慢而且也会很占内存。批梯度 -
油气差异泵吸作用机理探讨——以泌阳凹陷为例 (2003年)
2021-05-30 11:53:09通过对泌阳凹陷油气成藏过程的系统研究,发现在差异抬升过程中,深凹源岩区抬升幅度小,凹陷...研究表明:影响油气差异泵吸作用的因素主要有势能梯度、通道质量和泵源配置及油气运移距离;泌阳凹陷油气分布总体上受成藏运聚 -
常见梯度下降法变式总结(SGD, Momrntum,Adagrad等)
2019-09-14 16:12:34随机梯度下降法是梯度下降法的一个小变形,就是每次使用一批(batch)数据进行梯度的计算,而不是计算全部数据的梯度,因为现在深度学习的数据量都特别大,所以每次都计算所有数据的梯度是不现实的,这样会导致运算... -
TiM (M=Ni, Pd, Pt)合金势能面的理论研究
2019-12-29 02:48:58TiM (M=Ni, Pd, Pt)合金势能面的理论研究,姜振益,李盛涛,在广义梯度近似下采用密度泛函理论平面波超软赝势对钛基形状记忆合金TiM (M=Ni, Pd, Pt) 的B2与B19 (B19′)相超晶胞势能面进行了系统的理论 -
3. 机器学习中为什么需要梯度下降_以物理学观点形象优雅解释机器学习中梯度下降法...
2020-11-24 07:10:16本文展示了通过将随机或小批量梯度下降视为朗之万随机过程,其中利用损失函数识别能量,并通过学习率融入随机化,我们可以理解为什么这些算法可以与全局优化器工作的一样好。这是一个优雅的结果,表明从多个视度看... -
深度学习中多层全连接网络的梯度下降法及其变式
2020-08-05 15:11:21深度学习中多层全连接网络的梯度下降法及其变式1 梯度下降法2 梯度下降的变式1.SGD2.Momentum3.Adagrad4.RMSprop5.Adam6.小结 1 梯度下降法 梯度下降法的更新公式如下。 现在通过实际理论证明这样更新参数能够达到... -
梯度下降法--初探
2018-12-15 11:08:401、梯度下降法的基本思想 梯度下降法的基本思想可类比为一个下山的过程。假设一个场景:一个人困于山上,需要 从山上下来(即到山的最低谷)。 此时山上有大雾,看不见下山的路,他必须利用自己的脚 去探索下山的... -
梯度下降法的神经网络容易收敛到局部最优,为什么应用广泛?
2021-01-17 18:39:45当然了,我们似乎总是怀着良好的信念,认为实际遇到的函数的性质足够良好,并没有那么那么多猴鞍点、四岔鞍点、五岔鞍点……虽然好像没有什么理论上的证明,但至少根据大家对化学势能面的研究,这种信念在大多数情况... -
【菜菜的CV进阶之路-神经网络的深入理解-六】通过梯度下降法学习参数
2019-03-17 22:05:42目录 简介 第一章-使用神经网络识别手写数字 第一节-感知机 第二节-sigmoid神经元 第三节-神经网络的结构 第四节-用简单的神经网络识别手写数字 第五节-通过梯度下降法... -
梯度下降法改进过程:从 SGD 到 Adam算法
2021-05-30 22:25:531. SGD 梯度下降法 1.1 梯度下降(Gradient Descent) 梯度g指函数的某处的偏导数,指向函数上升方向。因此梯度下降法是指用梯度的负数-g更新参数,从而使下一次计算的结果向函数下降方向逼近,从而得到最小值。其中... -
不用L约束又不会梯度消失的GAN,了解一下?
2018-11-21 12:25:52这个形式好像就在 WGAN 的基础上加了一个平方形式的势能,所以称为平方势散度(QP-div,quadratic potential divergence)。 论文的附录已经证明了式 (12) 确实是一个散度。 性能分析 用 p(x)=δ(x−α),q(x)=δ(x... -
unity学习:寻路算法(AStar算法)与简单AI(势能场估价算法)
2018-06-19 22:15:49其实Astar算法和作为AI的势能场算法是有冲突的,下次重构的时候应该特别注意只使用势能场。因为势能场本身就已经包括了寻路算法,所以没必要特意写一个寻路算法增加代码复杂度,这是这次经验不足导致的。 两个核心... -
来自Swampland猜想的暗能量和暗物质的等曲率扰动
2020-03-21 00:56:44我们指出,最近提出的关于势梯度的Swampland猜想可能导致暗能量的等曲率扰动,如果典型场在该猜想首选的大规模膨胀过程中获得了大的量子涨落。 同样,如果典型场耦合到包含暗物质的暗区,则同样会诱发暗物质的等曲率... -
论文研究-基于改进的Snake模型的脑部MR图像分割方法.pdf
2019-07-22 20:04:44对各能量项进行归一化操作,并以归一化扩散方程各分量的梯度矢量流代替MR图像的梯度,提高了模型处理弱边界和深度凹陷区域的能力;对各能量函数的离散化和参数的选择进行了阐述。实验结果表明,该算法是一种有效的... -
梯度
2012-10-06 18:55:33导数,就是函数在该点的切线的斜率。所以 导数为零的地方可能是极值也可能是拐点。 物理参数的梯度,也即该物理参数的变化率 ...阻、功率、势能、引力势能、电势能等物理量。无论选取什么坐标系,标量 -
双弹簧系统中最小势能问题的基础优化算法研究
2015-12-05 20:23:47本文针对双弹簧系统中最小势能问题,通过数值实验的方法,研究了随机搜索、Powell法、共轭梯度法和牛顿法对非约束优化问题的求解效果,得出了牛顿法具有较少的计算复杂度,Powell法具有最小的迭代次数的结论。... -
【文献学习】具有高斯边缘势能的全连接CRF的高效推理
2017-12-27 15:53:35使用平均场近似估计划分函数Z的梯度。 八、实验评估 8.1收敛 通过分析Q与P之间的 K-L散度来评估平均场近似的收敛。 8.2数据集 MSRC-21数据集: PASCAL VOC2010: ... -
lecture6-mini批量梯度训练及三个加速的方法
2014-11-12 10:46:00Hinton的第6课,这一课中最后的... 这部分将介绍使用随机梯度下降学习来训练NN,着重介绍mini-批量版本,而这个也是现今用的最广泛的关于训练大型NN的方法。这里再回顾下关于一个线性神经元他的错误表面是怎样的。 ... -
《机器人动力学与控制》第七章—路径规划与避障 7.4 使用随机运动来逃离局部最小势能位置
2020-12-08 10:56:31正如前面提到过的,人工势场法的一个缺点就是在势场里面可能会存在一个局部最小势能位置导致机器人陷在那里出不来。局部极小值问题在优化领域很早就出现了,为此人们发展出了一些概率方法来应对这个问题。同样地,在...