机器学习笔记07:正规方程,解析解法:细节讨论,伪逆矩阵 木灵的炼金工作室

我们在前述的证明中,默认了:属性值矩阵$\vec{A}$中的列向量都无法被其他列向量线性表出(列满秩),这就保证了结果式中的$\vec{A}^T\vec{A}$是一个可逆矩阵,因此我们可以通过

\[\vec{W}=(\vec{A}^T\vec{A})^{-1}\vec{A}^T\vec{Y}\]

顺利对其求最小二乘解.

但若实际的情况下,训练集给出的属性值无法满足属性值矩阵$\vec{A}$列满秩(实际上我们应当尽量避免这样的情况),我们应当如何操作呢?

首先,最简单的方式是仅仅保留列向量的极大线性无关组,舍弃其他非独立的列向量. 但这一点在实际工程上可能会引来额外的运行时间,因此,我们在实际应用中会用矩阵的伪逆运算来代替上述逆运算.

“伪逆矩阵”

预备知识:奇异值分解

线性变换

线性变换具有如下2种种类:

  1. 拉伸: 这种变换对应的矩阵是一个对角矩阵,分别对应正交系中不同轴上的放缩倍率.
  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^+$:

  1. $AA^+A=A$
  2. $A^+AA^+=A^+$
  3. $(AA^+)^T=AA^+$
  4. $(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广义逆元需要更长的时间,所以我们还是建议在设计属性值的时候避免列不满秩的情况发生.


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn