梯度下降算法综述
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了梯度下降算法综述,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含10414字,纯文字阅读大概需要15分钟。
内容图文
![梯度下降算法综述](/upload/InfoBanner/zyjiaocheng/613/9c388319973f4b5497fbdeeaece1d2b0.jpg)
LawsonAbs的认知与思考,还请各位读者审慎阅读。
总结
- 文章来源:csdn:LawsonAbs
- 本文详细介绍了整个梯度下降算法的缘由,并给出了详细的背景知识,是彻底理解梯度下降算法的好文章。
关键词:机器学习;优化算法;梯度下降;
1 前言
机器学习任务通常分成三个步骤:模型表征+模型评估+优化算法。
- 模型表征是指该用什么样的映射函数,将数据映射到一个结果;
- 模型评估是按照某种评估准则设计的一个评估算法,用于评价这个表征模型到底具有什么样的效果;
- 优化算法的目的是优化表征模型;
优化并不仅能在感官上认识,更重要的是需要用数学量化出来,结合数学公式证明并优化整个模型表征的效果。下面结合一个通俗的例子来解释这个过程。
例1.现在有很多男男女女的配对信息,需要给出两个人的亲密程度。
分析:分别考虑如下三个问题:模型表征,模型评估,优化算法。
- 模型表征:使用一个映射函数 f ( x ) f(x) f(x)作为模型,用 x 1 , x 2 x_1,x_2 x1?,x2?分别表示男女,则有 y ^ = f ( x 1 , x 2 ) \hat{y}=f(x1,x2) y^?=f(x1,x2)表示出两者的亲密值。
- 模型评估:根据原始数据集 ( x 1 , x 2 , y ) (x_1,x_2,y) (x1?,x2?,y),以及预测到的亲密值 y ^ \hat{y} y^? 可以设计一个模型评估准则,这个准则用于衡量映射函数的好坏,也就是表征模型的性能。这里使用MSE方法作为评估函数,也就是常说的损失函数。
- 优化算法:因为想使得模型更好的拟合数据,所以这里得到损失之后,优化的过程就是想使得整个损失变得最小。
由上所述,可知问题就变转换成了该怎么缩小损失,从而更好地拟合模型。在这个过程中,便可使用梯度下降方法来解决这个问题。在介绍梯度下降之前,先来系统的学习一下梯度的由来。
2 背景知识
在谈及梯度的时候,我们不得不谈谈方向导数,而在谈方向导数时候,又不得不理解方向余弦。
2.1 方向余弦
方向余弦是为了方便刻画向量的方向而引出的一个概念。向量的方向可以用同方向的单位向量来表示。
设
l
l
l是一个
n
n
n维非零向量,
l
0
=
l
∣
∣
l
∣
∣
l_0=\frac{l}{||l||}
l0?=∣∣l∣∣l?,即
l
0
l_0
l0? 是与
l
l
l同方向的单位向量。取
0
≤
α
i
≤
π
0\leq\alpha_{i}\leq\pi
0≤αi?≤π,使得
l
0
=
(
c
o
s
α
1
,
.
.
.
,
c
o
s
α
n
)
l_0=(cos\alpha_{1},...,cos\alpha_{n})
l0?=(cosα1?,...,cosαn?)。显然,
c
o
s
2
α
1
+
.
.
.
+
c
o
s
2
α
n
=
1
cos^2\alpha_{1}+...+cos^2\alpha_{n}=1
cos2α1?+...+cos2αn?=1。称:
c
o
s
α
1
,
c
o
s
α
2
,
.
.
.
,
c
o
s
α
n
cos\alpha_{1},cos\alpha_{2},...,cos\alpha_{n}
cosα1?,cosα2?,...,cosαn?
为向量
l
l
l的方向余弦。例如,在二维空间中,向量
l
l
l与
x
x
x轴的夹角就是
α
1
\alpha_{1}
α1?,与
y
y
y轴的夹角就是
α
2
\alpha_{2}
α2?,其方向余弦就是
c
o
s
α
1
,
c
o
s
α
2
cos\alpha{1},cos\alpha{2}
cosα1,cosα2。
2.2 方向导数
导数常用来衡量一个函数的变化速率。方向导数也是一样,只不过方向导数衡量的是某个方向的变化速率。这点很重要,因为通过刚才的例1分析,我们知道要把损失降到最小,但是该怎么降?于是联想是否可以在该点往损失下降的方向靠近,但是损失下降的方向是什么方向?这就涉及到了方向导数。下面仔细看看方向导数是个什么?该怎么定义?
定义:
设
f
f
f是定义于
R
n
R^n
Rn中某区域
D
D
D上的函数,点
P
0
∈
D
P_0 \in D
P0?∈D,
l
l
l为一给定的非零向量,
P
P
P为一动点,向量
P
0
P
P_0P
P0?P与
l
l
l的方向始终一致。如果极限
lim
?
∣
∣
P
0
P
∣
∣
→
0
f
(
P
)
?
f
(
P
0
)
∣
∣
P
0
P
∣
∣
\lim_{||P_0P|| \to 0 } \frac{f(P)-f(P_0)}{||P_0P||}
∣∣P0?P∣∣→0lim?∣∣P0?P∣∣f(P)?f(P0?)?
存在,则称此极限为函数
f
f
f在
P
0
P_0
P0?处沿
l
l
l方向的方向导数,记作
?
(
f
)
?
(
l
)
\frac{\partial(f)}{\partial(l)}
?(l)?(f)?。方向导数可以用偏导数来表示:
下面就证明这一结论。
证明 方向导数的表达式是:
?
(
f
)
?
(
l
)
∣
p
0
=
?
(
f
)
?
(
x
1
)
∣
p
0
c
o
s
α
1
+
?
(
f
)
?
(
x
2
)
∣
p
0
c
o
s
α
2
+
.
.
.
+
?
(
f
)
?
(
x
3
)
∣
p
0
c
o
s
α
n
\left.\frac{\partial(f)}{\partial(l)}\right|_{p_{0}} = \left.\frac{\partial(f)}{\partial(x_1)}\right|_{p_{0}} cos \alpha_1 + \left.\frac{\partial(f)}{\partial(x_2)}\right|_{p_{0}} cos \alpha_2 + ... + \left.\frac{\partial(f)}{\partial(x_3)}\right|_{p_{0}} cos \alpha_n
?(l)?(f)?∣∣∣?p0??=?(x1?)?(f)?∣∣∣?p0??cosα1?+?(x2?)?(f)?∣∣∣?p0??cosα2?+...+?(x3?)?(f)?∣∣∣?p0??cosαn?
性质 接着来看方向导数的几个性质:
- 方向导数是个值;
2.3 梯度
介绍完方向导数之后,先以二元函数
z
=
f
(
x
,
y
)
z=f(x,y)
z=f(x,y)为例,再看看梯度的定义。
\paragraph{定义}设函数
z
=
f
(
x
,
y
)
z=f(x,y)
z=f(x,y)在平面D上有一阶连续偏导数,则在每点
(
x
,
y
)
∈
D
(x,y) \in D
(x,y)∈D ,都可定义一个向量:
?
(
f
)
?
(
x
)
?
i
?
+
?
(
f
)
?
(
y
)
?
j
?
\frac{\partial(f)}{\partial(x)} * \vec{i} + \frac{\partial(f)}{\partial(y)} * \vec{j}
?(x)?(f)??i
+?(y)?(f)??j
?
称这个向量为函数
z
=
f
(
x
,
y
)
z=f(x,y)
z=f(x,y) 在点
p
(
x
,
y
)
p(x,y)
p(x,y) 处的梯度,记作
g
r
a
d
f
(
x
,
y
)
grad f(x,y)
gradf(x,y),即:
g
r
a
d
f
(
x
,
y
)
=
?
(
f
)
?
(
x
)
?
i
?
+
?
(
f
)
?
(
y
)
?
j
?
grad f(x,y) = \frac{\partial(f)}{\partial(x)} * \vec{i} + \frac{\partial(f)}{\partial(y)} * \vec{j}
gradf(x,y)=?(x)?(f)??i
+?(y)?(f)??j
?
也可写作
g
r
a
d
f
(
x
,
y
)
=
{
?
(
f
)
?
(
x
)
,
?
(
f
)
?
(
y
)
}
grad f(x,y) = \{\frac{\partial(f)}{\partial(x)}, \frac{\partial(f)}{\partial(y)}\}
gradf(x,y)={?(x)?(f)?,?(y)?(f)?}
如果设
e
?
=
c
o
s
α
1
?
i
?
+
c
o
s
α
2
?
j
?
\vec{e}=cos \alpha_1 * \vec{i} + cos \alpha_2 *\vec{j}
e
=cosα1??i
+cosα2??j
? 是与方向
l
l
l同向的单位向量,则由方向导数的计算公式可知:
?
(
f
)
?
(
l
)
=
?
(
f
)
?
(
x
)
c
o
s
α
1
+
?
(
f
)
?
(
y
)
c
o
s
α
2
=
{
?
(
f
)
?
(
x
)
,
?
(
f
)
?
(
y
)
}
?
{
c
o
s
α
1
,
c
o
s
α
2
}
=
g
r
a
d
f
(
x
,
y
)
?
e
\frac{\partial(f)}{\partial(l)} = \frac{\partial(f)}{\partial(x)} cos \alpha_1 + \frac{\partial(f)}{\partial(y)} cos \alpha_2 \\ =\{ \frac{ \partial(f)} {\partial(x)} , \frac{ \partial(f)} {\partial(y)} \} * \{ cos\alpha_1 ,cos\alpha_2 \}\\ =grad f(x,y) * e
?(l)?(f)?=?(x)?(f)?cosα1?+?(y)?(f)?cosα2?={?(x)?(f)?,?(y)?(f)?}?{cosα1?,cosα2?}=gradf(x,y)?e
这里的
g
r
a
d
(
x
,
y
)
?
e
grad(x,y) * e
grad(x,y)?e 就是一个内积,当二者方向相同时,计算结果取到最大值。也就是说:当
l
l
l的方向与
g
r
a
d
f
(
x
,
y
)
grad f(x,y)
gradf(x,y)方向相同时,方向导数的值取最大;当
l
l
l的方向与梯度方向相反时,计算结果取最小。那么可以得出如下结论:
函数在某点的梯度是这样一个向量,它的方向与取得最大方向导数的方向一致,而它的模为方向导数的最大值. 同时,如果我们想优化某个问题,就可以使用梯度的这个性质,也有以下结论成立:
- 如果我们需要优化一个函数值,想让其变得小(即minimize的过程),那么就应该朝其负梯度方向变化;
- 如果想让其变得更大(即maxmum的过程),那么就应该朝其梯度方向变化。
但是梯度下降方向和等高线的切线方向有什么关系呢?仍以二元函数
z
=
f
(
x
,
y
)
z=f(x,y)
z=f(x,y)为例。一般说来,二元函数在集合上表示一个曲面,这曲面被平面
z
=
c
z=c
z=c(c是常数)所截得的曲线的方程是:
{
z
=
f
(
x
,
y
)
z
=
c
\left \{ \begin{aligned} z& = f(x,y) \\ z&=c \end{aligned} \right.
{zz?=f(x,y)=c?
这条曲线
l
l
l在
x
O
y
xOy
xOy平面上的投影是一个平面曲线
L
L
L,它在
x
O
y
xOy
xOy平面直角坐标系中的方程为
f
(
x
,
y
)
=
c
f(x,y)=c
f(x,y)=c。因为该函数的函数值都是
c
c
c,所以我们称平面曲线
L
L
L为函数
z
=
f
(
x
,
y
)
z=f(x,y)
z=f(x,y)的等高线.设方程
f
(
x
,
y
)
=
c
f(x,y)=c
f(x,y)=c确定了隐函数
y
=
y
(
x
)
y=y(x)
y=y(x),将此函数代入原方程,得恒等式:
f
(
x
,
y
(
x
)
)
≡
0
f(x,y(x)) \equiv 0
f(x,y(x))≡0
等式两端对x求导:
f
x
+
f
y
?
y
′
(
x
)
=
0
f_x + f_y * y'(x) = 0
fx?+fy??y′(x)=0
得:
y
′
(
x
)
=
?
f
x
f
y
y'(x) = -\frac{f_x}{f_y}
y′(x)=?fy?fx??
故等值线
f
(
x
,
y
)
=
c
f(x,y)=c
f(x,y)=c在点
(
x
,
y
)
(x,y)
(x,y)处的法向量为:
{
1
,
f
y
f
x
}
\{1,\frac{f_y}{f_x}\}
{1,fx?fy??} 或
{
f
x
,
f
y
}
=
?
f
(
x
,
y
)
\{f_x,f_y\} = \nabla f(x,y)
{fx?,fy?}=?f(x,y)
正好是函数
f
(
x
,
y
)
f(x,y)
f(x,y)在
(
x
,
y
)
(x,y)
(x,y)处的梯度.因此我们可以得到梯度与等高线的关系:函数在点
(
x
,
y
)
(x,y)
(x,y)处的梯度的方向与过点的等高线在这点的法线的一个方向相同,且从数值较低的等高线指向数值较高的等高线,而梯度的模等于函数在这个法线方向的方向导数.
3 梯度下降算法
结合上面的知识,我们可以推出一个优化算法——梯度下降算法:
令
x
0
x^0
x0作为初始搜索点,并沿着梯度负方向构造一个新点
x
0
?
α
?
f
(
x
0
)
x^0 - \alpha \nabla f(x^0)
x0?α?f(x0),由泰勒定理可得:
f
(
x
0
?
α
?
f
(
x
0
)
)
=
f
(
x
0
)
?
α
∣
∣
?
f
(
x
0
)
∣
∣
2
+
o
(
α
)
f(x^0 - \alpha \nabla f(x^0)) = f(x^0) - \alpha ||\nabla f(x^0)||^2 + o(\alpha)
f(x0?α?f(x0))=f(x0)?α∣∣?f(x0)∣∣2+o(α)
因此,如果
?
f
(
x
0
)
≠
0
\nabla f(x^0) \neq 0
?f(x0)?=0 ,那么当
α
\alpha
α 够小是,有:
f
(
x
0
?
α
?
f
(
x
0
)
)
≤
f
(
x
0
)
f(x^0 - \alpha \nabla f(x^0)) \leq f(x^0)
f(x0?α?f(x0))≤f(x0)
成立。这意味着,从搜索目标函数极小点的角度来看,
f
(
x
0
?
α
?
f
(
x
0
)
)
=
f
(
x
0
)
?
α
∣
∣
?
f
(
x
0
)
∣
∣
2
+
o
(
α
)
f(x^0 - \alpha \nabla f(x^0)) = f(x^0) - \alpha ||\nabla f(x^0)||^2 + o(\alpha)
f(x0?α?f(x0))=f(x0)?α∣∣?f(x0)∣∣2+o(α) 相对于
x
0
x^0
x0有所改善。这为极小点搜索工作提供了很好的启发。
可以设计一种方法实现以上理念。给定一个搜索点
x
k
x^k
xk,由此点出发,根据向量
?
α
k
?
f
(
x
k
)
-\alpha_k \nabla f(x^k)
?αk??f(xk)指定的方向和幅值运动,构造新点
x
k
+
1
x^{k+1}
xk+1,其中,
α
k
\alpha_k
αk? 是一个正实数,称为步长。这样,就可以得到一个迭代公式:
x
k
+
1
=
x
k
?
α
k
?
f
(
x
k
)
x^{k+1} = x^{k} - \alpha_k \nabla f(x^{k})
xk+1=xk?αk??f(xk)
这称为梯度下降方法 (或简称梯度方法)。在搜索过程中,梯度不断变化,当接近极小点时,梯度应该趋近于0。 可以设定很小的步长,每次迭代都重新计算梯度;当然也可以设置很大的步长。前者的工作量非常大,而后者则容易在极小点附近产生锯齿状的收敛路径,优势在于梯度的计算次数要少一些。梯度下降方法包括很多种不同的具体算法,最常用的算法为最速下降法。
3.1 最速下降法
最速下降法是梯度方法的一种具体实现,其理念为在每次迭代中选择合适的步长
α
k
\alpha_k
αk?,使得目标函数值能够得到最大程度的减小。梯度方法便于实现,且大部分情况下能够很好地运行。
下面针对具体的函数模型给出算法的迭代过程。利用最速下降法求解函数:
f
(
x
1
,
x
2
,
x
3
)
=
(
x
1
?
4
)
4
+
(
x
2
?
3
)
2
+
4
(
x
3
+
5
)
4
f(x_1,x_2,x_3) = (x_1 - 4)^4 + (x_2 - 3)^2 + 4(x_3 + 5)^4
f(x1?,x2?,x3?)=(x1??4)4+(x2??3)2+4(x3?+5)4
的极小点。初始搜索点为
x
0
=
[
4
,
2
,
?
1
]
T
x^0=[4,2,-1]^T
x0=[4,2,?1]T,开展3次迭代。
\subparagraph{} 目标函数的梯度为:
?
f
(
x
)
=
[
4
(
x
1
?
4
)
3
,
2
(
x
2
?
3
)
,
16
(
x
3
+
5
)
3
]
T
\nabla f(x) = [4(x_1-4)^3,2(x_2-3),16(x_3+5)^3]^T
?f(x)=[4(x1??4)3,2(x2??3),16(x3?+5)3]T
因此,
x
0
x^0
x0处的梯度为
?
f
(
x
0
)
=
[
0
,
?
2
,
1024
]
T
\nabla f(x^0)=[0,-2,1024]^T
?f(x0)=[0,?2,1024]T,确定
x
1
x^1
x1处的步长:
α
0
=
arg
?
min
?
α
0
f
(
x
0
?
α
?
f
(
x
0
)
)
=
arg
?
min
?
α
0
≥
0
(
0
+
(
2
+
2
α
?
3
)
2
+
4
(
?
1
?
1024
α
+
5
)
4
)
=
arg
?
min
?
α
0
≥
0
?
(
α
)
\begin{aligned} \alpha_0 &= \mathop{\arg\min}_{\alpha_0} f(x^0 - \alpha \nabla f(x^0) )\\ &=\mathop{\arg\min}_{\alpha_0 \geq 0} (0+(2+2\alpha-3)^2+4(-1-1024\alpha+5)^4)\\ &=\mathop{\arg\min}_{\alpha_0 \geq 0} \phi(\alpha) \end{aligned}
α0??=argminα0??f(x0?α?f(x0))=argminα0?≥0?(0+(2+2α?3)2+4(?1?1024α+5)4)=argminα0?≥0??(α)?
应用割线法开展一维搜索,可得:
α
0
=
3.967
?
1
0
?
3
\alpha_0 = 3.967 * 10^{-3}
α0?=3.967?10?3。于是得到新的迭代点
x
1
=
x
0
?
α
0
?
f
(
x
0
)
=
[
4.0000
,
2.0008
,
?
5.062
]
T
x^1 = x^0 - \alpha_0 \nabla f(x^0) = [4.0000,2.0008,-5.062]^T
x1=x0?α0??f(x0)=[4.0000,2.0008,?5.062]T
如此迭代计算,可得:
α
1
=
0.500
,
x
2
=
x
1
?
α
0
?
f
(
x
1
)
=
[
4.0000
,
3.0000
,
?
5.060
]
T
\alpha_1 = 0.500, x^2 = x^1 - \alpha_0 \nabla f(x^1) = [4.0000,3.0000,-5.060]^T
α1?=0.500,x2=x1?α0??f(x1)=[4.0000,3.0000,?5.060]T
α
2
=
16.29
,
x
3
=
x
2
?
α
0
?
f
(
x
2
)
=
[
4.0000
,
3.0000
,
?
5.002
]
T
\alpha_2 = 16.29, x^3 = x^2 - \alpha_0 \nabla f(x^2) = [4.0000,3.0000,-5.002]^T
α2?=16.29,x3=x2?α0??f(x2)=[4.0000,3.0000,?5.002]T
根据函数表达式,可以很直观的看到
f
(
x
1
,
x
2
,
x
3
)
f(x_1,x_2,x_3)
f(x1?,x2?,x3?)的最小值就是(4,3,-5).
3.2 固定步长梯度法
根据步长是否固定,可将梯度下降法分成固定步长梯度法和最速下降法。固定步长梯度法就是迭代更新时步长固定。这种步长固定梯度法简单实用。由于步长固定,因此,在每步迭代中,不需要开展以为搜索确定步长 α k \alpha_k αk?. 显然,该方法的收敛性与步长 α \alpha α有关。
4 结论
本文的贡献在于:
- 给出方向导数表达式的证明;
- 推导梯度和方向导数之间的关系;
- 证明梯度方向与等高线的切线方向垂直;
- 给出梯度下降算法及相关系列算法,并结合实例给出迭代结果;
内容总结
以上是互联网集市为您收集整理的梯度下降算法综述全部内容,希望文章能够帮你解决梯度下降算法综述所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。