完善资料让更多小伙伴认识你,还能领取20积分哦, 立即完善>
扫一扫,分享给好友
1. 小明假期结束回校,可以坐火车,可以坐汽车,可以坐飞机,还可以走着,小明从哪条路去学校更好呢? 2. 简单的数学,一元二次方程求根。 3. 高深的数学,七桥问题,怎么才能通过所有的桥各自一次走回七点所在的岸边。 4. 机器学习中,求代价函数在约束条件下的最优解问题。 其上四个问题,均是参数寻优问题。问题1中,小明可以通过试探法将所有的方式计算一下时间成本,经济成本,舒适程度,来选择一个性价比最合适的返校方式。问题2中,可以通过一元二次方程的求根公式直接求出解来。问题3中,七桥问题则是典型的图论问题,通过抽象为图,推理得出该题无解。问题4中,机器学习则是数值分析中方程的迭代解法。 本文目标 本文主要讲清楚梯度下降法、牛顿下降法是如何想到并引入参数寻优中的,以及他们为什么有效。 参数寻优的迭代法的基本原理 图1 一维的二阶代价函数展示 图2 二维的二阶代价函数展示 通过代价函数的形状,我们很自然地想到,如果我们从任意一个参数点出发,是否可以找到刚好是让代价下降的方向,沿着这个方向,一定能找到当前的极值点。 于是,迭代法参数寻优的基本原理有了:沿着(代价)函数下降的方向寻找参数,能够找到极值点。 梯度下降法的引入 在我们已经学过的数学知识中,导数和方向导数是能找到函数变化方向的。导数表示了曲线的斜率(倾斜度),方向导数表示了曲面沿着任意方向的斜率(倾斜度)。一维时,导数就足够了。但多维时,就需要借助方向导数了,而我们更希望能找到变化率最大的方向。因此,多维下借用方向导数变化最大的情况:梯度,梯度的方向是函数某点增长最快的方向,梯度的大小是该点的最大变化率。 三维下,推导方向导数与梯度的关系 方向导数: ∂f∂l=∂f∂x∗cos(α)+∂f∂y∗cos(β)+∂f∂z∗cos(γ) 方向: l=(cos(α),cos(β),cos(γ)) 梯度: Grad=(∂f∂x,∂f∂x,∂f∂x) ∂f∂l=Grad∗l ∂f∂l=|Grad|∗1∗cos(Grad,l) 当两者方向相同时, cos(Grad,l)=1,∂f∂l 取得最大值 |Grad| 。因此,梯度表示了函数增长最快的方向,和最大的增长率。 牛顿下降法的引入 牛顿法求解f(x)=0 在讲牛顿下降法之前,先讲一下 f(x)=0 的求解。将 f(x) 在 x0 处进行一阶泰勒展开: 图 3,牛顿法求解 f(x)=0 f(x)=f(x0)+f′(x0)1!(x−x0) 则得到 f(x0)+f′(x0)(x−x0)=0 解得 x=x0−f(x0)f′(x0)=x1 从图中可以看出, x1比x0 更靠近真实解。如果接下来在 x1 处一阶泰勒展开,会得到更靠近真实解的 x2 ,以此类推: xn+1=xn−f(xn)f′(xn) 牛顿法具有天然的迭代性,可以不断逼近真实解。 牛顿下降法 那么牛顿下降法是如何引入的呢?求解最优解 minx[Cost(x)] ,等价于 找到 x 满足 f′(x)=0 。对于 f′(x)=0 的求解,就可以用上面的牛顿法来不断逼近真实解了。 对 f′(x) 在 x0 处一阶泰勒展开。 f′(x)=f′(x0)+(x−x0)∗f′′(x0) 令 f′(x)=0 得 x=x0−f′(x0)f′′(x0)=x1 xn+1=xn−f′(xn)f′′(xn) 牛顿下降法的几何意义 一阶导数决定的函数当前是否增减,二阶则决定这当时是否凹凸。牛顿下降法用二次曲面去拟合当前所处位置的局部曲面,下降方向上的选择不仅考虑了坡度是否足够大,而且考虑了走了这一步之后,坡度是否会变得更大。所以,牛顿下降法比梯度下降法看得更远,能更快地走到局部的最底部。 牛顿下降法的局限性 (1)收敛性对初始点的选取依赖性很大; (2)每次迭代都要计算Hessian矩阵(二阶导数),计算量大; (3)要求二阶可微分,计算Dk时,方程组有时非正定或者病态,无法求解Dk或者Dk不是下降方向。 阻尼牛顿法的引入 对牛顿法局限性的不同改进,导致阻尼牛顿法和拟牛顿法的出现。 针对牛顿法,有时得到的牛顿方向不是下降的情况,提出了阻尼牛顿法。上升的情况,比如 f′(x)<0,f′′(x)<0 。 解决方法是:在新的迭代之前,找到下降方向,且是下降最大的方向。 (1)先确定最优解的所在区间[a, b]。 (2)一维搜索。在解区间[a, b]内搜索使得目标函数下降最大的点。 其中(1)可以用进退法,找到三个点,使得 f(a−h),f(a),f(a+h) 满足大小大的规律即可。 一维搜索方法主要分为试探法和插值法,试探法有黄金分割法、fibonacci法、平分法、格点法等;插值法有牛顿法、抛物线法等。判断解两边值的大小关系或者求导为0。 剩下的部分就是跟牛顿下降法一样了。(具体实现看前面的博客) 拟牛顿法的引入 针对牛顿下降法hessian矩阵计算量大,需要正定矩阵的局限性,提出了拟牛顿法,拟牛顿法的核心是对Hessian矩阵的逆的估计。 根据不同的估计方法,分为DFP和BFGS。 图 4 DFP 图 5 BFGS 机器学习的一个重要组成部分是如何寻找最优参数解。本文就常见寻优方法进行总结,并给出简单python2.7实现,可能文章有点长,大家耐心些。 寻找最优参数解,就是在一块参数区域上,去找到满足约束条件的那组参数。形象描述,比如代价函数是个碗状的,那我们就是去找最底部(代价最小)的那个地方的对应的参数值作为最优解。那么,如何找到那个底部的最优参数解呢,如何由一个初始值,一步一步地接近该最优解呢。寻优方法,提供了靠近最优解的方法,其中涉及到的核心点,无外乎两点:靠近最优解的方向和步幅(每步的长度)。 最优化,分为线性最优化理论和非线性最优化理论。其中线性最优化又称线性规划。目标函数和约束条件的表达是线性的, Y=aX ;非线性最优化理论,是非线性的。其中包括梯度法,牛顿法,拟牛顿法(DFP/BFGS),约束变尺度(SQP),Lagrange乘子法,信赖域法等。 算法原理及简单推导 最速下降法(梯度下降法) 借助梯度,找到下降最快的方向,大小为最大变化率。 θnew=θold−α∗Gradient 梯度:是方向导数中,变化最大的那个方向导数。 梯度方向:标量场中增长最快的方向。 梯度大小:最大变化率。 更新:沿着梯度的负向,更新参数(靠近最优解)。 ********************************************* Algorithm:GradientDescent Input:x−Data;y−Label;α−调节步幅;θ0;Iternum; Output:θoptimal Process: 1. Initial θ=θ0 2. While Loop H=f(x,θ);模型函数H Compute Gradient According to f(x,θ) Update θ:=θ−α∗Gradient Loop=Loop+1 3. Return θ ********************************************* 梯度下降法 优点:方便直观,便于理解。 缺点:下降速度慢,有时参数会震荡在最优解附近无法终止。 牛顿下降法 牛顿下降法,是通过泰勒展开到二阶,推到出参数更新公式的。 f(x+Δ(x))≈f(x)+f′(x)∗Δ(x)+12∗f′′(x)∗Δ2(x) 上式等价于 f′(x)+f′′(x)∗Δ=0 从而得到更新公式: xnew−xold=−f′(x)f′′(x)=−[f′′(x)]−1∗f′(x) 调整了参数更新的方向和大小(牛顿方向)。 ********************************************* Algorithm:Newton Descent Input:x−Data;y−label;θ0;ϵ−终止条件; Ouput:θoptimal Process: 1. Initial θ=θ0 2. Compute f′(x,θ) if|f′(x),θ)|⩽ϵ return θoptimal=θ else Compute H=f′′(x,θ) Dk=−[H]−1∗f′(x,θ) Update θ:=θ+Dk 3. Return step 2 ********************************************* 牛顿下降法 优点:对于正定二次函数,迭代一次,就可以得到极小值点。下降的目的性更强。 缺点:要求二阶可微分;收敛性对初始点的选取依赖性很大;每次迭代都要计算Hessian矩阵,计算量大;计算Dk时,方程组有时奇异或者病态,无法求解Dk或者Dk不是下降方向。 阻尼牛顿法 这是对牛顿法的改进,在求新的迭代点时,以Dk作为搜索方向,进行一维搜索,求步长控制量 α ,使得 α=argminθ[f(θ+α∗Dk)] ,找到 f 下降的 α ,且是 f 下降最大的 α ,然后令 θ=θ+α∗Dk 。克服了牛顿法的奇异和病态方程无解, Dk 非下降的缺点。 ********************************************* Algorithm:Damped Newton Descent Input:x−Data;y−label;θ0;ϵ Output:θoptimal Process: 1. Initial θ=θ0 2. Compute f′(x,θ) if|f′(x,θ)|⩽ϵ Return θoptimal=θ else Compute H=f′′(x,θ) Dk=−[H]−1∗f′(x,θ) Compute α According to: α=argminθ[f(θ+α∗Dk)] Update θ:=θ+α∗Dk 3. Return step 2 ********************************************* 阻尼牛顿法 优点:修改了下降方向,使得始终朝着下降的方向迭代。 缺点:与牛顿法一样。 一维搜索方法简介 一维无约束优化问题 minF(α) ,求解 F(α) 的极小值和极大值的数值迭代方法,即为一维搜索方法。常用的方法包括:试探法(黄金分割法,fibonacci方法,平分法,格点法);插值法(牛顿法,抛物线法)。 (1)确定最优解所在区间[a,b] (进退法) 思想:从初始点 α0 开始,以步长 h 前进或者后退,试出三个点 f(α0+h),f(α0),f(α0−h) ,满足大,小,大规律。 ********************************************* Process: 1. Initial α1=α0;α2=α0+h; f1=f(α1;f2=f(α2) 2. if f1>f2 forward,h=2h else backward,h=−h; swqp(α1,α2); swap(f1,f2); 3. Getthe third point, α3=α2+h;f3=f(α3) if f3>f2 a=min(α1,α3) b=max(α1,α3) Return [a,b] if f3 α1=α2;f1=f2; α2=α3;f2=f3; 4. Return step 2 ********************************************* (2)在[a, b]内,找到极小值(黄金分割法和平分法) ********************************************* Process:黄金分割法 1. Initial check point α1=a+0.382∗(b−a); α2=a+0.618∗(b−a); f1=f(α1); f2=f(α2); 2. Change the edge if f1>f2 a=α1;b=b; else a=a;b=α2 3. Stop condation if |a−b|⩽ϵ Return α=(b+a)/2 else Return step 1 Process:平分法(需要求导数) 1. Initial check point α=(b+a)/2 2. Compute gradient f′=f′(α) if f′=0,or |f′|<ϵ Return α if f′>0 a=a;b=α; if f′<0 a=α;b=b; Return step 1 ********************************************* 思考:如何在实际应用中,选择[a, b],函数 f 是什么样子的?这些问题需要讨论。整个优化的目标是:找到最优 θ ,使得代价 CostJ 最小。故此, f=CostJ 。 拟牛顿法 - DFP法 由于牛顿法计算二阶导数,计算量大,故此用其他方法(一阶导数)估计Hessian矩阵的逆。 f(x) 在 Xk+1 处,展开成二阶泰勒级数。 f(x)≈f(xk+1)+f′(xk+1)∗(x−xk+1)+12∗f′′(xk+1)∗(x−xk+1)2 f(x)−f(xk+1)≈f′(xk+1)∗(x−xk+1)+f′′(xk+1)∗(x−xk+1)2 两侧同时除以 x−xk+1 则得到: f′(x)=f′(xk+1)+f′′(xk+1)∗(x−xk+1) f′(xk+1)−f′(xk)≈f′′(xk+1)∗(xk+1−x) 令 sk=xk+1−xk;yk=f′(xk+1)−f′(xk); 则 yk=f′′(xk+1)∗sk 且 sk=[f′′(xk+1)]−1∗yk 用上式来估计Hessian的逆。设 H=[f′′(xk+1)]−1 根据H的构造函数不同,分为不同的拟牛顿方法,下面为DFP方法: Hk+1=Hk+DH DH=sk∗sk′sk′∗yk−Hk∗yk∗yk′∗Hkyk′∗Hk∗yk ********************************************* Algorithm:DFP Quasi−Newton Method Input:x−Data;y−Label;θ0;ϵ Output:θoptimal Process: 1. Initial paraments θ=θ0; H=I; Dk=−f′(xk,θ) 2. if |f′(xk,θ)|⩽ϵ Returnθoptimal=θ else Compute α according to: α=argminθ[f(θ+α∗Dk)] Update θ:=θ+α∗Dk Update H as follow: sk=θk+1−θk yk=f′(xk+1)−f′(xk) DH=sk∗sk′sk′∗yk−H∗yk∗yk′∗Hyk′∗H∗yk H:=H+DH Dk=−H∗f′(xk,θ) 3. Return step 2 ********************************************* 拟牛顿法DFP: 优点:减少了二阶计算,运算量大大降低。 拟牛顿法 - BFGS法 若构造函数如下,则为BFGS法。 Hk+1=Hk+DH DH=[1+yk′∗Hk∗yksk′∗yk]∗sk∗sk′sk′∗yk−sk∗yk′∗Hksk′∗yk ********************************************* Algorithm: BFGS Quasi−Newton Method Input:x−Data;y−Label;θ0;ϵ Output:θoptimal Process: 1. Initial paraments θ=θ0;H=I;Dk=−f′(xk,θ); 2. if |f′(xk,θ)|⩽ϵ Return θoptimal=θ else Compute α according to: α=argminα[f(θ+α∗Dk)] Update θ:=θ+α∗Dk Update H as follow: sk=θk+1−θk yk=f′(xk+1)−f′(xk) DH=[1+yk′∗H∗yksk′∗yk]∗sk∗sk′sk′∗yk−sk∗yk′∗Hsk′∗yk H:=H+DH Dk=−H∗f′(xk,θ) 3. Return step 2 ********************************************* 拟牛顿法是无约束最优化方法中最有效的一类算法。 |
|
|
|
只有小组成员才能发言,加入小组>>
2441 浏览 0 评论
9126 浏览 4 评论
36804 浏览 19 评论
5031 浏览 0 评论
24788 浏览 34 评论
1543浏览 2评论
1762浏览 1评论
2210浏览 1评论
1567浏览 0评论
539浏览 0评论
小黑屋| 手机版| Archiver| 电子发烧友 ( 湘ICP备2023018690号 )
GMT+8, 2024-12-26 02:31 , Processed in 1.212517 second(s), Total 78, Slave 62 queries .
Powered by 电子发烧友网
© 2015 bbs.elecfans.com
关注我们的微信
下载发烧友APP
电子发烧友观察
版权所有 © 湖南华秋数字科技有限公司
电子发烧友 (电路图) 湘公网安备 43011202000918 号 电信与信息服务业务经营许可证:合字B2-20210191 工商网监 湘ICP备2023018690号