通过多项式对函数进行逼近的方法得到
f
(
x
)
=
f
(
x
0
)
+
f
′
(
x
0
)
1
!
(
x
−
x
0
)
+
f
′
′
(
x
0
)
2
!
(
x
−
x
0
)
2
+
⋯
+
f
(
n
)
(
x
0
)
n
!
(
x
−
x
0
)
n
+
R
n
(
x
)
f(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\dots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x)
f(x)=f(x0)+1!f′(x0)(x−x0)+2!f′′(x0)(x−x0)2+⋯+n!f(n)(x0)(x−x0)n+Rn(x) 故
f
(
x
)
≈
f
(
x
0
)
+
f
′
(
x
0
)
(
x
−
x
0
)
f(x)≈f(x_0)+f'(x_0)(x-x_0)
f(x)≈f(x0)+f′(x0)(x−x0) 其中令
Δ
x
=
x
−
x
0
\Delta x=x-x_0
Δx=x−x0，则有
f
(
x
)
≈
f
(
x
0
)
+
Δ
x
∇
f
(
x
0
)
f(x)≈f(x_0)+\Delta x\nabla f(x_0)
f(x)≈f(x0)+Δx∇f(x0) 则得到
f
(
x
)
−
f
(
x
0
)
=
Δ
x
∇
f
(
x
0
)
f(x)-f(x_0)=\Delta x\nabla f(x_0)
f(x)−f(x0)=Δx∇f(x0) 其实
Δ
x
\Delta x
Δx和
∇
f
(
x
0
)
\nabla f(x_0)
∇f(x0)都是向量，因此需要
f
(
x
)
−
f
(
x
0
)
f(x)-f(x_0)
f(x)−f(x0)最小，只有当
Δ
x
\Delta x
Δx和
∇
f
(
x
0
)
\nabla f(x_0)
∇f(x0)两个方向相反，故有
Δ
x
=
−
α
∇
f
(
x
0
)
α
>
0
\Delta x=-\alpha \nabla f(x_0)~~~~~~~\alpha >0
Δx=−α∇f(x0)α>0 最终得到梯度下降法的递推公式为
x
:
=
x
−
α
∇
f
(
x
)
x:=x-\alpha \nabla f(x)
x:=x−α∇f(x)
2. 求解最小二乘问题（采用梯度下降算法求解线性回归模型最优解）
线性回归模型
f
ω
(
x
)
=
ω
0
+
ω
1
x
+
⋯
+
ω
d
x
d
f_\omega(x)=\omega_0+\omega_1x+\dots+\omega_dx_d
fω(x)=ω0+ω1x+⋯+ωdxd 其中d表示有d个特征.
损失函数
J
(
ω
^
)
=
1
2
m
∑
i
=
1
m
(
X
i
ω
^
−
y
i
)
2
J(\widehat{\omega})=\frac{1}{2m}\sum\limits_{i=1}^m(X_i\widehat{\omega}-y_i)^2
J(ω)=2m1i=1∑m(Xiω−yi)2 其中m表示有m个样本点.
使用梯度下降最小化损失函数，求解最优解
根据梯度下降递推公式有
ω
^
:
=
ω
^
−
α
∂
J
(
ω
^
)
∂
ω
^
\widehat{\omega}:=\widehat{\omega}-\alpha\frac{\partial{J(\widehat{\omega})}}{\partial{\widehat{\omega}}}
ω:=ω−α∂ω∂J(ω) 即
ω
^
:
=
ω
^
−
α
m
X
T
(
X
ω
^
−
y
)
=
ω
^
−
α
m
∑
i
=
1
m
(
X
i
ω
^
−
y
i
)
X
i
T
\widehat{\omega}:=\widehat{\omega}-\frac{\alpha}{m}X^T(X\widehat{\omega}-y)=\widehat{\omega}-\frac{\alpha}{m}\sum\limits_{i=1}^m(X_i\widehat{\omega}-y_i)X_i^T
ω:=ω−mαXT(Xω−y)=ω−mαi=1∑m(Xiω−yi)XiT
3. 优点
此时时间复杂度为
O
(
m
d
)
O(md)
O(md),迭代次数少
4. 缺点
每次迭代都要用到训练集所有的数据，因此当数据量大的时候迭代速度会很慢
随机梯度下降（SGD）
通过观察发现
1
m
∑
i
=
1
m
(
X
i
ω
^
−
y
i
)
X
i
T
\frac{1}{m}\sum\limits_{i=1}^m(X_i\widehat{\omega}-y_i)X_i^T
m1i=1∑m(Xiω−yi)XiT相当于是所有训练集样本点的均值
记
z
i
=
(
X
i
ω
^
−
y
i
)
X
i
T
z_i=(X_i\widehat{\omega}-y_i)X_i^T
zi=(Xiω−yi)XiT，每个样本点i选取的概率为
1
m
\frac{1}{m}
m1，则有
E
i
(
z
i
)
=
1
m
∑
i
=
1
m
(
X
i
ω
^
−
y
i
)
X
i
T
E_i(z_i)=\frac{1}{m}\sum\limits_{i=1}^m(X_i\widehat{\omega}-y_i)X_i^T
Ei(zi)=m1i=1∑m(Xiω−yi)XiT 故随机梯度下降法的递推公式为
ω
^
:
=
ω
^
−
α
(
X
j
ω
^
−
y
j
)
X
j
T
\widehat{\omega}:=\widehat{\omega}-\alpha(X_j\widehat{\omega}-y_j)X_j^T
ω:=ω−α(Xjω−yj)XjT
1. 优点
每次迭代使用随机的一个样本来对参数进行更新，使得训练速度加快，此时的时间复杂度为
O
(
d
)
O(d)
O(d)
2. 缺点
准确度下降，当目标函数为强凸函数的情况下，无法做到线性收敛
可能会收敛到局部最优
迭代次数比BGD多
小批量梯度下降法(MBGD)
鉴于BGD,SGD的优缺点，提出每次迭代使用部分样本来对参数进行更新，故MBGD的迭代公式为
ω
^
:
=
ω
^
−
α
#
J
∑
j
∈
J
(
X
j
ω
^
−
y
j
)
X
j
T
\widehat{\omega}:=\widehat{\omega}-\frac{\alpha}{\# J}\sum\limits_{j\in J}(X_j\widehat{\omega}-y_j)X_j^T
ω:=ω−#Jαj∈J∑(Xjω−yj)XjT
