Levenberg-Marquardt算法

普通梯度下降是一种最简单、最直观的寻找函数最小值的方法。通过在每一步加上负的缩放梯度来更新参数，即 x_{i+1} = x_i - \lambda \nabla f \quad (4) 简单的梯度下降存在各种收敛问题。逻辑上，我们希望在梯度较小的地方（斜率平缓）采取大步，在梯度较大时（斜率陡峭）采取小步，以免跳出最小值。然而，上述更新规则却恰恰相反。另一个问题是误差曲面的曲率在各个方向上可能并不相同。例如，如果误差曲面有一个狭长的山谷，沿着山谷底部方向的梯度分量很小，而沿着山谷墙壁方向的梯度分量却很大。这导致运动方向更多地沿着墙壁，尽管我们需要沿着底部移动很长的距离，而沿着墙壁移动的距离却很短。通过使用曲率和梯度信息，即二阶导数，可以改善这种情况。一种方法是使用牛顿法求解方程 \nabla f(x) = 0 。将 f 的梯度在当前状态 x_0 附近用泰勒级数展开，我们得到 \nabla f(x) = \nabla f(x_0) + (x - x_0)^T \nabla^2 f(x_0) + \text{更高阶项} \quad (5) 如果我们忽略更高阶项（假设 f 在 x_0 附近为二次函数），并通过将 (5) 的左边设为 0 来求解最小值 x ，我们得到牛顿法的更新规则 x_{i+1} = x_i - (\nabla^2 f(x_i))^{-1} \nabla f(x_i) \quad (6) 牛顿法隐式地使用了 f 的二次假设（源于在 f 的泰勒级数展开中忽略更高阶项），因此不需要精确计算海森矩阵。相反，可以使用 (3) 的近似。这种方法的主要优点是收敛速度快。然而，收敛速度对起始位置（或更准确地说，起始位置附近的线性）非常敏感。可以看出，简单的梯度下降和高斯-牛顿迭代在它们提供的优势上是互补的。Levenberg 基于这一观察提出了一个算法，其更新规则是上述算法的混合，给出为 x_{i+1} = x_i - (H + \lambda I)^{-1} \nabla f(x_i) \quad (7) 其中 H 是在 x_i 处评估的海森矩阵。这个更新规则的使用方法如下。如果更新后的误差减小，这意味着我们对 f(x) 的二次假设是有效的，我们将 \lambda 减小（通常减小 10 倍）以减少梯度下降的影响。另一方面，如果误差增加，我们希望更多地沿着梯度方向前进，因此 \lambda 增加相同的倍数。Levenberg 算法因此为：