一阶梯度下降法
首先是多维目标函数的梯度展开
F
(
x
k
+
Δ
X
k
)
≈
F
(
x
k
)
+
J
(
x
k
)
T
Δ
x
k
+
1
2
Δ
x
k
T
H
(
x
k
)
Δ
x
k
F(x_k+\Delta X_k) \approx F(x_k)+J(x_k)^T \Delta x_k +\frac{1}{2} \Delta x_k^T H(x_k) \Delta x_k
F(xk?+ΔXk?)≈F(xk?)+J(xk?)TΔxk?+21?ΔxkT?H(xk?)Δxk?
如果确保步长位梯度的相反数，就可以保证每次F(x)都是下降的
Δ
x
?
=
?
J
(
x
k
)
\Delta x*=-J(x_k)
Δx?=?J(xk?)
二阶梯度下降发
我们需要将二阶牛顿公式考虑进去 ！
## 点评
- 最速下降法过于贪心
- 牛顿法求解H在大规模数据集上过于困难,关键H太难以计算
- 因此对于最小二乘问题，还有几类更实用的方法
- 高斯牛顿法
- 列文伯格-马夸尔特方法
高斯牛顿法
在高斯牛顿法中，我们设目标函数如下
F
(
x
)
=
1
2
∣
∣
f
(
x
)
∣
∣
2
2
F(x)=\frac{1}{2} ||f(x)||_2^2
F(x)=21?∣∣f(x)∣∣22?
我们最小化目标如下：
有如下推导公式：
计算步骤：
高斯牛顿法，关键的步骤是求解增量
Δ
x
\Delta x
Δx ,而求解增量
Δ
x
\Delta x
Δx需要求解
H
?
1
H^{-1}
H?1 但H是半正定的，可能存在奇异或病态的情况，其次如果我们求出的
Δ
x
\Delta x
Δx太大也不太合适。 相对而言列文伯格-马夸尔特方法比高斯牛顿法更为健壮，当它的收敛速度可能比高斯牛顿法更慢，被称为阻尼牛顿法(Damped Newton Method)
列文伯格-马夸尔特方法
-
给 Δ x \Delta x Δx添加一个范围，称为信赖区域 信赖区域的指标如下公式所示:
ρ = f ( x + Δ x ) ? f ( x ) J ( x ) T Δ x \rho =\frac{f(x+\Delta x)-f(x)}{J(x)^T \Delta x} ρ=J(x)TΔxf(x+Δx)?f(x)? -
参考泰勒展开， ρ \rho ρ越是接近1，则近似效果好，我们可以扩大近似半径，如果 ρ \rho ρ比较小的话，则认为近似效果差，我们需要缩小近似范围
首先从主要步骤着手认识：
以上内容第六步，如果
ρ
\rho
ρ近似不可行，就不进行更新直接进入第7步。这个过程，我们要计算
Δ
x
k
\Delta x_k
Δxk? ,方法如下：
