线性代数|机器学习-P26随机梯度下降

1. 概述

• 所有的机器学习问题都需要进行优化，最终损失函数如下：
  $$\begin{array}{c}\underset{x}{\min }f(x)\end{array}$$
  常见的优化算法如下：梯度下降；牛顿法；次梯度法等等

2. 损失函数

2.1 介绍

• n个有限样本的损失函数,简单来说是将n个损失函数求平均，计算能够使得我们得到最小的平均损失函数值处的x值
  min ⁡ x 1 n ∑ i = 1 n f i ( x )

  $$\begin{equation} \min\limits_{x}\frac{1}{n}\sum_{i=1}^nf_i(x) \end{equation}$$ xmin​n1​i=1∑n​fi​(x)​​

• 大规模的机器学习
  – 定义训练标签数据Data如下：d:表示每一个训练样本的维度，n表示参与训练的样本数
  d a t a : { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x n , y n ) } ∈ R d × γ

  $$\begin{equation} data:\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}\in \mathbb{R}^d\times \gamma \end{equation}$$ data:{(x1​,y1​),(x2​,y2​),⋯,(xn​,yn​)}∈Rd×γ​​
  

• 现在在训练过程中n可能非常大，有可能有百万个训练样本。每个样本的维度d表示一个样本的特征，简单来说，把每个样本比作一个人，那么维度d表示的是这个人所有的特征数，比如这个人有5个特征，身高，肥胖，财富，社会地位，年龄；而样本n表示有n个这样的人，每个人对应特征类型一样，但是具体内容不一样。

2.2 常见损失函数

• 最小二乘法Least-Squares
  $$\begin{array}{c}\frac{1}{n}||Ax-b|{|}_2^2=\frac{1}{n}\sum _{i=1}^n(a_i^{T}x-b_i{)}^2=\frac{1}{n}\sum _{i=1}^n{f}_i(x)\end{array}$$
• 二范数定义
  $$\begin{array}{c}||x|{|}_2^2=x_1^2+x_2^2+\cdots +x_n^2\end{array}$$
• Lasso回归
  $$\begin{array}{c}\frac{1}{n}||Ax-b|{|}_2^2+\lambda ||x|{|}_1=\frac{1}{n}\sum _{i=1}^n(a_i^{T}x-b_i{)}^2+\lambda \sum _{j=1}^d|x_j|\end{array}$$
• SVM支持向量机
  1 2 ∣ ∣ x ∣ ∣ 2 2 + c n max ⁡ { 0 , 1 − y i ( x T a i + b ) } $$\begin{equation} \frac{1}{2}||x||_2^2+\frac{c}{n}\max\{0,1-y_i(x^Ta_i+b)\} \end{equation}$$ 21​∣∣x∣∣22​+nc​max{0,1−yi​(xTai​+b)}​​
• Deep Neural Networks
  深度神经网络损失函数为loss,神经网络为DNN,$y_i$表示真实标签，$\mathrm{DNN}(x;a_i)$表示输入x经过神经网络计算后的$y_m$，损失函数为真实标签$y_i$与$y_m$之间的差值
  1 n ∑ i = 1 n l o s s { y i , D N N ( x ; a i ) } = 1 n ∑ i = 1 n f i ( x ) $$\begin{equation} \frac{1}{n}\sum_{i=1}^n\mathrm{loss}\{y_i,\mathrm{DNN}(x;a_i)\}=\frac{1}{n}\sum_{i=1}^nf_i(x) \end{equation}$$ n1​i=1∑n​loss{yi​,DNN(x;ai​)}=n1​i=1∑n​fi​(x)​​
• MLE-极大似然估计
  从概率的角度去评估损失最小的意思就是给定一个参数得到计算值和目标值最大概率的参数值，就是极大似然估计，其实本质上一样，最小损失函数是从线性代数的角度思考模型，极大似然估计是从概率最大的角度思考模型，感觉像双人零和博弈一样，甲方最小的损失的策略就是要最大的概率击败乙方的模型。
  $$\begin{array}{c}\frac{1}{n}\sum _{i=1}^n\log -\mathrm{likehood}(x;a_i)=\frac{1}{n}\sum _{i=1}^n{f}_i(x)\end{array}$$

3. 迭代优化方法

3.1 梯度下降

常规的梯度下降法如下，将求n个样本的梯度均值，并加入到方程中
x k + 1 = x k − η k ∇ f ( x ) = x k − η k { 1 n ∑ i = 1 n ∇ f i ( x k ) }

$$\begin{equation} x_{k+1}=x_k-\eta_k\nabla f(x)=x_k-\eta_k\{\frac{1}{n}\sum_{i=1}^n\nabla f_i(x_k)\} \end{equation}$$ xk+1​=xk​−ηk​∇f(x)=xk​−ηk​{n1​i=1∑n​∇fi​(xk​)}​​

