线性代数|机器学习-P11方程Ax=b求解研究

1. 变量数和约束条件数大小分类

• 0 用伪逆矩阵 $x=A^{+}b$直接求解，[上一节已讲]
• 1 当矩阵A大小适中，条件数$\frac{{\sigma }_1}{{\sigma }_r}<1000时$， 用 $x=A\backslash b$；
• 2 当矩阵A列满秩m>n=r时，方程数多于变量数，无法求解，只能择中找近似解，将b投影到矩阵A的列空间中后，再找到近似解 $\hat{x}$ 用 $A^{T}A\hat{x}=A^{T}b\to \hat{x}=(A^{T}A{)}^{-1}{A}^{T}b$
• 3 当矩阵m < n时，方程数小于变量数，有无穷多的解，约束不够，所以我们增加$L_1,L2$约束来在众多的解中拿到一个好的解，这是深度学习中最重要的损失函数解决思路。

2. 最小二乘法和Gram-schmidt变换

2.1 Gram-schmidt变换

• 4 列向量情况很差，条件数$\frac{{\sigma }_1}{{\sigma }_r}>1000$，就是病态矩阵，简单理解就是矩阵A的列向量之间相关性太大，导致无法用相关性的列表示其他向量；
  当我们矩阵A的列向量为$a_1,a_2$时候，我们用$a_1,a_2$表示$v_3$时候，特别不方便，$a_1,a_2$越相近，越不方便，就是所说的列向量相关性太大，那gram-schmidt的方式就是，既然$a_1,a_2$太接近，那就改造其中一个，我们把$a_1$经过投影和相减后得到$a_{11}$，那么$a_{11}\perp a_2$，这样我们就用新的正交向量$a_{11},a_3$来表示 $v_3$. 将A分解为QR后就可以得到最优解$\hat{x}$，具体推导可以看上一节内容。另外一种是通过将列进行旋转，原理和行的交换一样，主要是关于数值稳定性的问题，保证不要出现大数吃小数的现象发生。
  

2.2 最小二乘法

2.2.1 损失函数-Lasso 和regression

• 5 矩阵A接近奇异矩阵，该矩阵的值不是满秩，无法进行直接求逆得到$A^{-1}$逆矩阵，就是会得到很多的解，我们的目的是从这么多的解中找到一个最好的解，目前加$L_1$项，即加$\lambda ||x|{|}_1$，即是我们的LASSO模型;加$L_2$项目，即加${\delta }^2||x|{|}_2^2$，即是我们的岭回归模型，是不是很神奇！！！，后面还有的是两个都加，后续会学习到的！！！

2.2.2 损失函数-Lasso

• Lasso 模型
  $$\begin{array}{c}\underset{min}{\arg }\frac{1}{2}||Ax-b|{|}_2^2+\lambda ||x|{|}_1\end{array}$$
• Redge 模型,在$\delta$较小的时候$\frac{1}{2}{\delta }^2$和${\delta }^2$无区别

2.2.3 损失函数-regression

$$\begin{array}{c}z=\underset{min}{\arg }\frac{1}{2}||Ax-b|{|}_2^2+\frac{1}{2}{\delta }^2|x|{|}_1^2\end{array}$$

• z的矩阵表达式
  $$\begin{array}{c}z=\underset{min}{\arg }\frac{1}{2}||Ax-b|{|}_2^2+\frac{1}{2}||\delta Ix-0|{|}_1^2\end{array}$$
• 也就是说惩罚项重新构成了增广矩阵$A^{\ast },b^{\ast }$
  $$\begin{array}{c}\left[\begin{array}{c}A\\ \\ \sigma I\end{array}\right]\left[\begin{array}{c}x\end{array}\right]=\left[\begin{array}{c}b\\ \\ 0\end{array}\right]\to A^{\ast }x=b^{\ast }\to (A^{T}A+{\sigma }^{2}I)x=A^{T}b\end{array}$$
