优化算法-梯度下降

优化与机器学习

机器学习的主要任务之一就是通过训练,学习获得一组最优的参数,我们经常以成本函数来作为参数估计的函数。所以机器学习的任务也就是最小成本函数。

优化也是机器学习算法的非常重要的组成部分,基本上每一个机器学习算法都有一个优化算法

梯度下降方法

用负梯度作搜索方向,即令$\bigtriangleup x=-\bigtriangledown f(x)$, 是一种自然的选择。相应的方法就称梯度方法或者梯度下降方法。

梯度下降算法的概念

梯度下降算法就是一个被广泛使用的优化算法, 它可以用于寻找最小化成本函数的参数值. 也就是说: 当函数 $$J(\theta)$$ 取得最小值时, 求所对应的自变量$\theta$的过程, 此处$\theta$就是机器要学习的参数,$$J(\theta)$$ 就是用于参数估计的成本函数, 是关于$$\theta$$ 的函数.

梯度下降的基本步骤

梯度下降法的计算过程就是沿梯度下降的方向求解极小值(也可以沿梯度上升方向求解极大值)


给定 初始点 $x \in dom f $
重复进行:
  1. $\bigtriangleup x :=-\bigtriangledown f(x)$
  2. 直线搜索。通过精确或回溯直线搜索方法确实步长$t$.
  3. 修改 :$x :=x+t\bigtriangleup x$.

    直到:满足停止准则。


换种方式:

  1. 对成本函数进行微分, 得到其在给定点的梯度. 梯度的正负指示了成本函数值的上升或下降:$ Δ(\theta)=\frac{∂J(\theta)}{∂\theta}$
  2. 选择使成本函数值减小的方向, 即梯度负方向, 乘以学习率为 α 计算得参数的更新量, 并更新参数:$\theta=\theta−αΔ(\theta) $
  3. 重复以上步骤, 直到取得最小的成本

批量梯度下降法(Batch Gradient Descent)

批量梯度下降法,是梯度下降法最常用的形式,具体做法也就是在更新参数时使用所有的样本来进行更新,这个方法对应于线性回归的梯度下降算法,也就是说线性回归的梯度下降算法就是批量梯度下降法。

具体实现过程:


  1. 假设函数:$h_\theta = \sum_{i=1}^n\theta_ix_i$
  2. 成本函数:$J(\theta)=\frac{1}{2m} \sum_{i=1}^n(h_\theta(x_i)-y_i)^2$
  3. 对成本函数进行求偏导:对每一个参数$\theta_j$进行分别求偏导,得出各自的梯度。

    $\frac{\partial J(\theta)}{\partial \theta}=-\frac1 m \sum_{i=1}^n(y_i-h_\theta(x_i))x_j^i$

  4. 每个参数都按照梯度的负方向进行更新:

    $\theta_j=\theta_j+\frac a m \sum_{i=1}^n(y_i-h_\theta(x_i))x_j^i$


BGD伪代码:


repeat{

$\theta_j=\theta_j+\frac a m \sum_{i=1}^n(y_i-h_\theta(x_i))x_j^i$

(for every j = 0, 1, .. n)

}


总结:

优点:BGD 得到的是全局最优解, 因为它总是以整个训练集来计算梯度,

缺点:因此带来了巨大的计算量, 计算迭代速度很很慢.

随机梯度下降法(Stochastic Gradient Descent)

随机梯度下降法,其实和批量梯度下降法原理类似,区别在与求梯度时没有用所有的m个样本的数据,而是仅仅选取一个样本j来求梯度。

具体实现过程:

SGD 每次以一个样本, 而不是整个数据集来计算梯度. 因此, SGD 从成本函数开始, 就不必再求和了, 针对单个样例的成本函数可以写成:

$J(\theta)=\frac{1}{2} (h_\theta(x_i)-y_i)^2$

于是, SGD 的参数更新规则就可以写成 :

$\theta_j=\theta_j+a (y_i-h_\theta(x_i))x_j^i$

SGD伪代码:


repeat {

for i = 1, .., m{

      $\theta_j=\theta_j+a (y_i-h_\theta(x_i))x_j^i$

        (for every j = 0, 1, .. n)

}

}


总结:

SGD 的关键点在于以随机顺序选取样本. 因为 SGD 存在局部最优困境, 若每次都以相同的顺序选取样本, 其有很大的可能会在相同的地方陷入局部最优解困境, 或者收敛减缓. 因此, 欲使 SGD 发挥更好的效果, 应充分利用随机化 带来的优势: 可以在每次迭代之前 (伪代码中最外围循环), 对训练集进行随机排列.

缺点:因为每次只取一个样本来进行梯度下降, SGD 的训练速度很快, 但会引入噪声, 使准确度下降

优点:. 可以使用在线学习. 也就是说, 在模型训练好之后, 只要有新的数据到来, 模型都可以利用新的数据进行再学习, 更新参数,以适应新的变化.

对比

随机梯度下降法和批量梯度下降法是两个极端,一个采用所有数据来梯度下降,一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说,随机梯度下降法由于每次仅仅采用一个样本来迭代,训练速度很快,而批量梯度下降法在样本量很大的时候,训练速度不能让人满意。对于准确度来说,随机梯度下降法用于仅仅用一个样本决定梯度方向,导致解很有可能不是最优。对于收敛速度来说,由于随机梯度下降法一次迭代一个样本,导致迭代方向变化很大,不能很快的收敛到局部最优解。

MBGD就综合了这两种方法的优点。

小批量梯度下降法(Mini-batch Gradient Descent)

MBGD 是为解决 BGD 与 SGD 各自缺点而发明的折中算法, 或者说它利用了 BGD 和 SGD 各自优点. 其基本思想是: 每次更新参数时, 使用 n 个样本, 既不是全部, 也不是 1. (SGD 可以看成是 n=1 的 MBGD 的一个特例)

MBGD 的成本函数或其求导公式或参数更新规则公式基本同 BGD 。

MBGD 的伪代码:


say b=10, m=1000,

repeat {

for i = 1, 11, 21, .., 991 {

$\theta_j=\theta_j+\frac a {10} \sum_{i=1}^{i+9}(y_i-h_\theta(x_i))x_j^i$

 (for every j = 0, 1, .. n)

 }

}


梯度下降算法总结

梯度下降算法优点缺点
BGD全局最优解计算量大, 迭代速度慢, 训练速度慢
SGD1.训练速度快 ,对于很大的数据集,也能以较快的速度收敛 2. 支持在线学习准确度下降, 有噪声, 非全局最优解
MBGD1. 训练速度较快, 取决于小批量的数目 2. 支持在线学习准确度不如 BGD, 速度比SGD慢,仍然有噪声, 非全局最优解

转载请注明:Seven的博客 » 点击阅读原文

本文标题:优化算法-梯度下降

文章作者:Seven

发布时间:2018年07月24日 - 00:00:00

最后更新:2018年12月11日 - 21:58:39

原始链接:http://yoursite.com/2018/07/24/2018-07-24-arithmetic-gradientDescent/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%