线性代数|机器学习-P10最小二乘法的四种方案
文章目录
- 1. 概述
- 2. SVD奇异值分解
- 3. 最小二乘法方程解
- 4. 最小二乘法图像解释
- 5. Gram-Schmidt
1. 概述
当我们需要根据一堆数据点去拟合出一条近似的直线的时候，就会用到 最小二乘法 .根据矩阵A的情况，有如下四种方法
- 在r = n = m 时，SVD奇异值分解，
A
=
U
Σ
V
T
A=U\Sigma V^T
A=UΣVT，伪逆矩阵A
+
=
V
Σ
−
1
U
T
A^{+}=V\Sigma^{-1}U^T
A+=VΣ−1UT - 在矩阵A列满秩的情况下(r=n),直接用方程
A
T
A
x
^
=
A
T
b
→
x
^
=
(
A
T
A
)
−
1
A
T
b
A^TA\hat{x}=A^Tb\rightarrow \hat{x}=(A^TA)^{-1}A^Tb
ATAx^=ATb→x^=(ATA)−1ATb - 在条件数
σ
1
σ
r
\frac{\sigma_1}{\sigma_r}
σrσ1太大时，通过Gram-Schmidt生成一个正交列向量，A
=
Q
R
→
x
^
=
R
−
1
Q
T
b
A=QR\rightarrow \hat{x}=R^{-1}Q^Tb
A=QR→x^=R−1QTb,通过消除后得到可以求逆的R
−
1
R^{-1}
R−1 - 加惩罚项，
(
A
T
A
+
δ
2
I
)
x
^
=
A
T
b
→
x
^
=
(
A
T
A
+
δ
2
I
)
−
1
A
T
b
(A^TA+\delta ^2 I)\hat{x}=A^Tb\rightarrow \hat{x}=(A^TA+\delta ^2 I)^{-1}A^Tb
(ATA+δ2I)x^=ATb→x^=(ATA+δ2I)−1ATb,通过在对角线上加一个趋近于0的δ
2
\delta ^2
δ2保证矩阵(
A
T
A
+
δ
2
I
)
(A^TA+\delta ^2 I)
(ATA+δ2I)可逆，这样通过方程就可以得到想要的x
^
\hat{x}
x^
2. SVD奇异值分解
假设我们矩阵A可逆，那么我们就可以直接得到矩阵A的逆，那么此时的矩阵A的伪逆就等于矩阵A的逆
当矩阵
A
可逆
→
A
+
=
A
−
1
\begin{equation} 当矩阵A可逆\rightarrow A^{+}=A^{-1} \end{equation}
当矩阵A可逆→A+=A−1
将矩阵A通过奇异值SVD分解可得如下：
A
=
U
Σ
V
T
,
A
T
=
V
Σ
T
U
T
\begin{equation} A=U\Sigma V^T,A^T=V\Sigma^TU^T \end{equation}
A=UΣVT,AT=VΣTUT
- 得到
A
A
T
,
A
T
A
AA^T,A^TA
AAT,ATA
A
A
T
=
U
Σ
Σ
T
U
T
,
A
T
A
=
V
Σ
T
Σ
V
T
\begin{equation} AA^T=U\Sigma\Sigma^T U^T,A^TA=V\Sigma^T\Sigma V^T \end{equation}
AAT=UΣΣTUT,ATA=VΣTΣVT A
A
T
AA^T
AAT可以看出矩阵A右乘以A
T
A^T
AT,所以得到结果为列空间向量，所以U为列空间基；同理A
T
A
A^TA
ATA可以看出矩阵A左乘以A
T
A^T
AT,所以结果为行空间向量，所以V为行空间基。那么我们可以通过A
v
i
=
σ
i
u
i
Av_i=\sigma_i u_i
Avi=σiui来对看作是行空间基v
i
v_i
vi 通过A
v
i
Av_i
Avi变换后直接得到列空间基σ
i
u
i
\sigma_i u_i
σiui，同理可得，A
T
u
i
=
σ
i
v
i
A^Tu_i=\sigma_i v_i
ATui=σivi可以看作是列空间基u
i
u_i
ui,通过A
T
u
i
A^Tu_i
ATui变换后直接得到行空间基σ
i
v
i
\sigma_i v_i
σivi,那么对于行空间(r个基向量)和列空间(r个基向量)之间可以通过A
,
A
T
A,A^T
A,AT进行转换
A
v
i
=
σ
i
u
i
,
A
T
u
i
=
σ
i
v
i
→
A
+
=
A
T
\begin{equation} Av_i=\sigma_iu_i,A^Tu_i=\sigma_iv_i\rightarrow A^{+}=A^T \end{equation}
Avi=σiui,ATui=σivi→A+=AT
- 通过奇异值分解可得：
A
=
U
Σ
V
T
=
[
u
1
u
2
⋯
u
m
]
[
σ
1
σ
2
⋱
σ
r
0
]
[
v
1
T
v
2
T
⋮
v
n
T
]
\begin{equation} A=U\Sigma V^T=\begin{bmatrix}u_1&u_2&\cdots &u_m\end{bmatrix}\begin{bmatrix}\sigma_1\\&\sigma_2\\&&\ddots\\&&&\sigma_r\\&&&&0\end{bmatrix}\begin{bmatrix}v_1^T\\v_2^T\\\vdots \\v_n^T\end{bmatrix} \end{equation}
A=UΣVT=[u1u2⋯um]
σ1σ2⋱σr0
v1Tv2T⋮vnT
- 将矩阵A求逆可得：
A
−
1
=
V
Σ
−
1
U
T
=
V
[
σ
1
−
1
σ
2
−
1
⋱
σ
r
−
1
0
−
1
]
U
T
\begin{equation} A^{-1}=V\Sigma^{-1} U^T=V\begin{bmatrix}\sigma_1^{-1}\\&\sigma_2^{-1}\\&&\ddots\\&&&\sigma_r^{-1}\\&&&&0^{-1}\end{bmatrix}U^T \end{equation}
A−1=VΣ−1UT=V
σ1−1σ2−1⋱σr−10−1
UT
Σ
Σ
−
1
=
[
1
1
⋱
1
0
⋱
0
]
\begin{equation} \Sigma\Sigma^{-1}=\begin{bmatrix}1\\&1\\&&\ddots\\&&&1\\&&&&0\\&&&&&\ddots\\&&&&&&0\end{bmatrix} \end{equation}
ΣΣ−1=
11⋱10⋱0
- 我们发现
0
−
1
0^{-1}
0−1根本不存在，所以奇异值分解直接求伪逆A
−
1
A^{-1}
A−1也出问题了。出问题的点在于对于特征值为0时候，无法求0的倒数，那就是所如果我们不用零空间的向量和其0特征值，只有行和列空间里面的向量，那么就没这个问题了，这就是Gram-Schmidt的思路，从矩阵A的列空间中挑选向量u_1，其他向量m
1
m_1
m1 不是列空间的，那就通过正交化Gram-Schmidt将其变换为m
1
→
u
2
m_1\rightarrow u_2
m1→u2，这样我们就能得到一个可逆矩阵M，这样我们就能通过公式M
−
1
M^{-1}
M−1直接计算所需要的x
^
\hat{x}
x^
3. 最小二乘法方程解
我们知道，当我们有一个方程
A
x
=
b
Ax=b
Ax=b时，我们得到的是一堆数据点，我们需要拟合一个直线，使得
∣
∣
A
x
^
−
b
∣
∣
2
2
=
(
A
x
^
−
b
)
2
||A\hat{x}-b||_2^2=(A\hat{x}-b)^2
∣∣Ax^−b∣∣22=(Ax^−b)2 值最小，所以我们得到如下方程：
y
=
(
A
x
−
b
)
2
=
(
A
x
−
b
)
T
(
A
x
−
b
)
=
(
x
T
A
T
−
b
T
)
(
A
x
−
b
)
\begin{equation} y=(Ax-b)^2=(Ax-b)^T(Ax-b)=(x^TA^T-b^T)(Ax-b) \end{equation}
y=(Ax−b)2=(Ax−b)T(Ax−b)=(xTAT−bT)(Ax−b)
- 整理可得：
y
=
x
T
A
T
A
x
−
x
T
A
T
b
−
b
T
A
x
+
b
T
b
\begin{equation} y=x^TA^TAx-x^TA^Tb-b^TAx+b^Tb \end{equation}
y=xTATAx−xTATb−bTAx+bTb - 因为
b
T
A
x
b^TAx
bTAx为常数，所以得到x
T
A
T
b
=
b
T
A
x
x^TA^Tb=b^TAx
xTATb=bTAx
y
=
x
T
A
T
A
x
−
2
b
T
A
x
+
b
T
b
→
∂
y
∂
x
=
∂
x
T
A
T
A
x
∂
x
−
2
∂
b
T
A
x
∂
x
\begin{equation} y=x^TA^TAx-2b^TAx+b^Tb\rightarrow \frac{\partial y}{\partial x}= \frac{\partial x^TA^TAx}{\partial x}-2 \frac{\partial b^TAx}{\partial x} \end{equation}
y=xTATAx−2bTAx+bTb→∂x∂y=∂x∂xTATAx−2∂x∂bTAx - 根据矩阵求导可得,
注意转置符号，别漏了：
∂
x
T
A
T
A
x
∂
x
=
2
A
T
A
x
;
−
2
∂
b
T
A
x
∂
x
=
A
T
b
\begin{equation} \frac{\partial x^TA^TAx}{\partial x}=2A^TAx;-2 \frac{\partial b^TAx}{\partial x}=A^Tb \end{equation}
∂x∂xTATAx=2ATAx;−2∂x∂bTAx=ATb - 所以求导公式可以整理得到：
∂
y
∂
x
=
2
A
T
A
x
−
2
A
T
b
=
0
→
A
T
A
x
^
=
A
T
b
\begin{equation} \frac{\partial y}{\partial x}=2A^TAx-2A^Tb=0\rightarrow A^TA\hat{x}=A^Tb \end{equation}
∂x∂y=2ATAx−2ATb=0→ATAx^=ATb - 是不是很神奇，用矩阵求导得到的结果，居然是跟我们用投影法一样的，如果要满足求出上述的
x
^
\hat{x}
x^，也就需要A
T
A
A^TA
ATA 可逆，也就是需要矩阵A满秩，所以跟以前对上来了。 - 当矩阵A列满秩，所以
A
T
A
A^TA
ATA 可逆，方程有解如下：
x
^
=
(
A
T
A
)
−
1
A
T
b
\begin{equation} \hat{x}=(A^TA)^{-1}A^Tb \end{equation}
x^=(ATA)−1ATb
4. 最小二乘法图像解释
假设我们有一个矩阵A和方程
A
x
=
b
Ax=b
Ax=b，求解最优
b
^
\hat{b}
b^?
- 从四个子空间可以看出，我们画出任意向量b，如下图所示：
当我们要求的向量b不在由矩阵A的列向量组成的空间时候，我们其实无法得到正确的解，那么怎么办呢？如果我们将向量b分解，一部分通过投影可得向量p
=
A
x
^
p=A\hat{x}
p=Ax^，其在矩阵A的列空间中，另外一部分就是e=A
x
−
b
Ax-b
Ax−b,只有投影上去了，我们才能够根据向量p来求得近似的解x
^
\hat{x}
x^
5. Gram-Schmidt
Gram-Schmidt 的作用是将矩阵A进行正交分解为
A
=
Q
R
A=QR
A=QR，本身也是通过投影后相减得到垂直向量，这样通过Gram-Schmidt 变换后的矩阵都正交，得到一个可逆矩阵Q和R
A
=
Q
R
,
A
T
=
R
T
Q
T
,
A
T
A
x
^
=
A
T
b
→
R
T
Q
T
Q
R
x
^
=
R
T
Q
T
b
→
R
x
^
=
Q
T
b
\begin{equation} A=QR,A^T=R^TQ^T,A^TA\hat{x}=A^Tb\rightarrow R^TQ^TQR\hat{x}=R^TQ^Tb\rightarrow R\hat{x}=Q^Tb \end{equation}
A=QR,AT=RTQT,ATAx^=ATb→RTQTQRx^=RTQTb→Rx^=QTb
- 整理可得：
x
^
=
R
−
1
Q
T
b
\begin{equation} \hat{x}=R^{-1}Q^Tb \end{equation}
x^=R−1QTb
