机器学习笔记05:正规方程,解析解法:超定方程的最小二乘解,背景知识 木灵的炼金工作室

超定线性方程组

超定方程组是指”行秩”大于未知量个数的方程组. 这样的方程是无解的矛盾方程,但依旧可以以统计方法来得出距离各个点”最近”的解超平面:

\[h(\vec{X}) = w_0 + w_1x_1+w_2x_2+...+w_nx_n\]

在多元线性回归问题中,这就是我们的模型. 我们需要解出所有的$w_i$以得到这个最优化模型.

一般我们采用”最小二乘”法来得到其统计解析解.

超定方程的”最小二乘”条件

记系数矩阵$\vec{A} = \begin{pmatrix}\vec{X_0}, \vec{X_1}, \vec{X_2}, …, \vec{X_n} \end{pmatrix}$,其中,$\vec{X_0}$是元素全为1的列向量,以适配我们方程中的常数项$w_0$.

属性值矩阵$\vec{B}=\begin{pmatrix} x_0, x_1, x_2, …, x_n \end{pmatrix}^T$,

标记矩阵$\vec{Y} = \begin{pmatrix} y_0, y_1, y_2, …, y_n \end{pmatrix}^T$

由于我们在讨论机器学习中的情景,属性值矩阵$\vec{A}$中的列向量都无法被其他列向量线性表出. 设置:

\[\vec{A}\vec{B}=\vec{Y}\]

是一个超定方程组,这意味着该方程组的增广矩阵$\begin{pmatrix}\vec{A}, \vec{Y}\end{pmatrix}$是一个满秩矩阵. 我们令$\widecheck{Y} = \vec{A}\vec{W}$, 现要求出一个解(这个解就是我们多元线性回归模型中的系数向量)$\vec{W}=(w_0,w_1,…,w_n)^T$使得:

\[(\widecheck{Y}-Y)^2=\sum(\widecheck{y_i}-y_i)^2\]

最小化,其中,在我们多元线性回归模型中,这个$\widecheck{Y}$即是模型在训练集上的估计值.

“最小二乘”优化求解

我们以简单的矩阵乘法重新表示上述的$\widecheck{Y}$:

\[\widecheck{Y}=\vec{A}\vec{W}=w_0\vec{x_0}+w_1\vec{x_1}+....+w_n\vec{x_n}\]

刚刚我们提到,”属性值矩阵$\vec{A}$中的列向量都无法被其他列向量线性表出“,因此,$\vec{A}$中的所有列向量$\vec{x_i}$是一个向量空间$S$的一组基底,而$\widecheck{Y}$可以表示向量空间$S$中的全部向量. 我们之前又由超定方程的性质提到,“该方程组的增广矩阵$\begin{pmatrix}\vec{A}, \vec{Y}\end{pmatrix}$是一个满秩矩阵.“,因此向量$\vec{Y}$在上述空间$S$之外,或者说$\vec{Y}$无法由所有的$\vec{x_i}$线性表出(否则方程组$\vec{A}\vec{B}=\vec{Y}$将有常规解).

因此,若$(\widecheck{Y}-Y)^2$取最小,那么$\widecheck{Y}$一定是$Y$在空间$S$上的投影. 这就导致了$\widecheck{Y}-Y$与$S$上的所有向量(即$\vec{A}$中所有的列向量$\vec{x_i}$)全部垂直. 即:

\[\left\{ \begin{aligned} \vec{x_0}^T(\vec{Y} - \widecheck{Y}) = 0 \\ \vec{x_1}^T(\vec{Y} - \widecheck{Y}) = 0 \\ \vec{x_2}^T(\vec{Y} - \widecheck{Y}) = 0 \\ ...\\ \vec{x_n}^T(\vec{Y} - \widecheck{Y}) = 0 \\ \end{aligned} \right.\]

将上述线性方程组写为矩阵模式:

\[\begin{pmatrix} \vec{X_0}^T\\ \vec{X_1}^T\\ \vec{X_2}^T\\ ...\\ \vec{X_n}^T\\ \end{pmatrix}(\vec{Y}-\widecheck{Y})=0\]

而:

\[\begin{pmatrix} \vec{X_0}^T\\ \vec{X_1}^T\\ \vec{X_2}^T\\ ...\\ \vec{X_n}^T\\ \end{pmatrix} = \vec{A}^T\]

即:

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

如果$\vec{A}^T\vec{A}$是满秩方阵(即$\vec{A}$列满秩),解出

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

证毕.


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