Basic Understanding of Optimization

course link: https://speech.ee.ntu.edu.tw/~hylee/mlds/2018-spring.html

THEORY 2: OPTIMIZATION

0. 引言

一句话概述Optimization: 基于凸优化方法，找到$L(\theta)$最小的值对应的参数.

注意: Optimization≠Learning

1. Hessian Matrix: When gradient is 0

当gradient=0的时候，通常包含两种情况：

• local minima
• saddle point

但是如何判断当前的位置是local minina还是saddle point?

Hessian Matrix.

当gradient=0时，假设存在下图所示中的式子: $f(\theta)$,其中, gradient是梯度, $Hessian H$是一个矩阵, $H$是一个对称矩阵.

其中, $H$参数用于决定曲率(curvature)，$H$不存在则$f(\theta)$是一条直线.

$g$和$H$的作用就是把图中绿色的直线转换为红色的曲线来实现更好的拟合.

通过牛顿法可以找到使得$\delta f(\theta)=0$的$g$和$H$.

通过计算可以得到:

每次计算之后找到曲线所在的最低点的$x$值进行更新.

然而, 如果gradient的重合度重合在起始位置, 就会出现上图中左半部分曲线的情况, loss反而会增加.

当g=0且到达critical point的时，会出现 local min, local max 以及 saddle point 三种情况. 因此, 需要分析$H$来判断当前的critical point属于哪种情况.

---

Review 1: Linear Algebra

$Av=\lambda v$

• $v$是$A$的特征向量
• $\lambda$是$A$上对应于$v$的特征向量

Review 2: Postive/Negative Definite

Review End Back to Hessian

---

通过宏毅老师给的Review 2的例子可以知道$Hessian\, H$可以取出不同的值, 取出不同的值则对应三个不同的状态.

e.g. 1

e.g. 2

鞍点判断参考: https://zhuanlan.zhihu.com/p/33340316

正定矩阵和半正定矩阵参考: https://zhuanlan.zhihu.com/p/44860862

2. Deep Linear Network

当hidden layers超过两层时就会产生不包含负特征值的鞍点.

经过证明，在Deep Linear Network中，local minima也就是global minima.

注: 带有证明过程的references可参考原PPT.

3. Does Deep Network have Local Minima

然鹅, ReLU会存在local minima的情况.

这就造成了盲点，导致gradient变为0.

e.g. 在MNIST数据集上使用Adam进行优化，图中上半部分使用一般的初始化进行训练，下半部分使用混乱的方法(标签打乱,例如手写数字为5，标签为2)进行训练，但是，在这种情况下，如果neuron数量比较少，则model不能训练出来.

然而, 在训练过程中进入盲点则acc保持为0. 因此, 数据的初始化结果会影响训练情况.

除了initialization，数据本身的情况也会影响训练的结果. 要找到global minima，使用正态分布选出n个$x$的数据，让其去与k个$y$进行匹配, 只要满足$w^i=v^i$且$n≥k$就能找到global minima.

如下所示，当network参数增多的时候，local minima出现的概率就减少，找到的就是global minima.

4. Conjecture about Deep Learning

分析$Hessian \, Matrix\, H$,在遇到critical point的时候，这个点可能是local minima ，也可能是saddle point. 其中$\lambda$参数可能为+，也可能为-，因此，$\lambda v$的值有1/2的几率为+，也有1/2的几率为-.

当不断增加neuron的个数时，local minima, local maxima 以及 saddle point 的可能性都在不断变化, 如下图所示.

当neuron足够大的时候，几乎每个critical point都是saddle point.