最优化算法数学详解之——梯度下降法和牛顿迭代法

目录应用情景为何不直接求解析解?梯度下降法牛顿迭代法两种算法比较

应用情景

当我们有了一堆数据,需要用这堆数据构建模型时,首先需要确定模型中的变量,其次确定模型形式,最后需要确定模型中的参数。如构建一个多元线性回归模型,参数就是变量前的系数。

选择模型参数的标准是什么?并不统一。但一般需要构造一个关于参数

θ\theta

θ的损失函数

F(θ,X)F(\theta,X)

F(θ,X)(X实际为已知数,就是样本值),一般逻辑是,若真实值和模型预测值差距较大,

F(θ,X)aF(\theta,X)\to a

F(θ,X)→a,若真实值和模型预测值差距较小,

F(θ,X)bF(\theta,X)\to b

F(θ,X)→b,且

F(θ,X)(a,b)F(\theta,X)\in (a,b)

F(θ,X)∈(a,b)。(这里的数学表达可能并不准确,勿喷)

接下来要构造的问题是,求参数

θ\theta

θ,使

F(θ,X)F(\theta,X)

F(θ,X)取

minmin

min。可以注意到,样本值的选取会影响

F(θ,X)F(\theta,X)

F(θ,X)的形式,从而影响参数

θ\theta

θ的选取。例如,在训练一元线性回归模型中,若选取100个样本,则

F(θ,X)F(\theta,X)

F(θ,X)中包含100个预测值和真实值之差的平方和;而若选取10个样本,则只包含10个项的平方和。对这两个函数取极值,一般会有很大的不同。因此,如何从样本中选取训练集来训练参数,也是一个重要问题。

为何不直接求解析解?

求解无约束优化问题有多种算法,如传统的公式解和数值优化。前者是通过代数方法解出方程理论解,是一个精确值;而数值优化方法求出的是一个近似值。这种方法又分为一阶优化算法(如梯度下降法)、二阶优化算法(如牛顿迭代法)、非梯度优化算法等。

为什么需要求近似值呢?因为有时候,需要解的函数太复杂,甚至不存在一个求解的公式。比如,伽罗瓦在群论中证明了,五次及以上多项式方程没有显示表达的求根公式。在理论解很难获得的情况下,求近似解成了一种替代方法。

个人理解,不管是一阶还是二阶优化算法,其本质都是构造迭代步长的函数,使得一个初始点可以通过该迭代函数收敛到极值点。而这个函数并不是唯一的,只要满足一定约束条件即可。这两种算法中所构造的函数只是这些函数中的几种可能。

梯度下降法

总体来看,梯度下降法就是从函数上的某个初始点开始,一次次移动到函数的极值点。
为什么是一次次移动?这是一种迭代思想。每次移动后,需要判断该移动结果是否满足某些既定条件,若不满足,从该点继续移动,若满足,移动结束。
本文讨论的极值点均为极小值点,因为机器学习中的一个关键步骤是构造损失函数,需要最小化损失函数。
网上有很多从下山走最陡坡的角度理解这个算法的,但个人感觉还是有很多疑问。因此,下面提出另外两种理解方式:

    猜测性构造

首先,需要选择进行移动的变量。虽然实际上移动的是一个点,但因为有函数对应关系

y=f(x)y=f(x)

y=f(x),可以只定义一个x轴或者y轴方向上的移动。此处定义一个x轴上的移动。这样,就可以构造一个问题:令

Δx=g(x)\Delta x=g(x)

Δx=g(x) ,那么这个函数与哪些变量相关?下面考虑三个问题:首先,往哪个方向移动?其次,每次移动多少?最后,移动到什么时候停止。
为简单起见,先以一个连续且存在唯一极小值点的代表函数:二次函数

y=x2y=x^2

y=x2为例。对上述3个问题,下文逐一分析:
问题1
对比初始点为x =1与x = -1,现在均需要移到x = 0。两者移动方向相反。什么导致了这种差别?注意到x = 1与x=-1处的切线斜率正好为相反数。因此,猜测初始点处的导数可能是影响移动方向的关键因素。
问题2
我们希望在离极小值更远的地方,

Δx\Delta x

Δx更大,在离极小值更近的地方,

Δx\Delta x

Δx更小。因此需要观察唯一的已知条件,即

y=f(x)y=f(x)

y=f(x)有什么性质是可以满足这种关系的,从而与需要解决的问题建立联系。注意到

y=f(x)y=f^\prime(x)

y=f′(x)的绝对值在趋近于函数极小值时越来越小,趋近于0,因此

Δx\Delta x

Δx还可以和

f(x)f^\prime(x)

f′(x)相关。且

f(x)>0f^\prime(x)>0

f′(x)>0时,x应该往左移,

xixi1x_i-x_{i-1}

xi​−xi−1​<0;

f(x)<0f^\prime(x)<0

f′(x)<0时,x应该往右移,

xixi1x_i-x_{i-1}

xi​−xi−1​>0;
因此,至此可以对

Δx\Delta x

Δx的函数形式进行推测:

Δx=g(f(x),fxi1(x))\Delta x=g(f(x),f_{x_{i-1}}^\prime(x))

