DL优化算法总结

踏雪的剑

本文记录笔者日常工作与学习中接触到的优化相关常识，纯个人技术随笔，不作为讲解用。
神经网络优化算法整理：

日常生活中，法式中最常用的就是Adam和SGD
梯度下降法与反向传布算法：

梯度下降法：gradient decent， 优化单个参数
反向传布算法：backpropagation，在所有参数上使用梯度下降法
梯度下降法家族

凸问题：定义域内只有一个极值点。（只有一个最小值，全局独一）
神经网络的训练与优化，一般可分为两个方面：调整网络布局＋优化算法本身的更改。
指数加权移动平均法：远距离的影响小，近距离的影响大




梯度下降法:看之前的文章。

SGD:　

随机梯度下降法，随机挑选一组数据求梯度下降，减少计算，加快优化速度。（其实是mini-batch 为１的GD）
小批量梯度下降法：

挑选一个batch数据求解梯度。




存在错误谬误：


动量法（也叫冲量法）：

累计梯度，调节梯度


AdapGrad（自适应梯度）与RMSProp：

累计梯度的平方，调节学习率（Adaptive指的就是本身调整学习率），AdapGrad斗劲适合稀疏数据。




AdapGrad算法公式：


RMSProp公式：




Adam：Adaptive moment estimation(自适应性矩估计)，

是一种随机优化算法，可以替代传统的随机梯度下降（SGD，Stochastic　Gradient　Decent），同时使用动量法和AdaGrad，同时使用修正偏差法式解决冷启动
１.　随机梯度下降保持单一的学习率（即alpha）更新所有权重，学习率在训练过程中并不会改变，而Adam通过计算梯度的一阶矩估计与二阶矩估计为分歧的参数设计独立的自适应学习率
２.　Adam算法同时兼顾AdaGrad(自适应梯度)与RMSProp（均方根传布）的长处
３.　Adam的本质为RMSProp＋动量
４.　公式：




引申：

牛顿法优化：



如上图：梯度下降法是用一阶导的沿着斜率的标的目的（橙色线）优化，牛顿法是操作二阶导，沿着二次曲线的标的目的优化（绿色线），灰色线是最好的优化，但往往得不到。


Nesterov算法：



矩估计：

数理统计学中有一类数字特征称为矩：
此中ｋ为正整数，叫做对ａ的ｋ阶矩（或叫动差）当ａ为０时，叫做ｋ阶原点矩，记作，也叫ｋ阶矩
矩估计：用矩来估计某个参数（凡是是一阶矩和二阶矩）
一阶矩：期望或均值
二阶矩：方差，代表离散程度
三阶矩：一个随机密度函数向左或向右偏斜的程度
矩估计还可以分为原点矩（包含期望）和中心矩（包含方差）
期望的公式：，所以期望其实是一阶原点矩方差的公式：２，所以方差其实是二阶中心矩
引申：
矩的定义与闵氏距离有点像，这里给出闵氏距离的定义，供对比：


线性最小二乘法的求解方式

超定齐次方程组的求解（SVD分化）：即求解AX＝０
对A做SVD分化，得：


因为U是一个正交矩阵：正交变换不改变矩阵的秩，特征值，行列式，迹。故


即求||AX||的最小值，转化成了求||DY||最小值:


又因为ｙ=V^TX, 即


所以用ｓｖｄ分化求最小二乘，解超定方程组的解，就是求Vn，即SVD分化中最小特征值\sigma_n所对应的右奇异向量Vｎ
最小二乘法的几何意义：

高维空间的一个向量（由ｙ决定）在低维子空间的（由ｘ数据决定）投影。
最小二乘法是投影矩阵的重要应用。
最小二乘：指的是误差最小。当AX＝ｂ无解时，我们但愿AX构成的向量与ｂ误差最小。AX＝ｂ无解，暗示ｂ不在A的列空间中，A的列空间中与ｂ误差最小的向量，即为ｂ在A的投影。


如上图，假设A所长成的空间为一个平面，此时ｂ无法用A暗示，而A中向量与ｂ误差最小的，即为向量ｐ（ｂ在A中的投影，即为ｐ）
求解超定方程组的方式：最小二乘法（其实就是求左逆）

超定方程组：方程个数大于未知数的个数（限制太多了，可能没有解）
欠定方程组：方程个数小于未知数的个数（限制太少了，可能会有无数解）
矩阵的转置乘以自身，必然为对称阵，即A^TA必然为对称阵。证明：(A^TA)^T＝A^TA
求AX=b无解，由于AX＝ｂ为超定方程组，限制太多，没有解，此时可以求一个最优近似解。
做变换：AX=b摆布两边同时乘以A^T


矩阵A的零空间与列空间：

对于所有AX=0的X，构成空间称为矩阵A的零空间，
矩阵A的列向量所构成的空间，称为A的列空间。
逆矩阵与伪逆（广义逆）

