预测误差均方值推导及最小二乘法解法总结

一、预测误差均方值最小值推导

二、最小二乘法总结

1、最小二乘法

最小二乘法（英语：least squares method），又称最小平方法，是一种数学优化方法。它通过最小化误差的平方和寻找数据的最佳函数匹配。

利用最小二乘法可以简便的求得未知的数据，并使得求得的数据与实际数据之间误差的平方和（目标函数）为最小。

目标函数形式如下；
$\text{目标函数} =\sum \left( \text{观测值} -\text{理论值} \right)^{2}$目标函数=∑(观测值−理论值)2

2、梯度下降法

（1）原理

多元函数的梯度定义为：
$\nabla f\left( x\right) =\left( \frac{\partial f}{\partial x_{1}} ,\cdots ,\frac{\partial f}{\partial x_{n}} \right)^{T}$∇f(x)=(∂x1​∂f​,⋯,∂xn​∂f​)T
其中∇ 称为梯度算子，它作用于一个多元函数，得到一个向量。可导函数在某一点处取得极值的必要条件是梯度为0，梯度为0的点称为函数的驻点，这是疑似极值点。需要注意的是，梯度为0只是函数取极值的必要条件而不是充分条件，即梯度为0的点可能不是极值点。

对于实际应用中的大部分函数，直接令梯度为0求得精确解不可行，因此只能转而求近似解。实现时通常采用的是迭代法，它从一个初始点x₀开始，反复使用某种规则从x_k移动到下一个点x_k+1，构造这样一个数列，直到收敛到梯度为0的点处。即有下面的极限成立：
$\lim_{k\rightarrow +\infty } \nabla f\left( x_{k}\right) =0$k→+∞lim​∇f(xk​)=0
方法的核心是得到这样的由上一个点确定下一个点的迭代公式：
$x_{k+1}=h\left( x_{k}\right)$xk+1​=h(xk​)
梯度的方向是函数在给定点上升最快的方向，那么梯度的反方向就是函数在给定点下降最快的方向。故在梯度下降法中，从起始点开始，沿着函数下降最快方向以一定步长前进，经过多次迭代最终可到达梯度为0位置，此时认为已经达到极值点。

迭代公式为：
$x_{k+1}=x_{k}-\alpha f\left( x_{k}\right)$xk+1​=xk​−αf(xk​)
其中α为一个接近于0的正数，称为步长（学习率），由人工设定。

（2）算法过程

1. 确定当前位置的损失函数的梯度；

2. 用步长乘以损失函数的梯度，得到当前位置下降的距离；

3. 确定是否所有的????????,梯度下降的距离都小于????，如果小于????则算法终止，当前所有的????????(i=0,1,…n)即为最终结果。否则进入步骤4；

4. 更新所有的????，更新完毕后继续转入步骤1；

（3）存在问题

• 局部极小值：有些函数可能有多个局部极小值点。假设A、B、C均为函数的极小值，而只有C是函数的全局极小值，梯度下降法可能迭代到B或者C点处就终止。

• ​ 鞍点：鞍点是指梯度为0，Hessian矩阵既不是正定也不是负定，即不定的点。在鞍点处，梯度下降法遇到了鞍点，认为已经找到了极值点，从而终止迭代过程，而这根本不是极值点。例子如下图：

3、牛顿法

和梯度下降法一样，牛顿法也是寻找导数为0的点，同样是一种迭代法。核心思想是在某点处用二次函数来近似目标函数，得到导数为0的方程，求解该方程，得到下一个迭代点。因为是用二次函数近似，因此可能会有误差，需要反复这样迭代，直到到达导数为0的点处。

（1）原理

