常用算法知识：最小二乘的几何意义及投影矩阵

weixin

　　什么是最小二乘?

　　假设我们手上有n组成对的数据，{(xi,yi):i=1…n}，为了探究y变量与x变量的关系，我们希望用一个多项式来匹配它，可是多项式中的系数怎么确定呢?拿来拼凑肯定是不行的，最小二乘法告诉我们，这个多项式的系数应该让每个点的误差的平方之和最小。

　　(百度百科)最小二乘法(又称最小平方法)是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。其他一些优化问题也可通过最小化能量或最大化熵用最小二乘法来表达。

　　对给定数据点集合{(Xi,yi)}(i=1,2,…,m)，在取定的函数类ψ中，求p(X)∈ψ，使误差的平方和E2最小。

　　从几何意义上讲，就是寻求与给定点集{(Xi,yi)}(i=1,2,…,m)的距离平方和为最小的曲线y=p(x)。函数p(x)称为拟合函数或最小二乘解，求拟合函数p(x)的方法称为曲线拟合的最小二乘法。

　　最小二乘法的矩阵形式
　　最小二乘法的矩阵形式为：

　　其中A为n×k的矩阵，x为k×1的列向量，b为n×1的列向量。如果n>k(方程的个数大于未知量的个数)，这个系统就是Under Determined System。

　　正常来看，这个方程是没有解的，但在数值计算领域，我们通常是计算min||Ax-b||，解出其中的x。比较直观的做法是求解

　　但通常比较低效。其中一种常见的解法是对A进行QR分解(A=QR)，其中Q是n×k正交矩阵(Orthonormal Matrix)，R是k×k上三角矩阵(Unter Triangular Matrix)，则有：

　　用MATLAB命令可解得x。
　　x=R\(Q\b)

　　最小二乘法的Matlab实现
　　    · 一次函数线性拟合使用polyfit(x,y,1)
　　    · 多项式函数线性拟合使用polyfit(x,y,n)，n为次数
　　    · 非线性函数使用Isqcurvefit(x,y,fun,b0)

　　拟合曲线
　　x=[0.5,1.0,1.5,2.0,2.5,3.0]
　　y=[1.75,2.45,3.81,4.80,7.00,8.60]
　　解：MATLAB的程序如下：
　　x=[0.5,1.0,1.5,2.0,2.5,3.0];
　　y=[1.75,2.45,3.81,4.80,7.00,8.60];
　　p=polyfit(x,y,2);
　　x1=0.5:0.5:3.0;
　　y1=polyval(p,x1);
　　plot(x,y,'*r',x1,y1,'-b')
　　计算结果为：
　　p=0.5614 0.8287 1.1560
　　即所得多项式为y=0.5614x2+0.8287x+1.1560

　　最小二乘的几何意义

　　最小二乘的几何意义：最小二乘法中的几何意义是高维空间中的一个向量在低维子空间的投影。

　　从上面的定义中，我们很难想象到最小二乘的几何意义，那么我们通过一个简单的例子来推导一下：

　　我们根据定义中的误差平方之和最小化来拟合直线：

　　每个点的误差表示：

　　最小误差的平方和：

　　要求解上面的最小化问题，我们可以通过求导的方式得到，最好是转化为矩阵表达形式：

　　这里x表示上述的系数a，求得结果为：

　　如果通过超定方程的解法，很容易就可以得到下面结果。

　　先来说说向量表达形式：

　　小括号中表示：它是两个向量[1,...,1]ᵀ和[[x1,...,xn]ᵀ的线性组合，换句话说，它是这两个向量构成的二维子空间(想成一个平面就可以)的任意一点。

　　那么上面式子的几何含义：表示向量[y1,...,yn]ᵀ(表示空间中的一点)到这个二维子空间任意一点的距离;(向量的长度)

　　最小化上面式子的平方(向量长度的最小化)的几何含义：寻找在[1,...,1]ᵀ和[x1, ...,xn]ᵀ构成的二维子空间上的一个点，使得向量[y1,...,yn]ᵀ到这个点的距离最小。怎么找这个点呢?只要做一个几何投影就好了。(如下图)

　　三维空间中的向量u到v1，v2所在平面的投影

　　如上图所示，在三维空间中给定一个向量u，以及由向量v1，v2构成的一个二维平面，向量p为u到这个平面的投影，它是v1，v2的线性组合。

　　利用投影的垂直性质，我们可以得到关于系数C的两个方程：

　　令V=[v1,v2]，p=c1v1+c2v2，将上述式子合并并转化为矩阵形式(更容易扩展到高维空间)，得到：

　　因此系数c的表达式为：

　　有没有发现很熟悉?和下面的式子一模一样有木有!!!

　　好了，我们回到原来的例子，看看几何关系中的投影点和被投影的空间分别代表什么。

　　把图中的u替换成[y1,...,yn]ᵀ，把v1，v2分别替换成[1,...,1]ᵀ和[x1,...,xn]ᵀ，系数c1和c2就是我们要求的a0，a1。

　　所以，最小二乘法的几何意义是高维空间的一个向量(由y数据决定)在低维子空间(由x数据以及多项式的次数决定)的投影。

　　正交投影矩阵

　　上面提到了最小二乘的几何意义就是空间中的投影，其实投影在线性代数中也是存在其数学公式的，可以联系以下数学知识来理解最小二乘的几何意义。

　　张成子空间：
　　在线性子空间中，十分重要的一个特例是生成子空间。设a1，a2，...as是线性空间V中一组向量，则集合

　　是非空集合，不难证明

　　定理1 span{a1，a2，...as}是V的线性子空间。

　　定义1 称非空子集span{a1，a2，...as}是由向量a1，a2，...at生成的子空间。

　　张成子空间的投影矩阵：

　　其中Φi为{Φλ:λ∈∧t}构成的矩阵，Φiᵀ表示Φi的转置，(ΦiᵀΦi)⁻1表示求(ΦiᵀΦi)得逆矩阵。

　　最小二乘的投影解释：
　　设方程组Ax=b的最小二乘解为z，则Az即为向量b在矩阵A=[a1,a2]的列向量所确定的平面上的正交投影向量，即向量b正交投影p=Az，而从前面我们知道：

　　所以向量b正交投影：

　　其中：P=A(AᵀA)⁻1Aᵀ，我们称为投影矩阵。

　　本文转载自数据与算法之美(ID：superdata1)，原文来自于博客园AndyJee的博客。

人走茶不凉

好像好多地方用的最小二乘法啊。

xinglong-liu

讲得很棒！