考虑一座在(x1,x2)点高度是f(x1,x2)的山。那么，某一点的梯度方向是在该点坡度最陡的方向，而梯度的大小告诉我们坡度到底有多陡。
Hesse矩阵常被应用于牛顿法解决的大规模优化问题(后面会介绍)，主要形式如下：
当f(x)为二次函数时，梯度以及Hesse矩阵很容易求得。二次函数可以写成下列形式：
其中x为列向量，A是n阶对称矩阵，b是n维列向量，c是常数。f(x)梯度是Ax+b,Hesse矩阵等于A
a)如果f(x)是一个标量函数，那么雅克比矩阵是一个向量，等于f(x)的梯度，Hesse矩阵是一个二维矩阵。如果f(x)是一个向量值函数，那么Jacobi矩阵是一个二维矩阵，Hesse矩阵是一个三维矩阵。
b)梯度是Jacobian矩阵的特例，梯度的jacobian矩阵就是Hesse矩阵（一阶偏导与二阶偏导的关系）。
补充在前：实际上在我使用LSTM为流量基线建模时候，发现有效的激活函数是elu、relu、linear、prelu、leaky_relu、softplus，对应的梯度算法是adam、mom、rmsprop、sgd，效果最好的组合是：prelu+rmsprop。
θ=θηθJ(θ)
每迭代一步，都要用到训练集的所有数据，每次计算出来的梯度求平均
η代表学习率LR
θ=θηθJ(θ;x(i);y(i))
通过每个样本来迭代更新一次，以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
缺点：
importtensorflowastftf.compat.v1.train.GradientDescentOptimizer()3.小批量梯度下降（MiniBatchGradientDescent，MBGD）θ=θηθJ(θ;x(i:i+n);y(i:i+n))
为了避免SGD和标准梯度下降中存在的问题，对每个批次中的n个训练样本，这种方法只执行一次更新。【每次更新全部梯度的平均值】
在深度学习中为了解决学习率的灵活性，防止迭代到一定次数时，因学习率过大使得函数值在某个值的附近来回波动而不能继续先最优解的方向迭代，可以对学习率进行指数退化。
特定的凸优化问题
一般而言，近端梯度下降法常用于解决以下这类优化问题：
以线性回归问题为例
近端算子(proximaloperator)
公式(4)给出的软阈值函数恰好与公式(2)中的目标函数相对应。至于为什么软阈值函数的形式是这样，其推导则需自己百度查找。
近端梯度下降(proximalgradientdescent)
线性回归问题的迭代过程
这条更新公式通常也被称为迭代软阈值算法(iterativesoft-thresholdingalgorithm,ISTA)。
importtensorflowastftf.compat.v1.train.ProximalGradientDescentOptimizer()当然，这里还有一个很值得思考的问题：
实际上，次梯度下降法也能求解这种线性回归问题。一般而言，对于损失函数
相应地，损失函数的次梯度为
指数加权平均(exponentiallyweightedaverges)，也叫指数加权移动平均，是一种常用的序列数据处理方式。
它的计算公式如下：
其中，
直接看上面的数据图会发现噪音很多，
这时，我们可以用指数加权平均来提取这组数据的趋势。
可以看出，红色的数据比蓝色的原数据更加平滑，少了很多噪音，并且刻画了原数据的趋势。
指数加权平均，作为原数据的估计值，不仅可以1.抚平短期波动，起到了平滑的作用，2.还能够将长线趋势或周期趋势显现出来。
根据前面的计算式子：
将V_{100}展开得到：
再来看下面三种情况：
当β=0.9时，指数加权平均最后的结果如图红色线所示，代表的是最近10天的平均温度值；
当β=0.98时，指结果如图绿色线所示，代表的是最近50天的平均温度值；
当β=0.5时，结果如下图黄色线所示，代表的是最近2天的平均温度值；
β越小，噪音越多，虽然能够很快的适应温度的变化，但是更容易出现奇异值。
β越大，得到的曲线越平坦，因为多平均了几天的温度，这个曲线的波动更小。但有个缺点是，因为只有0.02的权重给了当天的值，而之前的数值权重占了0.98，曲线进一步右移，在温度变化时就会适应地更缓慢一些，会出现一定延迟。
通过上面的内容可知，β也是一个很重要的超参数，不同的值有不同的效果，需要调节来达到最佳效果，一般0.9的效果就很好。
优点：【相较于滑动窗口平均】
上面提到了一些指数加权平均的应用，这里我们着重看一下在优化算法中的作用。
动量优化算法在梯度下降法的基础上进行改变，具有加速梯度下降的作用。类别：（1）标准动量优化方法Momentum,(2)NAG动量优化方法（NAG在Tensorflow中与Momentum合并在同一函数tf.train.MomentumOptimizer中，可以通过参数配置启用。）
以Momentum梯度下降法为例，
Momentum梯度下降法，就是计算了梯度的指数加权平均数，并以此来更新权重，它的运行速度几乎总是快于标准的梯度下降算法。
这是为什么呢？
让我们来看一下这个图，
例如这就是我们要优化的成本函数的形状，图中红点就代表我们要达到的最小值的位置，假设我们从左下角这里出发开始用梯度下降法，那么蓝色曲线就是一步一步迭代，一步一步向最小值靠近的轨迹。可以看出这种上下波动，减慢了梯度下降法的速度，而且无法使用更大的学习率，因为如果用较大的学习率，可能会偏离函数的范围。如果有一种方法，可以使得在纵轴上，学习得慢一点，减少这些摆动，但是在横轴上，学习得快一些，快速地从左向右移移向红点最小值，那么训练的速度就可以加快很多。
这个方法就是动量Momentum梯度下降法，它在每次计算梯度的迭代中，对dw和db使用了指数加权平均法的思想。
然而网上更多的是另外一种版本，即去掉（1-β）
相当于上一版本上本次梯度的影响权值*1/(1-β)
两者效果相当，只不过会影响一些最优学习率的选取
优点
即在正确梯度方向上加速，并且抑制波动方向张的波动大小，在后期本次计算出来的梯度会很小，以至于无法跳出局部极值，Momentum方法也可以帮助跳出局部极值参数设置。加上动量项就像从山顶滚下一个球，求往下滚的时候累积了前面的动量(动量不断增加)，因此速度变得越来越快，直到到达终点。同理，在更新模型参数时，对于那些当前的梯度方向与上一次梯度方向相同的参数，那么进行加强，即这些方向上更快了；对于那些当前的梯度方向与上一次梯度方向不同的参数，那么进行削减，即这些方向上减慢了。因此可以获得更快的收敛速度与减少振荡。
β的常用值为0.9，即可以一定意义上理解为平均了前10/9次的梯度。至于LR学习率的设置，后面所有方法一起总结吧。
由上面Momentum公式，可以画出Momentum第一和第二次参数更新的方向：
Momentum的想法很简单，就是多更新一部分上一次迭代的更新量，来平滑这一次迭代的梯度。从物理的角度上解释，就像是一个小球滚落的时候会受到自身历史动量的影响，所以才叫动量（Momentum）算法。这样做直接的效果就是使得梯度下降的的时候转弯掉头的幅度不那么大了，于是就能够更加平稳、快速地冲向局部最小点。
然后NAG就对Momentum说：“既然我都知道我这一次一定会走αvt-1的量，那么我何必还用现在这个位置的梯度呢？我直接先走到αvt-1之后的地方，然后再根据那里的梯度再前进一下，岂不美哉？”所以就有了下面的公式：
跟上面Momentum公式的唯一区别在于，梯度不是根据当前参数位置Wt，而是根据先走了本来计划要走的一步后，达到的参数位置Wt-αvt-1计算出来的。
优点：
这种基于预测的更新方法，使我们避免过快地前进，并提高了算法地响应能力，NAG可以使RNN在很多任务上有更好的表现。大大改进了RNN在一些任务上的表现【为什么对RNN好呢，不懂啊】
没有对比就没有伤害，NAG方法收敛速度明显加快。波动也小了很多。实际上NAG方法用到了二阶信息，所以才会有这么好的结果。先按照原来的梯度走一步的时候已经求了一次梯度，后面再修正的时候又求了一次梯度，所以是二阶信息。
为了从另一个角度更加深入地理解这个算法，我们可以对NAG原来的更新公式进行变换，得到这样的等效形式:
NAG的原始形式到等效形式的推导。由
可得
记:
上式代入上上式，就得到了NAG等效形式的第二个式子：
最终我们就得到了NAG的等效形式：
结论：
在原始形式中，NesterovAcceleratedGradient（NAG）算法相对于Momentum的改进在于，以“向前看”看到的梯度而不是当前位置梯度去更新。经过变换之后的等效形式中，NAG算法相对于Momentum多了一个本次梯度相对上次梯度的变化量，这个变化量本质上是对目标函数二阶导的近似。由于利用了二阶导的信息，NAG算法才会比Momentum具有更快的收敛速度。
参数设置：同Momentum，并把use_nesterov设为True
importtensorflowastftf.compat.v1.train.MomentumOptimizer(learning_rate,momentum,use_nesterov=True)momentum项和nesterov项都是为了使梯度更新更加灵活，对不同情况有针对性。但是，人工设置一些学习率总还是有些生硬，接下来介绍几种自适应学习率的方法（AdaGrad，RMSProp，Adam，AdaDelta等。优点：无需人为调节学习率，可以自动调节。缺点；随着迭代次数增多，学习率越来越小，最终趋于0。）
前面的一系列优化算法有一个共同的特点，就是对于每一个参数都用相同的学习率进行更新。但是在实际应用中各个参数的重要性肯定是不一样的，所以我们对于不同的参数要动态的采取不同的学习率，让目标函数更快的收敛。
adagrad方法是将每一个参数的每一次迭代的梯度取平方累加再开方，用基础学习率除以这个数，来做学习率的动态更新。然后给不同的参数不同的学习率【这样每一个参数的学习率就与他们的梯度有关系了，那么每一个参数的学习率就不一样了！也就是所谓的自适应学习率】
假设N元函数f(x)，针对一个自变量研究Adagrad梯度下降的迭代过程，
可以看出，Adagrad算法中有自适应调整梯度的意味（adaptivegradient），学习率需要除以一个东西，这个东西就是前n次迭代过程中偏导数的平方和再加一个常量最后开根号。
举例：
使用Adagrad算法求y=x2的最小值点
导函数为g(x)=2x
初始化x(0)=4，学习率η=0.25，ε=0.1
frommatplotlibimportpyplotaspltimportnumpyasnpfrommpl_toolkits.mplot3dimportAxes3Dfig=plt.figure()x=np.arange(-4,4,0.025)plt.plot(x,x**2)plt.title("y=x^2")deff(x):returnx**2defh(x):return2*xη=0.25ε=0.1x=4iters=0sum_square_grad=0X=[]Y=[]whileiters<12:iters+=1X.append(x)Y.append(f(x))sum_square_grad+=h(x)**2x=x-η/np.sqrt(sum_square_grad+ε)*h(x)print(iters,x)plt.plot(X,Y,"ro")ax=plt.subplot()foriinrange(len(X)):ax.text(X[i],(X[i])**2,"({:.3f},{:.3f})".format(X[i],(X[i])**2),color='red')plt.show()ViewCode公式的另一种写法：
其中，⊙是按元素相乘，r为梯度累积变量，r的初始值为0。ε为全局学习率，需要自己设置。δ为小常数，为了防止分母为零。
参数设置：
Adagrad的一大优势时可以避免手动调节学习率，比如设置初始的缺省学习率为0.01，然后就不管它，另其在学习的过程中自己变化。当然它也有缺点，就是它计算时要在分母上计算梯度平方的和，由于所有的梯度的平方必为正数，这样就造成在训练的过程中，分母累积的和会越来越大。这样学习到后来的阶段，网络的更新能力会越来越弱，能学到的更多知识的能力也越来越弱，因为学习率会变得极其小【就会提前停止学习】，为了解决这样的问题又提出了Adadelta算法。
由于AdaGrad算法的机制，导致每个元素的学习率在迭代过程中只能降低或者不变，因此很可能出现早期迭代到不好的极值点之后，由于学习率太小而无法冲出这个极值点导致最后收敛到的解不优，为了解决这一问题，RMSProp是基于AdaGrad算法做了一点小修改，其更新公式为：
其中，是防止分母爆0的常数。
这样，就有了一个改进版的AdaGrad。
该方法即Tieleman&Hinton的RMSProp，由于RMSProp和AdaDelta是同年出现的，
RMSProp利用了二阶信息做了Gradient优化，在BatchNorm之后，对其需求不是很大。
但是没有根本实现自适应的学习率，依然需要线性搜索初始学习率，然后对其逐数量级下降。
另外，RMSProp的学习率数值与MomentumSGD差别甚大，需要重新线性搜索初始值。
注意：建议取值为1。特点：
整理得更新公式为：
importtensorflowastftf.compat.v1.train.AdadeltaOptimizer()11.AdamAdam=Adaptive+Momentum，顾名思义Adam集成了SGD的一阶动量和RMSProp的二阶动量。
就像Adadelta和RMSprop一样Adam会存储之前衰减的平方梯度，同时它也会保存之前衰减的梯度。经过一些处理之后再使用类似Adadelta和RMSprop的方式更新参数。
特点：
importtensorflowastftf.compat.v1.train.GradientDescentOptimizer()tf.compat.v1.train.AdadeltaOptimizer()tf.compat.v1.train.AdagradOptimizer()tf.compat.v1.train.AdagradDAOptimizer()tf.compat.v1.train.MomentumOptimizer()tf.compat.v1.train.AdamOptimizer()tf.compat.v1.train.FtrlOptimizer()tf.compat.v1.train.ProximalGradientDescentOptimizer()tf.compat.v1.train.ProximalAdagradOptimizer()tf.compat.v1.train.RMSPropOptimizer()tf.keras.optimizers.SGD(lr=0.001,momentum=0.9)tf.keras.optimizers.Adagrad(lr=0.01,epsilon=1e-8)tf.keras.optimizers.Adadelta(lr=0.01,rho=0.95,epsilon=1e-8)tf.keras.optimizers.RMSprop(lr=0.001,rho=0.9,epsilon=1e-8)tf.keras.optimizers.Adam(lr=0.001,beta_1=0.9,beta_2=0.999,epsilon=1e-8)tensorflow中分布式Tensorflow中同步梯度更新（tf.compat.v1.train.SyncReplicasOptimizer）在tensorflow的训练中，分布式可以大大的加快模型训练速度，但是分布式怎么分配和参数设定，都和SyncReplicasOptimizer这个函数有很大关系。
首先这个SyncReplicasOptimizer函数是专门出来分布式深度学习中的同步梯度下降的(要用异步梯度的可以直接无视)
除开opt之外，其他可以先不指定，我们这里重点看看replicas_to_aggregate和total_num_replicas这两个参数，这是非常重要的。
replicas_to_aggregate：是指我们所需要通过分布式的worker计算完成之后所需要的副本数，这里可以认为就是梯度的个数
total_num_replicas：是指我们指定出入计算样本的数量（几个机器就分配几个batch_size）
#同步模式计算更新梯度rep_op=tf.train.SyncReplicasOptimizer(optimizer,replicas_to_aggregate=len(worker_hosts),total_num_replicas=len(worker_hosts),use_locking=True)我们可以看出，replicas_to_aggregate和total_num_replicas都是等于集群中worker的数量的，但是源码中对于这两个参数又添加了额外的解释，(replicas_to_aggregate以下简称副本数，total_num_replicas以下简称计算数)
replicas_to_aggregate:numberofreplicastoaggregateforeachvariableupdate.total_num_replicas:Totalnumberoftasks/workers/replicas,couldbedifferentfromreplicas_to_aggregate.Iftotal_num_replicas>replicas_to_aggregate:itisbackup_replicas+replicas_to_aggregate.Iftotal_num_replicas 源码中说，Iftotal_num_replicas>replicas_to_aggregate:itisbackup_replicas+replicas_to_aggregate. 这是指如果计算数大于副本数，那么多的那个就是backupworker，即备份工作节点。 比如：四个人交了三张试卷，没交试卷的我们就认为是备份工作节点 那这又是什么玩意儿呢，图啥呢？ 在同步梯度下降中，所有worker都要等大家一起计算完成之后才能进行计算，因此会出现等待机制。就像四个人做试卷，但是每个人的速度不一样，但是要同时交卷，所以我们要等待交卷最慢的那个人算完之后才能算完，这样很浪费算的很快的那个人的能力，所以就有了backup的提出，4个人交卷我们只要三个人的试卷，最慢的那个我们不要了，直接清除掉，开始下一轮的考试~ 因此，加入backupworker的方法可以加速分布式同步梯度下法的训练模型，那么backup取几个呢？RevisitingDistributedSynchronousSGD这篇论文中认为是20：1的比例。 还有一种情况，那就是计算数大于副本数。当计算数小于副本数，那么他会多计算其他worker的样本，就好比三个人(给三人一人发一个试卷，分配的是没多余的)，但是要交四份试卷，那就先各算各的，先计算完成的再从已知的三份试卷中拿一个计算，然后再等着这三个人一共上交了四份试卷之后，这样就ok了。有什么用呢？我也不清楚，我们看下一步 当我们说这计算数和副本数的时候总是和机器的物理数量有关系（gpu数量），那么其实这两个都可以不等于机器的物理数量。例如： gpu数量：3那么len（worker）就是3 计算数：10那么这10就指的是一次给分10个batch_size，然后让3个worker去算 副本数：8那么这是个batch_size算完之后我只要8个梯度，然后平均，参数服务器的什么后续操作 牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。牛顿法最大的特点就在于它的收敛速度很快。 具体步骤： 首先，选择一个接近函数f(x)零点的x0，计算相应的f(x0)和切线斜率f'(x0)（这里f'表示函数f的导数）。然后我们计算穿过点(x0,f(x0))并且斜率为f'(x0)的直线和x轴的交点的x坐标，也就是求如下方程的解： 我们将新求得的点的x坐标命名为x1，通常x1会比x0更接近方程f(x)=0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示： 已经证明，如果f'是连续的，并且待求的零点x是孤立的，那么在零点x周围存在一个区域，只要初始值x0位于这个邻近区域内，那么牛顿法必定收敛。并且，如果f'(x)不为0,那么牛顿法将具有平方收敛的性能.粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。 由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示： 牛顿法搜索动态示例图： 在最速下降法（梯度下降）中，我们看到，该方法主要利用的是目标函数的局部性质，具有一定的“盲目性”。牛顿法则是利用局部的一阶和二阶偏导信息，推测整个目标函数的形状，进而可以求得出近似函数的全局最小值，然后将当前的最小值设定近似函数的最小值。相比最速下降法，牛顿法带有一定对全局的预测性，收敛性质也更优良。牛顿法的主要推导过程如下： 第一步，利用Taylor级数求得原目标函数的二阶近似： 第二步，把x看做自变量，所有带有x^k的项看做常量，令一阶导数为0，即可求近似函数的最小值： 即： 第三步，将当前的最小值设定近似函数的最小值（或者乘以步长)。 牛顿法是二阶算法，因为该算法使用了海森矩阵（Hessianmatrix）求权重的二阶偏导数。牛顿法的目标就是采用损失函数的二阶偏导数寻找更好的训练方向。 因此牛顿下降法是用二次曲面去拟合当前的局部曲面,现在采用如下表示：f(wi)=fi、f(wi)=gi和Hf(wi)=Hi。在w0点使用泰勒级数展开式二次逼近函数f. H0为函数f在点w0的海森矩阵，对w求导，得到g,通过将g设定为0，我们就可以找到f(w)的最小值，也就得到了以下方程式。 因此，从参数向量w0开始，牛顿法服从以下方式进行迭代： 向量Hi-1·gi也就是所说的牛顿下降步（Newton'sstep）。注意，参数的这些变化将朝着极大值而不是极小值逼近，出现这样的情况是因为海森矩阵非正定。 因此在不能保证矩阵正定的情况下，损失函数并不能保证在每一次迭代中都是减少的。为了防止上述问题，牛顿法的方程式通常可以修改为： 牛顿法主要存在的问题是： importnumpyasnpdefJacobian(x):returnnp.array([x[0],0.4*x[1],1.2*x[2]])defHessian(x):returnnp.array([[1,0,0],[0,0.4,0],[0,0,1.2]])defNewton(x0):i=0iMax=10x=x0Delta=1alpha=1whilei 从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。） 根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。 注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。 牛顿法的优缺点总结： 拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和M.J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。 拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。 拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型： 其中我们要求步长ak满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型： 因为需要很多的操作求解海森矩阵的值还有计算矩阵的逆，应用牛顿法的计算量是十分巨大的。因此有一种称之为拟牛顿法（quasi-Newton）或 变量矩阵法来解决这样的缺点。这些方法并不是直接计算海森矩阵然后求其矩阵的逆，拟牛顿法是在每次迭代的时候计算一个矩阵，其逼近海森矩阵的逆。 最重要的是，该逼近值只是使用损失函数的一阶偏导来计算。 海森矩阵由损失函数的二阶偏导组成，拟牛顿法背后的思想主要是仅使用损失函数的一阶偏导数，通过另一矩阵G逼近海森矩阵的逆。拟牛顿法的公式可以表示为： 学习速率η可以设定为固定常数，也可以通过单变量函数优化得到。其中矩阵G逼近海森矩阵的逆，且有不同的方式进行逼近。通常，最常用的两种方式是Davidon–Fletcher–Powellformula(DFP)和theBroyden–Fletcher–Goldfarb–Shannoformula(BFGS)。 拟牛顿法的训练过程流程图如下所示，从图中我们可以看出来模型是通过第一次计算拟牛顿训练方向而优化参数的，然后再寻找适当的学习速率。拟牛顿法适用于绝大多数案例中：它比梯度下降和共轭梯度法收敛更快，并且也不需要确切地计算海森矩阵及其逆矩阵。 Levenberg–Marquardtalgorithm能结合以上两种优化方法的优点，并对两者的不足做出改进。与linesearch的方法不同，LMA属于一种“信赖域法”(trustregion)，牛顿法实际上也可以看做一种信赖域法，即利用局部信息对函数进行建模近似，求取局部最小值。所谓的信赖域法，就是从初始点开始，先假设一个可以信赖的最大位移s（牛顿法里面s为无穷大），然后在以当前点为中心，以s为半径的区域内，通过寻找目标函数的一个近似函数（二次的）的最优点，来求解得到真正的位移。在得到了位移之后，再计算目标函数值，如果其使目标函数值的下降满足了一定条件，那么就说明这个位移是可靠的，则继续按此规则迭代计算下去；如果其不能使目标函数值的下降满足一定的条件，则应减小信赖域的范围，再重新求解。LMA最早提出是用来解决最小二乘法曲线拟合的优化问题的。 Levenberg-Marquardt算法，也称为衰减最小二乘法（dampedleast-squaresmethod），该算法的损失函数采用平方误差和的形式。该算法的执行也不需要 计算具体的海森矩阵，它仅仅只是使用梯度向量和雅克比矩阵（Jacobianmatrix）。 这里解释一下雅克比矩阵（Jacobianmatrix）：Jacobi矩阵实际上是向量值函数的梯度矩阵，假设F:Rn→Rm是一个从n维欧氏空间转换到m维欧氏空间的函数。 这个函数由m个实函数组成: 这些函数的偏导数(如果存在)可以组成一个m行n列的矩阵(mbyn)，这就是所谓的雅可比矩阵： 该算法的损失函数如下方程式所示为平方误差和的形式： 在上式中，m是数据集样本的数量。我们可以定义损失函数的雅可比矩阵以误差对参数的偏导数为元素，公式如下： 其中m是数据集样本的数量，n是神经网络的参数向量。那么雅可比矩阵是m*n阶矩阵，损失函数的梯度向量就可以按如下计算出来： E在这里是所有误差项的向量。最终，我们可以利用一下表达式逼近海森矩阵： 其中λ为衰减因子，它确保了海森矩阵的证定性（positiveness），I是单位矩阵。下面的表达式定义了Levenberg-Marquardt算法中参数的更新和优化过程： 当衰减参数λ为0时，Levenberg-Marquardt算法就是使用海塞矩阵逼近值的牛顿法。而当λ很大时，该算法就近似于采用很小学习速率的梯度下降法。如果进行迭代导致了 损失函数上升，衰减因子λ就会下降，从而Levenberg-Marquardt算法更接近于牛顿法。该过程经常用于加速收敛到极小值点。 第一步就是计算损失函数、梯度和海森矩阵逼近值，随后再在每次迭代降低损失中调整衰减参数。 Levenberg-Marquardt算法是为平方误差和函数所定制的。这就让使用这种误差度量的神经网络训练地十分迅速。但是其缺点是： 共轭梯度法是共轭方向法的一种，意思是搜索方向都互相共轭 共轭向量及其性质 则称p0，p1，，pm1p0，p1，···，pm1是Q共轭向量或称向量p0，p1，，pm1p0，p1，···，pm1是Q共轭的(简称共轭)，称p0，p1，，pm1p0，p1，···，pm1的方向是Q共轭方向。当Q=I(单位矩阵)Q=I(单位矩阵)时，公式(1)变为 z的向量构成的集合为由点x0和向量p0，p1，，pm1所生成的线性流行。记为L[x0;p0,p1,···,pm1]。 基本思想 在考虑普通函数之前，我们首先用2元正定二次函数进行讲解。首先考虑如下的正定二次函数 在第二次迭代过程中我们不适用f(x1)作为这次迭代的搜索方向，我们想直在第二次迭代之后能直接到达最优点x*（x*表示是当前迭代找到的最优点），那么这次的迭代方向p1应该满足什么条件呢？首先根据最速下降法的迭代公式我们有 即 综上所述，对于n元正定二次函数，我们可以从任意点出发，然后沿着这n个共轭方向最多做n次直线搜索(原因将在下一小节进行讲解)，就可以求的目标函数的最优点。 优化模型建立 虽然梯度下降法的每一步都是朝着局部最优的方向前进的，但是它在不同的迭代轮数中会选择非常近似的方向，说明这个方向的误差并没通过一次更新方向和步长更新完，在这个方向上还存在误差，因此参数更新的轨迹是锯齿状。共轭梯度法的思想是，选择一个优化方向后，本次选择的步长能够将这个方向的误差更新完，在以后的优化更新过程中不再需要朝这个方向更新了。由于每次将一个方向优化到了极小，后面的优化过程将不再影响之前优化方向上的极小值，所以理论上对N维问题求极小只用对N个方向都求出极小就行了。为了不影响之前优化方向上的更新量，需要每次优化方向共轭正交。假定每一步的优化方向用pk表示，可得共轭正交 由此可得，每一步优化后，当前的误差和刚才的优化方向共轭正交。 若为N维空间优化问题，则每次优化方向可以组成这个空间中的一组基底。P={p1,p2,…,pn}。 算法只需要解决两个问题： 优化方向确定 优化步长的选取 三个推论 最终简化 算法在三中基本推导完毕，但是在工程应用中如果每次进行pk的正交化需要对之前所有的优化向量求解β，现简化如下： 最终的推导结束。整理为如下的伪代码（用于正定二次函数的共轭梯度法） 用于非二次函数的共轭梯度法 用于一般函数的Fletcher-Reeves共轭梯度法描述如下。 总结 共轭梯度法是一种典型的共轭方向法，它的搜索方向是负梯度方向和上一次搜索方向的一个组合 关于βk-1，有两种常用的计算公式 预处理共轭法改善了G的条件数，使算法的收敛速度加快 预处理的方法是寻找一个非奇异矩阵C，使得C-TGC-1的条件数小于G的条件数 再开始共轭梯度法是满足某一条件后重新使用最速下降方向作为搜索方向，这个条件包括迭代n步，或共轭梯度方向是上升方向 FR共轭梯度法： #coding=utf-8#FR-CG共轭梯度法fromlinear_search.Functionimport*fromlinear_search.wolfeimport*importnumpyasnpdefconjugate(_f,_x):fun=Function(_f)x=array(_x)d=-fun.grad(x)whilefun.norm(x)>0.01:alpha=wolfe(_f,x,d)g=np.mat(fun.grad(x))beta=1/np.dot(g,g.T)x=x+alpha*dg=np.mat(fun.grad(x))beta=beta*np.dot(g,g.T)d=array(-g+beta*d)[0]returnxViewCode再开始共轭梯度法： #coding=utf-8#再开始共轭梯度法fromlinear_search.Functionimport*fromlinear_search.wolfeimport*importnumpyasnpdefrestart_conjugate(_f,_x,n):fun=Function(_f)x=array(_x)whileTrue:d=-fun.grad(x)k=0if(np.linalg.norm(d)<0.01):breakwhilefun.norm(x)>0.01:g=np.mat(fun.grad(x))alpha=wolfe(_f,x,d)x=x+alpha*dk=k+1g1=np.mat(fun.grad(x))ifnp.dot(g1,g.T)/np.dot(g1,g1.T)>0.1ork>=n:ifnp.linalg.norm(g1)<0.01:returnxbreakelse:beta=np.dot(g1,g1.T)/np.dot(g,g.T)d=array(-g+beta*d)[0]ifnp.dot(mat(d),g1.T)>0:breakreturnxViewCode其他的文档介绍 上式中，Y称之为共轭参数，并且有一些方法计算这个参数。两种常用的方法源自Fletcher、Reeves和Polak、Ribiere。对于所有的共轭梯度算法，训练方向 周期性地重置为负梯度方向。参数通过下面的表达式得以更新和优化，通常学习速率η可使用单变量函数优化方法求得。 共轭梯度法的训练过程流程图如下表示，从图中我们可以看出来模型是通过第一次计算共轭梯度训练方向而优化参数的，然后再寻找适当的学习速率。 importnumpyasnpdefJacobian(x):#returnarray([.4*x[0],2*x[1]])returnnp.array([x[0],0.4*x[1],1.2*x[2]])defHessian(x):#returnarray([[.2,0],[0,1]])returnnp.array([[1,0,0],[0,0.4,0],[0,0,1.2]])defCG(x0):i=0k=0r=-Jacobian(x0)p=rbetaTop=np.dot(r.transpose(),r)beta0=betaTopiMax=3epsilon=10**(-2)jMax=5#RestarteverynDimiterationsnRestart=np.shape(x0)[0]x=x0whilei 综上分析，可以得出如下几个结论： 如图，收敛速度最慢的是梯度下降算法，但该算法同时也只要求最少内存。相反，Levenberg-Marquardt算法可能是收敛速度最快的，但其同时也要求最多的内存。 比较折中的方法是拟牛顿法。总而言之，如果我们的神经网络有数万参数，为了节约内存，我们可以使用梯度下降或共轭梯度法。如果我们需要训练多个神经网络，并且每个神经网络都只有数百参数、数千样本，那么我们可以考虑Levenberg-Marquardt算法。而其余的情况，拟牛顿法都能很好地应对。 在线学习算法强调的是训练的实时性，面向流式数据，每次训练不使用全量数据，而是以之前训练好的参数为基础，每次利用一个样本更新一次模型，是属于增量学习的一部分，从而快速更新模型，提高模型的时效性。 统计学习的先验假设是数据存在自己一定的分布，我们的目的是寻找与实际分布距离最小的策略来泛化未知的结果。数据由真实模型产生，如果能有无限数据、并在包含有真实模型的空间里求解，也许我们能算出真是模型。但实际上我们只有有限的有噪音的数据，这又限制我们只能使用相对简单的模型。所以，理想的算法是能够用不多的数据来得到一个不错的模型。 离线学习算法强调的是数据中不断训练已有的模型，不断迭代达到真实的数据分布，在训练过程中，所有数据都是可见的，目标是一定的（就是最终的那个真实分布），其中可以采用不同的更新策略和采样策略，所以有了批量梯度下降和随机梯度下降等算法。 梯度下降可以分成两种模式，batch模式和delta模式。batch模式的时效性比delta模式要低一些。分析一下batch模式，比如昨天及昨天的数据训练成了模型M，那么今天的每一条训练数据在训练过程中都会更新一次模型M，从而生成今天的模型M1。 batch学习可以认为是离线学习算法，强调的是每次训练都需要使用全量的样本，因而可能会面临数据量过大的问题。一般进行多轮迭代来向最优解靠近。onlinelearning没有多轮的概念，如果数据量不够或训练数据不够充分，通过copy多份同样的训练数据来模拟batchlearning的多轮训练也是有效的方法。 delta模式可以认为是在线学习算法，没有多轮的概念，如果数据量不够或训练数据不够充分，通过copy多份同样的训练数据来模拟batchlearning的多轮训练也是有效的方法。所以，OGD和SGD都属于在线学习算法，因为每次更新模型只用一个样本。SGD则每次只针对一个观测到的样本进行更新。通常情况下，SGD能够比GD“更快”地令逼近最优值。当样本数特别大的时候，SGD的优势更加明显，并且由于SGD针对观测到的“一条”样本更新，很适合进行增量计算，实现梯度下降的Online模式（OGD,OnlineGradientDescent）。 本文主要会分三个部分介绍，如果对理论产生背景不感兴趣的话，可以直接看第3部分的工程实现（这一部分google13年那篇工程化的paper介绍得很详细）： 对于loss函数+正则化的结构风险最小化的优化问题（逻辑回归也是这种形式）有两种等价的描述形式，以1范数为例，分别是： a、无约束优化形式的softregularizationformulation： b、带约束项的凸优化问题convexconstraintformulation： 批量算法中每次迭代对全体训练数据集进行计算（例如计算全局梯度），优点是精度和收敛还可以，缺点是无法有效处理大数据集（此时全局梯度计算代价太大），且没法应用于数据流做在线学习。这里分无约束优化形式和约束优化（与上面问题描述可以对应起来）两方面简单介绍一下一些传统批量算法。 如上所述，批量算法有自身的局限性，而在线学习算法的特点是：每来一个训练样本，就用该样本产生的loss和梯度对模型迭代一次，一个一个数据地进行训练，因此可以处理大数据量训练和在线训练。常用的有在线梯度下降（OGD）和随机梯度下降（SGD）等，本质思想是对上面【问题描述】中的未加和的单个数据的loss函数L（w，zi)做梯度下降，因为每一步的方向并不是全局最优的，所以整体呈现出来的会是一个看似随机的下降路线。典型迭代公式如下： 1）、简单加入L1范数 2）、在1范数的基础上做截断，最直观没技术含量的思路，那就设定一个阈值，做截断来保证稀疏，可以结合L1范数 但是简单截断方法有问题：权重小，可能是确实是无用特征，还或者可能是该特征才刚被更新一次（例如训练刚开始的阶段、或者训练数据中包含该特征的样本数本来就很少），另外，简单rounding技术太aggressive了，可能会破坏在线训练算法的理论完备性。 3）、Black-boxwrapperapproaches： 下面会提一下FOBOS（Forward-BackwardSplittingmethod，其实应该叫FOBAS的，历史原因）以及RDA，因为后面的FTRL其实相当于综合了这两种算法的优点。 优化函数： 其中x表示模型的参数，xi表示模型的第i个参数。 L(x)是逻辑回归的似然函数的负对数。 最右边那一项是L1正则项。 可以考虑加上L2正则来防止过拟合。 假设模型参数为x，第t个样本的特征表示为vt 则样本label为1的概率为： 该样本对应的对数损失函数为： 令 则lt关于xt的求导过程如下： 上式即为第t个样本的梯度gt。 原始的OGD使用的迭代公式为： 其中et表示非增的学习率，也叫做步长， OGD的算法比较简单，不够好，即使是加了L1正则化也可能不产生稀疏解。 FOBOS(Forward-BackwardSplitting)是由JohnDuchi和YoramSinger提出的[11]。从全称上来看，该方法应该叫FOBAS，但是由于一开始作者管这种方法叫FOLOS（ForwardLookingSubgradients），为了减少读者的困扰，作者干脆只修改一个字母，叫FOBOS。 RDA（Regularizeddualaveraging），微软10年的工作 RDA（正则对偶平均）是微软的研究成果，其权重更新策略为 权重更新包括三个部分第一部分线性加权，即对历史梯度进行加权平均；第二部分正则项部分对特征进行稀疏化；第三部分严格递增序列相当于额外的正则项。实验证明该方法能够产生较好的稀疏和精度。 主要用于CTR预测的在线训练，成千上万维度导致大量稀疏特征。一般希望模型参数更加稀疏，但是简单的L1正则无法真正做到稀疏，一些梯度截断方法（TG）的提出就是为了解决这个问题，在这其中FTRL是兼备精度和稀疏性的在线学习方法。FTRL的基本思想是将接近于0的梯度直接置零，计算时直接跳过以减少计算量。 在上文中我们从原理上定性比较了L1-FOBOS和L1-RDA在稀疏性上的表现。有实验证明，L1-FOBOS这一类基于梯度下降的方法有比较高的精度，但是L1-RDA却能在损失一定精度的情况下产生更好的稀疏性。那么这两者的优点能不能在一个算法上体现出来？这就是FTRL要解决的问题。 FTRL（FollowtheRegularizedLeader）是由Google的H.BrendanMcMahan在2010年提出的[1]，后来在2011年发表了一篇关于FTRL和AOGD、FOBOS、RDA比较的论文[2]，2013年又和GaryHolt,D.Sculley,MichaelYoung等人发表了一篇关于FTRL工程化实现的论文[3]。 本节我们首先从形式上将L1-FOBOS和L1-RDA进行统一，然后介绍从这种统一形式产生FTRL算法，以及介绍FTRL算法工程化实现的算法逻辑。 把这两个公式合并到一起，有： 再将这N个独立最优化子步骤合并，那么L1-FOBOS可以写作： 而对于L1-RDA，我们可以写作： 需要注意，与论文[2]中的Table1不同，我们并没有将L1-FOBOS也写成累加梯度的形式。 FTRL综合考虑了FOBOS和RDA对于正则项和W限制的区别，其特征权重的更新公式为： 公式(3)看上去很复杂，更新特征权重貌似非常困难的样子。不妨将其进行改写，将最后一项展开，等价于求下面这样一个最优化问题： 针对特征权重的各个维度将其拆解成N个独立的标量最小化问题： 到这里，我们遇到了与上一篇RDA中类似的优化问题，用相同的分析方法可以得到： 从公式(4)可以看出，引入L2正则化并没有对FTRL结果的稀疏性产生任何影响。 工程优化： 1.预测的内存方面：L1范式加策略，训练结果w很稀疏，在用w做predict的时候节省了内存，很直观 2.训练的内存方面： 1）在线丢弃训练数据中很少出现的特征，即稀疏特征处理： 2）浮点数重新编码 3）训练若干相似model 4）SingleValueStructure（据说有公司已经在实际中这么搞，大数据量下也能够保证不错的auc） ６)SubsamplingTrainingData 考虑特征维度的变化率：如果特征1比特征2的变化更快，那么在维度1上的学习率应该下降得更快。我们很容易就可以想到可以用某个维度上梯度分量来反映这种变化率。在FTRL中，维度i上的学习率是这样计算的： 大家对上面那一大坨前因后果和公式都不感兴趣，ok，没关系，google非常贴心地在13年给出了一篇工程性很强的paper，其实大部分公司使用FTRL的，根本不会关心上面那一大段东西，直接按着伪代码写，调调参，看结果很不错就可以了。我们公司开始就是这么搞的，哈哈，不过人总是要有点儿好奇心的不是，深究一下前因后果和基本的理论公式感觉还是挺不同的。 逻辑回归下的per-coordinateFTRL_Proximal的伪代码如下，在公式表达的基础上做了一些变换和实现上的trick，细节paper里有，大家在自己做实现的时候，可以在实际数据集上再并行加加速： 算法流程： 根据前面的学习，可以使用LR作为基本学习器，使用FTRL作为在线最优化的方法来获取LR的权重系数，从而达到在不损失精度的前提下获得稀疏解的目标。 工程化实现的几个核心点是： 算法代码实现如下所示，这里只给出了核心部分代码，主要做了以下优化: 传统Batch算法优点是精度和收敛还可以，缺点是无法有效处理大数据集（此时全局梯度计算代价太大），且没法应用于数据流做在线学习 SGD存在的问题上面主要列了1）精度低；2）收敛慢；3）几乎得不到稀疏解。其中对onlinelearning最重要的问题是SGD很难得到需要的正则化设计的解，特别是几乎得不到稀疏解 RDA，2010微软提出，特点：相对FOBOS，在精度与稀疏性之间做平衡，其中实验表明，在L1正则下，RDA比FOBOS可以更加有效地得到稀疏解。 不同的方法按照统一的描述形式，区别点主要在第二项和第三项： 这小结做了在线最优化算法的整理和总结，沿着稀疏性的主线，先后介绍了简单截断法、TG、FOBOS、RDA以及FTRL。从类型上来看，简单截断法、TG、FOBOS属于同一类，都是梯度下降类的算法,并且TG在特定条件可以转换成简单截断法和FOBOS；RDA属于简单对偶平均的扩展应用；FTRL可以视作RDA和FOBOS的结合，同时具备二者的优点。目前来看，RDA和FTRL是最好的稀疏模型OnlineTraining的算法。 对于Online模式的并行化计算，一方面可以参考ParallelSGD的思路，另一方面也可以借鉴batch模式下对高维向量点乘以及梯度分量并行计算的思路。总之，在理解算法原理的基础上将计算步骤进行拆解，使得各节点能独自无关地完成计算最后汇总结果即可。 加速收敛2.防止过拟合3.防止局部最优 在构建神经网络模型时，选择出最佳的优化器，以便快速收敛并正确学习，同时调整内部参数，最大程度地最小化损失函数。