machine-learning-notes
  • 封面
  • 目录
  • 前言
  • 个人前言
  • 机器学习前言
    • 什么是机器学习和模式识别
    • 机器学习的应用
    • 机器学习的流程
    • 不同的机器学习算法对相同数据预测效果不同
    • 快速入门机器学习
    • 机器学习需要参考哪些书
    • 机器学习的学习路径
    • 深度学习的学习路径
    • 互联网机器学习特定岗位所需技能
  • 机器学习面试
  • 数学基础
  • 微积分
    • 泰勒展开
    • e的直观认识
    • 傅里叶变换
    • 希尔伯特空间
  • 线性代数
    • 范数
    • 矩阵求导
    • 特征值
    • 奇异值分解
  • 概率与信息论
    • 综述概率论基本定义
    • 概率论与贝叶斯先验
    • 正态分布
    • 贝叶斯概率
    • 概率符号说明
    • 共轭先验
    • 信息论
  • 数值计算与优化
    • 最小二乘法
    • 等式约束的拉格朗日乘子法
    • 凸优化
      • 凸集和凸函数
      • 凸优化问题
  • 梯度下降算法
    • 随机梯度下降SGD
    • 动量法Momentum
    • 牛顿动量Nesterov
    • AdaGrad
    • RMSprop
    • Adadelta
    • Adam
    • Nadam
    • AMSGrad
    • AdasMax
  • 概率图模型
    • 概率图模型概论
    • 概率图简介
  • 编程基础
  • linux
    • linux常用命令
    • shell
      • 输入输出重定向
  • python
    • python简介
    • python语法
      • 基础语法
      • 数据结构
      • 过程控制
      • 函数
      • 类和对象
      • 文件操作
      • 正则表达式
    • python库
      • numpy
      • pandas
      • scipy
      • matplotlib
      • scikit-learn
    • python应用
      • 排序算法
  • 数据结构与算法
    • 数据结构
    • 算法思想
      • 排序
        • 堆排序
        • 归并排序
        • 快速排序
      • 递归
    • 剑指offer
      • 链表
      • 二叉树
      • 数组
      • 字符串
      • 栈和队列
      • 递归
      • 动态规划
      • 其他
    • leetcode
    • 编程语言
      • c++
  • Hadoop
    • Hadoop简介
    • MapReduce
  • Hive
  • Spark
  • TensorFlow
    • TensorFlow1.0
      • TensorFlow基础
      • TensorFlow基础概念解析
      • TensorFlow机器学习基础
      • Tensorflow分布式架构
    • TensorFlow2.0
  • PyTorch
  • 机器学习
  • 机器学习概论
  • 特征工程
  • 感知机
  • k近邻
  • 朴素贝叶斯
  • 线性模型
    • 最大熵模型
    • 指数族分布与广义线性模型
    • 线性回归
      • Ridge回归(岭回归)
      • Lasso回归
    • Logistic回归-对数几率回归
  • 决策树
  • 支持向量机
    • 线性可分支持向量机与硬间隔最大化
    • 线性支持向量机与软间隔最大化
    • 非线性支持向量机与核函数
    • 序列最小最优化算法SMO
    • SVM总结
  • 集成学习
    • Bagging
      • 随机森林
    • Boosting
      • AdaBoost
      • GradientBoosting
        • GBDT
        • XGBoost
          • XGBoost理论
          • XGBoost实践
    • Stacking
  • 降维
    • PCA主成分分析
    • 流形学习
  • EM算法
  • HMM隐马尔科夫模型
  • CRF条件随机场
  • 聚类
    • k均值聚类
    • 高斯混合模型
  • 主题模型
    • LDA隐狄利克雷分布
  • 知识点
    • 损失函数
    • 负采样
  • 机器学习算法总结
  • 深度学习
  • 深度学习概论
  • ANN人工神经网络
  • 知识点
    • Batch Normalization
  • CNN卷积神经网络
  • 深度学习优化算法
  • RNN循环神经网络
  • LSTM长短期记忆网络
  • GRU门控循环单元
  • GNN图神经网络
    • GNN图神经网络综述
    • GCN图卷积网络
      • GCN图卷积网络初步理解
      • GCN图卷积网络的numpy简单实现
      • GCN图卷积网络本质理解
      • GCN图卷积网络全面理解
      • SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS ICLR2017
  • 神经网络架构搜索
    • Weight-Agnostic-Neural-Networks Google2019
  • 强化学习
  • 强化学习概论
  • 马尔科夫决策过程
  • 动态规划
  • 无模型方法一:蒙特卡洛
  • 无模型方法二:时间差分
  • 无模型方法三:多步自举
  • 函数近似和深度网络
  • 策略梯度算法
  • 深度强化学习
  • 基于模型的强化学习
  • 强化学习前景
  • 自然语言处理
  • 自然语言处理概论
  • 自然语言
  • 语言模型和中文分词
  • word2vec
    • word2vec概述
    • word2vec算法原理
    • word2vec源码分析
    • word2vec实践
  • Seq2Seq模型和Attention机制
  • Self-Attention和Transformer
  • 知识图谱
  • 推荐系统
  • 推荐系统概论
  • 基础知识
  • 进阶知识
    • 机器学习
      • Factorization Machines ICDM2010
    • embedding
      • Network Embedding
        • LINE: Large-scale Information Network Embedding
    • 深度学习
      • DeepFM: A Factorization-Machine based Neural Network for CTR Prediction 2017
      • DSSM: Learning Deep Structured Semantic Models for Web Search using Clickthrough Data CIKM2013
    • 图卷积网络
      • Graph Convolutional Neural Networks for Web-Scale Recommender Systems KDD2018
    • 强化学习
      • DRN基于深度强化学习的新闻推荐模型
  • 业界应用
    • YouTube
      • Deep Neural Networks for YouTube Recommendations RecSys2016
    • Alibaba
      • Learning Tree-based Deep Model for Recommender Systems KDD2018
      • Deep Interest Network for Click-Through Rate Prediction KDD2018
      • DSIN:Deep Session Interest Network for Click-Through Rate Prediction IJCAI2019
