本文主要讲解基本最小二乘法和带有约束条件的最小二乘法。

一  基本最小二乘法

最小二乘法是回归中最为基础的算法。它是对模型的输出和训练样本输出的平方误差（这里还乘以了1/2只是为了求导简化）为最小时的参数 进行学习。

http://img.blog.csdn.net/20150704103435184带有约束条件的最小二乘法" />

特别地，对于线性模型有：

http://img.blog.csdn.net/20150704103500200带有约束条件的最小二乘法" />

求导可得：

http://img.blog.csdn.net/20150704103537575带有约束条件的最小二乘法" />

其中设计矩阵：

http://img.blog.csdn.net/20150704105416501带有约束条件的最小二乘法" />

 

http://img.blog.csdn.net/20150704214251479?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast带有约束条件的最小二乘法" />

 

最后得到 y = 2.9896*x^2 +1.9999*x + 0.9997 

设计矩阵的维数是n*b,当训练样本很大时，大规模的求偏导开销很大，容易计算内存不足，这时采用随机梯度算法往往会效果很好。

 随机梯度算法是指沿着训练平方误差 J 的梯度下降，对目标参数θ 进行学习的算法。下面是使用随机梯度算法对线性模型进行最小二乘法的算法步骤：

step 1 ：指定θ初值

step 2：随机选择一个训练样本 如（xi,yi）

step 3： 对于选定训练样本，采用梯度下降的方式，对参数θ进行更新。

http://img.blog.csdn.net/20150704160452921带有约束条件的最小二乘法" />

step 4 重复步骤2,3直到θ达到收敛精度

二 带有约束条件的最小二乘法

基本的最小二乘法对于包含噪声的学习过程常常有过拟合的弱点，主要是因为学习模型对于训练样本而言过度复杂，为了控制模型复杂程度，下面简述带约束条件额最小二乘法。

2.1部分空间约束的最小二乘法

基本最小二乘法中，所求参数θ 是在全体参数空间求取，而部分空间约束的最小二乘法，则是通过把参数空间约束在一定范围内，来防止过拟合现象。

http://img.blog.csdn.net/20150704215618666?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast带有约束条件的最小二乘法" />

其中矩阵P是正交投影矩阵，一般通过主成分分析法手动设置，将设计矩阵变为=设计矩阵右乘P求得。

下面是对以三角多项式作为基函数的线性模型进行部分空间约束的最小二乘法学习的例子。其中绿色曲线是基本最小二乘拟合曲线结果，可以看到，为了尽量达到最小平方误差，学习模型对于训练样本而言过于复杂，出现过拟合现象，而红色曲线是带空间约束后的结果，可见红色曲线的效果明显比绿色曲线好。

http://img.blog.csdn.net/20150704220141470?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast带有约束条件的最小二乘法" />

 

http://img.blog.csdn.net/20150704220708883?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast带有约束条件的最小二乘法" />

 

事实上，可以看到，部分空间约束的最小二乘法，只使用了参数空间的一部分，P矩阵的设置难度很大，接着介绍相对容易使用的l2约束的最小二乘法。

最小二乘法和带部分空间约束的最小二乘法，它们要么易过拟合，要么不易求解，下面介绍 l2约束的最小二乘法，又叫正则化最小二乘法，岭回归。

一个模型的复杂程度与系数有关，最简单的模型是直接给所有系数赋值为0，则该模型总会预测出0值，模型虽然足够简单，但是没有意义，因为它不能有效预测。

定义模型的复杂度为：

http://img.blog.csdn.net/20150705094940230带有约束条件的最小二乘法" />

由于我们的目的是使模型不要过于复杂，所以让上述值小是有意义的，因此新的目标函数为：

http://img.blog.csdn.net/20150705095424096带有约束条件的最小二乘法" />

即

http://img.blog.csdn.net/20150705184200645带有约束条件的最小二乘法" />

前一项为数据拟合程度的惩罚项，数据拟合的越好，该项值越小，但是也有可能过于拟合样本数据导致模型过于复杂；后一项为模型复杂程度的惩罚项，当模型越复杂，该项值越大，即为了最小化目标函数，我们要让数据拟合的好同时模型不至于太复杂。其实就是在基本最小二乘法的目标函数中增加了一个正则化项，所谓正则化，可以看为函数光滑性。将上式目标函数进行参数求偏微分，解得：

http://img.blog.csdn.net/20150705203930594带有约束条件的最小二乘法" />

下面从参数空间约束的角度介绍 L2 约束的最小二乘法。

http://img.blog.csdn.net/20150705215636208带有约束条件的最小二乘法" />

L2约束的最小二乘法是以参数空间的原点为圆心，在一定半径范围内（一般为超球）内进行参数求解。

转化为拉格朗日对偶问题为：

http://img.blog.csdn.net/20150706083312117带有约束条件的最小二乘法" />

http://img.blog.csdn.net/20150706083618251带有约束条件的最小二乘法" />

目标函数形式与前面分析是一致的。

下面对下面高斯核模型执行L2约束下的最小二乘学习。实例如下;

