线性最小二乘法

                     

贡献者: addis; ACertainUser

  • 本文存在未完成的内容。
预备知识 二元函数的极值,线性方程组解的结构

1. 直线拟合

   在许多情况下,我们需要将一组散点数据 $x_i, y_i \ \ (i = 1\dots N)$ 拟合成特定形式的函数曲线。其中最常见的情况之一是拟合一条直线,形式为 $y = ax + b$。例如给出(图 1),如何确定直线方程的两个最佳系数 $a$ 和 $b$ 呢?

   我们可以通过方差来计算拟合的误差,方差越小则说明拟合得越好。

\begin{equation} S_2 = \sum_{i = 1}^N (a x_i + b - y_i)^2~. \end{equation}
对于给定的 $N$ 个 $x_i, y_i$,方差是 $a$ 和 $b$ 的二元函数。我们只需找到这个二元函数的最小值点即可。由于函数处处光滑,最小值点必定满足 $ \partial S_2/\partial a = \partial S_2/\partial b = 0$。将式 1 代入,得到一个线性方程组。
\begin{equation} \left\{\begin{aligned} & \left(\sum_i x_i^2 \right) a + \left(\sum_i x_i \right) b = \sum_i x_i y_i \\ & \left(\sum_i x_i \right) a + N b = \sum_i y_i \end{aligned}\right. ~. \end{equation}
我们来计算系数行列式,如果能证明行列式恒不等于零,则方程组必有唯一解。若令 $\bar x$ 为 $N$ 个 $x_i$ 的平均值,考虑到 $x_i$ 互不相等,容易证明
\begin{equation} N\sum_i x_i^2 - \left(\sum_i x_i \right) ^2 = N\sum_i (x_i - \bar x)^2 > 0~, \end{equation}
证毕。由于方差恒大于零,可知其必定存在最小值,所以系数的唯一解必定是方差函数的极小值点。接下来解线性方程组即可得到系数 $a, b$。将解出的 $a,b$ 重新代入式 1 可以得出最小方差的值,用于判断拟合结果的好坏。

2. 一个简单的例子

图
图 1:最小二乘法。仿自 J. Leon 的 Linear Algebra with Applications

   若 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{b}} $ 无解,则基于最小二乘法的近似解 $ \boldsymbol{\mathbf{\hat x}} $ 是:

\begin{equation} \boldsymbol{\mathbf{\hat x}} = ( \boldsymbol{\mathbf{A}} ^T \boldsymbol{\mathbf{A}} )^{-1} \boldsymbol{\mathbf{A}} ^T \boldsymbol{\mathbf{b}} ~. \end{equation}

例 1 

   线性拟合散点(1,1),(2,2),(3,2)。

图
图 2:线性拟合散点

   设 $y=ax+b$, 即 $ \begin{cases} a+b&=1\\ 2a+b&=2\\ 3a+b&=2\\ \end{cases} \Rightarrow \begin{bmatrix} 1&1\\ 2&1\\ 3&1\\ \end{bmatrix} \begin{bmatrix} a\\ b\\ \end{bmatrix} = \begin{bmatrix} 1\\ 2\\ 2\\ \end{bmatrix} \Rightarrow \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{b}} ~. $

   $\therefore \hat { \boldsymbol{\mathbf{x}} } = ( \boldsymbol{\mathbf{A}} ^T \boldsymbol{\mathbf{A}} )^{-1} \boldsymbol{\mathbf{A}} ^T \boldsymbol{\mathbf{b}} $,即可解出 a, b.

   一些初级的 AI 通过拟合高维直线、曲线来建立模型。(A 是输入,b 是输出,x 即为模型的各系数)。

3. 多项式拟合

  

未完成:应该先列出超定线性方程组,系数就直接是范德蒙矩阵,在上面开一小节讲解如何用最小二乘法得到近似解(搬运)。参考 Wikipedia 相关页面

   直线可以看作一阶多项式,所以我们只需要把上面直线拟合的方法拓展一下即可。以二次多项式 $c_2 x^2 + c_1 x + c_0$ 为例,方差为

