分类选择: 产品分类一 产品分类二 产品分类三 产品分类四 产品分类五
最优化方法(一)
作者:佚名    所属栏目:【产品分类二】    时间:2024-04-22

本系列文章是阅读雷明老师《机器学习的数学》一书后整理的读书笔记。

首先介绍最优化方法中的相关知识点,下面两幅图是对最优化方法的分类和知识体系的一个总结。

一般将最优化问题统一表述为极小值问题,对于极大值问题,只需要将目标函数反号。其形式定义如下:

\\min_x f(x)\\ x \\in X \\\\

其中x为优化变量,f为目标函数,X \\subseteq \\mathbb{R^n}为优化变量允许的取值集合,称为可行域,它由目标函数的定义域、等式及不等式约束共同确定。可行域之内的解释为可行解。

假设 x^* 是一个可行解,如果对可行域内所有点 x 都有 f(x^*) \\leq f(x),则称 x^* 为全局极小值。

对于可行解 x^*,如果存在其 \\delta 邻域,使得该邻域内所有满足 ||x-x^*|| \\leq \\delta 的点 x 都有 f(x^*) \\leq f(x),则称 x^* 为局部最小值。

最优化算法的目标是寻找目标函数的全局极值点而非局部极值点。

一阶优化算法是利用目标函数的一阶导数构造 x_{k+1}=h(x_k) 的迭代公式。

梯度下降法(Gradient Descent Method)由数学家柯西提出,它沿着当前点 x_k 处梯度相反的方向进行迭代,得到 x_{k+1},直到收敛到梯度为0的点。其理论依据:在梯度不为0的任意点处,梯度正方向是函数值上升的方向,梯度反方向是函数值下降的方向。

将函数在 x 点处做一阶泰勒展开:

f(x+\\Delta x)=f(x)+(\
abla f(x))^T \\Delta x +o(\\|\\Delta x\\|)  \\\\

对上式变形:

f(x+\\Delta x)-f(x)=(\
abla f(x))^T \\Delta x +o(\\|\\Delta x\\|)  \\\\

如果令 \\Delta x=\
abla f(x),则有:

f(x+\\Delta x)-f(x)=(\
abla f(x))^T \
abla f(x) +o(\\|\\Delta x\\|)  \\\\

如果 \\Delta x 足够小,则可以忽略高阶无穷小项,有:

f(x+\\Delta x)-f(x)\\approx (\
abla f(x))^T \
abla f(x)\\geq 0  \\\\

如果在 x 点处梯度不为0,则能保证移动到 x+\\Delta x 时函数值增大。相反地,如果令\\Delta x=-\
abla f(x),则有:

f(x+\\Delta x)-f(x)\\approx -(\
abla f(x))^T \
abla f(x)\\leq 0  \\\\

则函数值减小。事实上,只要确保

(\
abla f(x))^T \\Delta x \\leq 0 \\\\

则有

f(x+\\Delta x) \\leq f(x)  \\\\

因此,选择合适的增量 \\Delta x 就能保证函数值下降,负梯度方向只是一个特例。那么,当增量的模一定时,为什么负梯度方向函数值下降最快呢?

由于

(\
abla f(x))^T \\Delta x=\\| \
abla f(x)\\|\\cdot  \\|\\Delta x\\|\\cdot \\cos \	heta \\\\

其中 \	heta\
abla f(x)\\Delta x 之间的夹角。因此如果 \	heta < \\frac{\\pi}{2},则 \\cos \	heta >0,函数值增大;如果 \	heta > \\frac{\\pi}{2},则 \\cos \	heta <0,函数值下降。\\Delta x 沿着负梯度方向即 \	heta=\\pi 是特例,如果向量 \\Delta x 的模大小一定,则 \\Delta x=-\
abla f(x), 则在梯度相反的方向函数值下降最快,此时 \\cos \	heta=-1

梯度下降法每次迭代的增量为

\\Delta x=-\\alpha \
abla f(x)  \\\\

其中 \\alpha 称为步长或学习率,其作用是保证 x+\\Delta xx 的邻域内,从而可以忽略泰勒公式中的 o(\\|\\Delta x\\|) 项,否则不能保证每次迭代时函数值下降。

由此得到梯度下降法的迭代公式,从起始点 x_0 开始,反复使用如下迭代公式

x_{k+1}=x_k - \\alpha \
abla f(x_k) \\\\

梯度下降法在每次迭代时只需要计算函数当前点处的梯度值,具有计算量小、实现简单的优点。只要未达到驻点处且学习率设置恰当,每次迭代时均能保证函数值下降。

最速下降法是对梯度下降法的改进,它用算法自动确定步长值。最速下降法同样沿着梯度相反的方向进行迭代,每次需要计算最佳步长 \\alpha

最速下降法的搜索方向与梯度下降法相同,也就是负梯度方向

d_k=-\
abla f(x_k) \\\\

在该方向上寻找使得函数值最小的步长,通过求解如下一元函数优化问题实现

\\alpha_k=arg\\min_\\alpha f(x_k + \\alpha d_k) \\\\

通过直接求该函数的驻点实现,这种方法也称为直线搜索,沿着某一确定的方向在直线上寻找最优步长。

在机器学习中,目标函数通常定义在一个训练样本集上。假设训练样本集有N个样本,机器学习模型在训练时优化的目标是这个数据集上的平均损失函数

L(w)=\\frac{1}{N}\\sum_{i=1}^N L(w,x_i, y_i) \\\\

其中L(w,x_i, y_i)是对单个训练样本(x_i,y_i)的损失函数,w是机器学习模型需要学习的参数,是优化变量。

但是如果训练样本每次都用所有的样本,那么计算成本太高了。

在每次迭代时只使用M \\ll N个样本来近似计算损失函数。

随机梯度下降法在数学期望的意义下收敛,随机采样产生梯度的期望值是真实的梯度。一种特殊情况是M=1,每次迭代只使用一个训练样本。

除了具有实现效率高的优点之外,随机梯度下降法还会影响收敛的效果。对于深度神经网络,随机梯度下降法比批量梯度下降法更容易收敛到一个好的极值点。

网站首页 关于我们 耀世动态 耀世注册 耀世登录 联系我们

电话:400-123-4567      手机:13800000000
E-mail:admin@youweb.com      联系人:张生
地址:广东省广州市天河区88号

Copyright © 2012-2018 耀世娱乐-耀世注册登录官方入口 版权所有      琼ICP备xxxxxxxx号

扫一扫  关注微信

平台注册入口