Powered by GitBook
On this page
  • 随机梯度下降
  • 各类梯度下降算法的演化
  • 三类梯度下降算法概述
  • 批量梯度下降BGD
  • 随机梯度下降SGD
  • 随机梯度下降的原理
  • 随机梯度下降的性质
  • 小批量梯度下降MBGD
  • BatchSize的理解
  • 最速梯度下降法和梯度下降法的区别
  • 参考资料

Was this helpful?

  1. 梯度下降算法

随机梯度下降SGD

Previous梯度下降算法Next动量法Momentum

Last updated 5 years ago

Was this helpful?

随机梯度下降

最优化问题在机器学习中有非常重要的地位,很多机器学习算法最后都归结为求解最优化问题。在各种最优化算法中,梯度下降法是最简单、最常见的一种。

各类梯度下降算法的演化

三类梯度下降算法概述

GD(Gradient Descent):就是没有利用Batch Size,用基于整个数据库得到梯度,梯度准确,但数据量大时,计算非常耗时,同时神经网络常是非凸的,网络最终可能收敛到初始点附近的局部最优点。

SGD(Stochastic Gradient Descent):就是Batch Size=1,每次计算一个样本,梯度不准确,所以学习率要降低。

mini-batch SGD:就是选着合适Batch Size的SGD算法,mini-batch利用噪声梯度,一定程度上缓解了GD算法直接掉进初始点附近的局部最优值。同时梯度准确了,学习率要加大。

总结:

  • Batch gradient descent: Use all examples in each iteration;

  • Stochastic gradient descent: Use 1 example in each iteration;

  • Mini-batch gradient descent: Use b examples in each iteration.