根据多元函数的泰勒展开公式，我们对目标函数在x0点处做泰勒展开，有：
$f\left( x\right) =f\left( x_{0}\right) +\nabla f\left( x_{0}\right) \left( x-x_{0}\right) +\frac{1}{2} \left( x-x_{0}\right)^{T} \nabla^{2} f\left( x_{0}\right) +o\left( \left( x-x_{0}\right)^{2} \right)$f(x)=f(x0​)+∇f(x0​)(x−x0​)+21​(x−x0​)T∇2f(x0​)+o((x−x0​)2)忽略二次及以上的项，并对上式两边同时求梯度，得到函数的导数（梯度向量）为：
$\nabla \left( x\right) =\nabla f\left( x_{0}\right) +\nabla^{2} f\left( x_{0}\right) f\left( x-x_{0}\right)$∇(x)=∇f(x0​)+∇2f(x0​)f(x−x0​)其中 $\nabla^{2} f\left( x_{0}\right)$∇2f(x0​) 即为Hessian矩阵，在后面我们写成H。令函数的梯度为0，则有：
$x=x_{0}-H^{-1}\nabla f\left( x_{0}\right)$x=x0​−H−1∇f(x0​)从初始点x0处开始，反复计算函数在处的Hessian矩阵和梯度向量，然后用下述公式进行迭代：
$x_{k+1}=x_{k}-H^{-1}_{k}\nabla f\left( x_{k}\right)$xk+1​=xk​−Hk−1​∇f(xk​)最终会到达函数的驻点处。迭代终止的条件是梯度的模接近于0，或者函数值下降小于指定阈值。

Hessian 矩阵，是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率。

Hessian 矩阵就是梯度的雅可比矩阵。

假设有一实值函数f(x₁,x₂, … ,x_n)，如果f的所有二阶偏导数都存在并在定义域内连续，那么函数f的Hessian 矩阵为：

与梯度下降法比较：

和梯度下降法相比牛顿法有更快的收敛速度，但每一步迭代的成本也更高。在每次迭代中，除了要计算梯度向量还要计算Hessian矩阵，并求解Hessian矩阵的逆矩阵。

• 梯度法自起始点出发，在局部进行下降步步逼近极值，行进路线往往呈之字形。

• 而牛顿法在二阶导数的作用下，考虑函数凹凸性，直接搜索如何达到极值。在选择行进方向上，不仅考虑当前坡度是否够大，还考虑前进后坡度是否会变得更大。

综上，牛顿法比梯度下降法收敛速度更快。

（2）算法过程

1. 给定初始值x₀和精度阈值ε，设置k = 0
2. 计算梯度g_k和矩阵H_k
3. 如果在此点处梯度的值接近于0，则达到极值点处，停止迭代
4. 计算搜索方向 d_k=-H_k^-1g_k
5. 计算新的迭代点 x_k=x_k+1+γd_k
6. 令k = k + 1，返回步骤2

其中γ是一个人工设定的接近于0的常数，和梯度下降法一样，需要这个参数的原因是保证x_k+1在x_k的邻域内，从而可以忽略泰勒展开的高次项。

（3）存在问题

• 局部极小:与梯度下降法类似
• Hessian矩阵可能不可逆
• 牛顿法在每次迭代时序列xi可能不会收敛到一个最优解，它甚至不能保证函数值会按照这个序列递减。解决第一个问题可以通过调整牛顿方向的步长来实现

4、高斯牛顿法

高斯牛顿法是对牛顿法的一种改进，它采用雅可比矩阵的乘积近似代替牛顿法中的二阶Hessian矩阵，从而省略了求二阶Hessian矩阵的计算。

Hessian矩阵中各元素的表达式如下：
$\frac{\partial^{2} S}{\partial \beta_{k} \partial \beta_{j} } =2\sum^{m}_{i=1} \left( \frac{\partial r_{i}}{\partial \beta_{k} } \frac{\partial r_{i}}{\partial \beta_{j} } +r_{i}\frac{\partial^{2} r_{i}}{\partial \beta_{k} \partial \beta_{j} } \right)$∂βk​∂βj​∂2S​=2i=1∑m​(∂βk​∂ri​​∂βj​∂ri​​+ri​∂βk​∂βj​∂2ri​​)其中，求和号内前半部分为雅可比矩阵的元素相乘，后半部分定义为O_kj。

由此，Hessian矩阵可简写为
$H=2\left( J^{T}J+O\right)$H=2(JTJ+O)若模型拟合程度较好，则O矩阵内的r_i应趋近于0，故可将后半部分忽略，直接采用雅可比矩阵的乘积近似代替二阶Hessian矩阵。

Hessian矩阵可简化为
$H=2 J^{T}J$H=2JTJ相应的迭代公式为
$x_{k+1}=x_{k}-\left( J^{T}J\right)^{-1} J^{T}r$xk+1​=xk​−(JTJ)−1JTr相比于牛顿法，计算量明显减小。

- [1] 理解梯度下降法

- [2] 理解牛顿法