\begin{equation} S_2(c_2, c_1, c_0) = \sum_{i = 1}^N (c_2 x_i^2 + c_1 x_i + c_0 - y_i)^2~. \end{equation}
分别令方差对 $c_2, c_1, c_0$ 的偏导为零,得线性方程组
未完成:系数矩阵应该左右翻转再上下翻转
\begin{equation} \left\{\begin{aligned} & \left(\sum_i x_i^4 \right) c_2 + \left(\sum_i x_i^3 \right) c_1 + \left(\sum_i x_i^2 \right) c_0 & &= \sum_i y_i x_i^2 \\ & \left(\sum_i x_i^3 \right) c_2 + \left(\sum_i x_i^2 \right) c_1 + \left(\sum_i x_i \right) c_0 & &= \sum_i y_i x_i \\ & \left(\sum_i x_i^2 \right) c_2 + \left(\sum_i x_i \right) c_1 + \quad N c_0 & &= \sum_i y_i \end{aligned}\right. ~. \end{equation}
观察系数矩阵可以看出它是一个方阵,每条斜线上 $x_i$ 的指数相等,且相邻斜线上 $x_i$ 的指数依次递减。按照此规律容易写出 $N$ 次多项式拟合的方程组。Matlab 代码见 “最小二乘法数值拟合(多项式)”。

   式 6 也可以用范德蒙矩阵 $ \boldsymbol{\mathbf{X}} $ 表示为

\begin{equation} ( \boldsymbol{\mathbf{X}} ^{\mathrm{T}} \boldsymbol{\mathbf{X}} ) \boldsymbol{\mathbf{c}} = \boldsymbol{\mathbf{b}} ~. \end{equation}

   可以证明当且仅当 $x_i$ 的个数大于多项式的阶数时该式存在唯一解:当 $x_i$ 各不相同时,范德蒙矩阵的各列都线性无关,根据定理 1 ,系数行列式 $ \left\lvert \boldsymbol{\mathbf{X}} ^{\mathrm{T}} \boldsymbol{\mathbf{X}} \right\rvert > 0$,方程有唯一解。证毕。

   此外,根据魏尔施特拉斯逼近定理,闭区间上的连续函数都可以使用多项式逼近,随着阶数增加,多项式会一致收敛于要拟合的函数。

4. 简谐波拟合

   若要拟合 $A \cos\left(x + \varphi_0\right) + C$ 形式的函数,可以先利用两角和公式把函数化为 $c_1 \cos x + c_2 \sin x + c_3$ 的等效形式(因为前者并不是待定系数的线性组合,得到的方程组也不是线性方程组),方差公式为

\begin{equation} S_2 = \sum_i (c_1 \cos x_i + c_2 \sin x_i + c_3 - y_i)^2~. \end{equation}
要求极值,分别令方差对 $c_1, c_2, c_3$ 的偏导为零,得线性方程组
\begin{equation} \left\{\begin{aligned} & \left(\sum_i \cos^2 x_i \right) c_1 + \left(\sum_i \sin x_i \cos x_i \right) c_2 + \left(\sum_i \cos x_i \right) c_3 & &= \sum_i y_i \cos x_i\\ & \left(\sum_i \sin x_i \cos x_i \right) c_1 + \left(\sum_i \sin^2 x_i \right) c_2 + \left(\sum_i \sin x_i \right) c_3 & &= \sum_i y_i \sin x_i\\ & \left(\sum_i \cos x_i \right) c_1 \quad + \quad \left(\sum_i \sin x_i \right) c_2 \quad + \quad N c_3 & &= \sum_i y_i\\ \end{aligned}\right. ~. \end{equation}
和多项式拟合同理,该方程的解总能得到方差的全局最小值。同理,只要能列出关于 $c_i$ 的线性方程组就都可以。

   该方程存在的一个问题是,各个 $c_i$ 偏导为零,就一定会是全局最小值吗?我们不能证明任意线性拟合中系数行列式都不为零,那么会不会解出的是局部最小值,最大值,甚至鞍点呢?首先要明确的是方差 $S_2$ 是一个关于 $c_i$ 的二次函数,处处可导,所以全局最小值必定满足各阶偏导为零。再来考虑有多个解的情况,根据线性方程组解的结构,若线性方程组存在多于一个解,那么这些解必定不可能是离散的而是会存在无穷个解构成一个连续的平面,在该平面上由于各方向偏导处处为零,$S_2$ 必定处处相等,所以所有解都是全局最优解。

                     

© 小时科技 保留一切权利