批量梯度下降BGD

批量梯度下降法(Batch Gradient Descent,简称BGD)是梯度下降法最原始的形式,它的具体思路是在更新每一参数时都使用所有的样本来进行更新,其数学形式如下:

批量梯度下降BGD的优缺点:

优点:全局最优解;易于并行实现;

缺点:当样本数目很多时,训练过程会很慢。

从迭代的次数上来看,BGD迭代的次数相对较少。其迭代的收敛曲线示意图可以表示如下:

随机梯度下降SGD

几乎所有的深度学习算法都用到了随机梯度下降,它是梯度下降算法的拓展。

机器学习中反复出现的一个问题是:好的泛化需要大的训练集,但是,训练集越大,计算代价也越大。

随机梯度下降的原理

由于批量梯度下降法在更新每一个参数时,都需要所有的训练样本,所以训练过程会随着样本数量的加大而变得异常的缓慢。随机梯度下降法(Stochastic Gradient Descent,简称SGD)正是为了解决批量梯度下降法这一弊端而提出的。其数学形式如下:

随机梯度下降是通过每个样本来迭代更新一次,如果样本量很大的情况(例如几十万),那么可能只用其中几万条或者几千条的样本,就已经将theta迭代到最优解了,对比上面的批量梯度下降,迭代一次需要用到十几万训练样本,一次迭代不可能最优,如果迭代10次的话就需要遍历训练样本10次。但是,SGD伴随的一个问题是噪音较BGD要多,使得SGD并不是每次迭代都向着整体最优化方向。

优点:训练速度快;

缺点:准确度下降,并不是全局最优;不易于并行实现。

从迭代的次数上来看,SGD迭代的次数较多,在解空间的搜索过程看起来很盲目。其迭代的收敛曲线示意图可以表示如下:

随机梯度下降的性质

梯度下降往往被认为很慢或不可靠。

在以前,将梯度下降应用到非凸优化问题被认为很鲁莽或者没有原则。而现在,在深度学习中,使用梯度下降的训练效果很不错。虽然优化算法不一定能保证在合理的时间内达到一个局部最小值,但它通常能及时地找到代价函数一个很小的值,并且是有用的。

在深度学习之外,随机梯度下降有很多重要的应用。它是在大规模数据上训练大型线性模型的主要方法。对于固定大小的模型,每一步随机梯度下降更新的计算量不取决于训练集的大小m。在实践中,当训练集大小增长时,我们通常会使用一个更大的模型,但是这并非是必须的。达到收敛模型所需的更新次数通常会随着训练集规模增大而增加。然而,当m趋于无穷大时,该模型最终会随机梯度下降抽样完训练集上所有样本之前收敛到可能的最优测试误差。继续增加m不会延长达到模型可能的最优测试误差的时间。从这点来看,我们可以认为用SGD训练模型的渐进代价是关于m的函数的O(1)级别。

小批量梯度下降MBGD

由上述的两种梯度下降法可以看出,其各自均有优缺点,那么能不能在两种方法的性能之间取得一个折衷呢?即,算法的训练过程比较快,而且也要保证最终参数训练的准确率,而这正是小批量梯度下降法(Mini-batch Gradient Descent,简称MBGD)的初衷。

mini-batch SGD其实就是选着合适Batch Size的SGD算法,mini-batch利用噪声梯度,一定程度上缓解了GD算法直接掉进初始点附近的局部最优值。同时梯度准确了,学习率要加大。

小批量梯度下降的核心是,梯度是期望。期望可使用小规模的样本近似估计。

具体步骤:我们在每一步都从训练集中均匀抽出一小批量(minibatch)样本

梯度的估计可以表示成

BatchSize的理解

直观的理解:

Batch Size定义:一次训练所选取的样本数。

Batch Size的大小影响模型的优化程度和速度。同时其直接影响到GPU内存的使用情况,假如你GPU内存不大,该数值最好设置小一点。

