当前位置:   article > 正文

【机器学习面试题】——梯度下降_梯度下降面试题

梯度下降面试题

1. 机器学习中为什么需要梯度下降

梯度下降的作用:

  • 梯度下降是迭代法的一种,可以用于求解最小二乘问题
  • 在求解损失函数的最小值时,可以通过梯度下降法来一步步的迭代求解,得到最小化的损失函数和模型参数值。
  • 如果我们需要求解损失函数的最大值,可通过梯度上升法来迭代。梯度下降法和梯度上升法可相互转换

2. 梯度下降法缺点

缺点

  • 靠近极小值时收敛速度减慢。
  • 直线搜索时可能会产生一些问题。
  • 可能会“之字形”地下降。

注意

  • 梯度是一个向量,即有方向有大小
  • 梯度的方向是最大方向导数的方向
  • 梯度的值是最大方向导数的值

3. 梯度下降法直观理解

在这里插入图片描述

​ 形象化举例,由上图所示,假如最开始,我们在一座大山上的某处位置,因为到处都是陌生的,不知道下山的路,所以只能摸索着根据直觉,走一步算一步,在此过程中,每走到一个位置的时候,都会求解当前位置的梯度,沿着梯度的负方向,也就是当前最陡峭的位置向下走一步,然后继续求解当前位置梯度,向这一步所在位置沿着最陡峭最易下山的位置走一步。不断循环求梯度,就这样一步步地走下去,一直走到我们觉得已经到了山脚。当然这样走下去,有可能我们不能走到山脚,而是到了某一个局部的山势低处。
​ 由此,从上面的解释可以看出,梯度下降不一定能够找到全局的最优解,有可能是一个局部的最优解。当然,如果损失函数是凸函数,梯度下降法得到的解就一定是全局最优解。

4. 梯度下降核心思想归纳

  • 确定优化模型的假设函数及损失函数。
  • 初始化参数,随机选取取值范围内的任意数;
  • 迭代操作:
    • 计算当前梯度
    • 修改新的变量
    • 计算朝最陡的下坡方向走一步
    • 判断是否需要终止,如否,梯度更新
  • 得到全局最优解或者接近全局最优解。

5. 如何对梯度下降法进行调优

实际使用梯度下降法时,各项参数指标不能一步就达到理想状态,对梯度下降法调优主要体现在以下几个方面:

(1)算法迭代步长 α \alpha α选择。
在算法参数初始化时,有时根据经验将步长初始化为1。实际取值取决于数据样本。可以从大到小,多取一些值,分别运行算法看迭代效果,如果损失函数在变小,则取值有效。如果取值无效,说明要增大步长。但步长太大,有时会导致迭代速度过快,错过最优解。步长太小,迭代速度慢,算法运行时间长。

(2)参数的初始值选择。
初始值不同,获得的最小值也有可能不同,梯度下降有可能得到的是局部最小值。如果损失函数是凸函数,则一定是最优解。由于有局部最优解的风险,需要多次用不同初始值运行算法,关键损失函数的最小值,选择损失函数最小化的初值。

(3)标准化处理。
由于样本不同,特征取值范围也不同,导致迭代速度慢。为了减少特征取值的影响,可对特征数据标准化,使新期望为0,新方差为1,可节省算法运行时间。

6. 随机梯度和批量梯度区别

​ 随机梯度下降(SDG)和批量梯度下降(BDG)是两种主要梯度下降法,其目的是增加某些限制来加速运算求解。
下面通过介绍两种梯度下降法的求解思路,对其进行比较。
假设函数为:
h θ ( x 0 , x 1 , . . . , x 3 ) = θ 0 x 0 + θ 1 x 1 + . . . + θ n x n h_\theta (x_0,x_1,...,x_3) = \theta_0 x_0 + \theta_1 x_1 + ... + \theta_n x_n hθ(x0,x1,...,x3)=θ0x0+θ1x1+...+θnxn
损失函数为:
J ( θ 0 , θ 1 , . . . , θ n ) = 1 2 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) 2 J(\theta_0, \theta_1, ... , \theta_n) = \frac{1}{2m} \sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)^2 J(θ0,θ1,...,θn)=2m1j=0m(hθ(x0j,x1j,...,xnj)yj)2
其中, m m m为样本个数, j j j为参数个数。

