梯度下降法的原理与实现
梯度下降法的原理与实现
概念介绍
梯度下降法目的是为了“下降”，下降的方法是按照“梯度”。比如你在一座山上，当前你只能迈出一步，如何走才能使你的高度下降的最多呢，根据梯度的理论，我们沿着当前梯度的反方向走，会让我们的下降幅度最大。
上述例子中，山就是一个函数，在山上的你就是函数中待优化的变量，人的坐标表示变量初始值，我们要 求的是函数最小值即到达山底，人该如何走即如何迭代变量。所以我们只要沿着函数梯度的反方向，就能最快的到达我们要去的地方。
梯度下降是一种更新参数的方法，具体如何更新跟原函数的在某点的梯度有关。不会改变要求的最优解。
我们可以利用梯度下降法求最大值和最小值，求最大值沿着梯度方向走即可，求最小值则沿着梯度的反方向走。
公式
抽象的公式就一个
θ
n
e
x
t
=
θ
n
o
w
−
α
▽
f
(
θ
n
o
w
)
\theta ^{next} = \theta ^{now} – \alpha\bigtriangledown f(\theta ^{now})
θnext=θnow−α▽f(θnow)
θ
n
e
x
t
\theta ^{next}
θnext：x在下个时刻的坐标
θ
n
o
w
\theta ^{now}
θnow：x在当前时刻的坐标
α
\alpha
α：步长，每一步走多远，即学习率
▽
f
(
θ
n
o
w
)
\bigtriangledown f(\theta ^{now})
▽f(θnow)：目标函数f(x)在
θ
n
o
w
\theta ^{now}
θnow点的导数
举个例子：
目标函数
y
=
x
2
y = x^{2}
y=x2，学习率
α
\alpha
α=0.1，当前位置x =1,要求y最小值，则下一时刻x的值应该更新为多少呢。根据梯度下降理论，下一时刻：x = 1 - 0.1*2*1 = 0.8，此时的x比x=1的时候更接近0这个最小值。这就是一元变量下的梯度下降算法，多元变量是也是一样的，只是求梯度时有些许不同而已。
算法实现
结合线性回归模型来实现梯度下降算法。梯度下降是线性回归求最优解的一种常用方法。
设我们的线性回归模型为:
h
θ
(
x
(
i
)
)
=
θ
0
+
θ
1
x
1
(
i
)
+
θ
2
x
2
(
i
)
+
.
.
.
+
θ
n
x
n
(
i
)
h_{\theta}( x^{(i)}) =\theta_{0} +\theta_{1}x_{1}^{(i)} + \theta_{2}x_{2}^{(i)} +…+\theta_{n}x_{n}^{(i)}
hθ(x(i))=θ0+θ1x1(i)+θ2x2(i)+...+θnxn(i)
即我们变量是n维的，对每个维度上都加了个权重，求所有维度上的带权和然后加上一个偏置项就是我们的回归函数。而我们的目的就是求出
Θ
0
.
.
.
Θ
n
\Theta_{0}…\Theta_{n}
Θ0...Θn这n+1个参数。
定义代价函数：
J
(
θ
)
=
1
2
m
∑
i
=
1
m
(
h
θ
(
x
(
i
)
)
−
y
(
i
)
)
2
J(\theta) = \frac{1}{2m}\sum_{i=1}^{m}(h_{\theta}( x^{(i)})-y^{(i)})^{2}
J(θ)=2m1i=1∑m(hθ(x(i))−y(i))2
这个代价函数就是预测值与实际值之间的距离的平方，m是样本的个数，求个平均更准确点嘛。分母的2是为跟后面平方项求导后的2约掉。
在程序中，多变量的运算都是通过矩阵来完成的，所以我们要将上述式子写成矩阵相乘的式子：
我们用
Θ
\Theta
Θ来表示
[
Θ
0
,
.
.
.
,
Θ
n
]
[\Theta_{0},…,\Theta_{n}]
[Θ0,...,Θn]，用
X
来
表
示
[
0
,
x
1
,
.
.
.
,
x
n
]
X来表示[0,x_{1},…,x_{n}]
X来表示[0,x1,...,xn]，
这样，原来的回归模型就可以写成：
h
Θ
(
X
)
=
X
Θ
h_{\Theta}( X) = X\Theta
hΘ(X)=XΘ
原来的代价函数可以写成：
J
(
Θ
)
=
1
2
m
(
X
Θ
−
Y
)
T
(
X
Θ
−
Y
)
J(\Theta) = \frac{1}{2m}(X\Theta-Y)^{T}(X\Theta-Y)
J(Θ)=2m1(XΘ−Y)T(XΘ−Y)
上述两式子中的变量全为矩阵表示。
将代价函数对我们要求的参数
Θ
\Theta
Θ求一阶导数得：
▽
J
(
Θ
)
=
1
m
(
X
Θ
−
Y
)
X
\bigtriangledown J(\Theta) = \frac{1}{m}(X\Theta-Y) X
▽J(Θ)=m1(XΘ−Y)X
这个一阶导数就是我们每次更新参数时需要的梯度。这样我们就从一元变量扩展到了多元变量上。可以对含有多元参数的目标函数利用梯度下降法求出最优解。
代码实现：
import numpy as np
row = 20
x0 = np.zeros((row,1))
x1 = np.arange(0,row+0).reshape(row,1)
x2 = np.arange(10,row+10).reshape(row,1)
x3 = np.arange(21,row+21).reshape(row,1)
x = np.hstack((x1,x2,x3))
y = 2*x1 +3*x2 + 4*x3 + np.random.random(row).reshape(row,1)
#定义代价函数
def error_function(theta, x, y):
diff = np.dot(x, theta) - y
return (1./2*row) * np.dot(np.transpose(diff), diff)
#求梯度的函数
def gradient_function(theta, x, y):
diff = np.dot(x, theta) - y
return (1./row) * np.dot(np.transpose(x), diff)
#利用梯度下降法不断迭代参数
def gradient_descent(x, y, alpha):
theta = np.array([1, 1, 1]).reshape(3, 1)
gradient = gradient_function(theta, x, y)
while not np.all(np.absolute(gradient) <= 1e-5):
theta = theta - alpha * gradient
gradient = gradient_function(theta, x, y)
# print(gradient)
return theta
alpa = 0.001
theta = gradient_descent(x,y,alpa)
print(theta)
输出结果：
[[1. ]
[1.97155845]
[2.96137676]
[4.05017691]]
可以看到这个跟我们设定函数时x0,x1,x2,x3是非常接近的。
注意
上述代码中 ，学习率为0.001，把学习率改成1会发生什么呢，自己试试看，会发现程序会一直运行不停止，打印出梯度会发现，梯度一直增加最终变成了无限大。
这是因为，如果学习率过大，会导致不收敛，因为跨的步数太大，会越过那个最低点，并一直震荡。至于为什么梯度会变得越来越大以至于无限大，可以举个例子，函数
y
=
2
x
2
y=2x^{2}
y=2x2,其一阶导数为
y
=
4
x
y =4x
y=4x
在A(10,200)点，梯度为40，所以下一时刻到B点的横坐标为10-140= -30,
在B(-30,1800)点，梯度为-120，所以下一时刻到达的点的横坐标为-30+1120=90，这样会导致离最优值越来越远。
所以：
- 学习率太大会导致不收敛
- 学习率太小会导致到达最低点的迭代次数太大，费时