您可以自由地共享和演绎本文稿, 只需遵守开源协议[CC By 4.0]
如果这篇文章帮助到你, 可以请我喝一杯咖啡~
我们在前述的证明中,默认了:属性值矩阵$\vec{A}$中的列向量都无法被其他列向量线性表出(列满秩),这就保证了结果式中的$\vec{A}^T\vec{A}$是一个可逆矩阵,因此我们可以通过
\[\vec{W}=(\vec{A}^T\vec{A})^{-1}\vec{A}^T\vec{Y}\]顺利对其求最小二乘解.
但若实际的情况下,训练集给出的属性值无法满足属性值矩阵$\vec{A}$列满秩(实际上我们应当尽量避免这样的情况),我们应当如何操作呢?
首先,最简单的方式是仅仅保留列向量的极大线性无关组,舍弃其他非独立的列向量. 但这一点在实际工程上可能会引来额外的运行时间,因此,我们在实际应用中会用矩阵的伪逆运算来代替上述逆运算.
“伪逆矩阵”
预备知识:奇异值分解
线性变换
线性变换具有如下2种种类:
- 拉伸: 这种变换对应的矩阵是一个对角矩阵,分别对应正交系中不同轴上的放缩倍率.
- 旋转: 这种变换对应的矩阵是一个标准正交矩阵.
所有的矩阵均可以认为是对某标准正交基进行的拉伸-旋转变换的组合:
\[MV=U\Sigma\]其中$M$是任意的矩阵,$V$是变换前向量空间中的一组标准正交基,$U$是变换后空间中的一组标准正交基,$\Sigma$是变换中蕴含的拉伸量,是一个对角矩阵.
奇异值分解
由于$V$是一个标准正交矩阵,故整理上式:
\[M = U\Sigma V^T\]上式即为:对矩阵$M$的奇异值分解(Singular Value Decomposition)
奇异值分解对于任意的矩阵M均可执行. 如$M$不满秩,则其多余的行不参与对于正交基$V$的变换(标准行变换可以清空”多余”的行向量,且不改变线性变换的性质),因此$\Sigma$的对应位置为0.
算法
考虑式:
\[M = U\Sigma V^T\]构造
\[MM^T=U\Sigma V^T(U\Sigma V^T)^T=U\Sigma V^TV\Sigma U^T\]基于标准正交矩阵的性质:
\[MM^T=U\Sigma \Sigma U^T=U\Sigma^2U^T\]又$\Sigma$是一个对角矩阵,因此$\Sigma^2$也是一个对角矩阵. 那么上式的形式与特征值矩阵一致:
\[MM^T=X\Lambda X^T\]其中,$X$是$MM^T$的正交归一化特征向量张成的矩阵,$\Lambda$是$MM^T$的特征值对角阵.
即,我们对矩阵$MM^T$执行特征值分解,得到其若干特征值$\lambda_1, \lambda_2,…, \lambda_n$和若干特征向量$\vec{l}_1, \vec{l}_2,…, \vec{l}_n$,将特征值组合为特征值矩阵:
\[\Lambda = \begin{pmatrix} \lambda_1& 0& ...& 0\\ 0& \lambda_2& ...& 0\\ ...&...&...&...\\ 0&0&...&\lambda_n\\ \end{pmatrix}=\Sigma^2\]因此求出
\[\Sigma = \begin{pmatrix} \sqrt{\lambda_1}& 0& ...& 0\\ 0& \sqrt{\lambda_2}& ...& 0\\ ...&...&...&...\\ 0&0&...&\sqrt{\lambda_n}\\ \end{pmatrix}\]再将其特征向量张成矩阵
\[(\vec{l}_1, \vec{l}_2,..., \vec{l}_n)=U\]同理,对$M^TM$执行上述步骤,可以得出矩阵$V$.
如此,我们完成了矩阵的奇异值分解.
矩阵的Moore–Penrose广义逆运算
https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse
定义
对于一个$m\times n$矩阵$A$,它的Moore–Penrose广义逆元被定义为:满足如下条件(Moore–Penrose条件)的一个$n\times m$矩阵$A^+$:
- $AA^+A=A$
- $A^+AA^+=A^+$
- $(AA^+)^T=AA^+$
- $(A^+A)^T=A^+A$
若矩阵$A$可逆,那么$A^{-1}$是其Moore–Penrose广义逆元.
我们仅需要证明其性质其一:
\[AB = ABB^+A^+AB\] \[AB = (AB)(AB)^+(AB)\]得到
\[ABB^+A^+AB = AB(AB)^+AB\]故
\[(AB)^+ = B^+A^+\]通过SVD计算Moore–Penrose广义逆元
由SVD运算的拆分式:
\[M = U\Sigma V^T\]由若矩阵$A$可逆,那么$A^{-1}$是其Moore–Penrose广义逆元和上述证明的性质得到
\[M^+ = V\Sigma^+ U^T\]而$\Sigma$是对角矩阵,其Moore–Penrose广义逆的算法明显是将其对角线元素取逆元(倒数).
由此,我们可以通过SVD计算出任意矩阵的Moore–Penrose广义逆元.
Moore–Penrose广义逆元用于超定方程组求解
我们回到超定方程组求解时的倒数第二步:
\[\vec{A}^T\vec{Y}-\vec{A}^T\vec{A}\vec{W} = 0\]此时,我们的$\vec{A}$不是列满秩矩阵,因此不可用$\vec{A}^T\vec{A}$的一般逆来计算其值,因此我们应用Moore–Penrose广义逆运算(此时我们可以继续化简,因为即使是非方阵也具有Moore–Penrose广义逆元):
\[\vec{W} = (A^TA)^+A^TY = A^+A^{T+}A^TY = A^+Y\]如此,我们解决了当属性矩阵列不满秩时的情况. 由于计算Moore–Penrose广义逆元需要更长的时间,所以我们还是建议在设计属性值的时候避免列不满秩的情况发生.