林轩田《机器学习基石》（九）—— Linear regression
上一次讲到VC bound适合各种err。以及有noise的情况下，VC Bound理论仍然是成立的。本节课介绍机器学习最常见的一种算法：Linear Regression.
一、回归问题
我们依旧从信用卡的问题来讲，现在的信用卡问题不再是给某人信用卡，而是该给这个多少额度。
学习流程图如下所示：
此刻的学习目标变为了输出实数的函数，即，上面的问题是线性回归（Linear Regression）问题。
我们利用资料来算一个加权的分数，决定给这个人多少额度：
顾客特征：
加权后的分数：
可视化来讲，在二维平面中，我们希望找到的这条蓝色直线，和资料‘o’越接近越好（红色竖线越短，直线与资料越接近）。
三维空间同理。回归分析要做的事情就是找到最好的直线/超平面来描述资料。红色竖线被叫做残差residuals。
如何衡量这些残差呢，我们使用平方误差来衡量。
在已知样本上：
在未知样本上：
之前我们知道err不影响VCbound，所以现在主要考虑如何让极小化。
二、线性回归算法
我们把写成矩阵的形式。
然后我们作出的图像，同时也可以看出
是连续的、可微的、凸的。
我们可以求最小值点，通过找到权重w。
要注意的是这里的w是每个方向的导数都是0：
接下来我们看看什么时候梯度会等于0 ，先将展开：
在一维上：
对于向量来说
无论是哪种情况，我们像之前说的一样，通过求解得到w，其中
为
我们推导得到了权重向量。
其中，又称为伪逆矩阵pseudo-inverse，记为
。事实上实际问题没有逆矩阵（除非一般满足样本数量N大于样本特征维度d+1才会有逆矩阵）。
但大部分的计算逆矩阵的软件程序，都可以处理这个问题，也会计算出一个逆矩阵。在这种情况下我们可以直接使用软件中自带的解。所以上述问题还是可以解决的。
线性回归算法的过程为：
三、泛化问题
可能有这样一个疑问，为什么线性回归问题有直接可以得到的闭式解，这样不需要迭代的问题还是机器学习问题吗？
答：它有好的和
，而且并不是“一步登天”的算法，也是要迭代的。在计算矩阵与逆矩阵的过程中会用到高斯迭代。
总结：如果很好，我们就说‘学习’这件事发生了。
之前的VC可能会帮我们说明很小，但是现在我们用另一种更简便的发方法说明，我们可以看
的平均值
。
对于什么的平均呢？每次我们会从资料库中抽一笔资料，把这么多笔资料做平均，可以写为：
、
其中noise level表示资料有多少噪音。其中为：
叫做帽子矩阵，用H表示。因为
，相当于给y加了一个帽子。
下面从几何图形的角度来介绍帽子矩阵H的物理意义。
1.，所以
与X在同一个空间span
2.我们希望越小越好，由于垂线最短，说明
是
在span上的投影，即
3.H：其实H就是在做投影这件事，将投影在span上。
4.I-H：也是一个线性变换，作用在上，主要是求
。
我们说以下式子是成立的，并不做太多的数学说明，只做结论性的物理解释。
物理意义：我们原本知道有N个自由度的向量，它投影在某个d维空间上取残差后，那么残差的最大自由度为N - (d + 1)。
接着，我们回到带噪声noise的情况。
由图可知，
y = noise+f(x)
显然noise经过I-H也能转换为，因为y和noise顶点都在point 1，他们做I-H变换得到的都是顶点到span的垂线距离，也就是
。
再加上之前说的自由度问题，从而有：
下面这张图，因为是我们看得见的样本平均误差，所以为了让他看起来小一点，我们让他往noise的方向偏一点。同理，
可以得到如下所示。
当N足够大时，和
逐渐接近，数值保持在noise level，我们发现这种方法满足我们之前推导VC Bound，泛化能力强
。
四、线性回归vs线性分类
线性分类：输出、h、误差度量、求解通常是NP-hard
线性回归：输出、h、误差度量、通常容易求解
两种方法看起来很不一样，但是转念一想，{+1，-1}也属于实数空间R，那么线性回归可以求解分类问题吗？
是否可以通过线性回归求出权重w，然后
结果的正负就是分类问题的正负。
但是这不是数学上的道理，我们希望从稍微数学的角度来看看这个问题
举例，
两种不同的误差，分别是线性分类（蓝色）和线性回归（红色）的。
在不同标签下，他们的图像如下（红色蓝色与上面对应）
红色的曲线总是在蓝色的线的上方，所以
这告诉我们
以数学中上限的观点来看，我们把红色的做好，也就把蓝色的做好了。这解释了我们为什么可以用线性回归来做分类（VC bound还成立，或者用我们上一章说的err的角度看也是相同结论）。
所以，我们用线性回归算出一个权重w可以将其用于二分类（得到一个差不多好的结果），二元分类问题得到了一个更宽松的上界，这也是一种更有效率的求解方式。
进一步地，我们可以将上述w当场PLA/pocket的初始值（再做修正）。
总结：