梯度下降理论

1. 基础

无约束优化

无约束优化

image-20220801113837555

当x属于欧几里得空间,属于无约束优化;

当x不属于欧几里得空间,有约束优化;

局部最小与驻点

所有优化办法,都是没有办法取得全局最小值的,所以优化的目标就是找局部最小值。

局部最小:f(x)在其邻域内最小;

驻点:(stationary point),一阶导数为0的点;

驻点未必是局部最小,这时也叫做鞍点。

image-20220801114657227

梯度下降

现实中实际的问题,往往并不存在解析解,这就需要数值优化,常用的方法是迭代的方法(如:EM)

image-20220801115243431

每次找一个方向走一点,再找一个方向再走一点。

这就需要:步长(step size)与方向(search direction)

一阶条件

一阶条件:▽f(x*) = 0是局部最小值的必要条件,即:局部最小值 => ▽f(x*) = 0

证明其逆否命题: ▽f(x*) ≠ 0 => 非局部最小值。

p = -▽f(x)* ,也就是负梯度方向,于是:

image-20220801122540800

存在f(x + αp) < f(x),也就推出了非局部最小。

二阶条件

二阶条件:▽2f(x*) >= 0是局部最小的必要条件,即:局部最小值 => ▽2f(x*) >= 0

=> ▽2f(x*)就是海塞矩阵,大于等于0也意味着海塞矩阵半正定。

证明也是证明其逆否命题:非半正定 => 非局部最小值。

采用的方法也是泰勒展开,展开到二阶。

![image-20220801123934939](2022-08-01梯度下降理论/image-20220801123934939.png

image-20220801123952682

凸性

Convexity:下凸,上凹。f(αx + (1-α)y) >= αf(x) + (1-α)f(y)

image-20220801124318521

凸函数有最小值,求优化(最小值)都会假设凸函数。

非凸会存在鞍点

2. 固定步长的梯度下降(GD: gradient descent)

算法

梯度下降是一种迭代的算法,可以写成:

η是步长,或者叫学习效率,-▽f (w^(t))是负梯度方向;

整个过程如下图所示:

梯度方向是法线方向,每次朝着负梯度方向走一点。

只要p与▽f (w)夹角为锐角,即可下降: pT▽f (w) < 0,但梯度下降是速度最快的方式。

算法:

  1. 从起点开始
  2. 计算梯度
  3. 行走一个距离η
  4. 是否满足停止条件,不满足第二步,满足结束

停止条件:

image-20220802094702014

  1. 前后两部误差很小
  2. 梯度值很小

eps: 机器误差,精度再高就无法做乘法了

证明

思路:利用凸性来证明f(w)与最小值f(w*)的差距很小。这里用的是image-20220802103029661

image-20220802095618462

这个意思就是可以通过迭代步数T的增大,结果逼近最小值

一阶近似:

image-20220802095920413

交叉项配方法:

基本思路,将乘积变成高级的相减,然后利用迭代来求解

image-20220802101805996

image-20220802104118747

这里假设 w(1) = 0,可得:

image-20220802105301812

这里假设,||vt|| <= ρ、||w*|| <= B,η = image-20220802111356390,得到:

image-20220802111426445

主要是η中带有了T

3. 随机梯度下降(SGD: stochastic gradient descent)

次梯度

如果一个向量v满足:

image-20220803114949498

就被称为v是f的次梯度。在一阶近似的情况下,满足类似导数的性质。

示例:

image-20220803120036997

应用到梯度下降中

当前这步的方向,在前一步w(t)基础之上的条件期望是f(w(t))的次梯度。

image-20220803120355644

改变包括:

  1. 梯度到次梯度
  2. 确定到随机(期望)

损失函数

参考

定义损失函数为平方损失函数:

image-20220803145118727

按照梯度下降的方法来使损失函数最小:

固定步长梯度下降

对θ的更新,所有样本都有贡献(因此也称批量梯度下降),计算得到的是一个标准梯度。

对于样本不多的情况下,收敛速度可以,样本太多时,计算速度就很很慢。

随机梯度下降

对于θ的更新,每次随机选取一个例子来计算,得到是并不是标准的梯度,而是次梯度。

这种方法样本很大时,计算的速度更快。

这里为什么要2层循环?

内循环只针对一个点算信息,外循环迭代几次。

对比

image-20220803124111686

在期望意义下GD与SGD相同。

4. 可变步长梯度下降

每一步先找一个合适的步长;再找一个方向;再往下走;

线搜索

设原始的函数为f(x),要找一个合适的α(前边的η)做为下一步的步长,设 h(α) = f(x + αp),c1为常数( 0<c1<1)。

α可以选所有能满足不等式 h(α) <= h(0) + h'(0)×c1×α 条件的值。

用图表示如下:

image-20220804103235528

上图中红线以下的h(α)满足不等式条件

通过c1可以控制步长

保证下降的速度比线性函数要快

附录1:损失函数

距离损失函数

平方损失函数,会使模型对异常值更灵敏,造成向异常值倾斜。

KL散度:log差的期望

交叉熵函数:KL散度中去掉固定值

附录2: 梯度下降的实现

这里包括GD、MGD、Ada、Adam等4种梯度下降算法的介绍

MGD:梯度不直接控制补偿,而是控制速度。梯度更像是加速度。

Ada、Adam都是可变步长随机梯度下降

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×