为什么要提出Batch Size?

在没有使用Batch Size之前,这意味着网络在训练时,是一次把所有的数据(整个数据库)输入网络中,然后计算它们的梯度进行反向传播,由于在计算梯度时使用了整个数据库,所以计算得到的梯度方向更为准确。但在这情况下,计算得到不同梯度值差别巨大,难以使用一个全局的学习率,所以这时一般使用Rprop这种基于梯度符号的训练算法,单独进行梯度更新。

在小样本数的数据库中,不使用Batch Size是可行的,而且效果也很好。但是一旦是大型的数据库,一次性把所有数据输进网络,肯定会引起内存的爆炸。所以就提出Batch Size的概念。

Batch Size设置合适时的优点:

1、通过并行化提高内存的利用率。就是尽量让你的GPU满载运行,提高训练速度。

2、单个epoch的迭代次数减少了,参数的调整也慢了,假如要达到相同的识别精度,需要更多的epoch。

3、适当Batch Size使得梯度下降方向更加准确。

Batch Size从小到大的变化对网络影响

1、没有Batch Size,梯度准确,只适用于小样本数据库

2、Batch Size=1,梯度变来变去,非常不准确,网络很难收敛。

3、Batch Size增大,梯度变准确,

4、Batch Size增大,梯度已经非常准确,再增加Batch Size也没有用

注意:Batch Size增大了,要到达相同的准确度,必须要增大epoch。

为什么说Batch size的增大能使网络的梯度更准确?

梯度的方差表示:

上式第三步是因为:由于样本是随机选取的,满足独立同分布,所以所有样本具有相同的方差。

可以看出当Batch size为m时,样本的方差减少m倍,梯度就更准确了。

假如想要保持原来数据的梯度方差,可以增大学习率lr(learning-rate)。

这也说明batch size设置较大时,一般学习率要增大。但是lr的增大不是一开始就设置的很大,而是在训练过程中慢慢变大。

一个具体例子分析:

在分布式训练中,Batch size随着数据并行的workers增加而增大,假如baseline的Batch Size为B,而学习率为lr,训练epoch为N。假如保持baseline的lr,一般达不到很好的收敛速度和精度。

原因:对于收敛速度,假如有K个workers,则每个批次为KB,因此一个epoch迭代的次数为baseline的1k,而学习率lr不变,所以要达到与baseline相同的收敛情况,epoch要增大。而根据上面公式,epoch最大需要增大KN个epoch,但一般情况下不需要增大那么多。

对于收敛精度,由于Batch size的使用使梯度更准确,噪声减少,所以更容易收敛。

最速梯度下降法和梯度下降法的区别

准确来说,它们并不是完全等价。

参考资料

  • 《深度学习》Goodfellow

“随机梯度下降SGD”参考了此书的第五章5.9小节“随机梯度下降”。

“BatchSize的理解”参考了此博客。

本文参考了此微信公众号。

“最速梯度下降法和梯度下降法的区别”参考了此博客。

===

g=1m▽θ∑i=1mL(x(i),y(i),θ)g=\frac{1}{m}\bigtriangledown_{\theta}\sum^{m}_{i=1}L(x^{(i)},y^{(i)},\theta)g=m1​▽θ​i=1∑m​L(x(i),y(i),θ)

其中,mmm为样本总数。

这个运算的计算复杂度是O(m)。随着训练集规模增长为数十亿的样本,计算一步梯度也会消耗相当长的时间。虽然它得到的是一个全局最优解,但是每迭代一步,都要用到训练集所有的数据,如果样本数目mmm很大,那么可想而知这种方法的迭代速度!所以,这就引入了另外两种方法,随机梯度下降和批量梯度下降。

