数值优化(Numerical Optimization)(4)最小二乘问题

在最小二乘问题中,目标函数通常具有如下形式

[公式]

其中

  1. [公式] 通常是一个特定模型的参数
  2. [公式] 通常是模型 [公式] (参数 [公式] )在点 [公式] 的预测值与实际值 [公式] 的残差

[公式]

Formulation

 [公式] ,则目标函数可以表示为

[公式]

目标函数的一阶导数(注意 [公式]  [公式] 维的, [公式] 关于 [公式] 求导应该对 [公式] 的每一个分量求导)为

[公式]

二阶导数为

[公式]

最小二乘的本质是利用 [公式] 来近似 [公式] (舍弃的二阶项通常很小,因为残差本身就很小,且越接近极小值点残差越小),也就是说只需要利用一阶导数信息。

线性最小二乘回归

假设 [公式] ,则

[公式]

其中 [公式] 的每一行是 [公式]

目标函数为

[公式]

注意:如果 [公式] 不是非常大的情况下,这一目标函数可以直接利用矩阵分解来求解。

一阶导数为

[公式]

注意:这一正规方程在样本数 [公式] 很大时求解更具优势,因为只需要求解一个 [公式] 的方程的系统。

线搜索:高斯牛顿法

高斯牛顿法是非线性最小二乘回归的一种线搜索方法,我们知道牛顿法每次迭代需要求解线性方程

[公式]

对牛顿类方法还不熟悉的可以看之前的博文

将最小二乘问题的二阶导数和一阶导数带入可得

[公式]

这一方程比标准的牛顿法要简便许多,它不需要计算海森矩阵,只需要残差和一阶导数信息即可。

算法流程

  1. 给定初始值
  2. 计算步长 [公式]
  3. 计算下一迭代点 [公式]
  4. 检验是否收敛,否则转步骤2

高斯牛顿法的一个主要缺点是 [公式] 在奇异时没有定义,因此有了下面介绍的LM方法。

信赖域:LM方法

LM方法的主要思想时使用强迫正定的策略,即

[公式]

其中 [公式] 使得 [公式] 是个正定阵。当 [公式] 时等价于高斯牛顿法,当 [公式]充分大时退化为梯度下降法。此外,LM方法属于信赖域法

对信赖域法还不熟悉的可以看之前的博文

从信赖域的角度出发, [公式] 的局部模型为:

[公式]

因为 [公式] ,求解 [公式] 的最小值等价于

[公式]

这里给出信赖域型的LM法的算法流程

  1. 给定初值,以及信赖域法的参数
  2. 检验终止条件(梯度 [公式] 是否小于一个阈值)
  3. 解信赖域问题得到 [公式]
  4. 解的接受算法
  5. 信赖域调整算法