「机器学习-李宏毅」：Gradient
总结「李宏毅老师-机器学习」的Gradient，主要从以下三个方面展开：调节learning rate；加快训练速度；对数据进行Feature Scaling。
Tip 1: Tuning your learning rates carefully
Visualize 损失函数随着参数变化的函数图
左图是Loss Function的函数图，红色是最好的Step，当Step过小（蓝色），会花费很多时间，当Step过大（绿色、黄色），会发现Loss越来越大，找不到最低点。
所以在Training中，尽可能的visualize loss值的变化。
但是当参数大于等于三个时， $loss function$的函数图就不能visualize了。
因此，在右图中，visualize Loss随着参数更新的变化，横轴即迭代次数，当图像呈现蓝色（small）时，就可以把learning rate 调大一些。
Adaptive Learning Rates(Adagrad)
但是手动调节 $\eta$是低效的，我们更希望能自动地调节。
直观上的原则是：
- $\eta$ 的大小应该随着迭代次数的增加而变小。
- 最开始，初始点离minima很远，那step应该大一些，所以learning rate也应该大一些。
- 随着迭代次数的增加，离minima越来越近，就应该减小 learning rate。
- E.g. 1/t decay： $\eta^t=\eta/ \sqrt{t+1}$
- 不同参数的 $\eta$应该不同（cannot be one-size-fits-all)。
Adagrad
Adagrad 的主要思想是：Divide the learning rate of each parameter by the root mean squear of its previous derivatives.(通过除这个参数的 计算出的所有导数 的均方根)
root mean squar : $ \sqrt{\frac{1}{n}(x_1^2+x_2^2+...+x_n^2)} $
Vanilla Gradient descent
$w^{t+1} \leftarrow w^{t}-\eta^{t} g^{t}$
Adagrad
$w^{t+1} \leftarrow w^{t}-\frac{\eta^{t}}{\sigma^{t}} g^{t} $$\eta^t$：第t次迭代的leaning rate
$ \eta^{t}=\frac{\eta}{\sqrt{t+1}}$ $g^{t}=\frac{\partial L\left(\theta^{t}\right)}{\partial w} $$\sigma^t$：root mean squar of previous derivatives of w
$\tau^{t}=\sqrt{\frac{1}{t+1} \sum_{i=0}^{t}\left(g^{i}\right)^{2}} $
对比上面两种Adaptive Gradient，Adagrade的优势是learning rate 是和parameter dependent（参数相关的）。
Adagrad步骤简化
步骤：
简化公式：
$ w^{t+1} \leftarrow w^{t}-\frac{\eta}{\sqrt{\sum_{i=0}^{t}\left(g^{i}\right)^{2}}} g^{t}$( $ \eta^{t}=\frac{\eta}{\sqrt{t+1}} $ , $ \sigma^{t}=\sqrt{\frac{1}{t+1} \sum_{i=0}^{t}\left(g^{i}\right)^{2}}$ ,约掉共同项即可)
Adagrad Contradiction? ——Adagrad原理解释
Vanilla Gradient descent
$w^{t+1} \leftarrow w^{t}-\eta^{t} g^{t}$
Adagrad
$ w^{t+1} \leftarrow w^{t}-\frac{\eta}{\sqrt{\sum_{i=0}^{t}\left(g^{i}\right)^{2}}} g^{t}$在Vanilla Gradient descent中， $g^t$越大，也就是当前梯度大，也就有更大的step。
而在Adagrad中，当 $g^t$越大，有更大的step,而当 $\sqrt{\sum_{i=0}^t (g^i)^2} $ 越大，反而有更小step。
Contradiction？
「Intuitive Reason（直观上解释）」
$ w^{t+1} \leftarrow w^{t}-\frac{\eta}{\sqrt{\sum_{i=0}^{t}\left(g^{i}\right)^{2}}} g^{t}$ $\sqrt{\sum_{i=0}^t (g^i)^2} $ 是为了造成反差的效果。
类比一下，如果一个一直很凶的人，突然温柔了一些，你会觉得他特别温柔。所以同样是 $0.1$,第一行中，你会觉得特别大，第二行中，你会觉得特别小。
因此 $\sqrt{\sum_{i=0}^t (g^i)^2} $ 这一项的存在就能体现 $g^t$的变化有多surprise。
「数学一些的解释」
1. Larger Gradient,larger steps?
在前面我们都深信不疑这一点，但这样的描述真的是正确的吗？
在这张图中，只有一个参数，认为当该点的导数越大，离minima越远，这样看来，Larger Gradient,larger steps是正确的。
在上图中的 $x_0$点，该点迭代更新的best step 应该正比于 $|x_0+\frac{b}{2a}|$ ，即 $\frac{|2,a, x_0+b|}{2a}$。
而 $\frac{|2,a, x_0+b|}{2a}$的分子也就是该点的一阶导数的绝对值。
上图中，有 $w_1,w_2$两个参数。
横着用蓝色的线切一刀，得到的是 $w_2$ 固定，loss随着 $w_1$变化的图像：比较a、b两点，a点导数大，离minima远。
竖着用绿色的线切一刀，得到的是 $w_2$ 固定，loss随着 $w_1$变化的图像：比较c、d两点，c点导数大，离minima远。
但是，如果比较a、c两点呢？
a点对 $w_1$ 的偏导数和c点对 $w_2$的偏导数比较？
比较出来，c点点偏导数更大，离minima更远吗？
再看左图的图像，横着的弧度更平滑，竖着的弧度更尖一些，直观上看应该c点离minima更近一些。
所以Larger Gradient,larger steps点比较方法不能（cross parameters)跨参数比较。
所以最好的step $\propto$ 一阶导数（Do not cross parameters)。
2.** Second Derivative**
前面讨论best step $\frac{|2,a, x_0+b|}{2a}$的分子是该点一阶导数，那么其分母呢？
当对一阶导数再求导时，可以发现其二阶导数就是best step的分母。
得出结论：the best step $\propto$ |First dertivative| / Second derivative。
因此，再来看两个参数的情况，比较a点和c点，a点的一阶导数更小，二阶导数也更小；c点点一阶导数更大，二阶导数也更大。
所以如果要比较a、c两点，谁离minima更远，应该比较其一阶导数的绝对值除以其二阶导数的大小。
回到 $ w^{t+1} \leftarrow w^{t}-\frac{\eta}{\sqrt{\sum_{i=0}^{t}\left(g^{i}\right)^{2}}} g^{t}$
上一部分得出的结论是：the best step $\propto$ |First dertivative| / Second derivative。
所以我们的learning rate 也应该和 |First dertivative| / Second derivative相关。
$g^t$也就是一阶导数，但为什么 $\sqrt{\sum_{i=0}^t (g^i)^2} $ 能代表二阶导数呢？
上图中，蓝色的函数图有更小的二阶导数，绿色的函数图有更大的二阶导数。
在复杂函数中，求二阶导数是一个很复杂的计算。
所以我们想用一阶导数来反映二阶导数的大小。
在一阶导数的函数图中，认为一阶导数值更小的，二阶导数也更小，但是取一个点显然是片面的，所以考虑取多个点。
也就是用 $ \sqrt{\text{(first derivative)}^2}$ 来代表best step中的二阶导数。
总结一下
Adagrad的为了找寻最好的learning rate，从找寻best step下手，用简单的二次函数为例，得出 best step $\propto$ |First dertivative| / Second derivative。
但是复杂函数的二阶导数是难计算的，因此考虑用多个点的一阶导数来反映其二阶导数。
得出 $ w^{t+1} \leftarrow w^{t}-\frac{\eta}{\sqrt{\sum_{i=0}^{t}\left(g^{i}\right)^{2}}} g^{t}$ 。
直观来解释公式中的一阶导数的root mean square，即来为该次迭代的一阶导数造成反差效果。
其他文献中的Adaptive Gradient理应都是为了调节learning rate使之有best step。(待补充的其他Gradient)[1]
Tip 2:Stochastic Gradient Descent
Stochastic Gradient Descent
在linear model中，我们这样计算Loss function： $L=\sum_{n}\left(\hat{y}^{n}-\left(b+\sum w_{i} x_{i}^{n}\right)\right)^{2} $
每求一次Loss function，L都对所有training examples的 $\text{error}^2$求和，因此每一次的loss function的计算，都是一重循环。
在Stochastic Gradient Descent中，每一次求loss function，只取一个example $x^n$，减少一重循环，无疑更快。
Stochastic Gradient Descent
Pick an example $x^n$
$L=\left(\hat{y}^{n}-\left(b+\sum w_{i} x_{i}^{n}\right)\right)^{2} $
上图中，传统的Gradient Descent看完一次所有的examples，离minima还很远；而Stochastic Gradient Descent ，看完一次，已经离minima较近了。
Tip 3:Feature Scaling
What is Feature Scaling
如上图所示，希望能让不同的feature能有相同的scale（定义域/规模）
Why Feature Scaling
假设model都是 $y = b+ w_1 x_1 +w_2 x_2$。
上图中，左边 $x_2$的规模更大，可以认为 $x_1$ 对loss 的影响更小， $ x_2$对loss的影响更大。
即当 $w_1,w_2$轻微扰动时，同时加上相同的 $\Delta w$时，$x_2$ 使 $y$的取值更大，那么对loss 的影响也更大。
如图中下方的函数图 $w_1$方向的L更平滑， $w_2$ 方向更陡峭些，Gradient descent的步骤如图所示。
但当对 $x_2$进行feature scaling后，图像会更像正圆，Gradient descent使，参数更新向着圆心走，更新会更有效率。
How Feature Scaling
概率论知识：标准化。
概率论：
随机变量 $X$ 的期望和方差均存在，且 $ D(X)>0$,令 $X^*=\frac{X-E(X)}{\sqrt{D(X)}} $ ，那么 $E(X^)=0,D(X)=1$, $X^$称为X的标准化随机变量。
对所有向量的每一维度，进行标准化处理： $x_{i}^{r} \leftarrow \frac{x_{i}^{r}-m_{i}}{\sigma_{i}} $
（ $m_i$是该维度变量的均值， $\sigma_i$ 是该维度变量的方差）
标准化后，每一个feature的期望都是0，方差都是1。
Gradient Descent Theory(公式推导)
当用Gradient Descent解决 $\theta^*=\arg \min_\theta L(\theta)$时，我们希望每次更新 $\theta $ 都能得到 $L(\theta^0)>L(\theta^1)>L(\theta^2)>…$ 这样的理论结果，但是不总能得到这样的结果。
上图中，我们虽然不能一下知道minima的方向，但是我们希望：当给一个点 $\theta^0$ 时，我们能很容易的知道他附近（极小的附近）的最小的loss 是哪个方向。
所以怎么做呢？
Tylor Series
微积分知识：Taylor Series（泰勒公式）。
Tylor Series:
函数 $h(x)$ 在 $x_0$ 无限可导，那么
当 x 无限接近 $x_0$ 时，忽略后面无穷小的高次项， $h(x) \approx h\left(x_{0}\right)+h^{\prime}\left(x_{0}\right)\left(x-x_{0}\right) $
上图中，用 $\pi/4$ 处的一阶泰勒展示来表达 $\sin(x)$ ,图像是直线，和 $\sin(x)$ 图像相差很大，但当 x无限接近 $\pi/4$ 是，函数值估算很好。
Multivariable Taylor Series
$h(x, y)=h\left(x_{0}, y_{0}\right)+\frac{\partial h\left(x_{0}, y_{0}\right)}{\partial x}\left(x-x_{0}\right)+\frac{\partial h\left(x_{0}, y_{0}\right)}{\partial y}\left(y-y_{0}\right) +\text{something raleted to} (x-x_x^0)^2 \text{and} (y-y_0)^2+…$当 $(x,y)$ 接近 $(x_0,y_0)$ 时， $h(x,y)$ 用 $(x_0,y_0)$ 处的一阶泰勒展开式估计。
$ h(x, y) \approx h\left(x_{0}, y_{0}\right)+\frac{\partial h\left(x_{0}, y_{0}\right)}{\partial x}\left(x-x_{0}\right)+\frac{\partial h\left(x_{0}, y_{0}\right)}{\partial y}\left(y-y_{0}\right)$Back to Formal Derivation
当图中的红色圆圈足够小时，红色圆圈中的loss 值就可以用 $(a,b)$ 处的一阶泰勒展开式来表示。
$ \mathrm{L}(\theta) \approx \mathrm{L}(a, b)+\frac{\partial \mathrm{L}(a, b)}{\partial \theta_{1}}\left(\theta_{1}-a\right)+\frac{\partial \mathrm{L}(a, b)}{\partial \theta_{2}}\left(\theta_{2}-b\right) $$(\theta_1-a)^2+(\theta_2-b)^2 \leq d^2$ ,d 足够小。
用 $s=L(a,b)$ , $ u=\frac{\partial \mathrm{L}(a, b)}{\partial \theta_{1}}, v=\frac{\partial \mathrm{L}(a, b)}{\partial \theta_{2}} $ 表示。
最后问题变成：
$L(\theta)\approx s+u(\theta_1-a)+v(\theta_2-b)$找 $(\theta_1,\theta_2)$，且满足 $(\theta_1-a)^2+(\theta_2-b)^2 \leq d^2$，使 $L(\theta)$ 最小。
变成了一个简单的最优化问题。
令 $\Delta \theta_1=\theta_1-a$ , $\Delta\theta_2=\theta_2-b$
问题简化为：
$\text{min}:u \Delta \theta_1+v\Delta\theta_2$
$\text{subject to}:{\Delta\theta_1}^2+{\Delta\theta_2}^2\leq d^2$
画出图，就是初中数学了。更新的方向应该是 $(u,v)$ 向量反向的方向。
所以：
$\left[\begin{array}{l} \Delta \theta_{1} \\ \Delta \theta_{2} \end{array}\right]=-\eta\left[\begin{array}{l} u \\ v \end{array}\right] $ $\left[\begin{array}{l} \theta_{1} \\ \theta_{2} \end{array}\right]=\left[\begin{array}{l} a \\ b \end{array}\right]-\eta\left[\begin{array}{l} u \\ v \end{array}\right] $ $ \left[\begin{array}{l} \theta_{1} \\ \theta_{2} \end{array}\right]=\left[\begin{array}{l} a \\ b \end{array}\right]-\eta\left[\begin{array}{l} u \\ v \end{array}\right]=\left[\begin{array}{l} a \\ b \end{array}\right]-\eta\left[\begin{array}{l} \frac{\partial \mathrm{L}(a, b)}{\partial \theta_{1}} \\ \frac{\partial \mathrm{L}(a, b)}{\partial \theta_{2}} \end{array}\right] $Limitation of Gradient Descent
- Gradient Descent 可能会卡在local minima或者saddle point（鞍点：一个方向是极大值，一个方向是极小值，导数为0）
- 实践中，我们往往会在导数无穷接近0的时候停下来（< 1e-7)，Gradient Descent 可能会停在plateau(高原；增长后的稳定)
Reference
[1] 待补充的其他Gradient
「机器学习-李宏毅」：Gradient
