线性代数|机器学习-P10最小二乘法的四种方案

1. 概述

当我们需要根据一堆数据点去拟合出一条近似的直线的时候，就会用到 最小二乘法 .根据矩阵A的情况，有如下四种方法

• 在r = n = m 时，SVD奇异值分解，$A=U\Sigma V^T$，伪逆矩阵$A^{+}=V{\Sigma }^{-1}{U}^T$
• 在矩阵A列满秩的情况下(r=n),直接用方程 $A^{T}A\hat{x}=A^{T}b\to \hat{x}=(A^{T}A{)}^{-1}{A}^{T}b$
• 在条件数$\frac{{\sigma }_1}{{\sigma }_r}$太大时，通过Gram-Schmidt生成一个正交列向量，$A=QR\to \hat{x}=R^{-1}{Q}^{T}b$,通过消除后得到可以求逆的 $R^{-1}$
• 加惩罚项，$(A^{T}A+{\delta }^{2}I)\hat{x}=A^{T}b\to \hat{x}=(A^{T}A+{\delta }^{2}I{)}^{-1}{A}^{T}b$,通过在对角线上加一个趋近于0的 ${\delta }^2$保证矩阵$(A^{T}A+{\delta }^{2}I)$可逆，这样通过方程就可以得到想要的 $\hat{x}$

2. SVD奇异值分解

假设我们矩阵A可逆，那么我们就可以直接得到矩阵A的逆，那么此时的矩阵A的伪逆就等于矩阵A的逆
$$\begin{array}{c}当矩阵A可逆\to A^{+}=A^{-1}\end{array}$$
将矩阵A通过奇异值SVD分解可得如下：
$$\begin{array}{c}A=U\Sigma V^T,A^T=V{\Sigma }^T{U}^T\end{array}$$

• 得到$A{A}^T,A^{T}A$
  $$\begin{array}{c}A{A}^T=U\Sigma {\Sigma }^T{U}^T,A^{T}A=V{\Sigma }^T\Sigma V^T\end{array}$$
• $A{A}^T$可以看出矩阵A右乘以 $A^T$,所以得到结果为列空间向量，所以U为列空间基；同理$A^{T}A$可以看出矩阵A左乘以 $A^T$,所以结果为行空间向量，所以V为行空间基。那么我们可以通过$A{v}_i={\sigma }_i{u}_i$来对看作是行空间基 $v_i$ 通过 $A{v}_i$变换后直接得到列空间基${\sigma }_i{u}_i$，同理可得，$A^T{u}_i={\sigma }_i{v}_i$可以看作是列空间基 $u_i$,通过$A^T{u}_i$变换后直接得到行空间基${\sigma }_i{v}_i$,那么对于行空间(r个基向量)和列空间(r个基向量)之间可以通过$A,A^T$进行转换
  $$\begin{array}{c}A{v}_i={\sigma }_i{u}_i,A^T{u}_i={\sigma }_i{v}_i\to A^{+}=A^T\end{array}$$
  
• 通过奇异值分解可得：
  $$\begin{array}{c}A=U\Sigma V^T=\left[\begin{array}{cccc}{u}_1& u_2& \cdots & u_m\end{array}\right]\left[\begin{array}{ccccc}{\sigma }_1& & & & \\ & & & & \\ & {\sigma }_2& & & \\ & & & & \\ & & \ddots & & \\ & & & & \\ & & & {\sigma }_r& \\ & & & & \\ & & & & 0\end{array}\right]\left[\begin{array}{c}{v}_1^T\\ \\ v_2^T\\ \\ ⋮\\ \\ v_n^T\end{array}\right]\end{array}$$
• 将矩阵A求逆可得：
  $$\begin{array}{c}{A}^{-1}=V{\Sigma }^{-1}{U}^T=V\left[\begin{array}{ccccc}{\sigma }_1^{-1}& & & & \\ & & & & \\ & {\sigma }_2^{-1}& & & \\ & & & & \\ & & \ddots & & \\ & & & & \\ & & & {\sigma }_r^{-1}& \\ & & & & \\ & & & & 0^{-1}\end{array}\right]U^T\end{array}$$
  $$\begin{array}{c}\Sigma {\Sigma }^{-1}=\left[\begin{array}{ccccccc}1& & & & & & \\ & & & & & & \\ & 1& & & & & \\ & & & & & & \\ & & \ddots & & & & \\ & & & & & & \\ & & & 1& & & \\ & & & & & & \\ & & & & 0& & \\ & & & & & & \\ & & & & & \ddots & \\ & & & & & & \\ & & & & & & 0\end{array}\right]\end{array}$$