1、 批量梯度下降的求解思路如下:
a) 得到每个 θ \theta θ对应的梯度:
∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) = 1 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n)=\frac{1}{m}\sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)x^{j}_i θiJ(θ0,θ1,...,θn)=m1j=0m(hθ(x0j,x1j,...,xnj)yj)xij
b) 由于是求最小化风险函数,所以按每个参数 θ \theta θ 的梯度负方向更新 $ \theta_i $ :
θ i = θ i − 1 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \theta_i=\theta_i - \frac{1}{m} \sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)x^{j}_i θi=θim1j=0m(hθ(x0j,x1j,...,xnj)yj)xij
c) 从上式可以注意到,它得到的虽然是一个全局最优解,但每迭代一步,都要用到训练集所有的数据,如果样本数据很大,这种方法迭代速度就很慢。
相比而言,随机梯度下降可避免这种问题。

2、随机梯度下降的求解思路如下:
a) 相比批量梯度下降对应所有的训练样本,随机梯度下降法中损失函数对应的是训练集中每个样本的粒度。
损失函数可以写成如下这种形式,
J ( θ 0 , θ 1 , . . . , θ n ) = 1 m ∑ j = 0 m ( y j − h θ ( x 0 j , x 1 j , . . . , x n j ) ) 2 = 1 m ∑ j = 0 m c o s t ( θ , ( x j , y j ) ) J(\theta_0, \theta_1, ... , \theta_n) = \frac{1}{m} \sum^{m}_{j=0}(y^j - h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n))^2 = \frac{1}{m} \sum^{m}_{j=0} cost(\theta,(x^j,y^j)) J(θ0,θ1,...,θn)=m1j=0m(yjhθ(x0j,x1j,...,xnj))2=m1j=0mcost(θ,(xj,yj))
b)对每个参数 $ \theta$ 按梯度方向更新 $ \theta$:
θ i = θ i + ( y j − h θ ( x 0 j , x 1 j , . . . , x n j ) ) \theta_i = \theta_i + (y^j - h_\theta (x^{j}_0, x^{j}_1, ... ,x^{j}_n)) θi=θi+(yjhθ(x0j,x1j,...,xnj))
c) 随机梯度下降是通过每个样本来迭代更新一次。
随机梯度下降伴随的一个问题是噪音较批量梯度下降要多,使得随机梯度下降并不是每次迭代都向着整体最优化方向。

小结:
随机梯度下降法、批量梯度下降法相对来说都比较极端,简单对比如下:

方法特点
批量梯度下降a)采用所有数据来梯度下降。
b)批量梯度下降法在样本量很大的时候,训练速度慢。
随机梯度下降a)随机梯度下降用一个样本来梯度下降。
b)训练速度很快。
c)随机梯度下降法仅仅用一个样本决定梯度方向,导致解有可能不是全局最优。
d)收敛速度来说,随机梯度下降法一次迭代一个样本,导致迭代方向变化很大,不能很快的收敛到局部最优解。

下面介绍能结合两种方法优点的小批量梯度下降法。

3、 小批量(Mini-Batch)梯度下降的求解思路如下
对于总数为 m m m个样本的数据,根据样本的数据,选取其中的 n ( 1 < n < m ) n(1< n< m) n(1<n<m)个子样本来迭代。其参数 θ \theta θ按梯度方向更新 θ i \theta_i θi公式如下:
θ i = θ i − α ∑ j = t t + n − 1 ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \theta_i = \theta_i - \alpha \sum^{t+n-1}_{j=t} ( h_\theta (x^{j}_{0}, x^{j}_{1}, ... , x^{j}_{n} ) - y^j ) x^{j}_{i} θi=θiαj=tt+n1(hθ(x0j,x1j,...,xnj)yj)xij