Δx=g(f(x),fxi−1​′​(x)),或者表示为

xixi1=λfxi1(x)x_i-x_{i-1}=-\lambda f_{x_{i-1}}^\prime(x)

xi​−xi−1​=−λfxi−1​′​(x),其中

λ>0\lambda>0

λ>0。
问题3
什么时候迭代停止?因为越趋近极小值点,

Δx\Delta x

Δx越小,因此需要先定义一个精度d,当

Δx<=d|\Delta x|<=d

∣Δx∣<=d时,

xix_i

xi​即为近似的极值点x值。

    数学构造(周志华《机器学习》方法)

直接从曲线上点的移动入手。首先构造初始点x附近的泰勒一次展开式:

f(x+Δx)=f(x)+Δxf(x)f(x+\Delta x)=f(x)+\Delta x f^\prime(x)

f(x+Δx)=f(x)+Δxf′(x)
若要移动到极小值,我们可以对每次的移动加一个约束:

f(x+Δx)<f(x)f(x+\Delta x)<f(x)

f(x+Δx)<f(x),以保证每次移动后函数值都在下降。不过这样的约束有一个问题,就是如果函数有多个极小值,那初始点的不同也会导致移动到极小值的不同(从该初始点可能需要先越过一个极大值才能到另一个极小值,但按照这个约束,只会从该点往下降的方向走)。这也说明了,梯度下降法得到的极小值仅是局部极小值。
这样,问题就转化成了要构造一个

Δx\Delta x

Δx,使

Δxf(x)<0\Delta x f^\prime(x)<0

Δxf′(x)<0。
一种很自然的方法就是构造平方。因此令

Δx=λf(x)\Delta x =-\lambda f^\prime(x)

Δx=−λf′(x)。

这是基本的梯度下降法。一个显著的缺点是在很接近极小值时候,因为

x0x\to0

x→0时候也有

f(x)0f^\prime(x)\to0

f′(x)→0,因此步长也会趋近于0。
因此,还有其他一些优化的梯度下降法。此处简单介绍几种梯度下降法,是从使用样本数量的角度进行分类:批量梯度下降(BGD)、随机梯度下降(SGD)和小批量随机梯度下降(Mini-Batch SGD)

批量梯度下降:用训练集中所有样本构造损失函数,进行迭代取极值
随机梯度下降:用训练集中一个样本构造损失函数,进行迭代取极值
小批量随机梯度:选取部分样本迭代取极值。通常是1-几百之间
一般来说,用到的样本量越大,其确定的下降方向越准,引起训练震荡越小。跑完一次全数据集所需的迭代次数减少,但因为损失函数变复杂了,计算复杂度也增加,从而对参数的修正也可能更慢。当Batch Size 增大到一定程度,其确定的下降方向已经基本不再变化,也就是说一部分的样本在确定下降方向上其实是冗余的。
也就是说,对于大样本+复杂模型,用小批量SDG更好些。

牛顿迭代法

与梯度下降法的主要区别在于对初始点取二阶泰勒展开式,也就是

f(x+Δx)=f(x)+f(x)Δx+12f(x)(Δx)2f(x+\Delta x)=f(x)+ f^\prime(x)\Delta x+{1 \over 2} f^{\prime\prime}(x)(\Delta x)^2

f(x+Δx)=f(x)+f′(x)Δx+21​f′′(x)(Δx)2
若沿用上述思路,令

f(x+Δx)<f(x)f(x+\Delta x)<f(x)

f(x+Δx)<f(x),目前还没有构造出来。看网上其他有人做法是:因为

x+Δxx+\Delta x

x+Δx为极值点,故令

f(x+Δx)=0f^\prime(x+\Delta x)=0

f′(x+Δx)=0。故要对等式两边对

Δx\Delta x

Δx求导。故

Δx=f(x)f(x)\Delta x=-{f^\prime(x) \over f^{\prime\prime}(x)}

Δx=−f′′(x)f′(x)​。
但不是很理解这个做法,因为迭代是逐渐趋近极值点,每一次的

x+Δxx+\Delta x

x+Δx并不会刚好是极值点。(附上一个近期的评论,有同学说这是一个试错的过程,假设下一个点是极值点。感觉有些道理。是不是可以这样理解,梯度下降是每次都找函数减小的方向,但用牛顿迭代法,每次下降并不一定是令函数减小的方向,因为下降最快的路径并不一定是使每一步都下降的路径)

两种算法比较

高阶优化算法比低阶收敛的更快,因为高阶算法相当于看的更远,在做出某一步点移动的选择时候,会考虑之后的更多步。直观的看,高阶算法所用的泰勒展开式阶数更高,也就是对每一步起始点附近区域的拟合与原函数更吻合,因此下降路径更符合真实的最快下降路径。低阶算法所考虑的下降路径则更局部。

当然,高阶算法的计算复杂度更高,因其每轮迭代中涉及到高阶导数矩阵的求逆,计算复杂度很高,尤其在高维问题中几乎不可行。因此在神经网络算法中,一般采取梯度下降法。

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

最优化算法数学详解之——梯度下降法和牛顿迭代法

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 最优化算法数学详解之——梯度下降法和牛顿迭代法
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