为什么我们要使用LU或者QR计算线性回归参数而不是用逆矩阵?

线性回归是最基本的机器学习模型,我们通过学习机器学习中本文假设你对线性回归和矩阵论有一定的了解,我们探索两种通过矩阵求解线性回归的相关的参数的一个算法,并且探究两种算法的区别。

通过求解逆矩阵求解线性回归的参数

今天遇到的问题是,就是在计算线性回归的参数的时候,我们一般学过线性回归的同学第一直觉能想到的公式就是: $$ \hat{w}^* = (X^TX)^{-1}X^Ty $$ 倘若你没有学过这个公式,说明你学过的线性回归没有讲通过矩阵计算线性回归的方法,建议去网上找一下相关的资料。回到现在的问题,我们知道,逆矩阵的求解方法是伴随矩阵除行列式,也就是 $$ A^{-1}=\frac{A^}{\det{A}} $$ 其中$A^$指的是$A$的伴随矩阵,伴随矩阵的求法就是通过求代数余子式来得到伴随矩阵。

通过LU分解求解得到线性回归的参数

我们首先回顾一下矩阵的基本知识,我们知道矩阵是对线性方程的一种表示方式。例如我们一组线性方程 $$ a_{1,1}x+a_{1,2}y + a_{1,3}z = 0 \\ a_{2,1}x+a_{2,2}y + a_{2,3}z = 0 \\ a_{3,1}x+a_{3,2}y + a_{3,3}z = 0 $$ 我们知道这可以得到一个系数矩阵: $$ \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix} $$ 如果我们有一组线性方程 $$ a_{1,1}x+a_{1,2}y + a_{1,3}z = \alpha_1 \\ a_{2,1}x+a_{2,2}y + a_{2,3}z = \alpha_2 \\ a_{3,1}x+a_{3,2}y + a_{3,3}z = \alpha_3 $$ 那么我们就可以得到一个增广矩阵也就是: $$ \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \alpha_1 \\ a_{2,1} & a_{2,2} & a_{2,3} & \alpha_2 \\ a_{3,1} & a_{3,2} & a_{3,3} & \alpha_3 \end{bmatrix} $$ 我们可以通过对这个增广矩阵进行高斯消元法得到一个阶梯矩阵,然后通过阶梯矩阵求到$x,y,z$的具体的值。

那么我们从上一节中的线性回归的中的公式可以得到 $$ XX^T\hat{w}^* = X^Ty $$ 所以系数矩阵为$XX^T$,同时等号的右边是一个向量,于是我们就可以得到一个增广矩阵 $$ \begin{bmatrix} XX^T & X^Ty \end{bmatrix} $$ 通过解这个增广矩阵得到每一个xyz的值,我们就可以得到线性方程组的参数了。从而得到每一个线性回归方程中的每一个参数的具体的量了。

通过LU分解求解得到线性回归的参数

等着填坑

两种算法的算法复杂度比较

对于第一种逆矩阵的求法,我们需要求代数余子式,每一个代数余子式需要求一次行列式,同时我们还需要求一次总的行列式,那么对于一个$\sqrt{n}$阶的矩阵,那么就会有$n$个参数,此时算法复杂度为: $$ O(n^3) $$ 而通过LU分解得到线性方程的方法也为相同的复杂度,也就是: $$ O(n^3) $$ 虽然两个算法的阶数相同,但是两个算法的前面的系数并不相同,一般来说,LU分解是逆矩阵求法的1/3,因此我们为了计算更加快速,我们平常在解这个方程的时候,能用LU分解就用LU分解,而不要用逆矩阵去求解