1 模型定义

错误衡量使用平方错误：

 

注：这里Eout计算是在考虑噪声的情况下，可以将x和y看作满足一个联合概率分布。

 

2 线性回归算法

先把训练集误差Ein推导成矩阵形式：

即：

可以证明Ein关于w是连续，可微的凸函数，因此最小的点就在梯度为0的地方，那么剩下的问题就是来求梯度为0的w：

 先把Ein展开成w的二次形式：

求这个函数的梯度，与w是一维的情况类似（这就是线性代数漂亮的地方）：

把A和b代回来，就是：

 

之后，令这个梯度为0，就能得到对应的w。对于XTX是否可逆的情况，我们都能求出一个称为pseudo-inverse 的矩阵X+（参考如何解线性方程组）。

这样，我们就能得到线性回归算法：

 

3 为什么线性回归能work?

这部分比较难理解，看的一知半解的。

线性回归同样具有VCbound，因此当N足够大时是能实现学习的。除了VC的角度，这里我们从另一个角度给出解释。

对于一个已经训练好的线性回归模型wLin来说，它的Ein可以做如下推导（其中yhat是预测值向量）：

我们把矩阵XX+称为矩阵H：

然后我们来看下矩阵H的几何意义：

 

这张图表示的是N维空间，显然y是其中的一个向量。由于使用了线性回归模型：

因此无论我们的W取多少，最后的得到的预测值向量一定是在X矩阵列向量展开来的线性空间中，即图中的红色平面。而为了使y-yhat最小，最佳的yhat应该是y在红色平面上的投影。

因此，矩阵H的作用是把y投影到X的展开平面上，而矩阵I - H的作用是把y变换到垂直于span of X的向量y - yhat。

 

而矩阵I - H的迹，表征了y - yhat向量的自由度，定性的来说（不作具体证明）：向量y的自由度是N，因为它是N维空间中的一个自由向量；而yhat的自由度则是d + 1,因为它被限制在d + 1个X矩阵的列向量组成的线性空间中。他俩的差y - yhat的自由度就是它们自由度相减：

 

接下来，假设有一个真实世界的线性回归函数f(X)，我们的真实y可以看作是训练集经过这个真实函数映射后再加上一定的噪声得到的。由于这个真实的函数也是一个线性回归模型，当然它对于训练集X的结果还是落在X展开的红色平面上：

因此，y - yhat就可以看作是I - H乘上noise得到，再结合I - H的迹，就可以得到：

 

对于所有可能取到的训练集作一个平均，则noise平均后被称为noise level:

 

Eout平均的推导更加复杂，这里我们直接给出结果：

 

因此可以看出，当N很大时，Ein和Eout的平均就会越来越接近，有如下的学习曲线：

 

并且泛化误差是：

这样我们就能说明线性回归确实是能work的。

 

4 用线性回归来做线性分类

之前我们提过，感知机PLA算法是一个NP-hard问题，需要迭代计算。而线性回归是可以直接一步求解的，不需要迭代。

那么我们能不能在一个二元分类的数据集上，把标签+1和-1看成是实数的两个值，运用线性回归来达到线性分类的效果呢？

 

答案是可以的。

我们来解释一下背后的原理：

主要的问题是，线性回归和线性分类的错误衡量使用的方式不同：

如果用线性回归，减少的是平方错误，较低的平方错误是否会使01错误也比较小？

不作数学公式上的证明，我们画出两种错误的曲线：

可以看出，平方错误是恒大于01错误的：

 

因此，只要我们把平方错误做的很小，就能保证01错误也很小。

如果担心这个上限太宽松，我们可以把线性回归的结果作为pocket算法的初始值，也能达到很好的效果。