• 对于一般矩阵A，不是特别大的矩阵A，解如下：
  $$\begin{array}{c}(A^{T}A+{\sigma }^{2}I)x=A^{T}b\to \hat{x}=(A^{T}A+{\sigma }^{2}I{)}^{-1}{A}^{T}b\end{array}$$

2.2.4 Regression岭回归-矩阵验证

• 验证上述是否正确，假设矩阵A为[a],整理可得如下：
  $$\begin{array}{c}(A^{T}A+{\sigma }^{2}I)x=A^{T}b\to (a^2+{\sigma }^2)x=ab\end{array}$$
  – 当 $a^2+{\sigma }^2\ne 0$:
  $$\begin{array}{c}(a^2+{\sigma }^2)x=ab\to \hat{x}=\frac{a}{a^2+{\sigma }^2}b\end{array}$$
• 当$\sigma =0,a\ne 0$时，可得：
  $$\begin{array}{c}(a^2+{\sigma }^2)x=ab\to \hat{x}=\frac{a}{a^2+{\sigma }^2}b\to \hat{x}=\frac{b}{a}\end{array}$$
  – 当 $a^2+{\sigma }^2=0\to a=\sigma =0$:
  $$\begin{array}{c}z=\underset{min}{\arg }\frac{1}{2}||Ax-b|{|}_2^2+\frac{1}{2}{\delta }^2|x|{|}_1^2\to z=\frac{1}{2}(ax-b{)}^2\end{array}$$
  此时的z是向上的抛物线，那么可得最小值就一定在x=0处。

2.2.5 Regression岭回归-导数验证

$$\begin{array}{c}z=\underset{min}{\arg }\frac{1}{2}||Ax-b|{|}_2^2+\frac{1}{2}{\delta }^2|x|{|}_1^2=\frac{1}{2}(ax-b{)}^2+\frac{1}{2}{\delta }^2{x}^2\end{array}$$

• 求导可得：
  $$\begin{array}{c}\frac{\partial z}{\partial x}=a(ax-b)+{\sigma }^{2}x=0\to (a^2+{\sigma }^2)\hat{x}=ab\to 居然跟矩阵表达式一样\end{array}$$
  所以我们暂时简单验证我们在最小二乘法中加二范数惩罚项是对的!!!

• 以上是损失函数的设计，也就是我们通过添加损失函数的约束条件来明确我们的目标，那么目标有了，现在缺少怎么找到目标的方法，常见的有随机梯度下降等方法，里面设计到学习率，迭代次数等，目的是怎么快速的找到最小的损失函数值，并根据结果来更新权重参数，这样矩阵就和深度学习联系上啦！

• 好的解指的是我们的解不仅对已知的数据集有好的损失函数值，同时我们的解还能对未知的数据有好的结果！有效性和泛化性都要有！！！

3. 迭代和随机采样

3.1 迭代

• 6 迭代
  当矩阵很大的时候，但是不是超级巨大，我们可以用迭代的方法处理，将矩阵A分解为
  $$\begin{array}{c}A=S-T\to Ax=b\to Sx=Tx+b\end{array}$$
• 迭代可得：
  $$\begin{array}{c}S{x}_{k+1}=T{x}_k+b;S{x}_k=T{x}_{k-1}+b;\to S(x-x_{k+1})=T(x-x_k)\end{array}$$
• 误差比可得：
  $$\begin{array}{c}\frac{x-x_{k+1}}{x-x_k}=S^{-1}T\end{array}$$
• 当$S^{-1}T$<1时，随着 $S^{-1}T$越小，$x_k$收敛的快。

3.2 随机采样

• 7 随机采样
  当矩阵A超级大的时候，我们用电脑计算已经无法直接计算 $A^{T}A$的时候，我们就需要用到神奇的概率采样技术了，我们通过一定的概率去采样得到新的矩阵$A_s$时，用$A_s$近似替代A。
  我们知道矩阵A左乘行变换，右乘列变换，当我们用x来采样A列向量时，得到$Ax=A_{sl}$,实现列采样，当我们用x来采样A行向量时，得到$A^{T}x=A_{sr}$,实现行采样，这样我们就可以用采样的小样本来代替大样本矩阵A了。