最小二乘法

最小二乘法通常用来研究两个变量或者多个变量之间的关系。比如常用的直线回归，使用$y=ax+b$来拟合一些散点，如下图所示。

解法

正如矩阵可以从多个角度看待一样，我们也可以从多个角度来求解最小二乘法。我们先分别从行空间和列空间的角度来求解。

行空间

问题可以化为：寻找$a,b$，使得如下公式尽量成立

$$
\left\{\begin{array}{c}
y_{1}=a x_{1}+b \\
y_{2}=a x_{2}+b \\
\vdots \\
y_{n}=a x_{n}+b
\end{array}\right.
$$

也就是说，求解下面这个优化模型：

$$
\min _{a, b} f(a, b)=\sum_{i=1}^{n}\left(a x_{i}+b-y_{i}\right)^{2}
$$

可以发现，这是求解一个二元函数的最小值，因此方法是求导，取极值点。

$$
\left\{\begin{array}{l}
\frac{\partial f}{\partial a}=2 \sum_{i=1}^{n}\left(a x_{i}+b-y_{i}\right) x_{i}=0 \\
\frac{\partial f}{\partial b}=2 \sum_{i=1}^{n}\left(a x_{i}+b-y_{i}\right)=0
\end{array}\right.
$$

化简可得：

$$
\left\{\begin{array}{l}
a=\frac{n \sum_{i=1}^{n} x_{i} y_{i}-\sum_{i=1}^{n} x_{i} \sum_{i=1}^{n} y_{i}}{n \sum_{i=1}^{n} x_{i}^{2}-\left(\sum_{i=1}^{n} x_{i}\right)^{2}} \\
b=\frac{1}{n} \sum_{i=1}^{n} y_{i}-\frac{a}{n} \sum_{i=1}^{n} x_{i}
\end{array}\right.
$$

列空间

从列空间角度，也就是利用矩阵求解。首先将每一列记成一个列向量，即：

$$
\mathbf{x}=\left(x_{1}, x_{2}, \cdots, x_{n}\right)^{T}, \mathbf{y}=\left(y_{1}, y_{2}, \cdots, y_{n}\right)^{T}, \mathbf{l}=(1,1, \cdots, 1)^{T}
$$

则线性模型可以表示为：

$$
\mathbf{y}=a\mathbf{x}+b\mathbf{l}
$$

再将这个式子化简一下，令：

$$
\mathbf{X}=[\mathbf{x}\ \ \ \mathbf{l}],\ \ \ \mathbf{c}=[a\ \ \ b]^T
$$

可得：

$$
\mathbf{y}=\mathbf{Xc}
$$

然后优化模型就变为：

$$
\min _{\mathbf{c}} f(\mathbf{c})=|\mathbf{y}-\mathbf{X} \mathbf{c}|^{2}
$$

求解过程：

$$
\begin{aligned}
|\mathbf{y}-\mathbf{X} \mathbf{c}|^{2}&= (\mathbf{y}-\mathbf{X} \mathbf{c})^T(\mathbf{y}-\mathbf{X} \mathbf{c}) \
&=\mathbf{y}^T\mathbf{y}-\mathbf{y}^T\mathbf{Xc}-\mathbf{c}^T\mathbf{X}^Ty+\mathbf{c}^T\mathbf{X}^T\mathbf{X}\mathbf{c}\
&=\mathbf{y}^T\mathbf{y}-2\mathbf{y}^T\mathbf{Xc}+\mathbf{c}^T\mathbf{X}^T\mathbf{X}\mathbf{c}
\end{aligned}
$$

注：$\mathbf{c}^{T}\mathbf{X}^{T}\mathbf{Y}=\mathbf{Y}^{T}\mathbf{X}\mathbf{c}$，原因：$\mathbf{Y}和\mathbf{X}\mathbf{c}$都是列向量。

对自变量c求导可得：（这里用到了矩阵的微积分）

$$
f'(\mathbf{c})=2 \mathbf{X}^T \mathbf{X} \mathbf{c}-2 \mathbf{X}^T \mathbf{y}=\mathbf{0}
$$

化简可得：

$$
\mathbf{c}=\left(\mathbf{X}^T \mathbf{X}\right)^{-1} \mathbf{X}^T \mathbf{y} \quad \mathbf{X}^{\#}=\left(\mathbf{X}^T \mathbf{X}\right)^{-1} \mathbf{X}^T
$$

其中，$\mathbf{X}^\#$称为广义逆矩阵。

最小二乘法的变量问题

问题：y=ax+b与x=a'y+b'，得到的结果一样吗？

答案：不一样，原因如下图所示。

几何解释——投影矩阵

根据下式：

$$
\mathbf{y}=a\mathbf{x}+b\mathbf{l}
$$

我们可以知道等式右边为$\mathbf{x}$和$\mathbf{l}$的线性组合，$a\mathbf{x}+b\mathbf{l}$在$\mathbf{x}$和$\mathbf{l}$张成的空间上。我们需要求的是：

$$
\min _{\mathbf{c}} f(\mathbf{c})=|\mathbf{y}-\mathbf{X} \mathbf{c}|^{2}
$$

可以知道这个式子表示$\mathbf{y}$到$\mathbf{x}$和$\mathbf{l}$张成的空间的最小距离。根据几何知识，可以知道最小的距离就是投影。这就是最小二乘法的几何解释。

根据上文计算的结果，可知：

$$
\mathbf{c}=\left(\mathbf{X}^T \mathbf{X}\right)^{-1} \mathbf{X}^T \mathbf{y} \quad \mathbf{X}^{\#}=\left(\mathbf{X}^T \mathbf{X}\right)^{-1} \mathbf{X}^T
$$

可以计算出投影为：

$$
\mathbf{y}^{\prime}=\mathbf{X c}=\mathbf{X}\left(\mathbf{X}^T \mathbf{X}\right)^{-1} \mathbf{X}^T \mathbf{y}
$$

将y前面的式子记为：

$$
\mathbf{P}_{\mathbf{x}}=\mathbf{X}\left(\mathbf{X}^T \mathbf{X}\right)^{-1} \mathbf{X}^T=\mathbf{X} \mathbf{X}^{\#}
$$

这个矩阵称为投影矩阵，表示向$\mathbf{X}$列向量张成的空间上的投影。所以$\mathbf{y}$到$\mathbf{X}$列向量张成的空间上的投影为：

$$
\mathbf{y}^{\prime}=\mathbf{P}_{\mathbf{x}} \mathbf{y}
$$

投影矩阵

例题：

$$\mathbf{X}=(x_1,x_2,\cdots,x_n),\ \ 问\mathbf{P_{X}}(k_1x_1+k_2x_2)等于多少$$

结果：$\mathbf{P_{X}}(k_1x_1+k_2x_2)=k_1x_1+k_2x_2$.

因为$\mathbf{P_{X}X}=\mathbf{X}，x\in Span(\mathbf{X})$

投影矩阵的正交补表示向X的正交补空间上的投影。

$$\mathbf{P_{X}^{\perp}}=\mathbf{I}-\mathbf{P_{X}}$$

投影矩阵的特征值为0和1。?=1对应于稳定状态，投影矩阵将列空间的所有向量都投影到列空间中去，也即还是它自身，$??_1=?_1$。?=0对应于零空间，投影矩阵将零空间的所有向量都投影到零向量，$??_2=?_2$。

从几何上看，广义逆就对应着正交投影。

概率解释——为什么要用误差的平方？

题外话：概率——probability 似然——likelihood

对于p(x|θ)，如果，你将θ设为常量，则你会得到一个概率函数（关于x的函数）；如果，你将x设为常量你将得到似然函数（关于θ的函数）。相当于概率是在给定条件不同结果下的p，而似然是在给定结果不同条件下的p。

使用平方的原因就是我们认为误差满足高斯分布。推导过程如下：

记

$$
\left\{\begin{array}{c}
y_1=\mathbf{c}^T \mathbf{x}_1+\varepsilon_1 \\
y_2=\mathbf{c}^T \mathbf{x}_2+\varepsilon_2 \\
\vdots \\
y_n=\mathbf{c}^T \mathbf{x}_n+\varepsilon_n
\end{array}\right.
$$

其中，$\varepsilon_i$满足正态分布，即

$$
\varepsilon_i\sim N(0,\sigma^2)
$$

概率密度函数为：

$$
P\left(\varepsilon_i\right)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\varepsilon_i^2}{2 \sigma^2}\right)
$$

由于$y_i=\mathbf{c}^T \mathbf{x}_i+\varepsilon_i$，如果给定$\mathbf{x}_i$和$\mathbf{c}$，那么因变量$y_i$也服从正态分布，将上式中的$\varepsilon_i$替换，可得：

$$
P\left(y_i \mid \mathbf{x}_i ; \mathbf{c}\right)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_i-\mathbf{c}^T \mathbf{x}_i\right)^2}{2 \sigma^2}\right)
$$

假设所有的$\varepsilon_i$独立同分布，可以得到关于参数$\mathbf{c}$的似然函数：

$$
L(\mathbf{c})=P(\mathbf{y} \mid \mathbf{x} ; \mathbf{c})=\prod_{i=1}^n P\left(y_i \mid \mathbf{x}_i ; \mathbf{c}\right)=\prod_{i=1}^n \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_i-\mathbf{c}^T \mathbf{x}_i\right)^2}{2 \sigma^2}\right)
$$

