欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

「最优化」求解线性方程组

最小二乘解

考虑线性方程组:

\(Ax=b\)

其中 \(A \in R^{m \times n}, b \in R^m, m\ge n, rank(A) = n\) 。未知数n的数量不大于方程m的数量,因此,如果b不属于矩阵A的值域空间,即 \(b \notin \Re (A)\) ,则称方程式矛盾或「过正定」的。在这种情况下,方程无解。求解该方程就变成了寻找一个向量,使得 \((Ax-b)^2\) 达到最小。达到最小的时候的值 \(x^*\) ,就是「最小二乘解」。

很容易可以发现,方程的解,一定是最小二乘解。

唯一性

能够最小化 \((Ax-b)^2\) 的向量 \(x^*\) 具有唯一性,可以通过求解方程组 \(A^TAx=A^Tb\) 得到,即:

\(x^*=(A^TA)^{-1}A^Tb\)

上式看的有点玄乎,由于是二次型,其实直接令 \((Ax-b)^2\) 的导数为0,可以直接解出来最优的x,导数方程为:

\(\Delta f(x)=2A^TAx -2A^Tb=0\)

几何解释

求解 \((Ax-b)^2\) 的最小值其实就是寻找一组参数x,对A的列向量进行线性组合后的到向量h,使得h-b的几何距离最小。如果b在A列向量确定的子空间,最小值为0.如果不在,最小值为b到A确定的空间的正交向量。

容易证明:

\(h=Ax^*=A(A^TA)^{-1}A^Tb\)

下图为示意图

152C8467-077C-4564-943F-0D1D9029C8C5

直线拟合

最小二乘可以作为损失函数,最典型的就是「线性回归」,每一条样本就是A的一行,每一个维度的特征就是一列,标注就是b。

递推最小二乘

在真实的世界中,训练样本是持续生成的,所以就会有模型更新的问题,例如对大规模的推荐系统和广告系统,训练数据是实时生成的,如果可以实时更新模型就可以更快的捕获「最新」的模式,从而取得更好的效果。

在最小二乘的问题中,原始问题的解 \(x_0 = G_0^{-1}A_0^Tb^0\) ,加入新样本 \(A_1,b_1\) 后,可以表示为:

\(\begin{Vmatrix}\begin{bmatrix} A_0\\ A_1\end{bmatrix}x-\begin{bmatrix}b_0\\b_1 \end{bmatrix}\end{Vmatrix}^2\)

上式的解为:

\(x^1=G_1^{-1}\begin{bmatrix}A_0\\A_1\end{bmatrix}^T\begin{bmatrix}b_0\\b_1\end{bmatrix}\)

其中 \(G_1\) 为:

\(G_1=\begin{bmatrix}A_0\\A_1\end{bmatrix}^T\begin{bmatrix}A_0\\A_1\end{bmatrix}\)

递推公式

最终可以得到递推公式为:

\(G_{k+1}=G_k +A_{k+1}^TA_{k+1}\)

\(x^{k+1}=x^k+G_{k+1}^{-1}A_{k+1}^T\left(b_{k+1}-A_{k+1}x^k \right )\)

矩阵求逆

上面递推公式可以观察到,需要求矩阵 \(G_k\) 的逆矩阵,因为求一个矩阵的逆矩阵是一件成本很高的事情,所以需要借助一些变换简化求逆的过程。在迭代过程中,上一步的矩阵的逆和这一步的矩阵的逆是有关系的,下面公式就是「谢尔曼-莫里森」公式和「谢尔曼-莫里森-伍德伯里」公式。

 

谢尔曼-莫里森公式

如果矩阵A非奇异,u和v为列向量,满足 \(1+v^TA^{-1}u \ne0\) ,那么 \(A+uv^T\) 非奇异,且下面式子成立

\((A+uv^T)=A^{-1}-\frac{(A^{-1}u)(u^TA^{-1})}{1+v^TA^{-1}u}\)

 

谢尔曼-莫里森-伍德伯里

A为非奇异矩阵,矩阵U和V能够使得 \(I+VA^{-1}U\) 非奇异,则有 \(A+UV\) 非奇异,且:

\((A+UV)^{-1}=A^{-1}-(A^{-1}U)(I+VA^{-1}U)^{-1}(VA^{-1})\)

上式中两侧同乘 \(A+UV\) 即可得证。

修正后的递推公式

\(P_k=G_k^{-1}\) ,迭代式可以修改为:

\(\begin{matrix} P_{k+1} & = &P_k -P_k A^T_{k+1}(I+A_{k+1}P_k A^T_{k+1})^{-1}A_{k+1}P_k\\&=&P_k -P_k A^T_{k+1} \left( 1-\frac{A_{k+1}P_kA_{k+1}^{T}}{1+A_{k+1}^TA_{k+1}P_k} \right )A_{k+1}P_k\\\end{matrix}\)

\(x^{k+1}=x^k+P_{k+1}A_{k+1}^T\left(b_{k+1}-A_{k+1}x^k \right )\)

特别的,当新样本只有一行的时候,公式可以进一步进行化简,这时 \(A_{k+1}=\alpha_{k+1}^T\) ,公式为:

\(P_{k+1}=P_k -\frac{P_k \ \ \alpha_{k+1} \ \ \alpha_{k+1}^T \ \ P_k \ \ }{1+ \ \alpha_{k+1}^T \ \ \ P_k \ \ \ \alpha_{k+1}}\)

\(x^{k+1}=x^k+P_{k+1}\alpha_{k+1}^T\left(b_{k+1}-\alpha_{k+1}x^k \right )\)

参考资料

《最优化导论》Edwin K.P.Chong Stanislaw H. Zak

未经允许不得转载:大数据算法 » 「最优化」求解线性方程组

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站