中国正规现货交易平台,win7优化大师,微信网页版入口,镇平建设局网站机器学习笔记之优化算法——梯度下降法铺垫#xff1a;总体介绍 引言回顾#xff1a;线搜索方法线搜索方法的方向 P k \mathcal P_k Pk线搜索方法的步长 α k \alpha_k αk 梯度下降方法整体介绍 引言
从本节开始#xff0c;将介绍梯度下降法 ( Gradient Descent,GD ) … 机器学习笔记之优化算法——梯度下降法铺垫总体介绍 引言回顾线搜索方法线搜索方法的方向 P k \mathcal P_k Pk线搜索方法的步长 α k \alpha_k αk 梯度下降方法整体介绍 引言
从本节开始将介绍梯度下降法 ( Gradient Descent,GD ) (\text{Gradient Descent,GD}) (Gradient Descent,GD)。
回顾线搜索方法
线搜索方法作为一种常见优化问题的策略该方法的特点是其迭代过程中将数值解的方向和步长分开执行。对应数学符号表达如下
其中 P k \mathcal P_k Pk是一个向量描述更新方向; α k \alpha_k αk是一个 0 0 0的实数表示步长。由于我们更关注向量 P k \mathcal P_k Pk的方向性因而通常将其表示为单位向量,即 ∣ ∣ P k ∣ ∣ 1 ||\mathcal P_k|| 1 ∣∣Pk∣∣1。 x k 1 x k α k ⋅ P k x_{k1} x_k \alpha_k \cdot \mathcal P_k xk1xkαk⋅Pk
线搜索方法的方向 P k \mathcal P_k Pk
在线搜索方法——方向角度中介绍过关于目标函数 f ( ⋅ ) f(\cdot) f(⋅)的终极目标 min X ∈ R n f ( X ) \mathop{\min}\limits_{\mathcal X \in \mathbb R^n} f(\mathcal X) X∈Rnminf(X)如果数值解序列 { x k } k 0 ∞ \{x_k\}_{k0}^{\infty} {xk}k0∞对应的目标函数结果 { f ( x k ) } k 0 ∞ \{f(x_k)\}_{k0}^{\infty} {f(xk)}k0∞服从严格的单调性 f ( x k 1 ) f ( x k ) f(x_{k1}) f(x_k) f(xk1)f(xk) 那么必然有
其中 [ ∇ f ( x k ) ] [\nabla f(x_k)] [∇f(xk)]表示数值解 x k x_k xk对应目标函数的梯度向量,详细推导过程见上方链接。 P k \mathcal P_k Pk化为单位向量产生的常数系数合并到 α k \alpha_k αk中。 f ( x k 1 ) − f ( x k ) ≈ [ ∇ f ( x k ) ] T P k ⋅ α k 0 f(x_{k1}) - f(x_k) \approx [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha_k 0 f(xk1)−f(xk)≈[∇f(xk)]TPk⋅αk0
从而将满足该条件的 P k \mathcal P_k Pk称作下降方向 ( Descent Direction ) (\text{Descent Direction}) (Descent Direction)。将上式展开有
其中 θ k \theta_k θk表示向量 ∇ f ( x k ) \nabla f(x_k) ∇f(xk)与向量 P k \mathcal P_k Pk之间的夹角。在仅考虑方向角度对 f ( x k 1 ) − f ( x k ) f(x_{k1}) - f(x_k) f(xk1)−f(xk)影响的情况下将 α k \alpha_k αk忽略不改变不等号方向。 ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ⋅ cos θ k 0 ||\nabla f(x_k)|| \cdot ||\mathcal P_k|| \cdot \cos \theta_k 0 ∣∣∇f(xk)∣∣⋅∣∣Pk∣∣⋅cosθk0
其中 ∣ ∣ ∇ f ( x k ) ∣ ∣ , ∣ ∣ P k ∣ ∣ ||\nabla f(x_k)||,||\mathcal P_k|| ∣∣∇f(xk)∣∣,∣∣Pk∣∣均表示向量的模(均为固定的正值)因而 cos θ k ∈ [ − 1 , 0 ) \cos \theta_k \in [-1,0) cosθk∈[−1,0)。当 cos θ k − 1 \cos \theta_k -1 cosθk−1时 f ( x k 1 ) − f ( x k ) f(x_{k1}) - f(x_k) f(xk1)−f(xk)可取得最小值从而达到最佳的优化方向。而此时下降方向 P k \mathcal P_k Pk与梯度方向 ∇ f ( x k ) \nabla f(x_k) ∇f(xk)方向相反。因此也称此时的 P k \mathcal P_k Pk为最速下降方向 其中 ∣ ∣ ∇ f ( x k ) ∣ ∣ ||\nabla f(x_k)|| ∣∣∇f(xk)∣∣是关于上一次迭代结果 x k x_k xk的函数因而是已知信息。 P k − ∇ f ( x k ) \mathcal P_k -\nabla f(x_k) Pk−∇f(xk)
线搜索方法的步长 α k \alpha_k αk
关于当前迭代步骤的最优步长 α k \alpha_k αk通常有两种求解方式
精确搜索在 P k \mathcal P_k Pk固定的情况下选择使得 f ( x k 1 ) f(x_{k1}) f(xk1)达到最小的步长结果作为当前迭代步骤的最优步长 其中 x k , P k x_k,\mathcal P_k xk,Pk是确定的信息因此可将 f ( x k 1 ) f(x_{k1}) f(xk1)视作关于 α \alpha α的函数 ϕ ( α ) \phi(\alpha) ϕ(α)。 α k arg min α 0 f ( x k 1 ) arg min α 0 f ( x k α ⋅ P k ) arg min α 0 ϕ ( α ) \begin{aligned}\alpha_k \mathop{\arg\min}\limits_{\alpha 0} f(x_{k1}) \\ \mathop{\arg\min}\limits_{\alpha 0} f(x_k \alpha \cdot \mathcal P_k) \\ \mathop{\arg\min}\limits_{\alpha 0} \phi(\alpha) \end{aligned} αkα0argminf(xk1)α0argminf(xkα⋅Pk)α0argminϕ(α) 具体求解方式就是对 α \alpha α求导从而获取极值。但真实情况下这种方式并不可取。 关于目标函数 f ( ⋅ ) f(\cdot) f(⋅)的复杂程度我们一无所知。关于梯度 ∇ f ( x k α ⋅ P k ) \nabla f(x_k \alpha \cdot \mathcal P_k) ∇f(xkα⋅Pk)可能非常复杂。这仅仅是一次迭代步骤的解。也就是说每次迭代都要求解精确解。这无疑增加了迭代的计算代价我们仅希望迭代产生的步长能够收敛到 lim k ⇒ ∞ f ( x k ) ⇒ f ∗ \mathop{\lim}\limits_{k \Rightarrow \infty}f(x_{k}) \Rightarrow f^* k⇒∞limf(xk)⇒f∗它的中间过程是否准确并不在乎。 { ∂ ϕ ( α ) ∂ α ϕ ′ ( α ) [ ∇ f ( x k α ⋅ P k ) ] T P k ϕ ′ ( α ) 0 ⇒ α k \begin{cases}\begin{aligned} \frac{\partial \phi(\alpha)}{\partial \alpha} \phi(\alpha) [\nabla f(x_k \alpha \cdot \mathcal P_k)]^T \mathcal P_k \\ \phi(\alpha) 0 \Rightarrow \alpha_k \end{aligned}\end{cases} ⎩ ⎨ ⎧∂α∂ϕ(α)ϕ′(α)[∇f(xkα⋅Pk)]TPkϕ′(α)0⇒αk 非精确搜索相比于精确搜索我们不计较迭代产生的步长结果是否最优仅需要该结果能够帮助 f ( x k ) f(x_k) f(xk)有效收敛即可 lim k ⇒ ∞ f ( x k ) ⇒ f ∗ \mathop{\lim}\limits_{k \Rightarrow \infty}f(x_{k}) \Rightarrow f^* k⇒∞limf(xk)⇒f∗ 常见的非精确方法有 Armijo \text{Armijo} Armijo准则对 Armijo \text{Armijo} Armijo准则进行优化的 Glodstein \text{Glodstein} Glodstein准则以及基于 Armijo \text{Armijo} Armijo准则对 Armijo,Glodstein \text{Armijo,Glodstein} Armijo,Glodstein准则进行优化的 Wolfe \text{Wolfe} Wolfe准则。 这里不再赘述。
梯度下降方法整体介绍
梯度下降法是一种典型的线搜索方法。并且它的更新方向 P k \mathcal P_k Pk就是最速下降方向 − ∇ f ( x k ) - \nabla f(x_k) −∇f(xk)。
梯度下降法也被称作最速下降法。这个最速下降方向仅仅是每一个迭代步骤中向量 x k x_k xk所在位置的最速下降方向而不是全局最速下降方向。这与贪心算法类似是一个局部最优。如下图: 很明显蓝色实线是指本次迭代步骤中的最优方向;而蓝色虚线是指全局最优方向。上图描述的是二维权重特征对应的迭代过程。如果权重特征只有一维特征(一维向量;标量)对应图像表示如下 此时函数关于 x k x_k xk的梯度 ∇ f ( x k ) [ f ′ ( x k ) ] 1 × 1 \nabla f(x_k) [f(x_k)]_{1 \times 1} ∇f(xk)[f′(xk)]1×1,在迭代过程中寻找最优方向时仅存在两个方向进行选择沿着坐标轴与逆着坐标轴(红色箭头)。而此时 f ′ ( x k ) 0 f(x_k) 0 f′(xk)0,因而我们将数轴的正方向视作梯度方向对应地将数轴的反方向视作负梯度方向。针对当前的斜率信息我们沿着负梯度方向更新到 x k 1 x_{k1} xk1。
关于梯度下降法的步长 在后续过程中将介绍梯度下降法中如何求解精确步长以及相应的限制条件。这里加一个传送门 关于非精确搜索求解步长这里补充一点关于各非精确搜索方法之间的一些逻辑上的关系。 在简单认识 Wolfe Condition \text{Wolfe Condition} Wolfe Condition的收敛性证明一节中介绍了使用 Zoutendijk \text{Zoutendijk} Zoutendijk定理验证了作用于 Wolfe \text{Wolfe} Wolfe准则的步长结果可以使 { f ( x k ) } k 1 ∞ \{f(x_k)\}_{k1}^{\infty} {f(xk)}k1∞收敛。但实际上 Zoutendijk \text{Zoutendijk} Zoutendijk定理同样可以作用于 Armijo,Glodstein \text{Armijo,Glodstein} Armijo,Glodstein准则并证明其步长能够使 { f ( x k ) } k 1 ∞ \{f(x_k)\}_{k1}^{\infty} {f(xk)}k1∞收敛。 由于 Wolfe \text{Wolfe} Wolfe准则是基于 Armijo \text{Armijo} Armijo准则提出的其本质就是在 Armijo \text{Armijo} Armijo准则的基础上那些梯度结果 ∇ f ( x k 1 ) \nabla f(x_{k1}) ∇f(xk1)过小的 ϕ ( α ) \phi(\alpha) ϕ(α)点对应的 α \alpha α通过参数 C 2 \mathcal C_2 C2消除掉了 Armijo Condition : { ϕ ( α ) f ( x k ) C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ α C 1 ∈ ( 0 , 1 ) Wolfe Condition : { ϕ ( α ) ≤ f ( x k ) C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ α ϕ ′ ( α ) ≥ C 2 ⋅ [ ∇ f ( x k ) ] T P k C 1 ∈ ( 0 , 1 ) C 2 ∈ ( C 1 , 1 ) \begin{aligned} \text{Armijo Condition : }\begin{cases} \phi(\alpha) f(x_k) \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \quad \\ \mathcal C_1 \in (0,1) \end{cases} \\ \text{Wolfe Condition : }\begin{cases} \phi(\alpha) \leq f(x_k) \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \phi(\alpha) \geq \mathcal C_2 \cdot [\nabla f(x_k)]^T \mathcal P_k \\ \mathcal C_1 \in (0,1) \\ \mathcal C_2 \in (\mathcal C_1,1) \end{cases} \end{aligned} Armijo Condition : ⎩ ⎨ ⎧ϕ(α)f(xk)C1⋅[∇f(xk)]TPk⋅αC1∈(0,1)Wolfe Condition : ⎩ ⎨ ⎧ϕ(α)≤f(xk)C1⋅[∇f(xk)]TPk⋅αϕ′(α)≥C2⋅[∇f(xk)]TPkC1∈(0,1)C2∈(C1,1) 反过来说 Armijo \text{Armijo} Armijo准则相当于 Wolfe \text{Wolfe} Wolfe准则的一种极端情况在 C 1 \mathcal C_1 C1确定划分边界的基础上一个 α \alpha α都不去除即 C 2 1 \mathcal C_2 1 C21。 同理 Glodstein \text{Glodstein} Glodstein准则也是 Wolfe \text{Wolfe} Wolfe准则中的一种情况。与 Armijo \text{Armijo} Armijo这种极端情况不同的是 Glodstein \text{Glodstein} Glodstein准则更像是一种取巧情况在 C 1 ∈ ( 0 , 1 2 ) \begin{aligned}\mathcal C_1 \in \left(0,\frac{1}{2} \right)\end{aligned} C1∈(0,21)确定划分边界的基础上选择一个合适的 C 2 ∈ ( 1 2 , 1 ) \begin{aligned}\mathcal C_2 \in \left(\frac{1}{2},1\right)\end{aligned} C2∈(21,1)使得斜率分别为 C 1 ⋅ [ ∇ f ( x k ) ] T P k \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k C1⋅[∇f(xk)]TPk和 C 2 ⋅ [ f ( x k ) ] T P k \mathcal C_2 \cdot [f(x_k)]^T \mathcal P_k C2⋅[f(xk)]TPk的直线关于斜率为 1 2 [ ∇ f ( x k ) ] T P k \begin{aligned}\frac{1}{2} [\nabla f(x_k)]^T \mathcal P_k\end{aligned} 21[∇f(xk)]TPk直线对称。 因为在 C 1 ∈ ( 0 , 1 2 ) \mathcal C_1 \in \begin{aligned} \left(0,\frac{1}{2}\right)\end{aligned} C1∈(0,21)情况下 Wolfe \text{Wolfe} Wolfe准则关于 C 2 \mathcal C_2 C2的描述范围 ( C 1 , 1 ) (\mathcal C_1,1) (C1,1)必然大于 ( 1 2 , 1 ) \begin{aligned}\left(\frac{1}{2},1\right)\end{aligned} (21,1)。因此必然能够找到这个合适的点从而使该点情况下 Wolfe \text{Wolfe} Wolfe准则等价于 Glodstein \text{Glodstein} Glodstein准则。
关于梯度下降法的收敛速度相比梯度下降法的收敛性我们更关心在已知收敛的情况下它的收敛速度情况。在上一节中对收敛速度进行了简单认识
从收敛速度判别标准的角度划分介绍了 Q \mathcal Q Q-收敛速度与 R \mathcal R R-收敛速度从收敛速度强度的角度划分(以 Q \mathcal Q Q-收敛速度为例)介绍了 Q \mathcal Q Q-次线性收敛/线性收敛/超线性收敛/二次收敛。
而在梯度下降法中它的收敛速度取决于目标函数 f ( ⋅ ) f(\cdot) f(⋅)自身的性质 关于目标函数 f ( ⋅ ) f(\cdot) f(⋅)的基础条件向下有界在定义域内可微(至少局部可微) 如果不可微我们甚至没有办法求解梯度更不要说梯度的更新了。 要求 f ( ⋅ ) f(\cdot) f(⋅)至少是局部凸函数并且其梯度 ∇ f ( ⋅ ) \nabla f(\cdot) ∇f(⋅)必然服从利普希兹连续。而利普希兹连续的作用在于目标函数梯度 ∇ f ( ⋅ ) \nabla f(\cdot) ∇f(⋅)的变化量被常数 L \mathcal L L限制住。或者说 ∇ f ( ⋅ ) \nabla f(\cdot) ∇f(⋅)的变化不会过于剧烈。 相反如果不对 ∇ f ( ⋅ ) \nabla f(\cdot) ∇f(⋅)进行约束很容易会出现梯度爆炸。因为可能存在目标函数梯度可能在某一范围内飙升至极大。
在综上条件下可达到次线性收敛级别的收敛速度。
在上述条件的基础上如果 f ( ⋅ ) f(\cdot) f(⋅)是一个强凸函数 ( Strong Convex Function ) (\text{Strong Convex Function}) (Strong Convex Function)可达到线性收敛级别的收敛速度。 关于凸函数的强度性质凸函数 严格凸函数 强凸函数。在后续进行介绍。传送门
在第二种条件的基础上如果 f ( ⋅ ) f(\cdot) f(⋅)仍然是一个强凸函数并且 f ( ⋅ ) f(\cdot) f(⋅)在其定义域内二阶可微其对应的 Hession Matrix ∇ 2 f ( ⋅ ) \text{Hession Matrix} \nabla^2 f(\cdot) Hession Matrix∇2f(⋅)存在并满足
其中 L \mathcal L L依然是利普希兹连续中的具有限制作用的常数; ≼ \preccurlyeq ≼表示矩阵小于等于; I \mathcal I I表示单位矩阵。关于 ∣ ∣ ∇ f ( x ) − ∇ f ( y ) ∣ ∣ ∣ ∣ x − y ∣ ∣ ∇ 2 f ( ξ ) \begin{aligned}\frac{||\nabla f(x) - \nabla f(y)||}{||x - y||} \nabla^2 f(\xi)\end{aligned} ∣∣x−y∣∣∣∣∇f(x)−∇f(y)∣∣∇2f(ξ)详见拉格朗日中值定理。 ∀ x , y ∈ R n : ∣ ∣ ∇ f ( x ) − ∇ f ( y ) ∣ ∣ ∣ ∣ x − y ∣ ∣ ∇ 2 f ( ξ ) ≼ L ⋅ I \forall x,y \in \mathbb R^n :\begin{aligned}\frac{||\nabla f(x) - \nabla f(y)||}{||x - y||} \nabla^2 f(\xi) \preccurlyeq \mathcal L \cdot \mathcal I \end{aligned} ∀x,y∈Rn:∣∣x−y∣∣∣∣∇f(x)−∇f(y)∣∣∇2f(ξ)≼L⋅I
同样可以达到线性收敛级别的收敛速度。
相关参考 【优化算法】梯度下降法-总体介绍