7. 各种梯度下降法性能比较

​ 下表简单对比随机梯度下降(SGD)、批量梯度下降(BGD)、小批量梯度下降(Mini-batch GD)、和Online GD的区别:

BGDSGDMini-batch GDOnline GD
训练集固定固定固定实时更新
单次迭代样本数整个训练集单个样本训练集的子集根据具体算法定
算法复杂度一般
时效性一般一般
收敛性稳定不稳定较稳定不稳定

​ Online GD于Mini-batch GD/SGD的区别在于,所有训练数据只用一次,然后丢弃。这样做的优点在于可预测最终模型的变化趋势。

​ Online GD在互联网领域用的较多,比如搜索广告的点击率(CTR)预估模型,网民的点击行为会随着时间改变。用普通的BGD算法(每天更新一次)一方面耗时较长(需要对所有历史数据重新训练);另一方面,无法及时反馈用户的点击行为迁移。而Online GD算法可以实时的依据网民的点击行为进行迁移。

8. 推导多元函数梯度下降法的迭代公式。

根据多元函数泰勒公式,如果忽略一次以上的项,函数在 x \mathbf{x} x点处可以展开为
f ( x + Δ x ) = f ( x ) + ( ∇ f ( x ) ) T Δ x + o ( ∥ Δ x ∥ ) f(\mathbf{x}+\Delta \mathbf{x})=f(\mathbf{x})+(\nabla f(\mathbf{x}))^{\mathrm{T}} \Delta \mathbf{x}+o(\|\mathbf{\Delta} \mathbf{x}\|) f(x+Δx)=f(x)+(f(x))TΔx+o(Δx)
对上式变形,函数的增量与自变量增量、函数梯度的关系为
f ( x + Δ x ) − f ( x ) = ( ∇ f ( x ) ) T Δ x + o ( ∥ Δ x ∥ ) f(\mathbf{x}+\Delta \mathbf{x})-f(\mathbf{x})=(\nabla f(\mathbf{x}))^{\mathrm{T}} \Delta \mathbf{x}+o(\|\Delta \mathbf{x}\|) f(x+Δx)f(x)=(f(x))TΔx+o(Δx)
如果令 Δ x = − ∇ f ( x ) \Delta \mathbf{x}=-\nabla f(\mathbf{x}) Δx=f(x)则有
f ( x + Δ x ) − f ( x ) ≈ − ( ∇ f ( x ) ) T ∇ f ( x ) ≤ 0 f(\mathbf{x}+\Delta \mathbf{x})-f(\mathbf{x}) \approx-(\nabla f(\mathbf{x}))^{\mathrm{T}} \nabla f(\mathbf{x}) \leq 0 f(x+Δx)f(x)(f(x))Tf(x)0
即函数值减小。即有
f ( x + Δ x ) ≤ f ( x ) f(\mathbf{x}+\Delta \mathbf{x}) \leq f(\mathbf{x}) f(x+Δx)f(x)
梯度下降法每次的迭代增量为
Δ x = − α ∇ f ( x ) \Delta \mathbf{x}=-\alpha \nabla f(\mathbf{x}) Δx=αf(x)
其中 α \alpha α为人工设定的接近于的正数,称为步长或学习率。其作用是保证 x + Δ x \mathbf{x}+\Delta \mathbf{x} x+Δx x \mathbf{x} x
邻域内,从而可以忽略泰勒公式中的 o ( ∥ Δ x ∥ ) o(\|\Delta \mathbf{x}\|) o(Δx)项。