g=▽θL(x(i),y(i),θ)g=\bigtriangledown_{\theta}L(x^{(i)},y^{(i)},\theta)g=▽θ​L(x(i),y(i),θ)
B={x(1),...,x(m′)}\mathbb{B}=\{x^{(1)},...,x^{(m^{'})}\}B={x(1),...,x(m′)}

,小批量的数目m′m'm′通常是一个相对较小的数,从一到几百(一般为10)。重要的是,当训练集大小m增长时,m′m'm′通常是固定的。我们可能在拟合几十亿样本时,每次更新计算只用到几百个样本。

g=1m′▽θ∑i=1m′L(x(i),y(i),θ)g=\frac{1}{m^{'}}\bigtriangledown_{\theta}\sum^{m^{'}}_{i=1}L(x^{(i)},y^{(i)},\theta)g=m′1​▽θ​i=1∑m′​L(x(i),y(i),θ)

使用来自小批量B\mathbb{B}B的样本。然后,随机梯度下降算法使用如下的梯度下降算法估计:

θ=θ−ϵg\theta=\theta-\epsilon gθ=θ−ϵg

其中,ϵ\epsilonϵ是学习率。

Var(g)=Var(1m∑i=1mg(xi,yi))=1m2Var(g(x1,y1)+g(x2,y2)+...+g(xm,ym))=1m2[Var(g(x1,y1))+Var(g(x1,y1))+...+Cov]=1m2(mVar(g(xi,yi)))=1mVar(g(xi,yi))\begin{aligned} Var(g)&=Var\left(\frac{1}{m}\sum_{i=1}^mg(x_i,y_i)\right)\\ &=\frac{1}{m^2}Var\left(g(x_1,y_1)+g(x_2,y_2)+...+g(x_m,y_m)\right)\\ &=\frac{1}{m^2}\left[Var\left(g(x_1,y_1)\right)+Var\left(g(x_1,y_1)\right)+...+Cov\right]\\ &=\frac{1}{m^2}\left(mVar\left(g(x_i,y_i)\right)\right)\\ &=\frac{1}{m}Var\left(g(x_i,y_i)\right) \end{aligned}Var(g)​=Var(m1​i=1∑m​g(xi​,yi​))=m21​Var(g(x1​,y1​)+g(x2​,y2​)+...+g(xm​,ym​))=m21​[Var(g(x1​,y1​))+Var(g(x1​,y1​))+...+Cov]=m21​(mVar(g(xi​,yi​)))=m1​Var(g(xi​,yi​))​
1mVar(lr⋅g(xi,yi))\frac{1}{m}Var\left(lr\cdot g(x_i,y_i)\right)m1​Var(lr⋅g(xi​,yi​))

只要lr取m\sqrt{m}m​,上式就变成Var(g(xi,yi))Var(g(x_i, y_i))Var(g(xi​,yi​))。

对于梯度下降法,我们需要预先设定步长α\alphaα。

xi+1=xi−α▽fxix_{i+1}=x_i-\alpha \bigtriangledown f_{x_i}xi+1​=xi​−α▽fxi​​

而最速下降法的这个步长αk\alpha_kαk​是通过一个优化函数结算得到的。

αk=argminαkf(xi−αk)▽fxi\alpha_k=\text{argmin}_{\alpha_k}f(x_i-\alpha_k)\bigtriangledown f_{x_i}αk​=argminαk​​f(xi​−αk​)▽fxi​​

神经网络中Batch Size的理解
梯度下降法的三种形式BGD、SGD以及MBGD
【最优化】一文搞懂最速下降法
梯度下降法和最速下降法的细微差别
SGD过程中的噪声如何帮助避免局部极小值和鞍点
返回上层目录
各类梯度下降算法的演化
三类梯度下降算法概述
批量梯度下降BGD
随机梯度下降SGD
随机梯度下降的原理
随机梯度下降的性质
小批量梯度下降MBGD
BatchSize的理解
最速梯度下降法和梯度下降法的区别
返回顶层目录
revolution-of-gradient-descent
GD
SGD