带宽h = 0.25  正则化参数 λ 设置为0.1.其中，绿色曲线是基本最小二乘法结果，红色曲线是正则化下的最小二乘结果。通过加入正则项，使过拟合现象得到很好地抑制。

带宽 h 和正则化参数 λ 值的选取会直接影响最终结果，为了得到更好的学习效果，应该选择合适的带宽和正则化参数。

 

%高斯核模型L2约束的最小二乘法学习
clear all;
close all;

n = 60;
N = 1000;
x = linspace(-4,4,n)';
X = linspace(-4,4,N)';
pix = pi*x;
y = sin(pix)./(pix) + 0.1*x + 0.05*randn(n,1);

x2 = x.^2;
X2 = X.^2;
hh = 2*0.25^2;%高斯核函数带宽 0.3
e =0.1;%正则化参数

k = exp(-(repmat(x2,1,n)+repmat(x2',n,1)-2*x*x')/hh);
K = exp(-(repmat(X2,1,n)+repmat(x2',N,1)-2*X*x')/hh);
t1 = k\y;
F1 = K*t1;
t2 = (k^2+1*eye(n))\(k*y);
F2 = K*t2;

figure(1);
clf;
hold on;
axis([-4 4 -0.5 1.2]);
plot(X,F1,'g-');
plot(x,y,'bo');
plot(X,F2,'r--');

http://img.blog.csdn.net/20150706090320633带有约束条件的最小二乘法" />

 

一点总结：

本文先介绍了基本的最小二乘法，基于其易过拟合，介绍了部分空间约束的最小二乘法和L2约束（正则化）的最小二乘法，是的过拟合现象得到了一定缓解。但是，它们都需要选择合适的正交投影矩阵P 对参数空间选择 和正则化参数选择抑制模型复杂度。此外，对于线性模型的基函数选择和以及核函数参数也需要选择。

从机器学习的角度来说，我们要做的其实就是一种问题真实模型的逼近。我们将训练样本的模型输出与真实结果之间的差值定义为经验风险，我们需要得到一个模型，而又没有定义模型好坏的标准，直观的说，我们能想到最简单的标准就是经验风险最小化，前面所做的其实也就是对经验风险平方和最小化的求解。

这种思想其实就是用训练样本（真实世界的一部分样本）的经验风险去逼近真实风险，数学上的以局部估计整体的思想，虽不一定正确，但也是一种选择。

事实上，对于有监督学习来说，我们学习的目的不在于记忆输入训练样本，而是对未知的测试输入样本也能正确的得到输出。所以，并不是要训练样本的误差越小越好，因为训练样本的数目远远不及真实的所有样本量。上面实验中的绿色曲线为了使误差最小，基本经过了每一个点，但是它的预测效果是相当差的。我们既要克服过拟合又要得到较好的泛化能力，这个折中问题就是偏差-方差平衡。（下面关于偏差-方差的内容来自http://scott.fortmann-roe.com/docs/BiasVariance.html）

 

偏差：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越大，越偏离真实数据，如下图第二行所示。

方差：描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散，如下图右列所示。

http://img.blog.csdn.net/20150706095304824带有约束条件的最小二乘法" />

一个很形象的例子如下（引用知乎网友回答）

想象你开着一架黑鹰直升机，得到命令攻击地面上一只敌军部队，于是你连打数十梭子，结果有一下几种情况:
1.子弹基本上都打在队伍经过的一棵树上了，连在那棵树旁边等兔子的人都毫发无损，这就是方差小（子弹打得很集中），偏差大（跟目的相距甚远）。
2.子弹打在了树上，石头上，树旁边等兔子的人身上，花花草草也都中弹，但是敌军安然无恙，这就是方差大（子弹到处都是），偏差大（同1）。
3.子弹打死了一部分敌军，但是也打偏了些打到花花草草了，这就是方差大（子弹不集中），偏差小（已经在目标周围了）。
4.子弹一颗没浪费，每一颗都打死一个敌军，跟抗战剧里的八路军一样，这就是方差小（子弹全部都集中在一个位置），偏差小（子弹集中的位置正是它应该射向的位置）。

一个算法如果逐渐提高对训练数据的适应性（如加入更多的模型参数使模型更复杂），那么它会很好地拟合数据，趋于更小的偏差，但是会导致更大的方差。相反，如果这个模型参数较少，通常偏差较大，数据拟合性能相对不太还，但是拟合的程度对于不同数据集变化不会太大，方差较低。

一个实际有效克服过拟合的方法是交叉验证法，把训练样本中的一部分拿出来不进行学习，而作为测试样本进行最终学习结果的评价。

参考文献：《Pattern Classfication》

    《机器学习基础教程》

    《图解机器学习》

注：看 斯坦福大学机器学习课程个人笔记完整版 百度ppt 。整理记录： 1、带权重的线性回归。权值的设置可以学习http://s12/mw690/002XIQaDzy76YkLkNxVcb&690带有约束条件的最小二乘法" TITLE="最小二乘法 带有约束条件的最小二乘法" />