数学教学系列8:梯度下降法

梯度下降法是一个一阶最优化算法,利用负梯度方向来决定每次迭代的新的搜索方向,使得每次迭代能使待优化的目标函数逐步减小。梯度下降法是2范数下的最速下降法。

向量微积分中,标量场的梯度是一个向量场。标量场中某一点上的梯度指向标量场增长最快的方向,梯度的长度是这个最大的变化率。

我们前一个系列介绍了机器学习的相关内容,梯度下降法相对牛顿法求取海瑟矩阵,耗费的内存较小,优化前期收敛速度较快得到了广泛的利用。

梯度下降法算法简介


梯度下降法(gradient descent)或最速下降法(steepest decent)使求解无约束最优化的一种最常用的方法,有实现简单的优点。梯度下降法是迭代法,每一步需要求解目标函数的梯度向量。
假设$f(x)$是$R^n$上具有一阶连续偏导数的函数。要求解的无约束最优化问题是$$min f(x)$$
$x^*$表示目标函数$f(x)$的极小点。
梯度下降法是一种迭代算法。选取适当的初值$x^{(0)}$,不断迭代,更新$x$的值,进行目标函数的**极小化**,直到收敛。由于负梯度方向是使函数值下降最快的方向,在迭代的每一步,以负梯度方向更新$x$的值,从而达到减少函数值的目的。
由于$f(x)$具有一阶连续偏导数,若第$k$次迭代值为$x^{(k)}$,则可将$f(x)$在$x^{(k)}$附近进行一阶泰勒展开:$$f(x)=f(x^{(k)})+g_{k}^T(x-x^{(k)})$$
这里,$g_k=g(x^{(k)})=\triangledown{f(x^{(k)}})$为$f(x)$在$x^{(k)}$的梯度。
求出第$k+1$次迭代值$x^{(k+1)}$:$$x^{(k+1)}\leftharpoonup x^{(k)}+\lambda_kp_k$$
其中,$p_k$使搜索方向,取负梯度方向$p_k = -\triangledown{f(x^{(k)}})$,$\lambda_k$是步长,由一维搜索确定,即$\lambda_k$使得$$f(x^{(k)}+\lambda_kp_k) = min(f(x^{(k)}+\lambda p_k),\lambda \succeq 0$$
梯度下降算法如下:
输入:目标函数$f(x)$,梯度函数$g(x) = \triangledown {f(x)}$,计算精度$\epsilon$;
输出:$f(x)$的极小值点$x^*$.
(1)取初值$x^{(0)}\in R^n$,值$k=0$
(2)计算$f(x^{(k)})$
(3)计算梯度$g_k = g(x^{(k)})$,当$||g_k|| < \epsilon$时,停止迭代,令$x^* = x^{(k)}$;否则,令$p_k = -g(x^{(k)})$,求$\lambda_k$,使$$f(x^{(k)}+\lambda_kp_k) = min(f(x^{(k)}+\lambda p_k),\lambda \succeq 0$$
(4)置$x^{(k+1)}= x^{(k)}+\lambda_kp_k$,计算$f(x^{(k+1)})$,当$||f(x^{(k+1)})-f(x^{(k)})< \epsilon|| $时,停止迭代,令$x^* = x^{(k+1)}$。
(5)否则,置$k = k+1$,转(3)
当目标函数时凸函数,梯度下降法的解时全局最优解,一般情况下,其解不保证全局最优。梯度下降法的收敛速度也未必是很快的。

梯度下降方向为什么是下降最快的方向


设$f(x,y)$为二元函数,$u = cos\theta i + sin \theta j$为一个单位向量,如果下列极限存在:次方向记为$D_uf$,则称这个极限值是$f$沿着$u$方向的方向导数,那么随着$\theta$ 的不同,我们可以求出任意方向的方向导数.这也表明了方向导数的用处,是为了给我们考虑函数对任意方向的变化率.
在求方向导数的时候,除了用上面的定义法求之外,我们还可以用偏微分来简化我们的计算.表达式是:$$D_uf(x,y) = f_x(x,y)cos \theta + f_y(x,y)sin \theta$$
求解函数延那个方向变化率最大:$D_uf(x,y) = f_x(x,y)cos \theta + f_y(x,y)sin \theta$,设$A = (f_x(x,y),f_y(x,y))$,$I = (cos\theta,sin \theta)$,可以得到 $D_uf(x,y) = A \centerdot I = |A|*|I|*con \alpha$,$\alpha$为向量$A$和向量$I$之间的夹角。
那么此时如果$D_{u}f(x,y)$要取得最大值,也就是当$\alpha $为0度的时候,也就是向量$I$(这个方向是一直在变,在寻找一个函数变化最快的方向)与向量$A$(这个方向当点固定下来的时候,它就是固定的)平行的时候,方向导数最大.方向导数最大,也就是单位步长,函数值朝这个反向变化最快.


机器学习系列目录

1. 机器学习系列1:算法基础-Logistic回归
2. 机器学习系列2:算法基础-K-Means
3. 机器学习系列3:算法基础-决策树
4. 机器学习系列4:进阶算法-SVM
5. 机器学习系列5:进阶算法-随机森林
6. 数学教学系列6:ARMA模型
7. 数学教学系列7:拉格朗日对偶问题
当前阅读>  8. 数学教学系列8:梯度下降法
9. 数学教学系列9:B-S期权定价模型

发表评论

邮箱地址不会被公开。 必填项已用*标注