转载请注明出处： http://blog.csdn.net/c602273091/article/details/79111771

机器学习或者是深度学习中涉及了不少优化理论，那么问题来了，在机器学习中，它优化的目标是什么？它是如何进行优化的？为什么进行这种优化？这种优化的好处以及坏处？以及这种优化方法适合什么情况？最近在上CMU 18-660 Optimization的课程，一开始看的Convexity看得我一脸懵逼，老师讲得慢，今年这个新来的老师把phd的10-725的课程搬了过来，它已经不是以前的水课了。所以我开始学习优化理论，从简单的GD和Newton Method入手感受一下【6】。

Learning可以说是机器学习的核心，而学习的过程的过程需要用到optimization这个工具。这篇文章主要是介绍了梯度下降和牛顿迭代法，顺带着用几句话介绍了牛顿迭代法的改进以及矩阵分解。

gradient descent

Optimization之GD，Newton Method

上面的式子结果是什么？如果没有理解透GD的话，以上这个可能都会算错。搞混了Lapalace Operator和Hessian Matrix也会搞错。

第一个求的是梯度，那么什么是梯度？梯度就是当前值往变量所在增长方向变化最快的数值，梯度是一个响亮，函数中有几个变量，那么梯度就是几维的向量。所以结果就是一个向量：（忘记了常用导数求导公式【15】）
[2∗x+cos(y),−x∗sin(y)]

第二个是Laplace operator,不是Hessian Matrix，Hessian Matrix在2的正下方会标出变量，等会儿会说到。所以这个Laplace Operator的结果就是：（如果忘记了各种算子，请看【16】）
2−x∗cos(y)，变成了对梯度再进行求导的和。

Gradient：
Optimization之GD，Newton Method

Hessian Matrix Representation：
Optimization之GD，Newton Method

Optimization之GD，Newton Method

Laplacian：
Optimization之GD，Newton Method

Train rule：对某个变量的求导，转换成在这个变量通向ouput构成的有向图累加梯度。比如u对x，y影响，所以u的权值更新需要把x，y的两部分都考虑进来。
Optimization之GD，Newton Method

现在举一个linear regression的例子：
y只有两个变量进行linear regression，算出拟合的y^与实际的y之间的loss，我们优化的目标就是最小化loss，计算loss的梯度：
Optimization之GD，Newton Method

使用泰勒一阶展开并忽略无穷小项（这里的x向量是我们要优化的参数）：
Optimization之GD，Newton Method

因为我们想最小化loss，那么就希望f(x+p)<=f(x)，那么另外一项就需要为负数。那么设置p=-g。
Optimization之GD，Newton Method
所以以上式子解决了方向的问题，但是scale的问题还存在，所以有一个学习率，一般采用gradient decay进行调节scale的大小，先大后小。快速收敛，后期减少防止梯度震荡，难以收敛。

batch gradient：
对所有的数据集计算loss，然后去平均的loss对权值进行更新。这种离线的方式导致不能把新的数据集加入，只能一次性计算完所有的loss。另外，这种方法计算loss的时候，需要大量的内存。(1) 训练集很大时，需要很大的计算资源(需要把所有data装进内存); (2) batch gd不支持online weight update (比如有的数据过来，没做用这些数据来更新网络); (3) Batch GD可以最终收敛到一个比较好的点(global or local minima, training loss比较小)，但这样可能就会产生过拟合的问题 (在训练集上performance很好，但是泛化性能不一定强)
Optimization之GD，Newton Method

梯度就是：

对f计算其梯度和Hessian Matrix，注意这里用到了梯度求导：【17】
Optimization之GD，Newton Method

刚才说到gradient descent的learning rate不好把握，所以采用牛顿法就可以不用设置learning rate。

Newton’s Method

采用二阶泰勒展开式，可以得到：
Optimization之GD，Newton Method

矩阵表示为：
Optimization之GD，Newton Method

对上面的fquad进行求导，可以得到：
Optimization之GD，Newton Method

由此可以得到下面的式子就是比较准确的梯度更新：
Optimization之GD，Newton Method

这个时候，把刚才计算的Hessian Matrix和gradient带入：
Optimization之GD，Newton Method

假设变量为n维，那么Hessian就是nxn的矩阵，那么如果n有billion个参数，那么Hessian就是billion的平方，这显然太大了。

Optimization之GD，Newton Method

而且牛顿迭代法牛顿法的好处是对强二次型的函数效果收敛速度非常快，但是对非二次型的函数很有可能导致迭代过程中函数上升。【18】

所以采用一个向量d来计算更新的权值：
Optimization之GD，Newton Method

实际计算是：所以只需要保存d来进行权值更新了，大大节约了内存。另外，需要注意的是使用牛顿法是需要一次就可以进行权值更新到global或者是local minimum，但是如果是使用d来更新，那么d也只是确定了梯度下降的方向，所以还需要乘以step size（learning rate）
Optimization之GD，Newton Method

Optimization之GD，Newton Method

对于gradient descent还需要进行一些说明就是关于stochastic gradient，mini-batch。SGD：(1) 对内存要求低 (每次只需要load 1个sample)；(2) 支持online weight update；(3) 对learning rate很敏感，网络参数更新频繁，目标函数值容易出现抖动，容易收敛到一个比较差的点。mini-batch就是计算n个sample的平均loss，这个n一般为100左右。SGD容易陷入很浅的local minimum，因为有一定的noise。所以在针对非凸优化的目标，SGD很流行。另外，对于mini-batch的n，如果n为1，那么就是stochastic，如果n=N，那么就是BGD。

SGD的分布式训练：downpour。就是同时计算n个网络的梯度，但是他们的权值初始值都是一样的，计算完一轮后可以共享数据计算平均梯度得到新的权值，然后继续计算。
Optimization之GD，Newton Method