• 上面的梯度下降有什么缺点？如何改进？
  我们知道上面是要将n个样本的梯度求出来后整体再除以n求得均值，在n比较小的时候还行，但是当n为100万个样本的时候，如果我们这样做，我们要算100万次后再才能求得梯度均值，这样就非常的浪费时间，有时候内存太大，根本算不过来。这样我们就需要将100万个样本按照小批量，比如100个进行打包，这样就能在小批量迭代中进行下去。

3.2 增量梯度法

优化算法网页版

• 思路：算法中对 的每次更新不需要再全部遍历一次整个样本，只需要随机选择查看一个训练样本$S_i$进行更新，之后再用下一个样本$S_j$进行下一次更新，梯度下降不断迭代更新
• step1: 在第 k 次迭代上，我们从随机选择一个k值
  i ( k ) ∈ { 1 , 2 , ⋯   , n } $$\begin{equation} \mathrm{}i(k)\in \{1,2,\cdots,n\} \end{equation}$$ i(k)∈{1,2,⋯,n}​​
• step2: 计算$\nabla f_{i(k)}$并且迭代
  $$\begin{array}{c}{x}_{k+1}=x_k-{\eta }_k\nabla f_{i(k)}(x_k)\end{array}$$
• step3: 不断循环step1&step2直到 $i(k)$里面的所有元素都取到后停止。
• 注意：不同的步长给迭代带来的扰动特别大，有时候会加快迭代进程，有时会产生剧烈震荡。

3.3 最小二乘法

• 假设所求的值都是标量：那么损失函数如下：
  $$\begin{array}{c}\min f(x)=\min \frac{1}{2}\sum _{i=1}^n(a_{i}x-b_i{)}^2\end{array}$$
• 等价转换为向量模式如下：
  $$\begin{array}{c}\min f(x)=\min \frac{1}{2}||A^{T}x-b|{|}_2^2\end{array}$$
• 当我们求$\nabla f(x)=0$可得：
  $$\begin{array}{c}\nabla f(x)=(A^{T}x-b)A=0\to x=\frac{Ab}{A^{T}A}\to x^{\ast }=\frac{{\sum }_i^n{a}_i{b}_i}{{\sum }_i^n{a}_i^2}\end{array}$$
• 对于每一个$f_i(x)$来说，可得：
  $$\begin{array}{c}\min f(x_i)=\frac{1}{2}(a_i{x}_i-b_i{)}^2\to x_i^{\ast }=\frac{b_i}{a_i}\end{array}$$
• 那么可得，均值的$x^{\ast }$的范围如下：
  $$\begin{array}{c}{x}^{\ast }\in [\min x_i^{\ast },\max x_i^{\ast }]=R\end{array}$$
• 对于每一个函数$f(x_i)$来说，导数如下：
  $$\begin{array}{c}\nabla f_i(x)=a_i(a_{i}x-b_i)\to \nabla f(x)=\sum _{i=1}^n{a}_i(a_{i}x-b_i)\end{array}$$
• 假设没有计算出子程序的$f(x),\nabla f(x)$，我们只能够用含有噪声的数据进行估计，SGD随机梯度算法用的是随机梯度$g(x)$进行无偏估计，保证计算的随机梯度的期望和整个数据的梯度一致，简单来说是进行样本估计的梯度期望来进行表示整体的均值,保证每次的小批量梯度的梯度不会有太大差异。
  $$\begin{array}{c}\mathbb{E}[g(x)]=\nabla f(x)\end{array}$$

3.4 随机梯度下降

• step1：以$x_0$为初始值
• step2: 循环 $k=0,1,\cdots ,$
  – 选择1：随机选择索引 i 进行替换
  – 选择2：随机选择索引 i 不进行替换
• step3: 用 $g_k=\nabla f_i(x)$ 作为随机梯度
• step4： 用迭代公式进行更新参数$x_{k+1}=x_k-{\eta }_k{g}_k$

4. 小批量梯度下降

4.1 概述

为了解决当样本数巨大时的无法一次性算出梯度问题，我们采用将整个样本打包成为小批量进行梯度计算，就像是一口吃不成一个胖子，但是胖子是一口一口吃成的。

• 目标函数：
  $$\begin{array}{c}\underset{x}{\min }f(x)=\frac{1}{n}\sum _{i=1}^n{f}_i(x)\end{array}$$
• 小批量计算梯度的迭代公式
  $$\begin{array}{c}{x}_{k+1}=x_k-\frac{{\eta }_k}{|l_k|}\sum _{j\in l_k}\nabla f_j(x_k)\end{array}$$
• 每次迭代都用$l_k$个随机梯度
• 在并行运算中非常有用，特别是基于GPU显卡的并行运算非常有效
• 在分布式架构中，能够增加并行效果，减少相互通讯时间，提高效率
• 但数字大的小批量随机梯度下降不适合当DNN神经网络

4.2 问题

• 如何选择迭代公式里面的步长?
• 如何选择小批量梯度下降里面的小批量大小？
• 如何计算随机梯度？
• 怎么做梯度裁剪？
• 如何用动量梯度下降法？
• 如何证明随机梯度下降方法有效？
• 理论落后于实践？
• 为什么SGD在神经网络里面如此有效？泛化理论？