使用该增量则有
( ∇ f ( x ) ) T Δ x = − α ( ∇ f ( x ) ) T ( ∇ f ( x ) ) ≤ 0 (\nabla f(\mathbf{x}))^{\mathrm{T}} \Delta \mathbf{x}=-\alpha(\nabla f(\mathbf{x}))^{\mathrm{T}}(\nabla f(\mathbf{x})) \leq 0 (f(x))TΔx=α(f(x))T(f(x))0
函数值下降。从初始点 x 0 \mathbf{x}_{0} x0开始,反复使用如下迭代公式
x k + 1 = x k − α ∇ f ( x k ) \mathbf{x}_{k+1}=\mathbf{x}_{k}-\alpha \nabla f\left(\mathbf{x}_{k}\right) xk+1=xkαf(xk)
只要没有到达梯度为0的点,函数值会沿序列 x k \mathbf{x}_{k} xk递减,最终收敛到梯度为0 的点。从 x 0 \mathbf{x}_{0} x0
出发,用迭代公式进行迭代,会形成一个函数值递减的序列 { x i } \left\{\mathbf{x}_{i}\right\} {xi}
f ( x 0 ) ≥ f ( x 1 ) ≥ f ( x 2 ) ≥ … ≥ f ( x k ) f\left(\mathbf{x}_{0}\right) \geq f\left(\mathbf{x}_{1}\right) \geq f\left(\mathbf{x}_{2}\right) \geq \ldots \geq f\left(\mathbf{x}_{k}\right) f(x0)f(x1)f(x2)f(xk)

9. 梯度下降法如何判断是否收敛?

迭代终止的条件是函数的梯度值为0(实际实现时是接近于0 即可),此时认为已经达到极值点。可以通过判定梯度的二范数是否充分接近于0 而实现。

10. 梯度下降法为什么要在迭代公式中使用步长系数?

其作用是保证 x + Δ x \mathbf{x}+\Delta \mathbf{x} x+Δx x \mathbf{x} x的邻域内,即控制增量的步长,从而可以忽略泰勒公式中的 o ( ∥ Δ x ∥ ) o(\|\Delta \mathbf{x}\|) o(Δx)项。否则不能保证每次迭代时函数值下降。

11. 梯度下降法和牛顿法能保证找到函数的极小值点吗,为什么?

不能,可能收敛到鞍点,不是极值点。

12. 解释一元函数极值判别法则。

假设 x 0 x_0 x0为函数的驻点,可分为以下三种情况。
case1:在该点处的二阶导数大于0,则为函数的极小值点
case2:在该点处的二阶导数小于0,则为极大值点
case3:在该点处的二阶导数等于0,则情况不定,可能是极值点,也可能不是极值点。

13. 解释多元函数极值判别法则。

假设多元函数在点M的梯度为0 ,即M 是函数的驻点。其Hessian 矩阵有如下几种情
况。
case1:Hessian 矩阵正定,函数在该点有极小值
case2:Hessian 矩阵负定,函数在该点有极大值
case3:Hessian 矩阵不定,则不是极值点,称为鞍点
Hessian 矩阵正定类似于一元函数的二阶导数大于0,负定则类似于一元函数的二阶导
数小于0。

14. 什么是鞍点?

Hessian 矩阵不定的点称为鞍点,它不是函数的极值点。

15. 解释什么是局部极小值,什么是全局极小值。

  • 全局极小值
    • 假设 x ∗ \mathbf{x}^{*} x是一个可行解,如果对可行域内所有点 x \mathbf{x} x都有 f ( x ∗ ) ≤ f ( x ) f\left(\mathbf{x}^{*}\right) \leq f(\mathbf{x}) f(x)f(x),则
      x ∗ \mathbf{x}^{*} x为全局极小值。
  • 局部极小值
    • 对于可行解 x ∗ \mathbf{x}^{*} x,如果存在其 δ \delta δ邻域,使得该邻域内的所有点即所有满足
      ∥ x − x ∗ ∥ ≤ δ \left\|\mathbf{x}-\mathbf{x}^{*}\right\| \leq \delta xxδ的点 x \mathbf{x} x,都有 f ( x ∗ ) ≤ f ( x ) f\left(x^{*}\right) \leq f(x) f(x)f(x),则称 x ∗ \mathbf{x}^{*} x为局部极小值。

16. 推导多元函数牛顿法的迭代公式。

根据费马定理,函数在点 x \mathbf{x} x 处取得极值的必要条件是梯度为0