• 我们发现$0^{-1}$根本不存在，所以奇异值分解直接求伪逆$A^{-1}$也出问题了。出问题的点在于对于特征值为0时候，无法求0的倒数，那就是所如果我们不用零空间的向量和其0特征值，只有行和列空间里面的向量，那么就没这个问题了，这就是Gram-Schmidt的思路，从矩阵A的列空间中挑选向量u_1，其他向量 $m_1$ 不是列空间的，那就通过正交化Gram-Schmidt 将其变换为$m_1\to u_2$，这样我们就能得到一个可逆矩阵M，这样我们就能通过公式$M^{-1}$直接计算所需要的$\hat{x}$

3. 最小二乘法方程解

我们知道，当我们有一个方程$Ax=b$时，我们得到的是一堆数据点，我们需要拟合一个直线，使得$||A\hat{x}-b|{|}_2^2=(A\hat{x}-b{)}^2$ 值最小，所以我们得到如下方程：
$$\begin{array}{c}y=(Ax-b{)}^2=(Ax-b{)}^T(Ax-b)=(x^T{A}^T-b^T)(Ax-b)\end{array}$$

• 整理可得：
  $$\begin{array}{c}y=x^T{A}^{T}Ax-x^T{A}^{T}b-b^{T}Ax+b^{T}b\end{array}$$
• 因为$b^{T}Ax$为常数，所以得到$x^T{A}^{T}b=b^{T}Ax$
  $$\begin{array}{c}y=x^T{A}^{T}Ax-2b^{T}Ax+b^{T}b\to \frac{\partial y}{\partial x}=\frac{\partial x^T{A}^{T}Ax}{\partial x}-2\frac{\partial b^{T}Ax}{\partial x}\end{array}$$
• 根据矩阵求导可得,注意转置符号，别漏了：
  $$\begin{array}{c}\frac{\partial x^T{A}^{T}Ax}{\partial x}=2A^{T}Ax;-2\frac{\partial b^{T}Ax}{\partial x}=A^{T}b\end{array}$$
• 所以求导公式可以整理得到：
  $$\begin{array}{c}\frac{\partial y}{\partial x}=2A^{T}Ax-2A^{T}b=0\to A^{T}A\hat{x}=A^{T}b\end{array}$$
• 是不是很神奇，用矩阵求导得到的结果，居然是跟我们用投影法一样的，如果要满足求出上述的$\hat{x}$，也就需要 $A^{T}A$ 可逆，也就是需要矩阵A满秩，所以跟以前对上来了。
• 当矩阵A列满秩，所以 $A^{T}A$ 可逆，方程有解如下：
  $$\begin{array}{c}\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b\end{array}$$

4. 最小二乘法图像解释

假设我们有一个矩阵A和方程$Ax=b$，求解最优 $\hat{b}$?

• 从四个子空间可以看出，我们画出任意向量b，如下图所示：
  当我们要求的向量b不在由矩阵A的列向量组成的空间时候，我们其实无法得到正确的解，那么怎么办呢？如果我们将向量b分解，一部分通过投影可得向量$p=A\hat{x}$，其在矩阵A的列空间中，另外一部分就是e=$Ax-b$,只有投影上去了，我们才能够根据向量p来求得近似的解$\hat{x}$
  

5. Gram-Schmidt

Gram-Schmidt 的作用是将矩阵A进行正交分解为$A=QR$，本身也是通过投影后相减得到垂直向量，这样通过Gram-Schmidt 变换后的矩阵都正交，得到一个可逆矩阵Q和R
$$\begin{array}{c}A=QR,A^T=R^T{Q}^T,A^{T}A\hat{x}=A^{T}b\to R^T{Q}^{T}QR\hat{x}=R^T{Q}^{T}b\to R\hat{x}=Q^{T}b\end{array}$$

• 整理可得：
  $$\begin{array}{c}\hat{x}=R^{-1}{Q}^{T}b\end{array}$$