「机器学习-李宏毅」:Gradient

「机器学习-李宏毅」:Gradient

总结「李宏毅老师-机器学习」的Gradient,主要从以下三个方面展开:调节learning rate;加快训练速度;对数据进行Feature Scaling。

Tip 1: Tuning your learning rates carefully

Visualize 损失函数随着参数变化的函数图

3gbjfJ.md.png

左图是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步骤简化

步骤:

3gbXY4.md.png

简化公式:

$ 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} $ 是为了造成反差的效果。 3gbqTU.md.png

类比一下,如果一个一直很凶的人,突然温柔了一些,你会觉得他特别温柔。所以同样是 $0.1$,第一行中,你会觉得特别大,第二行中,你会觉得特别小。

因此 $\sqrt{\sum_{i=0}^t (g^i)^2} $ 这一项的存在就能体现 $g^t$的变化有多surprise。

「数学一些的解释」

1. Larger Gradient,larger steps?

在前面我们都深信不疑这一点,但这样的描述真的是正确的吗?

3gbbwT.md.png

在这张图中,只有一个参数,认为当该点的导数越大,离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}$的分子也就是该点的一阶导数的绝对值。

3gbcef.png

上图中,有 $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**
3gbHmV.md.png

前面讨论best step $\frac{|2,a, x_0+b|}{2a}$的分子是该点一阶导数,那么其分母呢?

当对一阶导数再求导时,可以发现其二阶导数就是best step的分母。

得出结论:the best step $\propto$ |First dertivative| / Second derivative。

3gbTO0.md.png

因此,再来看两个参数的情况,比较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} $ 能代表二阶导数呢?

3gbIln.md.png

上图中,蓝色的函数图有更小的二阶导数,绿色的函数图有更大的二阶导数。

在复杂函数中,求二阶导数是一个很复杂的计算。

所以我们想用一阶导数来反映二阶导数的大小

在一阶导数的函数图中,认为一阶导数值更小的,二阶导数也更小,但是取一个点显然是片面的,所以考虑取多个点。

也就是用 $ \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} $ 3gbhWj.md.png

上图中,传统的Gradient Descent看完一次所有的examples,离minima还很远;而Stochastic Gradient Descent ,看完一次,已经离minima较近了。

Tip 3:Feature Scaling

What is Feature Scaling

3gbfYQ.md.png

如上图所示,希望能让不同的feature能有相同的scale(定义域/规模)

Why Feature Scaling

假设model都是 $y = b+ w_1 x_1 +w_2 x_2$。

3gb2TS.md.png

上图中,左边 $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的标准化随机变量。

3gbgw8.md.png

对所有向量的每一维度,进行标准化处理: $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)>…$ 这样的理论结果,但是不总能得到这样的结果。

3gb0Wd.md.png

上图中,我们虽然不能一下知道minima的方向,但是我们希望:当给一个点 $\theta^0$ 时,我们能很容易的知道他附近(极小的附近)的最小的loss 是哪个方向。

所以怎么做呢?

Tylor Series

微积分知识:Taylor Series(泰勒公式)。

Tylor Series:
函数 $h(x)$ 在 $x_0$ 无限可导,那么

$\begin{aligned} \mathrm{h}(\mathrm{x}) &=\sum_{k=0}^{\infty} \frac{\mathrm{h}^{(k)}\left(x_{0}\right)}{k !}\left(x-x_{0}\right)^{k} \\ &=h\left(x_{0}\right)+h^{\prime}\left(x_{0}\right)\left(x-x_{0}\right)+\frac{h^{\prime \prime}\left(x_{0}\right)}{2 !}\left(x-x_{0}\right)^{2}+\ldots \end{aligned}$

当 x 无限接近 $x_0$ 时,忽略后面无穷小的高次项, $h(x) \approx h\left(x_{0}\right)+h^{\prime}\left(x_{0}\right)\left(x-x_{0}\right) $

3gbrQI.md.png

上图中,用 $\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

3gLTaT.png

当图中的红色圆圈足够小时,红色圆圈中的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$

3gbwJH.png

画出图,就是初中数学了。更新的方向应该是 $(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

3gbsyt.md.png
  1. Gradient Descent 可能会卡在local minima或者saddle point(鞍点:一个方向是极大值,一个方向是极小值,导数为0)
  2. 实践中,我们往往会在导数无穷接近0的时候停下来(< 1e-7),Gradient Descent 可能会停在plateau(高原;增长后的稳定)

Reference

[1] 待补充的其他Gradient


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×