１.　可逆矩阵必然是方阵。如果一个矩阵不是方阵，是不存在逆矩阵的，对其求逆，就是求它的伪逆（要满足moore-penrose条件）
２.　伪逆也可以联想到运筹学的“线性规划”
３.　神经网络中，插手多层，有点类似软件开发中的中间层，当前调参的主要算法为BP算法，其实也应该可以操作“伪逆”的思想与“线性规划”的思想，求一个全局最优
伪逆（pseudo-inverse）用A^+来暗示



求逆矩阵（或伪逆矩阵）的方式

A为ｍ×ｎ的矩阵，ｒ为矩阵A的秩
１.　若A为方阵，则｜A｜！＝０，则A^{-1}存在
２.　若A不是方阵，或｜A｜＝＝０，此时只能求伪逆pinv(A):pseudo inverse


极限学习机（ELM，Extreme Learning Machine）

用于训练单隐层前馈神经网络，需要操作广义逆矩阵的理论。


非线性最小二乘优化算法整理

１.梯度下降法（梯度更新：一阶导）
２.牛顿法：二阶海塞矩阵（梯度更新：-阶导/二阶导）
３.高斯牛顿法（GN）：对牛顿法的改良，避免了二阶导（梯度更新：一阶导/一阶导平方）
４.列文伯格－马夸特法（LM）：对GN的改良，设定了一个评判指标


SLAM中最大似然估计，可以转化为最小二乘问题。
常规的思路为对最小二乘问题的方针函数F(x)进行求导，其导数为０的时候，即为ｘ的最优解，最终求得极值。
但有时候F（ｘ）并不容易求导，这时就需要用以上的方式进行迭代，求其最小值。


梯度下降法

若只保留一阶梯度，即


增量的标的目的为：


牛顿法

若保留二阶梯度，即


该方式称为牛顿法。
梯度下降法存在zigzag问题（过于贪婪），迭代次数多，牛顿法迭代次数少，但Hessian矩阵计算复杂。为了回避Hessian矩阵的计算，提出了高斯牛顿法和列文伯格－马夸尔法
高斯牛顿法（GN：Gaussian－Newton法）:

注意区分牛顿法
一阶近似:


即高斯牛顿法用J^TJ替代了牛顿法中的Hessian计算。
求解增量方式：


由于H是由J^T(x)J(x)求得，未必可逆，Levenberg-marquadt方式改良了它。
Levenberg-marquadt方式(LM算法)

提出了信赖区域的概念（Trust Region），认为近似只在区域内有效
近似法式的描述：


求解：


D在Levenberg里去D=I，即取一个球，Marquaardt令D取非负对角阵，即椭球（此处高翔的１４讲视频没讲清楚，需要再查资料）
Trust　Region内的优化：操作拉格朗日乘子法，转化为无约束：


最终求得增量方程为：


在Levenberg方式中，取D=I，则


LM对比于GN，能够保证增量方程的正定性


即认为近似只在必然范围内成立。如果近似不好，则缩小范围。
从增量方程上看，可以当作一阶和二阶的混合：


引申：凹凸函数的判定

凹凸函数在同济大学高等数学中的定义符合人们的思维定式。在国际上的定义恰好与同济大学高等数学中的定义相反。
1、同济大学高等数学定义：


判断函数的凹凸性，还可以使用上面提到的LM算法中的TrustRegion的概念，



2、国际上的定义：
国际上的定义刚好与国内的凹凸函数的定义相反。
二阶导数大于0，则为凸函数，有极小值；
二阶导数小于0，则为凹函数，有极大值
（后面涉及到的凹凸函数，均为国际上的定义）；
3、e^x的二阶导数大于0，为凸函数；logx的二阶导数小于0，为凹函数；


一元函数可以很容易的判断凹凸性，二元函数如何判断凹凸性？用到了海塞矩阵，按照海塞矩阵的正定性，判断凹凸性。
①海塞矩阵：二阶偏导构成的矩阵


②正定矩阵
判断海塞矩阵是否为正定矩阵。
若所有特征值均不小于零，则称为半正定。
若所有特征值均大于零，则称为正定。
特征值怎么求？|λE-A|=0，可以求出特征值。若主对角线上的元素都为0，则主对角线上的值为特征值。detA=|A|=对角线元素积。
③凹凸性判断（正定矩阵为凸函数）:
例题1：


所有的特征值均大于0，海塞矩阵为正定矩阵，函数为凸函数。
例题2：


例题3：


按照特征值，一个为2/y，一个为0，那么y的正负决定函数的凹凸性，若y>0,函数为凸函数。  
求解Hessian矩阵，一种可以手动去算，还有一种可以操作WofFram网站来求：


加速整理：

除以２^n, 采用移位：>>n
以２^n取模(fmod函数：取模运算，就是求余数)，采用：＆（２^n-1）
能用float，就不用double:定义常量时，后面加上“ｆ”
lookup table: 哈希的思想
多线程：OpenMP与Cuda
更短的数据类型代替
inline, static节省时间（避免多次分配／回收内存）
一个二维高斯卷积，转换成两个一维高斯卷积
算法逻辑改削
也可以参考TensorRT的做法：算子融合，常量折叠。
积分图：Harr特征提取时使用。
快速傅立叶变换：FFT
按照数字特征进行优化：


线性方程组的求解：