最小二乘

一维拟合

直线上有 $n$ 个点 $x_n$，在直线上再找一个点 $a$ 来代表这 $n$ 个点，使得误差最小

一般认为就应该找这 $n$ 个点的样本均值了，但为啥呢？取样本均值使得怎样的误差函数取到了最小值呢？

如果定义误差函数为 $f(a)=\Sigma (x_i-a{)}^2=\Sigma x_i^2-2(\Sigma x_i)a+n{a}^2$，则 $f^{\prime }(a)=2na-2(\Sigma x_i)$

可知此时 $f$ 有最小值 $f(\frac{1}{n}\Sigma x_i)$

当然，如果从大数定律出发，样本均值自然是一阶期望的无偏估计量

直线拟合

     ▲
     │                                                       x        ┌────┘
     │                                                           ┌────┘
     │                                                      ┌────┘
     │                                                 ┌────┘
     │               x                            ┌────┘
     │                                       ┌────┘
     │                                  ┌────┘
     │                             ┌────┘                                
     │                        ┌────┘       x                        
     │                   ┌────┘                                
     │              ┌────┘                                
     │         ┌────┘                                                                
     │    ┌────┘                                                                
     ┌────┘         x                                
 ────│                                                                
     │                                                                
     │                                               x               
     │                                                                
─────┼─────────────────────────────────────────────────────────────────────────►
     │

找一条直线 $y=ax+b$ 使得直线距离采样的误差最小

此时，最小二乘定义误差为采样点误差的平方和，也即找使得 $f(a,b)=\Sigma (y_i-a{x}_i-b{)}^2$ 最小的 $a,b$ 值

如果写为矩阵形式，记

$$Y=\left(\begin{array}{c}{y}_1\\ y_2\\ ..\\ y_n\end{array}\right),X=\left(\begin{array}{c}{x}_1\\ x_2\\ ..\\ x_n\end{array}\right),I=\left(\begin{array}{c}1\\ 1\\ ..\\ 1\end{array}\right)$$

$$\begin{array}{cc}1& 2\end{array}$$

则

$$\begin{array}{rl}f(a,b)& =\Sigma (y_i-a{x}_i-b{)}^2\\ & =(Y-aX-bI{)}^T(Y-aX-bI)\\ & =Y^{T}Y-2Y^T(aX+bI)+(aX+bI{)}^T(aX+bI)\\ & =Y^{T}Y-2Y^{T}Xa-2Y^{T}Ib+X^{T}X{a}^2+X^{T}I(2ab)+I^{T}I{b}^2\end{array}$$

分别求偏导，得

$$\{\begin{array}{l}\frac{\partial f}{\partial a}=-2Y^{T}X+X^{T}X2a+X^{T}I2b\\ \frac{\partial f}{\partial b}=-2Y^{T}I+X^{T}I2a+I^{T}I2b\end{array}$$

二元函数最值，那就先求极值，如果极值存在，肯定偏导为 $0$，解呗：

令两个偏导都等于 $0$，得到线性方程组：

$$\left(\begin{array}{cc}{X}^{T}X& X^{T}I\\ X^{T}I& I^{T}I\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{c}{Y}^{T}X\\ Y^{T}I\end{array}\right)$$

这是否...

$$\begin{gathered} \left(\begin{array}{cc}{X}^{T}X& X^{T}I\\ X^{T}I& I^{T}I\end{array}\right)=\left(\begin{array}{c}{X}^T\\ I^T\end{array}\right)\left(\begin{array}{cc}X& I\end{array}\right) \\ \left(\begin{array}{c}{Y}^{T}X\\ Y^{T}I\end{array}\right)=\left(\begin{array}{c}{X}^T\\ I^T\end{array}\right)Y \end{gathered}$$

只能说可以解，但是这也太丑陋了

更好的解释

来自 MIT linear algebra course: projection matrix and least square

最小二乘的原理在于求解一个拟合结果，使得 $n$ 个误差值 $e_n$ 的平方和 $\Sigma e_i^2$最小

如果将 $n$ 个误差值视为一个 $n$ 维向量 $e=\left(\begin{array}{c}{e}_1\\ e_2\\ ..\\ e_n\end{array}\right)$，那么恰有

$$\Sigma e_i^2=||e|{|}^2$$

这样一看，求最小值就变成了求最短向量的问题

课中老师举例为三个点 $(1,1),(2,2),(3,2)$

则有 $X=\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right),Y=\left(\begin{array}{c}1\\ 2\\ 2\end{array}\right)$

     ▲
     │           
     │           
     │           
     │           
     │           
     │                                                           
    2│                                    x                ┌─x───────┘
     │                                            ┌────────┘
     │                                   ┌────────┘
     │                          ┌────────┘
     │                 ┌────────┘
     │        ┌────────┘   
    1┌────────┘        x                          
 ────│                                                                
     │                                                                
     │                                                               
     │                                                                
─────┼─────────────────────────────────────────────────────────────────────────►
     │                 1                  2                  3        

直线拟合时，设直线为 $y=ax+b$，则误差向量为

$$\begin{array}{rl}e& =(aX+b)-Y\\ & =\left(\begin{array}{cc}X& I\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)-Y\\ & =\left(\begin{array}{cc}1& 1\\ 2& 1\\ 3& 1\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)-\left(\begin{array}{c}1\\ 2\\ 2\end{array}\right)\end{array}$$

也即，我们要通过选择 $a,b$ 使得 $e$ 最短

思考：这里 $a,b$ 相当于在组合 $(XI)$ 的列向量，如果

1. $Y$ 恰好在 $(XI)$ 的列空间当中，则误差向量可以取到 $0$，此时显然有最优解（可能不止一个）
2. $Y$ 不在列空间当中（如果列满秩的话，则一定不在列空间里），此时该如何取到最短的误差向量

下图中两个绿色向量 $(1,2,3),(1,1,1)$ 张成了一个列空间。蓝色向量是 $(1,2,2)$

选取 $(a,b)$ 就相当于在列空间上选定了一个橙色向量（两个绿色向量的组合），橙色向量和蓝色向量之差即为误差向量 $e$

此时该如何选取 $(a,b)$ 就变成了一件很显然的事情：$e$ 最短当且仅当选得向量是 $Y$ 在列空间上的投影

求列空间投影不太方便，并非求得 $Y$ 在每个列向量上的投影分量然后相加，而是解一个线性方程组：

$$\left(\begin{array}{ccc}1& 2& 3\\ 1& 1& 1\end{array}\right)\left(\begin{array}{cc}1& 1\\ 2& 1\\ 3& 1\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 2& 1\\ 3& 1\end{array}\right)Y$$

当 $A=\left(\begin{array}{cc}1& 1\\ 2& 1\\ 3& 1\end{array}\right)$ 列满秩时，$A^{T}A$ 显然是可逆的，于是可以解得 $(a,b)$

一维兼容

$$e=\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)\bar{x}-X$$

同样的可以以投影来解释

更高维度

同理