知识卡片
牛顿法及其两处修正
牛顿法同样求无约束极值,最大优点是收敛快。做法是对目标函数做二阶泰勒展开,利用”极值点处一阶导数为 0”这一必要条件,对展开式求导并令其为 0,解出下一步:
xₖ₊₁ = xₖ − [∇²f(xₖ)]⁻¹·∇f(xₖ)
其中 ∇f 是梯度向量,∇²f 是 Hessian 矩阵 H(f)。代入后一步到位,不需要像梯度下降那样试步长。
为什么更快:牛顿法是二阶收敛,梯度下降是一阶收敛。几何上,牛顿法用一个二次曲面拟合当前位置的局部曲面,梯度下降只用一个平面;曲面贴合得更好,下降路径更接近真实的最优路径。直观地说,梯度下降只看”现在哪边最陡”,牛顿法还会考虑”走一步之后坡度会不会更陡”,因此看得更远。
两处缺陷与两种修正:
| 缺陷 | 后果 | 修正 |
|---|---|---|
| 牛顿方向 d=−H⁻¹∇f 不一定是下降方向 | 初始点远离极小值时可能不收敛,函数值反而上升 | 阻尼牛顿法:乘上动态步长 λₖ,相当于沿牛顿方向做一次一维搜索 |
| 每步都要算 Hessian 的逆 | 变量多时计算量过大 | 拟牛顿法:用更简单的矩阵近似 H⁻¹ |
拟牛顿法的构造思路是:由二阶展开可得 H⁻¹(∇f(xₖ₊₁)−∇f(xₖ)) = xₖ₊₁−xₖ,记 pₖ 为位移、qₖ 为梯度差,则 pₖ = H⁻¹qₖ,这就是”拟牛顿条件”。每步只需算出 pₖ 与 qₖ,就能据此更新对 H⁻¹ 的近似,避开求逆。
三者的取舍很清晰:数据规模小、要求高精度时用牛顿法或阻尼牛顿法;参数维度高时用拟牛顿法或直接回到 [[负梯度走一步:批量与随机]]——后者每步只需一阶梯度,单步便宜但迭代多。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第1章 机器学习概述 1.3 机器学习方法三要素 · 查看原书依据
通俗地讲,比如你想找一条最短的路径走到一个盆地的底部,梯度下降法是每次从你当前所处位置选一个坡度最大的方向走一步,而牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。
参考来源
- 位置:《机器学习基础:从入门到求职》第1章《第1章 机器学习概述》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00004.html)
- 结论依据:原文由二阶泰勒展开推出牛顿迭代式,解释其收敛更快的原因,并依次给出阻尼牛顿法与拟牛顿法的动机和拟牛顿条件。
- 原始内容:通俗地讲,比如你想找一条最短的路径走到一个盆地的底部,梯度下降法是每次从你当前所处位置选一个坡度最大的方向走一步,而牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。