这是李宏毅老师2018年春季深度学习课程的第二章，主要讲了神经网络的损失函数是非凸的，但是我们仍然有办法去达到local minima，但是如何达到global minima，还有待探索。
优化(Optimization)：是否可能在网络可以表示的函数空间中找到使训练误差的函数。在深度学习中，损失函数是一个非凸函数，非凸函数的优化问题是一个NP难问题。
神经网络的损失函数是非凸的
结合下图，考虑一个只有一层隐藏层的全连接的网络，如果通过优化得到的参数能够使损失函数降到一个最小值，现在将隐藏层的神经元进行错位排列，并将对应的参数错位置换，可以想象得出这个网络所能表示的函数空间并没有发生变化（因为结构没变），而且相关参数随着神经元的错排进行了错位置换后，对应的损失函数的值也没有变。但是在以参数为应变量，损失函数为自变量的空间中，可以发现：将参数进行错位后，它对应的最小值的位置与原位置是不一样的，考虑有n个参数，则可以发现有很多个点都可以达到这个最小值，所以深度学习的损失函数是非凸的。
Hessian Matrix
critical point
critical(待鉴定的，临界的) point(接下来称为cp)，cp的梯度是为0，对于非凸函数，梯度为0不代表处于极值，还有可能是鞍点(saddle point)，即该点的梯度为0，但是在某些方向有上升的趋势，在某些方向有下降的趋势(想象一下马鞍的中心)，而不是像极值点一样，周围的变化趋势的是一致的，所以在深度学习中，对于cp，要借助Hessian Matrix进行判断。
Hessian
在之前的一篇博客中，描述了梯度下降的数学原理，即通过一阶泰勒展开来寻求梯度为0的点，因为之前是针对梯度为0则一定处于极值的凸函数进行优化，所以一阶展开就行了。但是对于非凸函数，一阶泰勒展开近似时梯度为0并不能代表该点是极值，所以要进一步近似，寻求更微小的变化趋势，能够表示的就是Hessian矩阵。
上式的g是梯度，是一个向量：$g_i = \frac{\delta f(\theta^0)}{\delta \theta_i}$
H就是Hessian矩阵而且是对称的:$H_{ij} = \frac{\delta^2}{\delta\theta_i\delta\theta_jf(\theta^0)}=H_{ji}$
而当梯度g为0时，有$f(\theta) = f(\theta^0)+\frac{1}{2}(\theta-\theta^0)^TH(\theta-\theta^0)+…$的近似，所以就要考虑Hessian矩阵是如何影响这个近似的。
通过牛顿法求二阶展开的critical point
对二阶近似两边进行微分取0，可以得到(没有验证)：
所以参数的更新就如下图，比梯度下降看起来步骤会更少，但是在高维空间中计算$H^{-1}$的代价会非常大，而且仍然不能避免让结果靠近鞍点。
分析Hessian
梯度g为0时，处于critical potint，有：
将$\theta-\theta_0$看作一个向量x，如果矩阵H是正定的，那么$x^THx > 0$，即H的所有特征值都是正的，那么在$\theta_0$附近的函数值都大于$f(\theta_0)$，所以这个点是local minima。
如果是负定的，那么$x^THx < 0$，同理，这个点是local maxima，H的特征值都是负的。
如果$x^THx$有些大于0，有些小于0，即特征值有正有负，那么这个点是鞍点。
但是如果H矩阵半正定或者半负定，即特征值有0的存在，那么就无法判断这个点的具体情况了，因为可能会被未考虑的近似所影响。
证明
设$v$为一个单元特征向量，由于$v^THv=v^T(\lambda v)=\lambda||v||^2=\lambda$，根据线代知识，H是一个对称方阵，它的所有特征向量都是正交的，而且正好能够张成$\theta$所在的空间，即$\theta_0$的到$\theta$的变化方向可以被这些特征向量的线性组合所表示，那么就有$(\theta-\theta_0)=m_1v_1+m_2v_2+…+m_nv_n$，$v_1$到$v_n$是所有的特征向量，通过这样表示，代入二阶泰勒展开，可以发现$f(\theta)$与$f(\theta_0)$的关系，完全由特征值的值所决定。
Deep Linear NetWork
考虑如图最简单的Linear Network的Hessian矩阵，可以发现梯度为0时，即便在鞍点也可以通过计算Hessian来判断往哪一个方向走。
考虑如图有两个hidden layers的Linear Network，有三种情况可以造成critical point，第一种情况，$W_1W_2W_3=1$，观察损失函数可以判断这个点是global minima，对于第二种情况,Hessian 矩阵是个0阵，无法通过Hessian矩阵来判断。对于第三种情况，H的特征值有正有负，所以可以确定是鞍点。
对于更加复杂的网络，还可以通过从不同的两个维度取点来观察函数的变化图像，可以观察出来是不是鞍点。
一些关于Linear Network的minima的论文
一些结论：
隐藏层的大小大于输入和输出的维度时是global minima
超过两层隐藏层的网络可能会制造出没有负特征值的鞍点。
- Kenji Kawaguchi, Deep Learning without Poor Local Minima, NIPS, 2016
- Haihao Lu, Kenji Kawaguchi, Depth Creates No Bad Local Minima, arXiv,2017
- Thomas Laurent, James von Brecht, Deep linear neural networks with arbitrary loss: All local minima are global, arXiv, 2017
- Maher Nouiehed, Meisam Razaviyayn, Learning Deep Models: Critical Points and Local Openness, arXiv, 2018
Non-linear Deep NetWork
ReLU has local
ReLU的network是有盲点的，由于ReLU的特性，会出现输入数据x后所有输出都是0，那么这个点的梯度就是0，因为在数据点x附近都是非常平坦的，所以对于这个critical point，只要存在另外的输入使y为负数（这很好得到），所以这个点就不是global minima。
关于Non-linear Deep Network的假想：使用某些特殊的参数初始化，或者特殊的训练数据，可以找到global minima
关于deep learning的猜想
猜想一：
几乎所有的局部最小值和全局最小值都是差不多的。
如果Hessian矩阵的特征值是大于0还是小于0的概率各为1/2，那么随着参数的增多，如果遇到cp，是鞍点的概率会越来越大。而特征值符号的概率p其实是由损失函数决定的，如下图，鞍点容易出现在loss高的地方，而localminima会出现在loss比较低的地方，从而有local minima都是差不多的猜想。
猜想二：
如果Hessian的正特征值越多，就越像一个local minima,如下图。
猜想三：
如果网络够大，可以通过梯度下降找到一个全局最优解。
- Razvan Pascanu, Yann N. Dauphin, Surya Ganguli, Yoshua Bengio, On the saddle point problem for non-convex optimization, arXiv, 2014
- Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, Yoshua Bengio, “Identifying and attacking the saddle point problem in high-dimensional non-convex optimization”, NIPS, 2014
- Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, Yann LeCun, “The Loss Surfaces of Multilayer Networks”, PMLR, 2015
- Jeffrey Pennington, Yasaman Bahri, “Geometry of Neural Network Loss Surfaces via Random Matrix Theory”, PMLR, 2017
Benjamin D. Haeffele, Rene Vidal, ” Global Optimality in Neural Network Training”, CVPR, 2017
关于损失函数的可视化
观察参数是如何影响损失函数的
一个维度：选择初始化的点与训练结束的点相连，然后继续延长两倍，然后可视化这一段线段上loss在某一个方向上的变化。
两个维度：固定某一个参数方向的变化，另一个参数方向则是在不断的变化的。
可视化训练过程
在每次update参数的时候记录下所有的参数以及对应的loss，最后将参数通过PCA降维到二维，最后将对应的loss可视化到二维平面上，如下图，不同的模型可能会得到不同的Solution。
比较不同的优化算法
使用同样的数据源喂给不同算法得到的网络，比较他们的差异。为什么会有这种差异（在鞍点时可能选择了不同的路线）
作业
做了前两个作业，收获最大的就是理解了tensorflow的优化器是分为两个步骤的，第一个步骤是compute_gradients，即计算梯度，第二个步骤是apply_gradients，即使用计算得到的梯度和上一次的参数去更新此次参数。具体代码放在了github上
Visualize the Optimization Process
即上面的可视化训练过程，记录每次的参数和损失函数，然后使用PCA降维参数，将权重展示到平面上，我使用神经网络模拟同一个函数训练了六次，六次的变化如下，和老师的看起来差不多吧(迫真)：
Observe Gradient Norm During Training
即记录每次训练的Gradient Norm和loss，然后放到一起比较，是在MNist_data数据集上跑的，如图：
所以有Gradient Norm接近0时越有可能是Solutin
What Happened When Gradient is Almost Zero
即可视化梯度接近0时，Hessian矩阵中正值的比例与损失函数之间的关系，可以发现当征值比例很大时，loss都是很小的，不过我没找到怎么算Hessian，就没做这题。