为了得到似然函数的最大值，令：

$$
\begin{aligned}
& l(\mathbf{c})=\ln (L(\mathbf{c}))=\ln \left(\prod_{i=1}^n P\left(y_i \mid \mathbf{x}_i ; \mathbf{c}\right)\right) \\
& =\ln \left(\prod_{i=1}^n \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_i-\mathbf{c}^T \mathbf{x}_i\right)^2}{2 \sigma^2}\right)\right) \\
& =\sum_{i=1}^n \ln \left(\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y_i-\mathbf{c}^T \mathbf{x}_i\right)^2}{2 \sigma^2}\right)\right) \\
& =n \ln \left(\frac{1}{\sqrt{2 \pi} \sigma}\right)-\sum_{i=1}^n \frac{\left(y_i-\mathbf{c}^T \mathbf{x}_i\right)^2}{2 \sigma^2}
\end{aligned}
$$

由上式可得，似然函数取得最大值的条件为：

$$
\sum_{i=1}^n\left(y_i-\mathbf{c}^T \mathbf{x}_i\right)^2=\sum_{i=1}^n\left(a x_i+b-y_i\right)^2=f(a, b)
$$

取得最小值。

而这个正好就是最小二乘法的模型，可以看到指数为2，即取误差的平方。

各个观测点的模型误差满足独立同分布的高斯分布是最小二乘法能够行之有效的概率机制前提。如果此条件不能得到满足，用最小二乘法拟合数据将不能得到最优解。而根据中心极限定理，这个条件一般情况下是近似成立的。

有约束的最小二乘法

可以看到约束都是作用在$\mathbf{c}$上，而$\mathbf{c}$由a和b构成，而a和b正好是$\mathbf{X}$列向量线性组合的性质，因此，不论是等式约束，还是不等式约束，还是全约束，都是对$\mathbf{X}$列空间进行限制。