∇ f ( x ) = 0 \nabla f(\mathbf{x})=\mathbf{0} f(x)=0
对于一般的函数,直接求解此方程组存在困难。对目标函数在 x 0 \mathbf{x}_{0} x0 处作二阶泰勒展开
f ( x ) = f ( x 0 ) + ∇ f ( x 0 ) T ( x − x 0 ) + 1 2 ( x − x 0 ) T ∇ 2 f ( x 0 ) ( x − x 0 ) + o ( ∥ k − x 0 ∥ 2 ) f(\mathbf{x})=f\left(\mathbf{x}_{0}\right)+\nabla f\left(\mathbf{x}_{0}\right)^{\mathrm{T}}\left(\mathbf{x}-\mathbf{x}_{0}\right)+\frac{1}{2}\left(\mathbf{x}-\mathbf{x}_{0}\right)^{\mathrm{T}} \nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right)+o\left(\left\|\mathbf{k}-\mathbf{x}_{0}\right\|^{2}\right) f(x)=f(x0)+f(x0)T(xx0)+21(xx0)T2f(x0)(xx0)+o(kx02)
忽略二次以上的项,将目标函数近似成二次函数,等式两边同时对 x \mathbf{x} x求梯度,可得
∇ f ( x ) ≈ ∇ f ( x 0 ) + ∇ 2 f ( x 0 ) ( x − x 0 ) \nabla f(\mathbf{x}) \approx \nabla f\left(\mathbf{x}_{0}\right)+\nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right) f(x)f(x0)+2f(x0)(xx0)
其中 ∇ 2 f ( x 0 ) \nabla^{2} f\left(\mathbf{x}_{0}\right) 2f(x0)为在 x 0 \mathbf{x}_{0} x0 处的Hessian 矩阵。令函数的梯度为0 ,有
∇ f ( x 0 ) + ∇ 2 f ( x 0 ) ( x − x 0 ) = 0 \nabla f\left(\mathbf{x}_{0}\right)+\nabla^{2} f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right)=\mathbf{0} f(x0)+2f(x0)(xx0)=0
解这个线性方程组可以得到
x = x 0 − ( ∇ 2 f ( x 0 ) ) − 1 ∇ f ( x 0 ) (1) \tag{1}\mathbf{x}=\mathbf{x}_{0}-\left(\nabla^{2} f\left(\mathbf{x}_{0}\right)\right)^{-1} \nabla f\left(\mathbf{x}_{0}\right) x=x0(2f(x0))1f(x0)(1)
如果将梯度向量简写为 g \mathbf{g} g ,Hessian 矩阵简记为 H \mathbf{H} H ,式(1)可以简写为
x = x 0 − H − 1 g (2) \tag{2}\mathbf{x}=\mathbf{x}_{0}-\mathbf{H}^{-1} \mathbf{g} x=x0H1g(2)
在泰勒公式中忽略了高阶项将函数做了近似,因此这个解不一定是目标函数的驻点,需要反复用式(2) 进行迭代。从初始点 x 0 \mathbf{x}_{0} x0处开始,计算函数在当前点处的Hessian 矩阵和梯度向量,然后用下面的公式进行迭代

x k + 1 = x k − α H k − 1 g k (3) \tag{3} \mathbf{x}_{k+1}=\mathbf{x}_{k}-\alpha \mathbf{H}_{k}^{-1} \mathbf{g}_{k} xk+1=xkαHk1gk(3)

直至收敛到驻点处。迭代终止的条件是梯度的模接近于0 ,或达到指定的迭代次数。其中 α \alpha α是人工设置的学习率。需要学习率的原因与梯度下降法相同,是为了保证能够忽略泰勒公式中的高阶无穷小项。

参考资料:

深度学习500问: https://github.com/scutan90/DeepLearning-500-questions

机器学习与深度学习习题集答案-1:https://mp.weixin.qq.com/s/4kWUE8ml_o6iF0F1TREyiA

个人总结 ,如有错误,请批评指正!
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/103987
推荐阅读
相关标签
  

闽ICP备14008679号